小编典典

为什么Java中没有SortedList?

java

在Java中,有SortedSetSortedMap接口。两者都属于Java的标准Collections框架,并提供了一种访问元素的分类方法。

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

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


阅读 1193

收藏
2020-02-28

共1个答案

小编典典

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

我将按照自己的见解按实用性的顺序进行排序:

1.Consider using Set or Bag collections instead

注意:我将此选项放在顶部,因为这通常是你通常要执行的操作。

排序集会在插入时自动对集合进行排序,这意味着在你将元素添加到集合时会进行排序。这也意味着你无需手动对其进行排序。

此外,如果你确定不必担心(或拥有)重复的元素,则可以使用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>

或者,你可以使用Multisets(也称为Bags),它是Set允许重复元素的,而是具有它们的第三方实现。最值得注意的是从番石榴库有一个TreeMultiset,一个可行的很像TreeSet。

2. Sort your list with 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"

Using comparators

一个明显的好处是你可以Comparator在该sort方法中使用。Java还为提供了一些实现,Comparator例如,Collator对于对语言环境敏感的排序字符串很有用。这是一个例子:

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

Collections.sort(strings, usCollator);

在并发环境中排序

请注意,尽管sort在并发环境中使用该方法并不友好,因为将操作集合实例,因此你应考虑使用不可变的集合。这是GuavaOrdering课堂上提供的东西,并且很简单:

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. 为什么要重新发明轮子?如上第一点所指出的,你应该使用TreeSetMultisets

但是,如果你想作为练习来做,这里是一个入门的代码示例,它使用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();
    }

}

请注意,如果你没有重写所需的方法,则from的默认实现AbstractList将抛出UnsupportedOperationException

2020-02-28