unordered_multimap :: 나는 unordered_multimap :: equal_range 평균 상수 복잡성 것으로 기대

Question

느린 equal_range 그러나 n 개의 선형 적으로 확장되지 않습니다 다음은 예상대로 :

#include <iostream> 
#include <tr1/unordered_map> 
#include <cstdlib> 

using namespace std::tr1; 
using namespace std; 

int main(){ 
     int n; 
     cin >> n; 
     unordered_map<int, int> um; 
     for(int i=0; i<n; ++i){ 
       um.insert(make_pair(i%100000, i)); 
       pair<unordered_map<int, int>::iterator,unordered_map<int,int>::iterator > t = um.equal_range(i); 
     } 
} 

$ g++ testbr.cpp 
$ time echo 10000 | ./a.out 

real 0m0.065s 
user 0m0.060s 
sys  0m0.003s 
$ time echo 100000 | ./a.out 

real 0m4.492s 
user 0m4.490s 
sys  0m0.003s 

인가 이 문제를 해결할 방법이 있습니까?

편집 : equal_range가 없으면 예상대로 조정됩니다.
또한 동일한 키 0 (와 항상 equal_range (0) 호출) 모든 요소를 ​​삽입하는 경우 동일한 문서의 범위가 평균적으로 O (count (k))라고 말하는 부스트 문서에도 불구하고 예상대로 확장됩니다 ...?

Answer 1

이것은 libstdC++의 버그 인 것 같습니다. 어디서나 버그 보고서를 찾을 수는 없지만 #include <unordered_map>을 사용하고 -std=c++11을 컴파일하면 예상되는 동작이 나타납니다.

Answer 2

이것은 축척이 없습니다 O(n)이지만 O(n * n) (전화 할 때 std::equal_rangen 번)입니다.

std::equal_range을 안쪽 루프 밖으로 이동하십시오.