53

リスト要素へのランダムアクセスが要件ではない単純なリンクリストの場合、std::list代わりに使用することには大きな利点(パフォーマンスまたはその他)がありstd::vectorますか? std::slist後方トラバーサルが必要な場合、要素を反復処理する前にreverse()リストを使用する方が効率的でしょうか?

4

7 に答える 7

61

いつものように、パフォーマンスに関する質問に対する最良の答えは、ユース ケースに合わせて両方の実装をプロファイリングし、どちらが速いかを確認することです。

一般に、データ構造への挿入がある場合 (最後以外) はvector遅くなる可能性があります。それ以外の場合、ほとんどの場合、データの局所性の問題のみの場合vectorよりもパフォーマンスが向上することが期待されます。これは、隣接する 2 つの要素がデータセットがメモリ内で隣接している場合、次の要素はすでにプロセッサのキャッシュにあり、メモリをキャッシュにページフォールトする必要はありません。list

また、a のスペース オーバーヘッドvectorは一定 (3 ポインター) であるのに対し、a のスペース オーバーヘッドはlist要素ごとに支払われることに注意してください。これにより、任意の時点でキャッシュに存在できる完全な要素 (データとオーバーヘッド) の数も減少します。時間。

于 2008-10-26T13:41:22.040 に答える
29

C++ で考えるデフォルトのデータ構造はVectorです。

次の点を考慮してください...

1] トラバーサル:リスト ノードはメモリ内のいたるところに散らばっているため、リスト トラバーサルはキャッシュ ミス
につながります。しかし、ベクトルの走査はスムーズです。

2] 挿入と削除:
ベクターに対して行う場合、要素の平均 50% をシフトする必要がありますが、キャッシュはそれを非常に得意としています! しかし、リストを使用すると、挿入/削除のポイントまでトラバースする必要があります...再び...キャッシュミス! そして驚くべきことに、このケースでもベクトルが勝ちます!

3]ストレージ：
リストを使用する場合、要素ごとに2つのポインター（前方および後方）があるため、リストはベクターよりもはるかに大きくなります! ベクトルは、実際の要素が必要とするよりも少し多くのメモリを必要とします。

ベクトルを使用しない理由があるはずです。

参考:
ビャルネ・ストラウストラップ卿の講演でこれを学びました: https://youtu.be/0iWb_qi2-uI?t=2680

于 2013-01-25T16:45:23.327 に答える
13

単にいいえ。List には Vector よりも優れた点がありますが、シーケンシャル アクセスはその 1 つではありません。

ただし、特に途中で挿入する場合、ベクトルはリストよりも追加の要素を追加するのに費用がかかります。

これらのコレクションがどのように実装されているかを理解してください。ベクトルはデータの連続配列であり、リストはデータと次の要素へのポインターを含む要素です。それを理解すれば、なぜリストが挿入に適していて、ランダム アクセスに適していないかがわかります。

(そのため、ベクトルの逆方向反復は順方向反復とまったく同じです。反復子は毎回データ項目のサイズを減算するだけで、リストはポインターを介して次の項目にジャンプする必要があります)

于 2008-10-26T13:41:22.460 に答える
4

このトピックに関するいくつかの厳密なベンチマーク: http://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html

他の人が指摘しているように、連続したメモリストレージは std::vector がほとんどのものに適していることを意味します。少量のデータ (キャッシュにすべて収まる場合) および/または消去と再挿入が頻繁に行われる場合を除いて、std::list を使用する正当な理由は事実上ありません。複雑さの保証は、キャッシュとメイン メモリの速度 (200 倍) の違いと、連続したメモリ アクセスがキャッシュの使用にどのように影響するかにより、実際のパフォーマンスには関係しません。この問題についての Chandler Carruth (google) の講演を参照してください: https://www.youtube.com/watch?v=fHNmRkzxHWs

また、Mike Acton の Data Oriented Design の講演はこちら: https://www.youtube.com/watch?v=rX0ItVEVjHc

于 2016-04-02T07:35:37.707 に答える
4

後方トラバーサルが必要な場合、slist がデータ構造になる可能性は低いです。

従来の (二重に) リンクされたリストでは、リスト内のどこでも一定の挿入時間と削除時間が得られます。ベクトルは、償却された定数時間の挿入とリストの最後での削除のみを行います。ベクターの挿入と削除の時間は、最後以外は直線的です。これがすべてではありません。一定要因もあります。ベクトルは、コンテキストに応じて長所と短所がある、より単純なデータ構造です。

これを理解する最善の方法は、それらがどのように実装されているかを理解することです。リンクされたリストには、各要素の次と前のポインターがあります。ベクトルには、インデックスによってアドレス指定される要素の配列があります。このことから、効率的なランダム アクセスを提供できるのはベクトルだけであるのに対し、どちらも効率的な前方および後方トラバーサルを実行できることがわかります。また、連結リストのメモリ オーバーヘッドは要素ごとであるのに対し、ベクトルでは一定であることもわかります。また、2 つの構造間で挿入時間が異なる理由もわかります。

于 2008-10-26T13:42:31.787 に答える
2

コストの詳細については、この質問を参照してください:
複雑さとは何ですか 標準コンテナの保証

slist があり、それを逆の順序でトラバースしたい場合は、type をすべてのリストに変更してみませんか?

于 2008-10-26T15:19:17.863 に答える