Java中的排序数组列表

Question

我很困惑,我找不到快速的答案.我基本上在Java中寻找一个实现java.util.List接口的数据结构,但它以排序顺序存储其成员.我知道你可以使用普通ArrayList并使用Collections.sort()它,但我有一个场景,我偶尔会添加并经常从我的列表中检索成员,我不希望每次检索成员时都要对它进行排序,以防万一新增了一个.有人能指出我存在于JDK甚至第三方库中的这样的东西吗？

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

答案摘要:我发现所有这些都非常有趣并且学到了很多东西.Aioobe尤其值得一提,因为他坚持不懈地努力实现上述要求(主要是支持重复的有序java.util.List实现).我已经接受了他的答案,因为我提出的问题是最准确的,而且最让我发现的是我正在寻找的内容的影响,即使我问的不完全是我所需要的.

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

该接口的用户可以精确控制列表中每个元素的插入位置.

插入排序列表无法精确控制插入点.然后,你必须考虑如何处理一些方法.就拿add例如:

public boolean add(Object o)

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

你现在处于令人不安的境地:1)打破合同并实现添加的排序版本2)让add一个元素添加到列表的末尾,打破你的排序顺序3)add抛出(作为其可选)抛出一UnsupportedOperationException和实施这增加了在一个有序的物品的另一种方法.

选项3可能是最好的,但我发现它有一个你不能使用的添加方法和另一个不在界面中的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

Answer 1

简约的解决方案

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

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得到的东西(插入元素右侧的所有元素都必须以这种或那种方式移动).

在ClassCastException中插入不可比较的结果.(这也是采用的方法PriorityQueue:依赖于自然排序的优先级队列也不允许插入不可比较的对象(这样做可能会导致ClassCastException).)

重写 List.add

请注意,以排序方式重写List.add(或List.addAll就此而言)插入元素将直接违反接口规范.你可以做的是,重写这个方法来抛出一个UnsupportedOperationException.

来自以下文件List.add:

boolean add(E e)
    将指定的元素追加到此列表的末尾(可选操作).

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

一些测试

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]

Answer 2

使用java.util.PriorityQueue.

Answer 3

看看SortedList

此类实现排序列表.它由比较器构成,可以比较两个对象并相应地对对象进行排序.将对象添加到列表时,它将插入到正确的位置.根据比较器相等的对象将按照它们添加到此列表的顺序位于列表中.仅添加比较器可以比较的对象.

当列表已经包含根据比较器相等的对象时,新对象将紧接在这些其他对象之后插入.

Answer 4

你可以试试Guava的 TreeMultiSet.

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
 System.out.println(ms);

Answer 5

列表通常保留添加项目的顺序。您确实需要一个列表，还是一个排序集（例如TreeSet<E>）适合您？基本上，您需要保留重复项吗？

Answer 6

Aioobe 的方法是要走的路。不过，我想建议对他的解决方案进行以下改进。

class SortedList<T> extends ArrayList<T> {

    public void insertSorted(T value) {
        int insertPoint = insertPoint(value);
        add(insertPoint, value);
    }

    /**
     * @return The insert point for a new value. If the value is found the insert point can be any
     * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.).
     */
    private int insertPoint(T key) {
        int low = 0;
        int high = size() - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = (Comparable<T>) get(mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else {
                return mid; // key found
            }
        }

        return low;  // key not found
    }
}

使用大型列表时，aioobe 的解决方案变得非常缓慢。使用列表已排序的事实允许我们使用二进制搜索找到新值的插入点。

我也会使用组合而不是继承，类似于

SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable