dequeとlist STLコンテナの違いは何ですか？

StackOverflow https://stackoverflow.com/questions/1436020

  •  07-07-2019
  •  | 
  •  

質問

この2つの違いは何ですか？方法はすべて同じです。そのため、ユーザーにとっては同じように機能します。

それは正しいですか？

役に立ちましたか？

解決

（日付は付けられているが、非常に便利） SGI STL の deque ：

  

dequeはベクターに非常に似ています。ベクターと同様に、要素へのランダムアクセス、シーケンスの最後での要素の一定時間の挿入と削除、および要素の線形時間の挿入と削除をサポートするシーケンスです。中央。

     

dequeがvectorと異なる主な方法は、dequeがシーケンスの開始時の要素の一定時間の挿入と削除もサポートすることです。さらに、dequeにはベクターのcapacity（）およびreserve（）に類似したメンバー関数はなく、それらのメンバー関数に関連付けられているイテレーターの有効性に関する保証も提供しません。

list の概要は、同じサイト：

  

リストは二重にリンクされたリストです。つまり、前方または後方の両方のトラバース、および開始時または終了時、または途中での要素の（償却された）一定時間の挿入と削除をサポートするシーケンスです。リストには、挿入とスプライシングによってリスト要素へのイテレータが無効にならず、削除しても削除される要素を指すイテレータのみが無効になるという重要なプロパティがあります。イテレータの順序は変更できます（つまり、list :: iteratorは、リスト操作の前とは異なる先行操作または後続操作を持つ場合があります）が、イテレータ自体は無効化されず、無効化しない限り異なる要素を指すようになりませんまたは突然変異は明示的です。

要約すると、コンテナはルーチンを共有している可能性がありますが、これらのルーチンの時間保証はコンテナごとに異なります。これは、これらのコンテナのどれをタスクに使用するかを考慮する際に非常に重要です。コンテナが最も頻繁に使用される方法を考慮する（たとえば、挿入/削除よりも検索の方が）適切なコンテナに誘導します。

他のヒント

違いをリストしてみましょう：

  • Deque は、 動的配列、ランダムを提供します アクセス、ほぼ同じ ベクターとしてのインターフェース。
  • リストは、その要素を 二重リンクリスト ランダムアクセスを提供します。
  • Deque は、次の場所で高速な挿入と削除を提供します 終わりと始まりの両方。要素の挿入と削除 中央が比較的遅いのは 両方のいずれかまでのすべての要素 端を移動してスペースを確保したり、 ギャップを埋めます。
  • リストでは、各位置での要素の挿入と削除が高速で、 両端を含む。
  • Deque ：要素の挿入または削除 開始時または終了時以外 すべてのポインタ、参照、 要素を参照するイテレータ dequeの。
  • リスト：要素の挿入と削除は ポインター、参照、 他の要素のイテレータ。

複雑さ 

             Insert/erase at the beginning       in middle        at the end

Deque:       Amortized constant                  Linear           Amortized constant
List:        Constant                            Constant         Constant

std :: list は基本的に二重リンクリスト。

std :: deque 、上の一方、 std :: vector のように実装されます。インデックスによる一定のアクセス時間、および先頭と末尾での挿入と削除があり、リストとは劇的に異なるパフォーマンス特性を提供します。

いいえ。 dequeは、前面と背面でのみO（1）の挿入と削除をサポートします。たとえば、ラップアラウンドでベクターに実装できます。また、O（1）ランダムアクセスも保証されるため、二重リンクリストを（ちょうど）使用していないことを確認できます。

別の重要な保証は、各コンテナがメモリにデータを保存する方法です：

  • ベクターは、単一の連続したメモリブロックです。
  • dequeはリンクされたメモリブロックのセットであり、複数の要素が各メモリブロックに格納されます。
  • リストは、メモリに分散された要素のセットです。つまり、メモリ「ブロック」ごとに1つの要素のみが保存されます。

dequeは、それぞれの欠点なしにベクターとリストの両方の利点をバランスさせるように設計されていることに注意してください。これは、マイクロコントローラーなど、メモリに制限のあるプラットフォームで特に興味深いコンテナーです。

メモリストレージ戦略は見過ごされがちですが、特定のアプリケーションに最適なコンテナを選択することが最も重要な理由の1つであることがよくあります。

パフォーマンスの違いは、他の人によって十分に説明されています。オブジェクト指向プログラミングでは、類似または同一のインターフェースが一般的であることを追加したかっただけです。これは、オブジェクト指向ソフトウェアを作成する一般的な方法論の一部です。 2つのクラスが同じインターフェースを実装しているという理由だけで2つのクラスが同じように動作すると仮定する必要があります。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top