16

Java 中是否有现有的List实现基于提供的顺序来维护Comparator？

可以通过以下方式使用的东西：

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

以便someT插入，以便列表中的顺序根据cmp

（根据@andersoj 的建议，我又提出了一个要求来完成我的问题）

此外，我希望能够在不删除元素的情况下按排序顺序遍历列表，即：

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

应该通过。

欢迎所有建议（除了告诉我Collections.sort在无序的完整列表中使用），不过，我更喜欢其中java.*或最终的东西，org.apache.*因为此时很难引入新的库。

注意：（UPDATE4）我意识到这种列表的实现会性能不足。有两种通用方法：

  1. 使用链接结构（某种）B-tree 或类似的
  2. 使用数组和插入（使用二分查找）

1. CPU 缓存未命中有问题 2. 数组中的元素移位有问题。

UPDATE2： TreeSet不起作用，因为它使用提供的比较器 (MyComparator) 来检查是否相等，并基于它假定元素相等并排除它们。我只需要比较器进行排序，而不是“唯一性”过滤（因为元素的自然排序不相等）

UPDATE3： PriorityQueue不工作List（因为我需要），因为没有办法按“排序”的顺序遍历它，要按排序顺序获取元素，您必须将它们从集合中删除。

更新：

类似的问题：
A good Sorted List for Java
Sorted array list in Java

4

3 回答 3

17

您可能应该使用TreeSet：

元素使用它们的自然顺序或在集合创建时提供的 Comparator 进行排序，具体取决于使用的构造函数。

例子：

Comparator<T> cmp = new MyComparator<T>();
TreeSet<T> t = new TreeSet<T>(cmp);
l.add(someT);

请注意，这是一个set，因此不允许重复条目。这可能适用于您的特定用例，也可能不适用。

于 2012-05-20T17:09:20.443 回答
9

响应新要求。我看到了两个潜力：

  • 按照 JavaDocPriorityQueue所说的去做：

    此类及其迭代器实现了 Collection 和 Iterator 接口的所有可选方法。方法中提供的 Iteratoriterator()不能保证以任何特定顺序遍历优先级队列的元素。如果您需要有序遍历，请考虑使用Arrays.sort(pq.toArray()).

    我怀疑这将根据您的要求产生最佳性能。如果这是不可接受的，您需要更好地解释您要完成的工作。

  • 构建一个在添加新元素时简单地对自身进行排序的列表。这是一个真正的痛苦......如果您使用链接结构，您可以进行有效的插入排序，但局部性很差。如果您使用数组支持的结构，则插入排序会很痛苦，但遍历会更好。如果迭代/遍历不频繁，您可以保留未排序的列表内容并仅按需排序。

  • 考虑使用我建议的PriorityQueue，如果您需要按顺序迭代，请编写一个包装迭代器：

    class PqIter implements Iterator<T>
{
   final PriorityQueue<T> pq;
   public PqIter(PriorityQueue <T> source)
   {
     pq = new PriorityQueue(source); 
   }

   @Override
   public boolean hasNext()
   {
     return pq.peek() != null
   }

   @Override
   public T next()
   { return pq.poll(); }

   @Override
   public void remove()
   { throw new UnsupportedOperationException(""); }
}

  • 使用番石榴的TreeMultiSet. 我测试了以下代码，Integer它似乎做了正确的事情。

    import com.google.common.collect.TreeMultiset;

public class TreeMultiSetTest { 
  public static void main(String[] args) {
    TreeMultiset<Integer> ts = TreeMultiset.create();
    ts.add(1);  ts.add(0); ts.add(2);
    ts.add(-1); ts.add(5); ts.add(2);

    for (Integer i : ts) {
      System.out.println(i);
    } 
  } 
}

下面解决了您在使用SortedSet. 我看到你也想要一个迭代器，所以这行不通。

如果你真正想要的是一个类似有序列表的东西，你可以使用PriorityQueue. 

Comparator<T> cmp = new MyComparator<T>();
PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
pq.add(someT);

请注意 API 文档中关于各种操作的时间属性的说明：

实现说明：此实现为入队和出队方法（ 、和）提供O(log(n))时间；和方法的线性时间；检索方法（、和）的固定时间。offerpollremove()addremove(Object)contains(Object)peekelementsize

您还应该知道，由 生成的迭代器的PriorityQueue行为并不像人们预期的那样：

提供的Iteratorin 方法iterator()不能保证以任何特定顺序遍历优先级队列的元素。如果您需要有序遍历，请考虑使用Arrays.sort(pq.toArray()).

我刚刚注意到 Guava 提供了一个MinMaxPriorityQueue. 此实现是由数组支持的，而不是 JDK 中提供的链接形式PriorityQueue，因此可能具有不同的计时行为。如果您正在做一些对性能敏感的事情，您不妨看看。虽然注释给出的大 O 时间略有不同（线性和对数），但所有这些时间也应该是有界的，这可能很有用。

本身并没有List维护顺序的实现，但您可能正在寻找的是SortedSet. ATreeSet是最常见的。另一个实现， aConcurrentSkipListSet用于更具体的用途。请注意， aSortedSet提供排序，但不允许重复条目， a 也是如此List。

参考：

于 2012-05-20T17:09:58.993 回答
-1

我有一个类似的问题，我正在考虑使用 TreeSet。为了避免排除“相等”元素，我将修改比较器，因此它不会返回 0，而是返回一个介于 (-1,1) 之间的随机数，或者它将始终返回 1。

如果您无法控制比较器，或者您将其用于与插入此解决方案不同的其他用途，则对您不起作用。

于 2014-02-26T08:29:05.200 回答