지우기 (시작())를 사용하여 unordered_set에서 "하나의 요소 제거"가 느림 gcc

Question

unordered_set에서 "하나의 요소 제거"기능을 원합니다.

그러나 지우기 (begin())를 사용하여 구현하면 매우 느려집니다. (이것은 g ++ - 4.5.3에 있으며 어쩌면 begin()은 더 많은 수의 빈 해시 버킷을 트래버스해야할까요?)

놀랄만 한 타이밍으로 아래 예제 코드를 참조하십시오.

효율성이 더 뛰어난 "요소 하나 제거"를 구현하는 다른 방법이 있습니까? (I는 반복자를 무효화하는 다른 개입 설정 작업을 허용 할 않습니다.)

#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 

Answer 1

이 최신 버전에서 수정 된 GNU 라이브러리의 버전에 문제처럼 보인다. 그것은 당신이 당신의 컴파일러를 업데이트 할 수없는 경우 옵션 그래서

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

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

가 나는 또한 boost::unordered_set를 사용하여 유사하게 빠른 결과를 얻었다 : 여기에 내가 설치 한 일이 두 버전을 사용하여 내 테스트의 결과이다.