为什么Java中没有SortedList ?

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

我将按照我个人认为的有用性来排序:

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)，这是一个允许重复元素的集合，而不是它们的第三方实现。Guava库中最值得注意的是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"

使用比较器

一个明显的好处是可以在sort方法中使用Comparator。Java还为Comparator提供了一些实现，例如Collator，它对于locale敏感的字符串排序非常有用。这里有一个例子:

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

Collections.sort(strings, usCollator);

并发环境中的排序

但是请注意，在并发环境中使用sort方法并不友好，因为集合实例将被操作，您应该考虑使用不可变的集合。这是Guava在ordered类中提供的东西，是一个简单的一行程序:

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在评论中指出的那样)，您需要轮询()队列直到空为止。

注意，你可以通过接受任何集合的构造函数将列表转换为优先级队列:

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方法应该确保元素驻留在用户指定的索引中。为什么要重新发明轮子?你应该使用树集或多集，而不是在上面的第一点指出。

但是，如果你想把它作为练习，这里有一个代码示例来开始，它使用了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。

2012-01-04 10:41:01

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

2012-01-04 10:44:59

另一点是插入操作的时间复杂度。对于列表插入，期望复杂度为O(1)。但是，排序的列表并不能保证这一点。

最重要的一点是，列表对它们的元素没有任何假设。例如，您可以列出不实现等于或比较的东西。

2012-01-04 13:50:44

https://github.com/geniot/indexed-tree-map

考虑使用索引树映射。它是一个增强的JDK的TreeSet，它提供了通过索引访问元素的功能，并且无需迭代或隐藏的底层列表来备份树，就可以找到元素的索引。该算法基于每次有变化时更新已更改节点的权重。

2014-01-27 14:32:07