arrays - STL リストとベクトル、連結リストと配列を使用することの長所と短所

Question

STL:list、STL:vector、array、およびリンクされたリストの基本的なレベルでの違いを互いに比較して、どのような違いがあるのか​​ 疑問に思っています。

私の理解では、一般に、リンクされたリストは拡張可能なリストを可能にし、挿入と削除ははるかに簡単ですが、すべての要素をトラバースする必要があるため、リンクされたリスト内の単一の要素に直接アクセスするには時間がかかります。

私はおそらく他の多くの重要な違いを見逃しているので、もっと明白なものを指摘することもできます.

リストとベクトルは比較してどのように機能し、どちらを選択しますか?

Answer 1

以下は、リストとベクトルの違いです。

1. 挿入にかかる時間:リストに要素を挿入するには一定の時間がかかります。ベクトルの容量がベクトルに存在する要素の数と等しい場合、ベクトルは新しい値を挿入する前にベクトルに存在するデータを内部的に再配置する必要があります。これには、プロセッサのオーバーヘッドと時間がかかります。
2. データへのアクセスにかかる時間: ベクトルは、この点でリストよりも優れています。ベクターは途中にある要素にアクセスするのに一定の時間がかかります。リストは、必要な要素に到達するためにリストをトラバースする必要があります。
3. コンテナーが使用するメモリ: vector の容量とサイズは必ずしも同じである必要はありません。vector の容量は指数関数的に増加し、コンテナーが実際に必要とするよりも多くのメモリを消費します。リストは、要素を格納するために必要なメモリとまったく同じメモリを使用するため、割り当て中にメモリを節約できる余分なメモリは割り当てられません。