벡터 또는 멀티 맵 딜레마

Question

나는 multimap <int key, int value>을 가질지 또는 int 키에 해당하는 모든 값의 벡터를 포함하는 벡터를 유지할 것인지에 대한 딜레마가 있습니다.

특정 int 키의 값을 조회 할 때 더 빨리 수행하는 것에 관심이 있습니다.

Answer 1

당신은 multimap 단지 map이 대안은 아마 될 것입니다하지 그런 vector< list<int> > 또는 무언가를 원하는 경우에 (실제로는 multimap 더이거나 적은 list 요소 유형의 map). 일반적으로

가하는 vector 조회가 빠르다 : 그것은 두 경우에 나는 list/vector/set로 검색을 계산하고 있지 않다 (지도에 대한 O(log n) 대 배열 O(1)있어 /은 "멀티"에 사용되는 어떤 부품). 그러나을 사용하려면 vector을 사용하려면 가장 큰 int 키만큼 커야합니다. 키가 순차적이라면 문제가되지 않지만 색인이 희박한 경우 multimap을 선택하는 것이 좋습니다.

반면에 순회가 필요하지 않은 경우 unordered_multimap (실제로 해시 테이블 임)은 두 세계 모두에서 최상일 수 있습니다. 배열과 같은 O(1) 조회는 엄청난 빈 배열을 유지하지 않고도 얻을 수 있습니다. .

Answer 2

난 당신이 모든 값을 가진 벡터를지도에서 검색을 수행 한 번 때문에 map<int, vector<int>>

를 추천 할 것입니다.

그렇지 않으면 솔루션은 각각의 값

Answer 3

난 당신이 조기 최적화를하고있는 생각의 새로운 검색이 필요합니다. 모든 것이 프로파일 러를 사용하여 작업 한 후에 만 ​​최적화해야하기 때문에 좋지 않습니다. 시간을 낭비하지 말고 필요에 따라 전문 용기를 사용하십시오.

Answer 4

만약 당신의 키가 순차적으로 벡터와 함께 움직인다 고 말할 수는 있지만 키에 큰 구멍이 있다면 벡터가 더 좋을 것입니다 (벡터 에서처럼 "빈"레코드를 저장할 필요가 없기 때문에) 더하기 등 당신이 얼마나 많은 레코드를 계산하기가 더 쉽게됩니다. 성능 현명한 벡터는 배열을 기반으로하므로 조회는 일반적으로 더 빠릅니다 (조회는 조회를 수행하기 위해 몇 개의 데이터 조각을 거쳐야하므로).

Answer 5

'빠름'을 잊어 버립니다. 당신은 나중에 그것을 프로파일 링 할 수 있지만 이것에 사로 잡히지 마십시오. 훨씬 더 중요한 것은 하나의 접근 방식이 당신에게 희소 한 스토리지를 제공하고, 다른 하나는이 문제에 집중하지 않고 어떤 것이 당신의 문제에 가장 적합한 지 결정하는 것입니다.