java - 维护顺序的列表实现

Question

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 树或类似结构
2. 使用数组和插入(使用二分查找)

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

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

更新3:PriorityQueue 不能像 List 一样工作(因为我需要)，因为没有办法按照它“排序”的顺序遍历它，以获取排序顺序中的元素您必须将它们从集合中移除。

更新:

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

Answer 1

您可能应该使用 TreeSet :

The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

例子:

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

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