私は混乱しています。配列を使用したベクトルの実装について読んでいました。単純な動的配列の実装を行っている間、すべて問題ありませんでした。
循環方式で配列を使用してベクトルを実装できること、および要素の追加と削除 (最初と最後) が一定時間で実行されることが言及されました。それは、リンクされたリストがすべきことではありませんか?
それがどのように機能するか知りたいのですが、実装や適切な説明を実際に見つけることができませんでした。一般的なアイデアとそれを実装する方法についての情報は大歓迎です。
編集：私の推測では、新しいデータは「最も古い」データに書き込まれる必要があり、配列のサイズは固定されており、最後に使用された位置を格納する変数が必要です。
あなたは循環バッファについて話している
残念ながら、途中で挿入したり、途中から削除したりできないため、ベクターを使用して実装することはできません。
C++03vectorは連続したストレージを保証するため、つまり、各0 <= n < vec.size():
&vec[n] == &vec[0] + n
これは、循環バッファを使用して を実装できないvectorことを意味します。バッファの最後から最初に「ラップアラウンド」した時点で、この制限に違反しています。
operator[]この要件を満たすオーバーロードされたプロキシを返すことができると思われる場合operator&-いいえ、できません。返す必要がありT&ます。
vectorこの要件を除けば、標準には循環バッファの使用を妨げるものは何もないと思います。バッファーがいっぱいの場合、vector実際に行うのと同じことを行います。つまり、より大きなバッファーに再割り当てします。動作の唯一の違いは、最初に消去または挿入したときに何が起こるかです。循環バッファーを使用すると、他のすべての要素は十分なスペースがあると仮定して静止しますが、通常はすべて移動します。しかし、標準では明示的にそれらを移動する必要はありません。最初に挿入または消去すると、イテレータとすべての要素への参照が無効になるため、プログラムはそれらが特定の方法で移動することに正当に依存することはできません。
std::list開始時も終了時も一定時間内に抜き差しできるのは本当です。そうすることができstd::dequeます。