1

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）を呼び出すと）、ブーストドキュメントに等しい範囲が平均O（count（k））であると記載されていても、期待どおりにスケーリングされます...？

4

2 に答える 2

1

これはlibstdc++のバグのようです。バグレポートはどこにも見つかりませんが、を使用し#include <unordered_map>てコンパイルする-std=c++11と、期待どおりの動作が得られます。

于 2013-09-02T10:04:56.187 に答える
0

これはスケーリングしませんO(n)が、O(n * n)（時間を呼び出していますstd::equal_range n）！

std::equal_range内側のループの外に移動します。

于 2012-07-17T09:30:55.960 に答える