정렬되지 않은지도의 충돌을 검색하는 방법은 무엇입니까?

Question

키 ("달걀")를 공유하는 두 개의 요소 (6과 747)가 있습니다. 나는 열쇠를 공유하는 모든 요소를 ​​찾고 싶다. ("달걀"이라고하자. 그러나 모든 열쇠에 대해 현실에서 그렇게하겠다.) 그렇게하는 방법?

데이터 구조에서 컨테이너 나 다른 것을 가져 오는 방법이 있어야합니다. . .

Answer 1

키의 값이이고 키의 해시가 인 것으로 잘못 생각하고 있습니다. 질문하지만 질문에 대답 : 당신이 버킷 반복자와 unordered_map의 bucket() 멤버 함수를 사용할 수 있습니다

간단하고 대부분 올바른 관점에서

std::unordered_map<int,int,dumbest_hash> m; 
m[0] = 42; 
m[1] = 43; 

size_t bucket = m.bucket(1); 

for(auto it = m.begin(bucket), e = m.end(bucket); it != e; ++it) { 
    cout << "bucket " << bucket << ": " << it->first << " -> " << it->second << '\n'; 
} 

demo

가 정렬되지 않은 컨테이너 인터페이스의 관점에서 자신의 주문 대응을 모방. 즉, map에서 중복 키를 허용하지 않으면 어느 쪽도 unordered_map이됩니다.

unordered 검색 속도를 높이기 위해 해싱 기능을 사용하지만 두 개의 키가 동일한 해시를 가질 경우 반드시 같은 값을 가질 필요는 없습니다. 동작을 순서가있는 컨테이너와 비슷하게 유지하려면 unordered_set과 unordered_map은 해시 값이 충돌하지 않을 때 요소가 실제로 같을 때 (operator== 또는 제공된 비교자를 사용하여) 요소가 같다고 간주합니다.

원근감을 내기 위해 "eggs"과 "chicken"이 동일한 해시 값을 갖고 있다고 가정하고 평등성 검사가 없다고 가정 해 봅시다.

unordered_map<string, int> m; 
m["eggs"] = 42; 
m.insert(make_pair("chicken", 0)); // not inserted, key already exists 
assert(m["chicken"] == 42); 

을하지만 같은 맵에 중복 키를 허용하려면, 단순히 unordered_multimap를 사용 : 다음 코드는 "올바른"일 것이다.

Answer 2

정렬되지 않은지도에는 키를 공유하는 요소가 없습니다.

정렬되지 않은 멀티 맵 않습니다.

umm.equal_range(key)을 사용하면지도에서 지정된 키와 일치하는 요소를 설명하는 반복자를 pair 가져올 수 있습니다.

그러나 해시 컨테이너에 대해 이야기 할 때 "충돌"은 일반적으로 동일한 해시 키가 아닌 동일한 키가있는 요소를 나타냅니다.

또한 멀티 맵 대신 unordered_map<key, std::vector<value>>을 사용하는 것이 좋습니다.