std::vector からのランダムな削除が std::list よりも速いのはなぜですか? 高速化するために私がやっていることは、ランダム要素を最後に交換してから最後を削除することです。ランダムな削除が目的であるため、リストの方が高速になると思いました。
for(int i = 500; i < 600; i++){
swap(vector1[i], vector1[vector1.size()-1]);
vector1.pop_back();
}
for(int i = 0; i < 100; i++){
list1.pop_front();
}
結果 (秒単位):
Vec swap delete: 0.00000909461232367903
List normal delete: 0.00011785102105932310
あなたがやっていることは、ランダムな削除ではありません。最後から削除しています。これは、ベクトルが（とりわけ）構築されているものです。
また、スワップするときは、ベクトルが得意とする単一のランダムなインデックス操作を行っています。
との違いはstd::list、std::vectorパフォーマンスだけではありません。また、反復子の無効化のセマンティクスも異なります。からアイテムを削除してstd::listも、リスト内の他のアイテムを指すすべての反復子は有効なままです。ではそうではありませんstd::vector。アイテムを消去すると、そのアイテムの後にあるすべての反復子が無効になります。(実装によっては、有効なイテレータとして引き続き機能する場合がありますが、標準によれば使用できなくなり、使用しようとするとチェック実装がアサートする必要があります。)
したがって、コンテナーの選択は、必要なセマンティクスにも関係します。
それはランダムではありません。vector1.erase(vector.begin() + rand() % vector.size()); を試してください。代わりは。
実際、さらに高速化が必要な場合は、ベクター内の要素にiteratorsを介してインデックスを付ける必要があります。一部のアーキテクチャでは、パフォーマンスが向上することが知られています。