c++ - unordered_multimap::equal_range 慢

Question

我希望 unordered_multimap::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)），它会按预期缩放，即使 boost doc 声明相等范围平均为 O(count(k))...？

Answer 1

这似乎是 libstdc++ 中的一个错误，我在任何地方都找不到错误报告，但是使用#include <unordered_map>和编译-std=c++11我得到了预期的行为。

Answer 2

这不是按比例计算的O(n)，但是O(n * n)（您正在调用std::equal_range n时间）！

移出std::equal_range内循环。