2

NavigableSetインターフェイスは、法線Setにはない多くの便利なメソッドを提供します (具体的には、たとえば や のようなメソッドについて考えていheadSetますtailSet)。ただし、 であるためSet、重複する要素はサポートされません。また、 であるためSortedSet、順序付けは一貫性がequalsありhashCode、インターフェースの規約に違反しないようにする必要がありSetます。

自然な順序付けまたは Comparator に従って「等しい」がメソッドによれば「等しい」ではない、重複する要素または複数の要素が存在する可能性がある場合に適した代替データ構造はありますequalsか? NavigableSet動機付けとなる例として、aが適切でない理由を示す次のコードを考えてみましょう。

public class Foo implements Comparable<Foo>{
  double x;
  double y;

  @Override
  public int compareTo(Foo o) {
    return Double.compare(x, o.x);  // only x matters for sort order
  }

  public static void main(String...args){
    Foo a = new Foo();
    a.x = 1;
    a.y = 2;

    Foo b = new Foo();
    b.x = 1;
    b.y = 42;

    Foo c = new Foo();
    c.x = 2;
    c.y = 12.34;

    NavigableSet<Foo> set = new TreeSet<Foo>();
    set.add(a);
    set.add(a);
    set.add(b);
    set.add(c);

    System.out.println(set.size());
  }
}

要素は 1 回だけ追加されることに注意してくださいa(もちろん、これは であるためSet)。また、b比較が 0 を返す要素が既に存在するため、 が追加されないことに注意してください。

これはおそらくかなり一般的なことだと感じたので、独自の実装を作成するのではなく、既存の実装を見つけたいと考えました。私の目的に適した、広く使用されているデータ構造はありますか?

この質問を書いているときにBiscotti Projectに出くわしたことを付け加えておきますが、a) それが比較/等号の問題を解決するとは確信していません。

4

1 に答える 1

0

よく理解できるように、あなたの質問を再構成させてください。headSetandの必要性はtailSet、コレクションをソートする必要があることを意味します。これは、 に従って重複メンバーを許可する必要性と矛盾していcompareToます。

競合は、そのようなコレクションの効果的な使用から生じます。ソートされたコレクションへのメンバーの追加は、 O(log n)compareToのメソッドを利用して行われます- 二分探索の一種であり、追加します。は、に従って 2 つの同じメンバーを使用できないように実装されています。TreeSetTreeMapcompareTo

あなたが探しているものは効果的ではありません。

  • 単純なものを使用しArrayListて並べ替えてからCollections.sort、sublistメソッドを使用することもできます。これの問題は、重複をまったく処理しないことです。
  • 重複を処理する which を使用することもできますLinkedHashSet(に従ってequals()および の影響を受けcompareTo()ません) が、ソートされません。もちろん、コンストラクターでインスタンスを渡すことにより、LinkedHashSetインスタンスを に変換できます。SortedSet
于 2012-09-18T23:53:10.447 に答える