维护排序的列表实现

list collections java insertion-order

2022-09-03 05:49:01

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

可以按以下方式使用的内容：

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

因此，插入该命令，以便根据someTcmp

（根据@andersoj建议，我正在用另一个请求完成我的问题）

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

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

应该通过。

欢迎所有建议（除了告诉我在无序的完整列表中使用），但是，我更喜欢在或最终使用某些内容，因为目前很难引入新库。Collections.sortjava.*org.apache.*

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

使用链接结构（排序）B树或类似
使用数组和插入（使用二进制搜索）

否 1.有 CPU 缓存未命中 2 号的问题。在数组中移动元素时出现问题。

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

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

更新：

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

答案 1

您可能应该使用树集：

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

例：

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

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

答案 2

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

做 JavaDoc 所说的：PriorityQueue

此类及其迭代器实现集合和迭代器接口的所有可选方法。方法中提供的迭代器不保证以任何特定顺序遍历优先级队列的元素。如果需要有序遍历，请考虑使用。iterator()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(""); }
}

使用番石榴的树多层套装。我用以下代码进行了测试，它似乎做了正确的事情。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 文档对各种操作的时间属性的描述：

实现说明：此实现为排队和取消排队方法（，和）;和方法的线性时间;和检索方法的常量时间（、和）。offerpollremove()addremove(Object)contains(Object)peekelementsize

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

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

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

没有一个实现本身来维持排序，但你可能正在寻找的是SortedSet的实现。树集是最常见的。另一个实现，a用于更具体的用途。请注意，a 提供了排序，但不允许重复条目，就像 .ListConcurrentSkipListSetSortedSetList

裁判：

博客文章 优先级队列迭代器未排序
关于PQ有序迭代器的SO问题