std :: list.begin（）は大きいリストのために減速します

私は以下の問題があります。私は二重リンクリストを使用する必要があるLexBFSアルゴリズムを実装する必要があります。私はstd::listを選んだ。私のコードを最終的にデバッグしたとき、私は奇妙な動作に気付きました。リストの動作が遅くなるにつれてリストの動作が遅くなります。 Classは、いくつかのフィールドと私のシンプルな構造体ですstd::list<Class>あるstd :: list.begin（）は大きいリストのために減速します

// start new iteration 
clock_t tbegin = clock(); 
if(L.size() && L.begin()->empty) { 
    double ee = double(clock() - tbegin)/CLOCKS_PER_SEC; 
    cerr << fixed << setprecision(6) << "t: " << ee << " size: " << L.size() << "\n"; 
    //... 
} 
// here I make other operations on L...

L：私はこの1つの行に絞り込みます。

これが出力されます。

t: 0.000086 size: 5224 
t: 0.000124 size: 7818 
t: 0.000281 size: 17515 
t: 0.000300 size: 19310 
t: 0.000341 size: 21202 
t: 0.000406 size: 25117 
t: 0.000459 size: 29202 
t: 0.000510 size: 31307 
t: 0.000528 size: 33413 
t: 0.000562 size: 35487 
t: 0.000638 size: 39740 
t: 0.000706 size: 41885 
t: 0.000710 size: 44037 
t: 0.000747 size: 46261 
t: 0.000868 size: 52670 
t: 0.000982 size: 54800 
t: 0.000957 size: 56895 
t: 0.001084 size: 58993 
t: 0.001114 size: 61101

シンプルなルックアップが遅くなります！何が起こっている？

ありがとうございます。

コンパイルフラグ：C++ 98に

clang++ a.cpp -o ./a -std=c++11 -Wall -g 

Ubuntu clang version 3.4-1ubuntu3 (tags/RELEASE_34/final) (based on LLVM 3.4) 
Target: x86_64-pc-linux-gnu 
Thread model: posix

出典

2017-03-11 tomwesolowski

私はあなたのタイミング結果の原因となっているstd :: list :: sizeだと思います。 C++ 11以来、それは一定の複雑さでなければなりません。 – rubenvb

Read：http://stackoverflow.com/questions/228908/is-listsize-really-on –