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

问题描述

我很困惑，我找不到一个快速的答案。我基本上是在Java中寻找一个实现 java.util.List 接口的数据结构，但是它的成员按排序顺序存储。我知道你可以使用一个正常的 ArrayList 并使用 Collections.sort（），但我有一个场景我偶尔会添加并经常从我的列表中检索成员，并且我不想每次检索一个成员时都要对它进行排序，以防新添加一个成员。任何人都可以指出JDK甚至第三方图书馆中存在的这样的事情？

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

答案总结：我发现这一切都非常有趣，学到了很多。 Aioobe特别值得一提，因为他坚持不懈地努力实现我上面的要求（主要是一个支持重复的排序的java.util.List实现）。我已经接受了他的答案，对于我所问的最准确的答案，也是最令我激动的问题，即使我问的不完全是我所需要的，我正在寻找的内容。

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

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

插入排序列表对插入点没有精确控制。那么你必须考虑如何处理一些方法。以添加为例：

public boolean add（Object o）

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

您现在处于$ b $的不舒服情况b 1）打破合同并执行add
的排序版本2）让添加添加一个元素到列表的末尾，打破你的排序顺序
3）通过抛出一个 UnsupportedOperationException ，将添加（作为其可选项），并实现另一种添加项目的方法一个排序的顺序。

选项3可能是最好的，但是我发现它有一个不可用的添加方法，另一个排序方法不在界面。

其他相关解决方案（无特别顺序）：

• <可能最接近的href =http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html =noreferrer> java.util.PriorityQueue 我需要什么比我要求的在我的情况下，队列不是对象集合的最精确定义，但在功能上它完成了我需要的一切。


• net.sourceforge.nite.util.SortedList 。但是，该实现通过在 add（Object obj）方法中实现排序来破坏List接口的合同，并且奇怪地对 add（int index，Object obj）一般共识表明，在这种情况下，抛出新的UnsupportedOperationException（）可能是一个更好的选择。


• Guava's TreeMultiSet 支持重复的一个集合实现


• ca.odell.glazedlists。 SortedList 此类附带了javadoc中的警告：警告：此类打破了列表

解决方案

极简解决方案

这是一个最小的解决方案。

  class SortedArrayList< T>扩展ArrayList< T> {
 
 @SuppressWarnings（unchecked）
 public void insertSorted（T value）{
 add（value）; 
可比较< T> cmp =（可比较T）值; （int i = size（） -  1; i> 0&& cmp.compareTo（get（i-1））< 0; i--）
 Collections.swap这个，我，i-1）; 
} 
} 
  

插入运行在线性时间，但这将是你会得到使用ArrayList的方式（插入元素右侧的所有元素都必须以某种方式移动）。

插入一些不可比较的结果在ClassCastException中。 （这是 采取的方法PriorityQueue 以下：依靠自然排序的优先级队列也不允许插入不可比较的对象（这样做可能会导致ClassCastException）。）

覆盖 List.add

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

从 List.add 的文档：

boolean添加（E e）

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

相同的推理适用于两个版本的 add ，两个版本的 addAll 和设置。 （所有这些都是根据列表界面的可选操作。）

一些测试

  SortedArrayList< String> test = new SortedArrayList< String>（）; 
 
 test.insertSorted（ddd）; System.out.println（测试）; 
 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] 
  

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: 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.

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.

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)

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

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.

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 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

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);
    }
}

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).

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).)

Overriding List.add

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.

From the docs of List.add:

boolean add(E e)
    Appends the specified element to the end of this list (optional operation).

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.)

Some tests

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);

....prints:

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

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