Java中的排序数组列表

Question

我为无法快速找到答案感到困惑。我本质上是在寻找Java中的一种实现java.util.List接口的数据结构，但该结构按顺序存储其成员。我知道您可以使用法线ArrayList并Collections.sort()在其上使用，但是我遇到的情况是，我偶尔会添加并经常从列表中检索成员，并且我不想每次检索成员时都对其进行排序，以防万一新增加了一个。谁能指出我在JDK甚至第3方库中都存在的这种东西？

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

总结
：我发现所有这些都很有趣，并且学到了很多东西。尤其值得一提的是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）打破合同并实现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一个支持重复项的set实现
• 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]