從unordered_set「刪除一個元素」使用擦除（開始（））在gcc緩慢

我想有一個函數來從unordered_set「刪除一個元素」。從unordered_set「刪除一個元素」使用擦除（開始（））在gcc緩慢

但是，當它使用擦除（begin（））實現時，它變得非常慢。（這是在g ++ - 4.5.3;也許begin（）必須遍歷大量的空散列桶？）

請參閱下面的示例代碼，令人驚訝的時間。

有沒有其他一些方法來實現「刪除一個元素」，將有更大的效率？（我想允許這將迭代器失效等干預組操作。）

#include <unordered_set> 
#include <iostream> 
#include <chrono> 
using namespace std; 

struct Timer { 
    Timer(string s) : _s(s), _start(Clock::now()) { } 
    ~Timer() { 
     auto t=chrono::duration_cast<chrono::milliseconds>(Clock::now()-_start).count(); 
     cerr << "Timer(" << _s << ") = " << t << "ms\n"; 
    } 
private: 
    typedef chrono::high_resolution_clock Clock; 
    string _s; 
    Clock::time_point _start; 
}; 

int main() 
{ 
    unordered_set<int> s; 
    const int num=200000; 
    { Timer t("insert"); for (int i=0;i<num;i++) { s.insert(i); } } 
    { Timer t("remove half"); for (int i=0;i<num/2;i++) { s.erase(s.begin()); } } 
    long long s1=0, s2=0; 
    { Timer t("access begin()"); for (int i=0;i<num/2;i++) { s1+=*s.begin(); } } 
    { Timer t("access all"); for (auto it=s.begin();it!=s.end();++it) { s2+=*it; } } 
    cerr << s1 << " " << s2 << "\n"; 
    return 0; 
} 

// Timer(insert) = 36ms 
// Timer(remove half) = 3039ms 
// Timer(access begin()) = 5958ms 
// Timer(access all) = 1ms

來源

2012-04-17 Hugues

這個測試一個接一個地去掉了很多元素，而沒有做任何其他的事情。這可能不是你實際程序行爲的方式。請描述你的更大的目標;它可能是你應該使用unordered_set以外的東西。 – zwol 2012-04-17 16:51:32

你想優化移除一個元素還是從unordered_set中移除N個元素？ – 2012-04-17 17:02:56

看起來與版本的GNU庫，固定在較新版本的問題。下面是我的測試結果，使用兩個版本我碰巧已經安裝：

[email protected]:~$ g++-4.4.5 -std=c++0x -O3 test.cpp 
[email protected]:~$ ./a.out 
Timer(insert) = 15ms 
Timer(remove half) = 3815ms 
Timer(access begin()) = 7722ms 
Timer(access all) = 0ms 
10000000000 14999950000 

[email protected]:~$ g++-4.6.1 -std=c++0x -O3 test.cpp 
[email protected]:~$ ./a.out 
Timer(insert) = 16ms 
Timer(remove half) = 2ms 
Timer(access begin()) = 0ms 
Timer(access all) = 1ms 
10000000000 14999950000

我也用了boost::unordered_set同樣快速的結果，所以這就是，如果你不能更新你的編譯器的選項。

來源

2012-04-17 17:03:38

謝謝邁克。我會期待下一個版本的編譯器。 – Hugues 2012-04-17 18:12:12

從unordered_set「刪除一個元素」使用擦除（開始（））在gcc緩慢

回答

相關問題