为什么Java中没有SortedList？

Question

在Java中有SortedSet和SortedMap接口.两者都属于Java的标准集合框架,并提供了一种访问元素的排序方式.

但是,根据我的理解SortedList,Java中没有.您可以使用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"

如果您不想要自然排序,可以使用带有a的构造函数参数Comparator<T>.

或者,您可以使用Multisets(也称为Bags),Set即允许重复元素,而且还有第三方实现.最值得注意的是,从番石榴图书馆有一个TreeMultiset,它有很多像TreeSet.

2.使用排序列表 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"

使用比较器

一个明显的好处是您可以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"

写自己的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将抛出UnsupportedOperationExceptions.

Answer 2

因为List的概念与自动排序集合的概念不兼容.List的重点是,在调用之后list.add(7, elem),list.get(7)将返回一个调用elem.使用自动排序列表,元素可能最终处于任意位置.

Answer 3

由于所有列表已按照添加项目的顺序(FIFO排序)进行"排序",因此您可以使用另一个订单"求助"它们,包括元素的自然排序java.util.Collections.sort().

编辑:

列表作为数据结构基于有趣的是插入项目的顺序.

集合没有该信息.

如果您想通过添加时间来订购,请使用List.如果您想按其他标准订购,请使用SortedSet.

Answer 4

Set和Map是非线性数据结构.列表是线性数据结构.

树数据结构SortedSet和SortedMap接口实现 TreeSet并TreeMap分别使用使用的Red-Black树实现算法.因此,它确保没有重复的项目(或密钥Map).

• List 已经维护了有序集合和基于索引的数据结构,树不是基于索引的数据结构.
• Tree 根据定义,不能包含重复项.
• 在List我们可以有重复,所以没有TreeList(即没有SortedList).
• List按插入顺序维护元素.因此,如果我们想对列表进行排序,我们必须使用它java.util.Collections.sort().它根据元素的自然顺序将指定列表按升序排序.

Answer 5

JavaFX的 SortedList

虽然花了一段时间,但Java 8确实有一个排序List. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

正如您在javadocs中看到的,它是JavaFX集合的一部分,旨在提供ObservableList的排序视图.

更新:请注意,对于Java 11,JavaFX工具包已移出JDK,现在是一个单独的库.JavaFX 11可作为可下载的SDK或MavenCentral提供.请参阅https://openjfx.io

Answer 6

对于任何新手,截至2015年4月,Android现在在支持库中有一个SortedList类,专门设计用于RecyclerView.这是关于它的博客文章.