c++ - deque 実装オプション

Question

私がプログラムしている環境にはそのようなものがないため、独自の両端キューを作成する必要があります。それを実装する方法について、私は2つの選択肢の間で自分自身が引き裂かれていることに気づきました。

• データを保持する配列へのポインターの成長可能な配列を管理できます。問題は、各アレイ セカンダリのサイズをどのように決定するかということです。
• 定期的に成長する大きなバッファを 1 つ持つことができ、基本的にその上に循環キューを構築できます。これは、大きな割り当てを効率的に実行するのが難しくなるため、特定のサイズになると良くないように思えます。

何か案は？

Answer 1

最初のオプションでは、アプリケーションまたはメモリの制約について知っていることによって決定される上限まで、各配列のサイズを以前のサイズから単純に 2 倍にすることができます。

あなたが理解したように見える秒。

単純な二重連結リストではないのはなぜですか? 高速ランダムアクセスが必要ですか?

Answer 2

私はあなたの2つのオプションの組み合わせを行います.複数の小さなバッファと、それぞれの「端」が他のものを指すようにし、本質的により大きな循環配列になります. そうすれば、バッファを頻繁に割り当てる必要がなくなります。セカンダリ バッファのサイズに関しては、Collin の提案が適切であると思います。サイズを大きくしてください。