为什么在Java中没有SortedList？ [英] Why is there no SortedList in Java?

问题描述

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

但是，根据我的理解，在Java中没有 SortedList 。您可以使用 java.util.Collections.sort（）对列表进行排序。

设计像这样？

解决方案

列表迭代器首先保证你得到列表的元素在列表的内部顺序插入顺序）。更具体地说，它是按照您插入元素的顺序或您如何操作列表。排序可以看作是对数据结构的操作，并且有几种排序列表的方法。

我会按照有用性：

1。考虑使用设置或包集合

注意：我将此选项置于顶部，因为这是您通常想要执行的操作。

在插入时，这意味着它在您向集合中添加元素时进行排序。这也意味着你不需要手动排序它。

此外，如果你确定你不需要担心（或有）重复的元素，那么你可以使用 TreeSet< T> 。它实现 SortedSet 和 NavigableSet 接口和工作，你可能期望从一个列表：

  TreeSet< String> set = new TreeSet< String>（）; 
 set.add（lol）; 
 set.add（cat）; 
 //添加
时自动排序自然顺序b 
（String s：set）{
 System.out.println（s）; 
} 
 //打印出cat和lol
  

你不想要自然排序，你可以使用构造函数参数，它接受 比较器< T> 。

href =https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/Multiset.html =nofollow>多媒体广告（也称为），这是一个设置，允许重复的元素，而是有第三方实现它们。最着名的是 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）; 
} 
 //打印出cat和lol
  

比较器

一个明显的好处是您可以使用 Comparator 。 Java还为 Comparator 提供了一些实现，例如 Collat​​or ，这对于区域设置敏感的排序字符串很有用。这里有一个例子：

  Collat​​or usCollat​​or = Collat​​or.getInstance（Locale.US）; 
 usCollat​​or.setStrength（Collat​​or.PRIMARY）; //忽略套管
 
 Collections.sort（strings，usCollat​​or）; 
  

在并发环境中排序

尽管使用 sort 方法在并发环境中不友好，因为集合实例将被操作，并且您应该考虑使用不可变集合。这是Guava在 订购 类，并且是一个简单的单行：

  List< string> sorted = Ordering.natural（）。sortedCopy（strings）; 
  

3。用 java.util.PriorityQueue包装你的列表

虽然Java中没有排序列表，队列，这可能会工作，以及对你。这是 java.util。 PriorityQueue 类别。

Nico Haase在评论中链接到

在有序集合中，您很可能会't想操纵内部数据结构，这就是为什么PriorityQueue不实现List接口（因为这将让你直接访问它的元素）。

在 PriorityQueue 迭代器上注意

code> 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（））; 
} 
 //打印出cat和lol
  

4 。编写您自己的 SortedList class

注意：您不应该。

您可以编写自己的List类，每次添加新元素时对其进行排序。根据您的实施而且无意义，这可能会导致计算量很大，除非您希望将其作为一个练习，因为两个主要原因：

1. 它打破了 List< E> 接口具有的合约，因为 add 方法应该确保元素将驻留在用户指定的索引中。


2. 为什么要重新发明轮子？

但是，如果你想做一个更好的方法，你应该使用TreeSet或Multisets。练习这里是一个代码示例让你开始，它使用 AbstractList 抽象类：

 code> public class SortedList< E> extends AbstractList< E> {
 
 private ArrayList< E> internalList = new ArrayList< E>（）; 
 
 //注意AbstractList中的add（E e）调用这个
 @Override 
 public void add（int position，E e）{
 internalList。添加（e）; 
 Collections.sort（internalList，null）; 
} 
 
 @Override 
 public E get（int i）{
 return internalList.get（i）; 
} 
 
 @Override 
 public int size（）{
 return internalList.size（）; 
} 
 
} 
  

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

In Java there are the SortedSet and SortedMap interfaces. Both belong to Java's standard Collections framework and provide a sorted way to access the elements.

However, in my understanding there is no SortedList in Java. You can use java.util.Collections.sort() to sort a list.

Any idea why it is designed like that?

解决方案

List iterators guarantee first and foremost that you get the list's elements in the internal order of the list (aka. insertion order). More specifically it is in the order you've inserted the elements or on how you've manipulated the list. Sorting can be seen as a manipulation of the data structure, and there are several ways to sort the list.

I'll order the ways in the order of usefulness as I personally see it:

1. Consider using Set or Bag collections instead

NOTE: I put this option at the top because this is what you normally want to do anyway.

A sorted set automatically sorts the collection at insertion, meaning that it does the sorting while you add elements into the collection. It also means you don't need to manually sort it.

Furthermore if you are sure that you don't need to worry about (or have) duplicate elements then you can use the TreeSet<T> instead. It implements SortedSet and NavigableSet interfaces and works as you'd probably expect from a list:

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"

If you don't want the natural ordering you can use the constructor parameter that takes a Comparator<T>.

Alternatively you can use Multisets (also known as Bags), that is a Set that allows duplicate elements, instead and there are third party implementations of them. Most notably from the Guava libraries there is a TreeMultiset, that works a lot like the TreeSet.

2. Sort your list with Collections.sort()

As mentioned above, sorting of Lists is an manipulation of the data structure. So for situations where you need "one source of truth" that will be sorted in a variety of ways then sorting it manually is the way to go.

You can sort your list with the java.util.Collections.sort() method. Here is a code sample on how:

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

One clear benefit is that you may use Comparator in the sort method. Java also provides some implementations for the Comparator such as the Collator which is useful for locale sensitive sorting strings. Here is one example:

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

Collections.sort(strings, usCollator);

Sorting in concurrent environments

Do note though that using the sort method is not friendly in concurrent environments, since the collection instance will be manipulated, and you should consider using immutable collections instead. This is something Guava provides in the Ordering class and is a simple one-liner:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Wrap your list with java.util.PriorityQueue

Though there is no sorted list in Java there is however a sorted queue which would probably work just as well for you. It is the java.util.PriorityQueue class.

Nico Haase linked in the comments to a related question that also answers this.

In a sorted collection you most likely don't want to manipulate the internal data structure which is why PriorityQueue doesn't implement the List interface (because that would give you direct access to it's elements).

Caveat on the PriorityQueue iterator

The PriorityQueue class implements the Iterable<E> and Collection<E> interfaces so it can be iterated as usual. However the iterator is not guaranteed to return elements in the sorted order. Instead (as Alderath points out in the comments) you need to poll() the queue until empty.

Note that you can convert a list to a priority queue via the 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"

4. Write your own SortedList class

NOTE: You shouldn't have to do this.

You can write your own List class that sorts each time you add a new element. This can get rather computation heavy depending on your implementation and is pointless, unless you want to do it as an exercise, because of two main reasons:

1. It breaks the contract that List<E> interface has, because the add methods should ensure that the element will reside in the index that the user specifies.
2. Why reinvent the wheel? You should be using the TreeSet or Multisets instead as pointed out in the first point above.

However if you want to do it as an exercise here is a code sample to get you started, it uses the AbstractList abstract class:

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();
    }

}

Note that if you haven't overridden the methods you need, then the default implementations from AbstractList will throw UnsupportedOperationExceptions.

这篇关于为什么在Java中没有SortedList？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！