この質問を読み、ここでいくつかの結果を見た後、C++ のリストを完全に避けるべきだと思われます。挿入はポインター操作の問題であり、再割り当てする必要がないため、すべてのコンテンツを反復処理するだけでよい場合には、リンクされたリストが最適なコンテナーになると常に思っていました。
どうやら、「キャッシュの局所性」のために、リストは非常にゆっくりと繰り返されるため、使用する予約メモリを少なくしたり、追加を高速化したりすることによる利点（2番目のリンクからはそれほど高速ではないようです）は価値がないようですそれ。
そうは言っても、パフォーマンスの観点から、可能であればstd::listoverまたは?std::dequestd::vector
余談ですが、std::forward_list多くのキャッシュ ミスも発生しますか?
std::listいくつかのまれなケースで役立ちます。
ただし、C++ 順次コンテナーの一般的なルールは、「アルゴリズムに互換性がある場合は を使用しますstd::vector。アルゴリズムに互換性がない場合は、アルゴリズムを変更して を使用できるようにするstd::vector」です。
std::list例外はありますが、より良い選択である理由を徹底的にリストする試みは次のとおりです:
(A) コンテナーの中央に挿入する必要がある場合、および (B) メモリ内の各オブジェクトの場所を安定させる必要がある場合。要件 (B) は、通常、要素へのポインターで構成される非安定コンテナーを使用することで取り除くことができるため、これは を使用する強い理由にはなりませんstd::list。
(A) コンテナーの途中で挿入または削除する必要がある場合 (B) コンテナーを反復する必要がある場合よりも桁違いに頻繁に。これも極端なケースです。 から削除する要素を見つけるにはlist、通常、反復する必要があります。
につながる
（A）コンテナの途中で挿入または削除する必要があり、（B）他のすべての要素へのイテレータが有効なままである必要があります。これは、ケース 1 とケース 2 の隠れた要件になります。永続的なイテレータがない場合、繰り返しよりも頻繁に削除または挿入するのは難しく、イテレータとオブジェクトの安定性は非常に関連しています。
最後のケースは、かつて使用する理由だったスプライシングのケースですstd::list。
C++03 では、すべてのバージョンのstd::list::splice(理論上) O(1) 時間で実行できました。ただし、非常に効率的な形式のO(n) 操作がsplice必要です。sizeC++11 ではO(1) でsizeある必要があるため、の極端な効率は、「他のリスト全体をスプライシングする」場合と「サブリストを自己スプライシングする」場合に限定されます。単一要素スプライスの場合、これは単に挿入と削除です。サブ範囲スプライスの場合、コードはスプライス内のすべてのノードにアクセスして、O(1) として維持するためにそれらをカウントする必要があります(自己スプライシングを除く)。listsplicesize
listしたがって、全体スプライスまたは自己リスト部分範囲のみを実行している場合は、spliceこれらlistの操作を他の非リスト コンテナーよりもはるかに高速に実行できます。
提供できる最大の改善std::listは、1 つまたは複数の要素を 1 つのリストの途中から別のリストに移動する場合です。このsplice操作は非常に効率的ですがlist、vector. とはいえ、これは非常にまれであり、多くのvector場合、パフォーマンスとシンプルさの点で最高のコンテナーです。
コンテナーの選択でパフォーマンスの問題が疑われる場合は、常にコードをプロファイリングしてください。
コンテナーの途中でアイテムを頻繁に追加/削除する場合は、 and (およびその他の連続したメモリ コンテナー) を選択std::listしました。も参照してください。std::dequestd::vector