为什么Java中没有SortedList?

问题:

在Java中有SortedSetSortedMap接口。它们均属于Java标准的集合框架,并提供了一种排序方式来访问元素。
但是,据我所知,Java中没有SortedList。您可以使用java.util.Collections.sort()对列表进行排序。
任何想法为什么这样设计?

回答:

列表迭代器首先确保您以列表的内部顺序(也称为。insertion order)获取列表的元素。更具体地说,它是按照您插入元素的顺序或您如何操纵列表。排序可以看作是对数据结构的操纵,并且有几种方法可以对列表进行排序。
我会按照我个人的看法来排列usefulness的顺序:

考虑使用

 注意:我把这个选项放在顶部,因为这是你通常想做的。
一个排序的集合在插入时自动对集合进行排序,这意味着在将元素添加到集合中时进行排序。这也意味着您不需要手动排序。
此外,如果您确定不需要担心(或拥有)重复的元素,则可以使用TreeSet<T>。它实现了SortedSetNavigableSet接口,并且可以像您期望的列表一样工作:

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>
或者,您可以使用,这是允许重复元素的Set,而是第三方实现它们。最显着的是Guava libraries,有一个TreeMultiset,这很像TreeSet

2.用你的列表排序

如上所述,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,这对于区域设置敏感的排序字符串很有用。这里有一个例子:

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中没有排序列表,但是排序的队列可能也适用于您。这是java.util.PriorityQueue类。
Nico Haase在评论中链接到related question也回答了这一点。
在排序集合你最有可能不想操纵内部数据结构中,为什么PriorityQueue不实现List接口(因为这将使您直接访问它的元素)。

警告上

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"

写你自己的

 注意:你不应该这样做。
您可以编写自己的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

 
 
Code问答: http://codewenda.com/topics/python/
Stackoverflow: Why is there no SortedList in Java?

*转载请注明本文链接以及stackoverflow的英文链接

发表评论

电子邮件地址不会被公开。 必填项已用*标注

− 6 = 2