2

该NavigableSet接口提供了许多普通方法Set没有的有用方法（特别是我正在考虑诸如headSet和之类的方法tailSet）。但是，作为 a Set，它不支持重复元素。另外，作为 a SortedSet，排序必须与接口的约定一致，equals避免hashCode违反Set接口的约定。

当根据自然排序或比较器可能存在重复元素或多个元素“相等”但根据方法不“相等”时，是否有任何好的替代数据结构equals？作为一个激励示例，请考虑以下代码，该代码说明了 aNavigableSet不合适的原因：

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());
  }
}

请注意，元素a只添加一次（当然，因为这是 a Set）。另外，请注意b没有添加，因为已经有一个元素的比较返回 0。

我觉得这可能是一件相当普遍的事情，所以我希望找到一个现有的实现，而不是自己动手。是否有适合我的用途的良好、广泛使用的数据结构？

我要补充一点，在写这个问题时我确实遇到了Biscotti Project，但是 a）我不相信它可以解决比较/等于问题，并且 b）常见问题解答明确表示使用起来并不安全。

4

1 回答 1

0

让我重新表述你的问题，以确保我能很好地理解它。需要headSet并且tailSet意味着必须对集合进行排序。这与根据compareTo.

冲突来自对此类集合的有效使用。使用O(log n)compareTo中的方法将成员添加到已排序的集合中- 一种二进制搜索然后添加。是使用which can't two same members 根据 实现的。TreeSetTreeMapcompareTo

您正在寻找的东西不会有效。

  • 您可以尝试使用简单的ArrayList排序方法Collections.sort，然后使用sublist方法。问题在于它根本不处理重复项。
  • 您也可以使用LinkedHashSetwhich 处理重复项（根据并且equals()它对免疫compareTo()），但它没有排序。当然，您可以通过在构造函数中传递其实例LinkedHashSet来将实例转换为 。SortedSet
于 2012-09-18T23:53:10.447 回答