c++ - C++ ベクトルとリストの挿入

Question

ベクトルの途中に要素を挿入するよりもリストの途中に要素を挿入する方が速い理由を誰か知っていますか?

ベクトルを使用することを好みますが、可能であればリストを使用するように言われました。誰でも理由を説明できますか？ベクトルよりもリストを使用することを常にお勧めしますか?

Answer 1

ベクトルの途中に挿入するには、挿入ポイントの後のすべての要素をシャッフルしてスペースを作る必要があり、多くのコピーが必要になる可能性があります。

リストはリンクされたリストとして実装され、各ノードは隣接するノードへの参照でメモリ内の独自のスペースを占有するため、新しいノードを追加するには、新しいノードを指すように 2 つの参照を変更するだけで済みます。

使用するデータ型によっては、ベクトルはリストよりもはるかに高速に実行される場合があります。しかし、オブジェクトのコピーが複雑になればなるほど、ベクトルは悪化します。

Answer 2

簡単に言えば、ベクトルは配列です。そのため、その要素は連続したメモリ位置 (つまり、隣り合う場所) に格納されます。唯一の例外は、データを失うことなく実行時にベクトルのサイズを変更できることです。

ここで、リストに挿入するには、ノードを識別し、新しい要素を (メモリ内の任意の場所に) 作成し、値を格納してポインターを接続します。

ただし、ベクター (配列) の場合、新しい要素用のスペースを作成するために、要素を 1 つのセルから別のセルに物理的に移動する必要があります。特に多くの要素 (データなど) を移動する必要がある場合は、その物理的な移動が遅延の原因となります。配列要素を物理的に移動していません。むしろ、その内容です。