列出维护排序的实现

Java中是否存在基于提供的Comparator维护订单的现有List实现？

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

 Comparator cmp = new MyComparator(); List l = new OrderedList(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树或类似
2. 使用数组和插入（使用二进制搜索）

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

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

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

更新：

类似的问题：
一个很好的Java排序列表
Java中的排序数组列表

Answer 1

对新要求的回应。 我看到两个潜力：

• 执行PriorityQueue的JavaDoc所说的内容：

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

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

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

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

   class PqIter implements Iterator { final PriorityQueue pq; public PqIter(PriorityQueue  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(""); } } 

• 使用Guava的TreeMultiSet 。 我用Integer测试了下面的代码，它似乎做了正确的事情。

   import com.google.common.collect.TreeMultiset; public class TreeMultiSetTest { public static void main(String[] args) { TreeMultiset 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 cmp = new MyComparator(); PriorityQueue pq = new PriorityQueue(cmp); pq.add(someT); 

请注意API文档中有关各种操作的时间属性的内容：

实现说明：此实现为enqueing和dequeing方法提供O（log（n））时间（ offer ， poll ， remove()和add ）; remove(Object)和contains(Object)方法的线性时间; 和检索方法的持续时间（ peek ， element和size ）。

您还应该知道PriorityQueue生成的迭代器的行为与预期的不同：

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

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

没有List实现本身维护排序，但您可能正在寻找的是SortedSet实现。 TreeSet是最常见的。 另一个实现， ConcurrentSkipListSet用于更具体的用途。 请注意， SortedSet提供排序，但不允许重复输入， List 。

参考文献：

• 博客文章PriorityQueue迭代器未订购
• 关于PQ订购迭代器的问题

Answer 2

您可能应该使用TreeSet ：

元素按照其自然顺序排序，或者在创建时创建时提供的比较器，具体取决于使用的构造函数。

例：

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

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

Answer 3

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

如果您无法控制比较器，或者您正在使用它而不是插入此解决方案，则不适合您。