C++：STD対のstd ::ベクトル::リスト

Question

の性能I同じの複数の実行のために様々なN.

void vectorPerf(size_t n) 
{ 
    std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now(); 
    std::vector<size_t> cache; 
    for (size_t i = 0; i < n; i++) { 
     cache.push_back(i); 
    } 
    std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now(); 

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count(); 

    std::cout << duration << " us." << "\n"; 

    return; 
} 

void listPerf(size_t n) 
{ 
    std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now(); 
    std::list<size_t> cache; 
    for (size_t i = 0; i < n; i++) { 
     cache.push_back(i); 
    } 
    std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now(); 

    auto duration = std::chrono::duration_cast<std::chrono::microseconds>(t2-t1).count(); 

    std::cout << duration << " us." << "\n"; 

    return; 
} 

int main(int argc, char** argv) 
{ 

    if (argc != 2) { 
     return -1; 
    } 
    std::stringstream ss(argv[1]); 
    size_t n; 
    ss >> n; 
    vectorPerf(n); 
    std::cout << "\n"; 
    listPerf(n); 
    std::cout << "\n"; 
} 

のためのstd ::リスト対のstd ::ベクトル性能をプロファイリングするために、次のコードを持っています

N  std::vector std::list 
1000 46   116 
2000 85   217 
5000 196   575 
10000 420   1215 
100000 3188   10497 
1000000 34489  114330 

私は疑問に思ってするのstd ::リストのパフォーマンスを来る方法ですがのstd ::ベクトル一貫して悪化している：Nのセットが、私は結果は下記の番号と同じオーダーで一貫している結果を得ます。 std :: vectorの場合、std :: vectorの基盤となる内部オブジェクトは時々サイズを変更する必要があるため、パフォーマンスは償却されることが予想されます（O）。私がやっていることは、リストの最後に要素を挿入することです。私はstd :: listがO（1）であると期待していました。だから、std :: listはstd :: vectorよりもうまくいくと示唆していますが、その反対は真実であるようです。

なぜこのようなことが起こっているのか、誰かが明らかにすることができれば幸いです。私は2015 MBPでg ++を使ってMacOS 10.12.6でコンパイルしています。

ありがとうございました。

編集：私は今std :: vector :: push_back（）がO（1）を償却することを理解します。しかし、私には分かりませんが、なぜstd :: list :: push_back（）はstd :: vector :: push_back（）よりも一貫してパフォーマンスが悪いのですか？

Answer 1

ベクトル挿入は、リストが常にO（n）である償却O（n）ではなく、償却定数（つまり償却O（1））であり、この状況ではベクトル容量は実際のサイズそれは余分なスペースを割り当てて、それが進むにつれていっぱいになるので、すべてのpush_backに対して割り当てが不要になります。