Java中的排序数组列表

Question

我很困惑，我找不到一个快速的答案。我本质上是在寻找 Java 中的数据结构，它实现了 java.util.List 接口，但它按排序顺序存储其成员。我知道您可以使用普通的 ArrayList 并在其上使用 Collections.sort() ，但我有一个场景，我偶尔会添加并经常从我的列表中检索成员，我不想每次我检索成员时都必须对其进行排序，以防添加新成员。任何人都可以指出 JDK 甚至 3rd 方库中存在的东西吗？

编辑：数据结构需要保留重复项。

ANSWER’s SUMMARY ：我发现所有这些都非常有趣并且学到了很多东西。 Aioobe 尤其值得一提，因为他坚持不懈地努力实现我的上述要求（主要是支持重复项的排序 java.util.List 实现）。我接受了他的回答，因为他的回答对于我所问的内容是最准确的，并且对我正在寻找的内容的含义最发人深省，即使我所问的并不是我所需要的。

我要求的问题在于 List 接口本身和接口中可选方法的概念。引用 javadoc：

该界面的用户可以精确控制每个元素在列表中的插入位置。

插入到排序列表中并不能精确控制插入点。然后，您必须考虑如何处理某些方法。以 add 为例：

公共布尔添加（对象 o）

  Appends the specified element to the end of this list (optional operation).

你现在处于一种不舒服的境地 1) 违反合同并实施 add 的排序版本 2) 让 add 添加一个元素到列表的末尾，打破你的排序顺序 3) 离开 add 通过抛出 UnsupportedOperationException 并实现另一种按排序顺序添加项目的方法来输出（作为其可选）。

选项 3 可能是最好的，但我发现它有一个你不能使用的 add 方法和另一个不在界面中的 sortedAdd 方法是令人讨厌的。

其他相关解决方案（排名不分先后）：

• java.util.PriorityQueue 可能比我要求的更接近我的需要。在我的案例中，队列并不是对象集合的最精确定义，但在功能上它可以完成我需要它做的一切。
• net.sourceforge.nite.util.SortedList 。但是，此实现通过在 add(Object obj) 方法中实现排序打破了 List 接口的契约，并且奇怪地对 add(int index, Object obj) 有一个无效的方法。一般共识建议 throw new UnsupportedOperationException() 在这种情况下可能是更好的选择。
• Guava 的 TreeMultiSet 支持重复的集合实现
• ca.odell.glazedlists.SortedList 此类在其 javadoc 中附带警告： Warning: This class breaks the contract required by List

原文由 Chris Knight 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

简约解决方案

这是一个快速而肮脏的解决方案。

 class SortedArrayList<T> extends ArrayList<T> {
    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        int i = Collections.binarySearch((List<Comparable<T>>) this, value);
        add(i < 0 ? -i - 1 : i, value);
    }
}

Note that despite the binarySearch , insertSorted will run in linear time since add(index, value) runs in linear time for an ArrayList .

插入不可比较的内容会导致 ClassCastException。 （这也是 PriorityQueue 采用的方法： 依赖自然排序的优先级队列也不允许插入不可比较的对象（这样做可能会导致 ClassCastException）。 ）

更完整的实现将像 PriorityQueue 一样，还包括一个允许用户传入 Comparator 的构造函数。

演示

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

….印刷：

 [ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]

覆盖 List.add

请注意，覆盖 List.add （或 List.addAll ）以按排序方式插入元素将 直接违反接口规范。

来自 List.add 的文档：

boolean add(E e)

将指定的元素附加到此列表的末尾（可选操作）。

保持排序不变性

除非这是一些一次性代码，否则您可能希望保证所有元素都保持排序。 This would include throwing UnsupportedOperationException for methods like add , addAll and set , as well as listIterator to返回一个 ListIterator 其 set 方法抛出。

原文由 aioobe 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

使用 java.util.PriorityQueue 。

原文由 Gadolin 发布，翻译遵循 CC BY-SA 2.5 许可协议