data-structures - 最適なベクトルデータ構造？

Question

重複の可能性：
O（1）ランダムアクセスと最悪の場合のO（1）追加をサポートするデータ構造？

StackOverflowで、おそらく最適な （「配列リスト」）データ構造に関する回答を見ましたvector。これは、正しく覚えていれば、要素をより大きなベクトルに遅延コピーして、ベクトルが毎回大きな一時停止を引き起こさないようにするものです。再割り当てされました。

簿記のためにO（sqrt（n））の余分なスペースが必要であり、その答えは出版された論文にリンクしていることを覚えていますが、それだけです...私はそれを探すのに本当に苦労しています（あなたはそれを検索することを想像できます最適なベクトルのように私はどこにも行きません）。

紙はどこにありますか？

Answer 1

あなたが参照している論文は、 Brodnikらによる「最適な時間と空間でのサイズ変更可能なアレイ」だと思います。それらのデータ構造は、この構造を組み立てるための構成要素として、質問で言及したレイジーコピー動的配列を使用します。レイジーコピーのデータ構造を説明するStackOverflowに関するこの古い質問があります。これは、データ構造がどのように機能するかをよりよく理解するのに役立つ可能性があります。

お役に立てれば！