어떤 데이터 구조가 가장 좋을까요?

Question

내 게임의 경우, 객체가 센서에 들어갈 때, 그것을 목록에 추가해야하고, 객체가 센서를 떠날 때 해당 목록에서 제거해야합니다. 나는 또한 그 물체를 빨리 찾을 수 있어야한다. 그래서 본질적으로

: 빠른 추가 신속하게 제거 및 빨리 찾기 :

나는 그것을 할 필요가있다.

어떤 주어진 시간에 구조에는 약 10 개의 개체가 있습니다. 어떤 종류의 데이터 구조가 가장 좋을까요?

감사 (10) 아무것도 할 것입니다 오브젝트 (std::vector, deque 또는 set), 및 프로파일 링 전에 더 나은 수행하는 하나 말할 수있는 아무도

Answer 1

.

무엇을 사용해야할지 모르겠 으면 std::set에는 요소를 찾는 데 더 멋진 구문이있을 것입니다. 이것은 내가 s.find(sensor)을 쓸 수있는 곳에서 std::find(v.begin(), v.end(), sensor)을 쓰고 싶지 않기 때문에이 상황에서 사용할 것입니다.

일반적인 조언으로 std::list을 사용하지 마십시오. C++에서 링크 된 목록을 사용하는 강력한 이유가 필요합니다 (상수 시간 연결은 하나, 반복자 무효화 부재는 또 다른 것임). 다른 데이터 구조는 대부분의 작업 (스플 라이스 제외)에서 더 잘 수행됩니다. 여기에서는 예를 들어 list을 사용하는 데 어떤 시점도 보이지 않습니다. set.

Answer 2

빠른 추가, 빠른 제거 및 빠른 찾기, 당신은 많이 원하지 않습니다! 당신이 말한 것을 감안할 때 나는 링크드리스트를 말할 것입니다, 그러나 그것은 또한 얼마나 자주 추가, 삭제 및 발견 이냐에 달려 있습니다. 추가 또는 삭제하는 것보다 훨씬 더 자주 찾는 경우 변경됩니다.

정말 유일한 방법은 몇 가지 다른 선택을 시도하고 시간을 정하는 것입니다.

Answer 3

나는 Linked List가 가장 좋을 것이라고 생각합니다. 크기가 작 으면 포인터를 이동시키는 동작이 성능에 영향을 미치지 않습니다.

Answer 4

요소의 삽입 및 제거에 완벽하게 적용되므로 std::list을 제안합니다.