リンクされたリストを表すには、少なくとも 2 つの方法があります。
1.) リンク リストの配列ベースの表現を使用してstd::vector、型の構造体を保持します。
struct {
<whatever-type-you-want> item ;
int nextitem;
}
ここでのリストへの挿入とは、ベクトルに対して push_back() を実行し、適切な値を next-item に与えることです。
2）RAM全体に構造体のコレクションがあります。ここで挿入は C++ 演算子で行われますnew。
すべてのアイテムがメモリ内の連続した場所にあるため、最初の方法の方が効率的であると言うのは正しいですか?
2 番目の方法では、巨大なリンク リストによるメモリの断片化が発生する可能性があります。
私はここで他のすべての人に反対し、そうです、最初のアプローチがより効率的になる可能性があると言います。2 番目のアプローチでは、ヒープにメモリを O(N) 回割り当てます。N はリスト内のノードの数です。ベクトルを使用している場合、O(log N) 数のヒープ割り当てのみを行っています。
また、64 ビット マシンを使用している場合、多数の小さな項目を処理している場合、各ノードにポインターを保存するオーバーヘッドが少し大きすぎる可能性があります。ベクトルを使用すると、より小さな値を使用できます。nextItemたとえば、64 の代わりに 32 ビットを使用できます。32 ビットの整数を保持するリストを作成している場合、メモリ使用量が 1.5 向上します。
別の最適化として考えられるのは、多くの要素を処理することを前もって知っている場合、大きなベクトルを予約して、かなり長い間単一のヒープ割り当てを持つことができるということです。
私は最近、オートマトンのアプリケーションに関するコースを受講しました。講師は、かなり大きなデータ セットのアルゴリズムのいくつかを実装しています。彼が教えてくれたテクニックの 1 つは、リンクされたリストを表現する最初のアプローチでした。私は両方の方法（ポインターとベクターなどnextItem）を実装しようとしたコースワークがあり、ベクターの方がはるかに優れていました（他の最適化もありましたが、ベクターには間違いなく効果がありました）。
他の人への注意
@smilingbuddha が求めているのは、リンクされたリストのコレクションのようなものだと思います-または、少なくともそれが私が使用したものです. たとえば、隣接リストを使用してグラフを保存する場合。各ノードのすべての隣接ノードのリンク リスト (または配列など) が必要です。したがって、リンクされたリストの配列またはベクトルのベクトルを保持する代わりに、すべてのノードの最後に挿入された隣接ノードを指すインデックスの配列を保持するだけです。
ベクトルでリストを実装するのは見当違いです。
説明します。通常、コンテナーは特定の一連の目標を達成するように設計されており、基礎となる実装はそれらの目標に基づいて選択されます。
ベクターは連続したメモリを持ち、ポインター演算によって任意のセルに到達できるため、非常に優れています。残念ながら、ベクトルの中心で要素を挿入または削除すると、ベクトルのパフォーマンスが低下します。
リストには、正反対の意図があります。リスト内の特定のポイントに移動するには、リンクが連続していないためにリンクをたどる必要があるため、時間がかかります。しかし、リストの主な目的は、迅速な挿入、削除、並べ替え、スプライシング、反転などを可能にすることです。
そのため、ベクターをリストの実装ベースと考えるのは (実行可能ですが)、実際にはこれを見る方法ではありません。ベクトルを使用してリストを実装するということは、基本的に、最初にリストを選択する利点がまったくないことを意味します。
編集
以下のコメントで他の人が指摘しているように、より複雑な実装を考えている場合は、パフォーマンス上の利点を確実に得ることができます。
たとえば、すべてのポインターへの参照を含むベクトルを維持し、その参照ベクトルを順番に維持するように作業する場合、比較的高速な削除/挿入などを行いながら、ポインター演算アクセスの利点を得ることができます。また、参照ベクトルは動的に割り当てられたオブジェクトへのポインターを保持するだけなので、参照ベクトルの操作はコストがかからず、連続したメモリの大量の領域を使用する必要はありません (ベクトルは単に NumElements * sizeof(pointer) on になります)あなたのアーキテクチャ）。
楽しみのために std::deque の実装を見てください。 挿入/削除/その他の操作を高速化するために、ポインターによってリンクされた連続したメモリ領域間にいくつかの興味深い相互作用があります。
それどころか; 最初の方法を使用すると、リンクされたリストからアイテムを削除するのは非効率的です。そのアイテムが格納されていたベクター内のスロットを「失う」ため、そうでないスロットを発見するためにガベージ コレクション スタイルでリスト全体を調べなければならないからです。使用されています。
メモリの断片化に関しては、小さな割り当てがたくさんあることは一般的に問題ではありません。実際、ベクトルは連続している必要があるため、メモリを割り当てると、連続したメモリのブロックがますます大きくなり、断片化が発生します。さらに、ベクトルのサイズが変更されるたびに、大きなメモリ ブロックがコピーされます。
実際、あなたの最初の答えは、メモリ アロケータとメモリ管理ユニットの仕事を自分自身に任せることです。メモリ アロケータの仕事は、メモリの小さなチャンクを配布することです。MMU (とりわけ) の仕事は、メモリのブロック間のポインタが、物理メモリ内で移動された場合でも同じ論理メモリを指し続けることを保証することです。intnextitemメンバーは基本的にポインタとして機能しています。非常に特殊な要件がない限り、ハードウェア、カーネル、および malloc は、この仕事をあなたよりもはるかにうまく行うことができます。
あなたの論理は完全に逆です。最初のアプローチでは、メモリが連続している必要があり、連続したメモリが不足するとすぐに失敗します。2番目のアプローチは、連続しているかどうかに関係なくメモリを使用でき、メモリがまったくなくなるまで機能し続けます。
あなたの最初のアプローチは2つのアルゴリズムをブレンドしているように見えるので、効率が悪いと思います.
リンクされたリストの利点の 1 つは、項目を簡単に挿入および削除できることです。しかし、あなたのアプローチを使用すると、データを移動する必要があります。単純にサイズ変更可能な配列を使用することもできます。
さらに、配列ではメモリが連続している必要があります。状況によっては、大量のデータを操作しているときに、真の連結リストよりも早くメモリ不足になることがあります。これは、一定量のメモリが利用可能であるが、連続していない場合があるためです。
ケース #1 でリストから要素を削除すると、残りの要素のかなりの部分でnextitemインデックスが台無しになる可能性があります。したがって、＃2は通常の方法であり、適切に実装されていれば、非常に多くの要素をリストまたはその他のコンテナに挿入しようとしない限り、メモリの問題は発生しません。