c++ - 中央でのVectorとDequeの挿入

Question

挿入が前または最後にある場合、 dequeはベクトルよりも効率的であり、ポインター演算を行う必要がある場合はベクトルの方が優れていることを私は知っています。しかし、途中で挿入を実行する必要がある場合は、どちらを使用しますか？なぜ。？

Answer 1

dequeデータをブロックに分割して保存するため、aには利点があると思われるかもしれません。ただし、一定時間で実装するoperator[]には、これらすべてのブロックが同じサイズである必要があります。途中で要素を挿入または削除するには、と同じように、すべての値を片側または反対側にシフトする必要がありますvector。はより単純で、キャッシュの局所性が優れているためvector、先に出てくるはずです。

Answer 2

標準ライブラリコンテナの選択基準は次のとおりです。以下に応じてコンテナを選択します。

1. 保存するデータの種類と
2. データに対して実行する操作のタイプ。

途中で多数の挿入を実行する場合は、を使用することをお勧めしますstd::list。

選択がastd::dequeとの間にある場合std::vectorは、考慮すべきいくつかの要因があります。

• 通常、要素にアクセスするためのdequeの場合、もう1つの間接参照があるため、要素へのアクセスとdequeの反復子の移動は通常少し遅くなります。
• メモリのブロックにサイズ制限があるシステムでは、複数のメモリブロックを使用するため、dequeにはより多くの要素が含まれる場合があります。したがって、max_size()両端キューの場合は大きくなる可能性があります。
• Dequesは、容量と再割り当ての瞬間を制御するためのサポートを提供しません。特に、最初または最後以外の要素を挿入または削除すると、両端キューの要素を参照するすべてのポインター、参照、およびイテレーターが無効になります。ただし、典型的な内部構造によれば、両端キューは再割り当て時にすべての要素をコピーする必要がないため、再割り当てはベクトルよりもパフォーマンスが優れている場合があります。
• メモリのブロックは、使用されなくなると解放される可能性があるため、両端キューのメモリサイズが縮小する可能性があります（これは標準によって課される条件ではありませんが、ほとんどの実装では縮小されます）

Answer 3

std :: deque は、で使用される単一のブロックではなく、通常、連続するデータブロックのリンクされたシーケンスとして実装されるため、大きなコンテナーのパフォーマンスが向上する可能性がstd::vectorあります。したがって、途中に挿入すると、ある場所から別の場所にコピーされるデータが少なくなり、再割り当てが少なくなる可能性があります。

もちろん、それが重要かどうかは、コンテナのサイズと保存されている要素をコピーするコストに依存します。C ++ 11の移動セマンティクスでは、後者のコストはそれほど重要ではありません。しかし、結局のところ、知る唯一の方法は、現実的なアプリケーションでプロファイリングすることです。

Answer 4

Dequeは、要素を挿入するたびに配列の半分を移動する必要がないため、さらに効率的です。

もちろん、これは、多数の要素を検討する場合にのみ実際に問題になります。ベンチマークを実行して、特定のケースでどれがより適切に機能するかを確認することをお勧めします。時期尚早の最適化がすべての悪の根源であることを忘れないでください。