私は、ランダム アクセス (または少なくとも O(n) よりも優れている) を備えたコンテナーを設計しなければならないアプリケーションに直面しています。 ) 挿入時に指定します。
たとえば、次の配列があるとします。
[2, 9, 10, 3, 4, 6]
インデックス 2 で remove を呼び出して10 を削除できます。また、インデックス 1 で insert を呼び出して13 を挿入することもできます。
これらの 2 つの操作の後、次のようになります。
[2, 13, 9, 3, 4, 6]
番号は順番に格納され、挿入/削除操作には、番号を挿入する場所または削除する番号を指定するためのインデックス パラメータが必要です。
私の質問は、Linked List とベクトル以外に、どのような種類のデータ構造がこのようなものを維持できるかということです。次に利用可能なインデックスを優先するヒープに傾いています。しかし、私はフュージョン ツリーが有用であることについて何かを見てきました (ただし、より理論的な意味で)。
メモリ消費を抑えながら、最適な実行時間を実現できるデータ構造はどのようなものでしょうか? ハッシュテーブルを保持する広告掲載順で遊んでいますが、これまでのところ成功していません。
std:: ベクトルをまっすぐに使用して放り投げる理由は、これらの基本的な操作に関してベクトルを実行するものを作成する必要があるためです。コンテナーのサイズは、数十万の要素に成長する可能性があるため、std::vector でシフトにコミットすることは問題外です。リンクされたリスト（二重にリンクされている場合でも）と同じ問題行があり、それを特定のインデックスにトラバースすると、最悪の場合 O (n/2) になり、O (n) に丸められます。
私は、Head、Tail、および Middle ポインターを含む 2 倍のリンク リストを考えていましたが、あまり良くないと感じました。