为什么Java中没有SortedList？

Question

在Java中，有SortedSet和SortedMap接口。两者都属于Java的标准Collections框架，并提供了一种访问元素的分类方法。

但是，据我了解SortedList，Java没有。你可以java.util.Collections.sort()用来对列表进行排序。

知道为什么要这样设计吗？

Answer 1

列表迭代器首先确保你以列表的内部顺序（也称为插入顺序）获取列表的元素。更具体地说，它是按照插入元素的顺序或操作列表的方式进行的。排序可以看作是对数据结构的一种操作，有几种方法可以对列表进行排序。

我将按照自己的见解按实用性的顺序进行排序：

1.Consider using Set or Bag collections instead

注意：我将此选项放在顶部，因为这通常是你通常要执行的操作。

排序集会在插入时自动对集合进行排序，这意味着在你将元素添加到集合时会进行排序。这也意味着你无需手动对其进行排序。

此外，如果你确定不必担心（或拥有）重复的元素，则可以使用TreeSet<T>代替。它实现SortedSet和NavigableSet接口并按你可能期望的那样工作：

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

如果你不希望自然排序，则可以使用带有的构造函数参数Comparator<T>。

或者，你可以使用Multisets（也称为Bags），它是Set允许重复元素的，而是具有它们的第三方实现。最值得注意的是从番石榴库有一个TreeMultiset，一个可行的很像TreeSet。

2. Sort your list with Collections.sort()

如上所述，对Lists进行排序是对数据结构的一种操作。因此，对于需要以多种方式进行分类的“一个真理源”的情况，则必须手动进行分类。

你可以使用该java.util.Collections.sort()方法对列表进行排序。这是有关如何的代码示例：

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Using comparators

一个明显的好处是你可以Comparator在该sort方法中使用。Java还为提供了一些实现，Comparator例如，Collator对于对语言环境敏感的排序字符串很有用。这是一个例子：

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

在并发环境中排序

请注意，尽管sort在并发环境中使用该方法并不友好，因为将操作集合实例，因此你应考虑使用不可变的集合。这是Guava在Ordering课堂上提供的东西，并且很简单：

List<string> sorted = Ordering.natural().sortedCopy(strings);

3.用 java.util.PriorityQueue

尽管Java中没有排序列表，但是有一个排序队列可能对你同样有效。这是java.util.PriorityQueue上课。

Nico Haase在评论中链接到一个相关问题，该问题也得到了回答。

在排序的集合中，你很可能不想操纵内部数据结构，这就是为什么PriorityQueue不实现List接口的原因（因为这将使你直接访问其元素）。

警告PriorityQueue迭代器

在PriorityQueue类实现Iterable<E>和Collection<E>接口，因此它可以重复如常。但是，不能保证迭代器以已排序的顺序返回元素。相反（如Alderath在评论中指出的那样），你需要poll()排队直到空着。

请注意，你可以通过采用任何集合的构造函数将列表转换为优先级队列：

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4.编写自己的SortedList课程

注意：你不必这样做。

你可以编写自己的List类，该类在每次添加新元素时进行排序。取决于你的实现，这可能会增加相当大的计算量，并且毫无意义，除非你希望将其作为练习，这有两个主要原因：

1. 它打破了List<E>接口的约定，因为add方法应确保元素将驻留在用户指定的索引中。
2. 为什么要重新发明轮子？如上第一点所指出的，你应该使用TreeSet或Multisets。

但是，如果你想作为练习来做，这里是一个入门的代码示例，它使用AbstractList抽象类：

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

请注意，如果你没有重写所需的方法，则from的默认实现AbstractList将抛出UnsupportedOperationException。