89

以来

  1. どちらも連続したメモリ コンテナーです。
  2. 機能的には、deque には vector のほとんどすべてが含まれていますが、前に挿入する方が効率的であるため、より多くの機能があります。

なぜ誰が好むstd::vectorのですstd::dequeか？

4

10 に答える 10

122

a の要素はメモリ内で連続しdequeていません。vector要素であることが保証されています。したがって、連続した配列を必要とする単純な C ライブラリと対話する必要がある場合、または空間的局所性を (かなり) 気にする場合は、vector. さらに、追加の簿記があるため、他の操作はおそらく同等のvector操作よりも (わずかに) コストがかかります。一方、 のインスタンスを多数または大量に使用するvectorと、不要なヒープの断片化が発生する可能性があります ( の呼び出しが遅くなりますnew)。

また、 StackOverflow の他の場所で指摘されているように、http://www.gotw.ca/gotw/054.htmでさらに適切な議論が行われています。

于 2011-03-17T21:03:29.073 に答える
40

違いを知るにdequeは、一般的にどのように実装されているかを知る必要があります。メモリは同じサイズのブロックに割り当てられ、(配列または場合によってはベクトルとして) 連結されます。

したがって、n 番目の要素を見つけるには、適切なブロックを見つけて、その中の要素にアクセスします。これは常に正確に 2 回のルックアップであるため一定時間ですが、それでもベクトル以上です。

vectorまた、C API であるか、ポインターと長さを取得できるという点でより汎用性があるため、連続したバッファーが必要な API でもうまく機能します。(したがって、下にベクトルまたは通常の配列を配置して、メモリ ブロックから API を呼び出すことができます)。

最大の利点dequeは次のとおりです。

  1. どちらかの端からコレクションを拡大または縮小する場合
  2. 非常に大きなコレクション サイズを扱っている場合。
  3. ブール値を扱うとき、ビットセットではなくブール値が本当に必要です。

これらの 2 番目はあまり知られていませんが、コレクションのサイズが非常に大きい場合:

  1. 再配置のコストが大きい
  2. 連続したメモリ ブロックを見つけなければならないオーバーヘッドは限定的であるため、メモリ不足をより早く実行できます。

過去に大規模なコレクションを扱っていて、連続モデルからブロック モデルに移行したとき、32 ビット システムでメモリが不足する前に、約 5 倍の大きさのコレクションを格納できました。これは、要素をコピーする前に、再割り当て時に古いブロックと新しいブロックを実際に格納する必要があったためです。

これだけ言っても、std::deque「楽観的な」メモリ割り当てを使用するシステムでは問題が発生する可能性があります。a の再割り当てのために大きなバッファ サイズを要求しようとすると、vectorある時点で a によって拒否されるbad_alloc可能性がありますが、アロケータの楽観的な性質により、 a によって要求された小さいバッファの要求が常に許可されるdeque可能性が高く、オペレーティングシステムがプロセスを強制終了して、メモリを取得しようとします。どちらを選んでも、あまり楽しいものではないかもしれません。

このような場合の回避策は、システムレベルのフラグを設定して楽観的な割り当てをオーバーライドするか (常に実行できるとは限りません)、メモリの使用状況をチェックする独自のアロケータなどを使用して、より手動でメモリを管理することです。明らかに理想的ではありません。（ベクトルを好むというあなたの質問に答えるかもしれません...）

于 2013-01-15T10:30:13.623 に答える
33

vector と deque の両方を複数回実装しました。deque は、実装の観点からすると非常に複雑です。この複雑さは、より多くのコードとより複雑なコードに変換されます。そのため、通常、ベクトルではなく deque を選択すると、コード サイズがヒットします。ベクトルが得意とするもの (push_back など) だけをコードで使用すると、速度が少し低下することもあります。

両端のキューが必要な場合は、 deque が明らかに勝者です。ただし、ほとんどの挿入と消去を後ろで行っている場合は、ベクトルが明らかに勝者になります. よくわからない場合は、typedef を使用してコンテナーを宣言し (前後に簡単に切り替えられるようにします)、測定してください。

于 2011-03-17T22:06:09.890 に答える
5

std::deque連続メモリが保証されていません。また、インデックス付きアクセスの場合は多少遅くなることがよくあります。両端キューは通常、「ベクトルのリスト」として実装されます。

于 2011-03-17T21:02:14.027 に答える
2

http://www.cplusplus.com/reference/stl/deque/によると、「ベクターとは異なり、deque はすべての要素が連続した記憶域にあることが保証されないため、ポインター演算による安全なアクセスの可能性が排除されます。」

Deque は、必ずしも連続したメモリ レイアウトを持っているとは限らないため、もう少し複雑です。その機能が必要な場合は、両端キューを使用しないでください。

（以前、私の回答は標準化の欠如をもたらしました（上記と同じソースから、「dequesは特定のライブラリによってさまざまな方法で実装される可能性があります」）が、実際にはほぼすべての標準ライブラリのデータ型に当てはまります。）

于 2011-03-17T21:04:12.033 に答える
0

一方では、ベクトルは非常に多くの場合、deque よりも単純に高速です。deque のすべての機能を実際に必要としない場合は、ベクトルを使用してください。

一方、ベクターでは提供されない機能が必要な場合もあります。その場合は、deque を使用する必要があります。たとえば、deque を使用せず、アルゴリズムを大幅に変更せずに、このコードを書き直してみてください。

于 2016-12-17T19:40:56.133 に答える
0

これらのテスト結果（ソース付き）によると、ベクターをデキューすることはお勧めしません。

もちろん、アプリ/環境でテストする必要がありますが、要約すると:

  • push_back は基本的にすべて同じです
  • 両端キューの挿入、消去は、リストよりもはるかに高速で、ベクターよりもわずかに高速です

さらにいくつかの熟考と、circular_buffer を検討するためのメモ。

于 2016-05-05T03:53:49.810 に答える
0

各ケースの性能テストを行うのは良い考えだと思います。そして、このテストに基づいて決定を下してください。

私はほとんどの場合std::dequeよりも好むでしょう。std::vector

于 2011-06-10T00:12:10.563 に答える
0

両端キューは、その要素へのランダム アクセスを許可するシーケンス コンテナーですが、連続したストレージを持つことは保証されません。

于 2011-03-17T21:02:24.877 に答える