java - 为什么 Java 中没有 SortedList？

Question

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

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

知道为什么它是这样设计的吗？

Answer 1

列表迭代器首先保证您以列表的内部顺序(也就是插入顺序)获取列表的元素。更具体地说，它是按照您插入元素的顺序或您如何操作列表的顺序。排序可以看作是对数据结构的一种操作，有几种方法可以对列表进行排序。

我将按照我个人认为的有用顺序对这些方式进行排序:

1. 考虑使用Set或 Bag取而代之的是 Collection

注意:我把这个选项放在最上面，因为这是你通常想要做的。

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

此外，如果您确定不需要担心(或拥有)重复元素，那么您可以使用 TreeSet<T> 反而。它实现了 SortedSet和 NavigableSet接口(interface)和工作正如您可能从列表中所期望的那样:

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 (又名包) , 那是 Set允许重复元素，相反，它们有第三方实现。最值得注意的是来自 Guava libraries有一个 TreeMultiset ，这很像 TreeSet .

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

如上所述，排序 List s 是对数据结构的操作。因此，对于需要以多种方式排序的“单一事实来源”的情况，手动排序是可行的方法。

您可以使用 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 结束你的 list

尽管 Java 中没有排序列表，但是有一个排序队列，它可能对您同样有效。它是 java.util.PriorityQueue 类(class)。

Nico Haase 在评论中链接到了 related question这也回答了这个问题。

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

关于 PriorityQueue 的警告迭代器
PriorityQueue类实现了 Iterable<E>和 Collection<E>接口(interface)，所以它可以像往常一样迭代。但是，迭代器不能保证按排序顺序返回元素。相反(正如 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类(class)

注意:你不应该这样做。

您可以编写自己的 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 s。