私は整数の順序付きリストを保持できるデータ構造（または構造体）を探しています。重複はなく、インデックスと値は同じです範囲。高速ランダムアクセス、検索、挿入、削除のための効率的なデータ構造
Iは、重要度の粗いために、効率的に4つの主要な操作を必要とします私はOで1（1）を有するが、2はO（N）であり、アレイを使用して、指定されたインデックス
の値を削除指定されたインデックス
リンクされたリストにはO（1）の挿入と削除がありますが、1と2はO（N）なので、利得は無効になります。
私は1と2をO（1）にするが、3と4をもっと高価な操作に変えるa [index] = valueとb [value] = indexの2つの配列を保持しようとした。
これに適したデータ構造はありますか？
私はred-black treeを使用してキーを値にマッピングします。これにより、1、3、4のO（log（n））が得られます。また、ソート順にキーが保持されます。
2の場合、キーに値をマップするハッシュテーブルを使用して、O（1）のパフォーマンスを得ます。また、赤黒のツリーにキーを追加したり削除したりするときに、ハッシュテーブルを更新したままにするためのO（1）オーバーヘッドが追加されます。
ソートされた配列をバイナリ検索で使用する方法はありますか？
挿入と削除が遅いです。 CやC++を使用している場合は、memcpy（）の呼び出しでデータを単純な整数に最適化することができます。配列の最大サイズを知っている場合は、配列の使用中にメモリの割り当てを避けることもできます。これは、配列を最大サイズに事前に割り当てることができるためです。
"ベスト"アプローチは、保存する必要があるアイテムの数と、検索に比べて挿入/削除が必要な頻度によって異なります。 O（1）を使ってソートされた配列を挿入したり削除したりすることはめったにありませんが、値を頻繁に挿入して削除するとバイナリツリーが配列よりも優れています。十分に小さいnの場合、どのような場合でも配列は木を打つ可能性が最も高い。
ストレージサイズが問題になる場合、アレイはツリーよりも優れています。ツリーはまた、格納するアイテムごとにメモリを割り当てる必要があり、小さな値（整数）を格納するだけでメモリ割り当てのオーバーヘッドが大きくなる可能性があります。
ソートされた配列やツリーにメモリ（de）割り当てを挿入/削除すると、より高速なものをプロファイルすることができます。
どのようにトレ絵がありますか？説明された操作のlog（n）。
私はバランスのとれたバイナリツリーがたくさんあります。ハッシュテーブルや他の構造よりも時間がかかることもありますが、予測がはるかに優れています。それらはすべての操作に対して一般にO(log n)です。 Red-black treeまたはAVL treeを使用することをおすすめします。
ハッシュテーブルはデータを注文しないでしょう。 –
おっと、私は注文された部分を見ませんでした...私はそれを固定しました。 – Zifre
使用している言語はわかりませんが、Javaの場合はLinkedHashMapまたは類似のコレクションを利用できます。これは、リストとマップの利点のすべてを持っている、ほとんどの操作のための一定の時間を提供し、象のメモリフットプリントを持っています。 :)
Javaを使用していないのであれば、LinkedHashMapのアイデアはおそらくあなたの問題のために使用可能なデータ構造に適しています。
LinkedHashMapを使って、どのようにランダムな要素を取得しますか？ – Hengameh
あなたは.NETで作業している場合は、MSのドキュメントによるとhttp://msdn.microsoft.com/en-us/library/f7fta44c.aspx
2つのメモリの使用と挿入/削除の速度によって異なります。 SortedListはSortedDictionaryより少ないメモリしか使用しません。 SortedListがソートされたデータから一度にすべて取り込まれる場合、SortedDictionaryよりも高速です。だから、それは本当にあなたのために最高の状況に依存します。
また、リンクされたリストの引数は実際には有効ではありません。なぜなら、挿入のためのO（1）かもしれませんが、挿入ポイントを見つけるためにリストをトラバースする必要があるからです。
どのようにRBツリーで2を達成するのですか？すべての挿入/削除操作で子どもを数えることができます。これにより、これらの操作が大幅に長くなることはありません。その後、木を下ってi番目の要素を見つけることはlog n時間で可能です。しかし、私はjavaやstlではこのメソッドの実装を見ません。
配列アクセス用のベクトルを使用します。
マップをベクトルへの添字への検索インデックスとして使用します。
あなたはどの言語を使用していますか？ –
本当に問題ではありませんが、C++です – Leonel
問題ありません。すべての言語が同じデータ構造を提供するわけではありません。たとえば、この特定の問題は、C Judy配列またはC＃CPTrieによって非常に効率的に解決できます。 （または、もちろん、Aymanのようなバランスの取れたバイナリツリーがあります。） – Qwertie