Java中的排序数组列表 [英] Sorted array list in Java

问题描述

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

I'm baffled that I can't find a quick answer to this. I'm essentially looking for a datastructure in Java which implements the java.util.List interface, but which stores its members in a sorted order. I know that you can use a normal ArrayList and use Collections.sort() on it, but I have a scenario where I am occasionally adding and often retrieving members from my list and I don't want to have to sort it every time I retrieve a member in case a new one has been added. Can anyone point me towards such a thing which exists in the JDK or even 3rd party libraries?

编辑:数据结构需要保留重复项.

EDIT: The datastructure will need to preserve duplicates.

ANSWER's Summary:我发现所有这些都非常有趣并且学到了很多东西.特别值得一提的是，Aioobe 坚持不懈地努力实现我的上述要求(主要是支持重复的排序 java.util.List 实现).我接受了他的回答，认为他对我所问的问题最准确，并且即使我问的不是我所需要的，也最能激发我所寻找的含义.

ANSWER's SUMMARY: I found all of this very interesting and learned a lot. Aioobe in particular deserves mention for his perseverance in trying to achieve my requirements above (mainly a sorted java.util.List implementation which supports duplicates). I have accepted his answer as the most accurate for what I asked and most thought provoking on the implications of what I was looking for even if what I asked wasn't exactly what I needed.

我所要求的问题在于 List 接口本身以及接口中可选方法的概念.引用 javadoc:

The problem with what I asked for lies in the List interface itself and the concept of optional methods in an interface. To quote the javadoc:

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

The user of this interface has precise control over where in the list each element is inserted.

插入排序列表无法精确控制插入点.然后，您必须考虑如何处理某些方法.以add为例:

Inserting into a sorted list doesn't have precise control over insertion point. Then, you have to think how you will handle some of the methods. Take add for example:

public boolean add(Object o)

public boolean add(Object o)

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

你现在处于两种不舒服的境地1) 打破契约，实现一个排序版本的add2) 让 add 在列表的末尾添加一个元素，打破你的排序顺序3) 通过抛出 UnsupportedOperationException 并实现另一种按排序顺序添加项目的方法，将 add 排除在外(作为其可选).

You are now left in the uncomfortable situation of either 1) Breaking the contract and implementing a sorted version of add 2) Letting add add an element to the end of the list, breaking your sorted order 3) Leaving add out (as its optional) by throwing an UnsupportedOperationException and implementing another method which adds items in a sorted order.

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

Option 3 is probably the best, but I find it unsavory having an add method you can't use and another sortedAdd method which isn't in the interface.

其他相关解决方案(排名不分先后):

Other related solutions (in no particular order):

• java.util.PriorityQueue可能最接近我所需要的而不是我所要求的.在我的例子中，队列不是对象集合的最精确定义，但在功能上它可以完成我需要的一切.
• net.sourceforge.nite.util.SortedList.然而，这个实现打破了List接口的约定，在add(Object obj)方法中实现了排序，奇怪的是对于add(int index, Object obj).普遍共识表明 throw new UnsupportedOperationException() 在这种情况下可能是更好的选择.
• Guava 的 TreeMultiSet支持重复的集合实现
• ca.odell.glazedlists.SortedList 此类在其 javadoc 中带有警告:警告:此类违反 List 要求的约定

• java.util.PriorityQueue which is probably closest to what I needed than what I asked for. A queue isn't the most precise definition of a collection of objects in my case, but functionally it does everything I need it to.
• net.sourceforge.nite.util.SortedList. However, this implementation breaks the contract of the List interface by implementing the sorting in the add(Object obj) method and bizarrely has a no effect method for add(int index, Object obj). General consensus suggests throw new UnsupportedOperationException() might be a better choice in this scenario.
• Guava's TreeMultiSet A set implementation which supports duplicates
• ca.odell.glazedlists.SortedList This class comes with the caveat in its javadoc: Warning: This class breaks the contract required by List

推荐答案

Minimalistic Solution

这是一个最小"的解决方案.

Minimalistic Solution

Here is a "minimal" solution.

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
            Collections.swap(this, i, i-1);
    }
}

插入以线性时间运行，但这将是使用 ArrayList 无论如何都会得到的结果(插入元素右侧的所有元素都必须以一种或另一种方式移动).

The insert runs in linear time, but that would be what you would get using an ArrayList anyway (all elements to the right of the inserted element would have to be shifted one way or another).

插入不可比较的内容会导致 ClassCastException.(这是PriorityQueue:依赖于自然排序的优先级队列也不允许插入不可比较的对象(这样做可能会导致 ClassCastException).)



Inserting something non-comparable results in a ClassCastException. (This is the approach taken by PriorityQueue as well: A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).)

注意覆盖List.add(或 List.addAll 以排序方式插入元素将直接违反接口规范.你可以做的是覆盖这个方法来抛出一个UnsupportedOperationException.

Note that overriding List.add (or List.addAll for that matter) to insert elements in a sorted fashion would be a direct violation of the interface specification. What you could do, is to override this method to throw an UnsupportedOperationException.

来自 List.add 的文档:

布尔加法(E e)
   将指定的元素附加到此列表的末尾(可选操作).

同样的推理适用于 add 的两个版本，addAll 和 set 的两个版本.(根据列表界面，都是可选操作.)

Same reasoning applies for both versions of add, both versions of addAll and set. (All of which are optional operations according to the list interface.)

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]

这篇关于Java中的排序数组列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！