c++ - STLベクトルとリスト：グラフ隣接リストに最も効率的ですか？

Question

リストは、pushing_back時にメモリを割り当てる際にほとんどの時間を消費します。一方、サイズ変更が必要な場合、ベクターは要素をコピーする必要があります。したがって、隣接リストを格納するのに最も効率的なコンテナはどれですか？

Answer 1

これは絶対に確実に答えられるとは思いません。それにもかかわらず、私は、aがより良くなる可能性が少なくとも90％あると推定しvectorます。vector隣接リスト内の要素の順序は通常重要ではないため、隣接リストは実際には多くのアプリケーションよりも優先される傾向があります。つまり、要素を追加するときは通常、コンテナの最後にあり、要素を削除するときは、最初にコンテナの最後にスワップできるため、最後に追加または削除するだけです。

はい、vector拡張時に要素をコピーまたは移動する必要がありますが、実際には、これが実質的な問題になることはほとんどありません。特に、aの指数関数的拡張率は、vector要素がコピー/移動される平均回数が一定になる傾向があることを意味します。通常の実装では、その定数は約3です。

正直にコピーすることが実際の問題である状況にある場合（たとえば、要素のコピーは非常に高価です）、その後の私の次の選択はvectorまだそうではありませんlist。std::deque代わりに、おそらく¹を使用することを検討します。これは基本的に、オブジェクトのブロックへのポインタのベクトルです。拡張を行うために何かをコピーする必要があることはめったになく、まれに、コピーする必要があるのはオブジェクトではなくポインタだけです。deque（両端で一定時間に挿入/削除する）の他の独自の機能が必要でない限り、vector通常はaの方が適していますが、それでもdequeほとんどの場合、リストよりもaの方が適しています（つまり、vector通常は最初の選択肢です。dequeかなり近い秒、そしてlistかなり遠い最後）。

---

^{1.マイナーなことは別として、少なくとも過去には、Microsoftの `std :: deque`の実装には、私が一種の欠陥と見なすものがありました。`deque`の要素のサイズが16より大きい場合、1つの要素のみの「ブロック」へのポインタを格納することになります。これは、最初に`deque`を使用する利点の多くを打ち消す傾向があります。ただし、これは通常、隣接リストの使用にはあまり影響しません。}

Answer 2

答えはユースケースによって異なります。PS @quasiverse-暗黙的または明示的に「::reserve」のメモリが不足すると、ベクトルはreallocを呼び出します

常に変化する隣接リスト（挿入と削除）がある場合は、リストが最適です。多かれ少なかれ静的な隣接リストがあり、ほとんどの場合トラバーサル/ルックアップを実行している場合、ベクトルは最高のパフォーマンスを提供します。

Answer 3

STLコンテナは厳密に定義されていないため、実装はさまざまです。注意が必要な場合は、使用されているのがベクトルであるかリストであるかを気にしないようにコードを記述し、どちらが速いかを試してみることができます。キャッシュ効果などの複雑さを考えると、相対速度を正確に予測することはほぼ不可能です。

Answer 4

この比較に3番目のオプションを追加できます：専用アロケータを使用したリスト。

固定サイズの小さなオブジェクトにアロケータを使用すると、割り当て/割り当て解除の速度が大幅に向上する可能性があります。

Answer 5

このチュートリアルサイトでは、リストの配列を使用することをお勧めします。または、代わりにリスト要素のベクトルを使用できると思います。リストの 配列adj list