C++では、STL、テンプレートクラス<vector>があります。 私たちはそれがO(1)ランダムアクセスとテール変更をサポートしていることを知っています。 私の質問は、なぜ我々は<vector>のpush_front、またはpop_frontを定義していないのですか？ベクトルの前にプッシュ/ポップがないのはなぜですか？
ベクトルの前に要素をプッシュ/ポップしたい場合は、配列内の各要素を1ステップずつ移動しなければならず、それにはO(n)が必要です。
しかし、必ずしもそうとは限りません。我々が円アレイを用いて<vector>を実装すると、O(1)ランダムアクセスの能力を失うことなく、ベクトルのフロントとテールの両方からO(1)プッシュ/ポップを達成できることを考慮してください。個人的には、実装しないほんの少しのオーバーヘッドではなく、何らかの理由で考えることができませんpush_front/pop_front<vector>です。何かご意見は？
一つの説明は、我々は、ベクターの前に/ポップ要素をプッシュしたい場合、我々は一の工程によりアレイ内の各要素をシフトする必要があり、それはO（N）
を要するであろうということですあなたは絶対に正しいです、push_frontは、可能な再配分に加えて、すべてのアイテムを1つの位置でコピーする必要があるため、すぐに実行する方法がありません。これにより、n個のオブジェクトに対するO（n ）の償却されたパフォーマンスが得られます。これは、ライブラリデザイナーが奨励したいものではありません。
我々は円形配列で
<vector>を実装する場合、円形の配列を持つベクトルを実装
は、ベクターのために真でなければならないいくつかの重要な保証を実装することが多くの困難になりことを考えます。たとえば、イテレータaがイテレータbよりも低いインデックスを持つ要素を指している場合、ベクトルはa < bを保証する必要があります。ベクトルが線形の場合、比較は、イテレータaとbが指している要素の比較アドレスになります。円形配列の実装では、ベクトル原点のアドレスを考慮する必要があり、これは割り当てられたメモリブロックの途中にある可能性があります。
違反するという保証は別のがこれです：vがvector<T>とき
は、
Tはゼロとベクトルの大きさの間の任意bool以外のタイプ、およびn数で、&v[n] == &v[0] + nアイデンティティは真でなければなりません。
これは円形配列では実装できません。
私はイテレータを比較することは、実際に実装するのがかなり簡単だと思います。 たとえば、ポインタを開始する特定のポインタの間の距離の余りをとり、その剰余と比較するだけです。それは実装に問題を引き起こしますか？ –
@TaylorHuangそれは確かに実装することができますが、それは良い配列の置換から離れてベクトルを遠ざけます。設計上、ベクトルは非常に低いオーバーヘッドを提供します。円形配列は性能面では近いものの、まだフリーではありません。ライブラリデザイナーにとって、要素をフロントに追加する柔軟性は、パフォーマンスを犠牲にすることを正当化するものではありませんでした。 – dasblinkenlight
ああ、これもプロトコルに違反していますが、私はかなりきちんと考えていないと思います。 –
STLに記載されているとおり、すでに何かがあります。それはdequeと命名されています。
あなたが書いたように、実際にはオーバーヘッドです。したがって、この機能が必要で、オーバーヘッドに問題がなければ、dequeを使用してください。オーバーヘッドを必要としない場合は、オーバーヘッドは不要なので、このオーバーヘッドを避けるためにはvectorという名前を付けたほうがよいでしょう。
さらに、vectorは、すべての要素が連続した格納場所に格納されることを保証しているため、ポインタ演算を適用できます。これは循環バッファの場合ではありません。
ああ私は確かにデュークが私が探していたものだと思う。 私はdequeがO（1）ランダムアクセスをサポートしていないと思っていましたが、私は間違っていたと思います。 :) –
ありがとうございました。 これは参考になったと思いますが、@ dasblinklightは多くの弱点を指摘していますので、私は彼を受け入れるように選択すると思いますが、あなたも役立ちます。 :) –
実際には、はです。私の知る限り、標準では、ベクトルがの前にの要素（v.prefix_capacity()）の前にのように、（v.capacity() - v.size()）のようにバッファを持つことはできません。これにより、v.push_front()とv.push_back()のランタイムが保証されますが、使用していないユーザーは無料です。さらに、イテレータを無効にしてもO（1）v.pop_front()を保証することができます。素晴らしい提案を書いていますか？
pre_capacity_が0に初期化フィールドとpre_capacity()pre_reserve(size_t i)を実装ゲッターを持っています（？devector）ところで 、あなたはベクトルの観点からテンプレートを作成することがあります：
reserve(capacity() - pre_capacity_ + i)pre_capacity_ += iv.at(i + pre_capacity())at(size_t i)とデリゲートを実装しv[i + pre_capacity()]operator[](size_t i)とデリゲートを実装しv.begin() + pre_capacity()vectorそれとも、缶にメソッドのすべての残りをbegin()とデリゲートを実装あなたがプッシュした要素の数を追跡する/前面からポップした:)。
私は、このような汎用コンテナは、 'デキュ'のように役立つと思いますか？:) しかし、そのようなプロトコルはどうですか？ '' 'の場合、Tはbool以外の任意の型で、ゼロとベクトルのサイズの間のナンバー＆v [n] ==＆v [0] + n同一性は真でなければならない。 '' ' 要素の前のバッファで、そのような保証がどのように満たされますか？ –
私は[devector]（https://github.com/orlp/devector）と呼ばれるこのようなデータ構造を取り入れています。実装はまだ完了していません（私はいつかそれを実際に完了すべきです）。 – orlp
@TaylorHuang： 'push_front（）'はイテレータを無効にします。したがって、再割り当てなしで 'push_front（）'を実行すると '＆v [0]'が減少します。これを次のように考える：再割り当ては、現在のバッファの前に 'sizeof（T）'バイトで行われる。 – lorro
それはそれがそうであるように設計されました。物語の終わり。 –
循環バッファーを処理するために必要な計算のオーバーヘッドは考える価値がありませんか？それは常にO（）についてのことではなく、現実の世界のパフォーマンスについても同じです。 –
標準によって設定された制限のため、std :: vectorを循環として定義することはできません。 –