unordered_multimap::equal_range slow
-
21-06-2021 - |
Question
I would expect unordered_multimap::equal_range to be in average constant complexity, however the following does not scale linearly with n as expected:
#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
Is there a way to fix this?
Edit:
Without equal_range it scales perfectly as expected.
Also if I insert all elements with the same key 0 (and alway call equal_range(0)) it scales as expected, even though boost doc states that equal range is in average O(count(k))...?
Solution
This seems to be a bug in libstdc++, I cannot find a bug report anywhere, but with #include <unordered_map>
and compilation with -std=c++11
I get the expected behaviour.
OTHER TIPS
This doesn't scale O(n)
, but O(n * n)
(you're calling std::equal_range
n
times)!
Move the std::equal_range
out of the inner loop.