ランダムアクセスエレメントを削除したキューのようなデータ構造

Question

キューのようなデータ構造があり、任意のポイントでのエレメントの削除もサポートしていますか？エンキューおよびデキューは最も頻繁に発生しますが、中途半端な要素の削除はスピードの点で似ている必要があります。なぜなら、それが最も一般的な操作である期間があるからです。絶対速度よりもパフォーマンスの一貫性が重要です。時間は記憶より重要です。キューの長さは、絶対最大負荷で1,000要素以下では小さくなります。明白でない場合は、明示的に述べます：ランダム挿入は不要です。

これは私の実装言語であるため、C++にタグ付けされていますが、私はSTLまたはBoostを使用していません。 （C言語のソリューションをC++クラスに変換します）

編集：私が望むのは、キューインターフェイス（または辞書インターフェイスも持つキュー）を持つ種類の辞書です。私はこのようなことを行うことができるように：

Container.enqueue(myObjPtr1); 
MyObj *myObjPtr2 = Container.dequeue(); 
Container.remove(myObjPtr3); 

Answer 1

私は（あなたがプライオリティキューをしたくないと仮定）、ダブルリンクリストが正確に何をしたいと思い：

1. 速く簡単との両方に要素を追加する
2. 簡単かつ要素の迅速な除去を終了しますに包まれた（

どこからでもあなたはstd::listコンテナを使用することができますが、（あなたのケースでは）あなたが唯一の要素へのポインタ（または参照）を持っている場合は、リストの途中から要素 を除去することは困難ですSTLのリスト）、しかし イテレータはありません。イテレータを使用している（例えばそれらを格納している）場合はオプションではありません - ダブルリンクリスト（要素カウンタでさえ）を実装するのはかなり簡単です。あなたがあなた自身のリストを実装する場合 - あなたは直接要素（それらのそれぞれは、その隣人の両方へのポインタが含まれています）へのポインタを操作することができます。あなたはブーストやSTLを使用したくない場合は、これはおそらく最良の選択肢（と最も簡単な）で、あなたは（あなたも物事をスピードアップするために、リストの要素のための独自のブロックアロケータを書くことができます）、すべての制御を持っています。

Answer 2

1つのオプションは、（ログOとともに、各要素へのランダムアクセスを（n個のログを記録）順序統計ツリー、Oをサポート増強ツリー構造を使用することですn）任意の点での挿入と削除。内部的には、注文統計ツリーは、それに関連付けられた余分な情報をバランスよくバイナリ検索するトレイルとして実装されています。その結果、ルックアップは標準ダイナミック配列よりも遅くなりますが、挿入がはるかに高速です。

希望すると便利です。

Answer 3

リンクされたリストやハッシュテーブルの組み合わせを使用することができます。 javaでは、それはLinkedHashSetと呼ばれます。

アイデアは、要素のリンクリストを有する、単純であり、また(key,nodes)のhash mapを維持し、nodeは、リンクされたリスト内の関連ノードへのポインタであり、そしてkeyこのノードを表す鍵です。基本的な実装がsetであり、いくつかの余分な作業がdupesを許可し、このデータ構造を作るために必要とされるであろうことを

注意。

このデータ構造では、O(1)ヘッド/テールアクセスと、リスト内の任意の要素へのアクセスO(1)の両方にアクセスできます。[平均してすべて平均化された]