题

是否有现有的 List Java 中的实现，根据提供的内容维护顺序 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.* 因为目前很难引入新的库。

笔记：（更新4） 我意识到这种列表的实现性能不足。有两种一般方法：

  1. 使用链接结构（某种）B 树或类似结构
  2. 使用数组和插入（使用二分搜索）

没有 1。CPU高速缓存的问题缺失2号。移动数组中的元素时出现问题。

更新2： TreeSet 不起作用，因为它使用提供的比较器（MyComparator) 检查是否相等，并据此假设元素相等并排除它们。我需要该比较器仅用于排序，而不是“唯一性”过滤（因为元素的自然排序不相等）

更新3： PriorityQueue 不作为 List （根据我的需要）因为无法按照“排序”的顺序遍历它，所以要按排序顺序获取元素，您必须将它们从集合中删除。

更新：

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

有帮助吗？

解决方案

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

  • 执行 JavaDoc 的操作 PriorityQueue 说：

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

    我怀疑这将根据您的要求产生最佳性能。如果这是不可接受的，您需要更好地解释您想要实现的目标。

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

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

    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)) 入队和出队方法的时间（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. 。A TreeSet 是最常见的。另一个实现是 ConcurrentSkipListSet 用于更具体的用途。请注意，一个 SortedSet 提供排序，但不允许重复条目，就像 List.

参考文献：

其他提示

你可能应该使用 树集:

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

例子：

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

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

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

如果您无法控制比较器，或者您将其用于其他用途，则插入此解决方案将不适合您。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top