によって要素にアクセスすることができますセットI基本的に必要だけSetのように動作しますが、だけでなく、get(index)方法により、後でそれらを得る私をみましょうと順番を挿入保持するデータ構造。順序を挿入し維持し、そのインデックス
これを達成するのに最適なデータ構造は何ですか？私は、必要に応じて、それを実装することに問題はありません。悪いケースでは、ArrayListとHashSetの両方を使うことができますが、タスクまで特殊なデータ構造があるかどうかは疑問です。
パフォーマンスが最も重要です（それ以外の場合は、通常のリストでO(n)の検索を行うことができます）。私は空間的な複雑さを心配していません。
これは何か？ を編集：Jiddo氏によれば、この構造では要素を効率的に削除できません。 ArrayList + Setは、効率的な削除が必要ない場合は簡単です。したがって、この構造は実際にはあまり効果がありません。
import java.util.*;
public class ArraySet<T> {
private final Map<Integer, T> indexToElem;
private final Map<T, Integer> elemToIndex;
public ArraySet() {
indexToElem = new HashMap<Integer, T>();
elemToIndex = new HashMap<T, Integer>();
}
public T get(int index) {
if (index < 0 || index >= size())
throw new IndexOutOfBoundsException();
return indexToElem.get(index);
}
public void add(T elem) {
if (!contains(elem)) {
int index = indexToElem.size();
indexToElem.put(index, elem);
elemToIndex.put(elem, index);
}
}
// Doesn't work; see comment.
/*public void remove(T elem) {
int index = elemToIndex.get(elem);
indexToElem.remove(index);
elemToIndex.remove(elem);
}*/
public boolean contains(T elem) {
return elemToIndex.containsKey(elem);
}
public int size() {
return indexToElem.size();
}
}
ニース。しかし、それはセット+アーライルのミックスよりも優れていますか？ –
ArrayListから効率的に削除する方法がわかりません。 –
ああ、その細部については忘れてしまった。 –
約OrderedDictionary？
キーまたはインデックスでアクセス可能なキーと値のペアの集合を表します。
http://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary.aspx
Ahhh。私はそれを知らなかった。それはアルゴリズムの汎用名ですか？ –
@devouredelysium私がリンクしている特定のものは、C＃コレクション型です。 – asawyer
私は知っています。しかし、私は、アルゴリズムとデータ構造の大学院コースのために使用されているアルゴリズムの名前を知るための既存の実装を見つけることについて心配しています。 –
既存のコードを使用することに開いていますか？ Apache Commonsには、すべての要件に適合すると思われるListOrderedSetクラスがあります。最悪の場合、C＃でソースコードを調べて実装することができます。
nongeneric !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!しかし、ありがとう、ちょうど私が探しているようです。私はその源についても見ていきます。 –
* *は*オーダー*がありません。あなたはこれを意識しているかもしれないし、意識していないかもしれないが、強調する価値はあると思う。 –
索引を項目にマップするディクショナリと項目のハッシュマップの2つのデータ構造はどうですか。 – harold
このデータ構造はC＃またはJavaで必要ですか？ –