java - 为什么Java中没有SortedList？

Question

在Java中，有SortedSet和SortedMap接口。两者都属于Java Collections framework并提供访问元素的排序方式。

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

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

Answer 1

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

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

1.考虑改用Set或Bag集合

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

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

此外，如果您确定不必担心（或拥有）重复的元素，则可以使用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，并且存在第三方的实现。最明显的是 Guava libraries中有一个 TreeMultiset，其作用与 TreeSet非常相似。

2.用 Collections.sort()对列表进行排序

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

您可以使用 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"

使用比较器

一个明显的好处是您可以在 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在评论中链接到一个 related question，它也回答了这个问题。

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

PriorityQueue迭代器上的警告

PriorityQueue类实现了 Iterable<E>和 Collection<E>接口，因此可以照常进行迭代。但是，不能保证迭代器按排序顺序返回元素。相反，（如Alderath在注释中指出的那样），您需要 poll()队列直到为空。

请注意，您可以通过 constructor that takes any collection将列表转换为优先级队列：

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类，该类在每次添加新元素时进行排序。取决于您的实现，这可能会使计算工作变得繁重，并且毫无意义，除非您希望将其作为练习，这有两个主要原因：


因为 List<E>方法应确保元素将驻留在用户指定的索引中，所以它破坏了 add接口具有的约定。
为什么要重新发明轮子？如上第一点所指出的，您应该使用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();
    }

}

请注意，如果您尚未覆盖所需的方法，则 AbstractList的默认实现将抛出 UnsupportedOperationException。