unordered_multimap에서 비 고유 키를 모두 액세스/반복하는 방법은 무엇입니까?

Question

unordered_multimap에서 비 고유 키를 모두 액세스/반복하고 싶습니다. 해시 테이블은 기본적으로 실제로는 식별자 <ID>에 여러 번 발생하는 <SIG> 서명의 맵입니다. 한 번 발생하는 해시 테이블에서 해당 항목을 찾고 싶습니다. 해당 키가 더 존재한다면

// map <SIG> -> <ID> 
typedef unordered_multimap<int, int> HashTable; 
HashTable& ht = ...; 
for(HashTable::iterator it = ht.begin(); it != ht.end(); ++it) 
{ 
    size_t n=0; 
    std::pair<HashTable::iterator, HashTable::iterator> itpair = ht.equal_range(it->first); 
    for ( ; itpair.first != itpair.second; ++itpair.first) { 
     ++n; 
    } 
    if(n > 1){ // access those items again as the previous iterators are not valid anymore 
     std::pair<HashTable::iterator, HashTable::iterator> itpair = ht.equal_range(it->first); 
     for ( ; itpair.first != itpair.second; ++itpair.first) { 
      // do something with those items 
     } 
    } 
} 

이 확실히 (ht.begin() 통해) 해시 테이블의 모든 요소를 ​​외부 루프 반복하고 내부 루프 테스트 효율적 아니다 :

현재 I이 방법을 사용하여 한번 이상.

더 효율적이고 우아한 방법이 있습니까?

참고 : 내가 대신 unordered_multimap의 unordered_map와 나는이 문제가없는 것으로 알고 있지만 인해 애플리케이션 요구 사항에 나는 서로 다른 식별자 <ID>에 여러 개의 키를 <SIG> 포인팅을 저장 할 수 있어야합니다. 또한 unordered_map<SIG, vector<ID> >은 많은 고유 키를 가지고 있고 각 항목에 대해 상당히 많은 오버 헤드를 추가하기 때문에 약 150 %의 메모리를 사용하기 때문에 좋은 선택이 아닙니다.

Answer 1

특정 키가있는 요소의 수를 확인하려면 std::unordered_multimap::count()을 사용하십시오. 이렇게하면 첫 번째 내부 루프가 저장됩니다.

HashTable 전체에서 반복을 방지 할 수 없습니다. 이를 위해 HashTable은 카디널리티를 키에 매핑하는 두 번째 인덱스를 유지해야합니다. 이로 인해 상당한 런타임 및 스토리지 오버 헤드가 발생하고 소수의 경우에만 유용합니다.

std::for_each()을 사용하여 외부 루프를 숨길 수는 있지만 그만한 가치는 있다고 생각하지 않습니다. 그럼 당신은 쉽게지도를 반복하고, 각 요소 size()

으로하지만이 상황에서 포함 얼마나 많은 항목을 확인할 수 있습니다

std::map<int, std::vector<int> > ht; 

:

Answer 2

난 당신이 뭔가에 데이터 모델을 변경해야한다고 생각 데이터 구조를 만들고 선형 모드로 읽는 것은 좀 더 복잡합니다.