为什么Java中没有SortedList？

Question

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

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

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

原文由 Jijoy 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 库 的 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"

使用比较器

一个明显的好处是您可以在 sort 方法中使用 Comparator —。 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();
    }

}

请注意，如果您没有覆盖所需的方法，那么来自 AbstractList 的默认实现将抛出 UnsupportedOperationException s。

原文由 Spoike 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

因为 List 的概念与自动排序集合的概念是不兼容的。 List 的要点是在调用 list.add(7, elem) 之后，调用 list.get(7) 将返回 elem 。使用自动排序列表，元素可以在任意位置结束。

原文由 Michael Borgwardt 发布，翻译遵循 CC BY-SA 4.0 许可协议