c++ - リンクリストベースのベクトル

Question

コンテナーを使用することのマイナス面について考えていたのでstd::vector、チャンク化されたリンクリストをバックエンドとして使用すると、ベクターが拡張されたときに発生するコピーを回避できるかどうか疑問に思っていました。

このようなもの。

私の質問は、これは実用的なアイデアであり、コンテナからの読み取りは配列ベースのベクトルと同様のランタイムを持ち、「成長」時間は大幅に短縮されると想定するのは正しいですか?

Answer 1

を使用していくつかの実験を行うことができstd::dequeます。これは説明として機能します。

Answer 2

ソリューションの実行時 (ランダム) アクセスは、std::vector.

element にアクセスするにNは、多くのリンクをたどって適切なブロックに到達し、ブロックを介して要素にアクセスする必要がある場合があります。

前もって大きなサイズを割り当てることで、大きなベクトルのパフォーマンスを低下させることができます。

挿入と削除が頻繁に行われる場合は、ベクターのデータ構造が間違っている可能性があります。