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

查看：32
本文介绍了为什么 Java 中没有 SortedList?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

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

然而，据我所知，Java 中没有 SortedList.您可以使用 java.util.Collections.sort() 对列表进行排序.

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

解决方案

列表迭代器首先保证您以列表的内部顺序(也就是插入顺序)获取列表的元素.更具体地说，它是按照您插入元素的顺序或您如何操作列表的顺序.排序可以看作是对数据结构的一种操作，对列表进行排序有多种方式.

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

1.考虑使用 Set 或 Bag 集合代替

注意:我将此选项放在顶部，因为无论如何这是您通常想要做的.

排序集在插入时自动对集合进行排序，这意味着它在您向集合中添加元素时进行排序.这也意味着您无需手动对其进行排序.

此外，如果您确定不需要担心(或拥有)重复元素，那么您可以使用 TreeSet 代替.它实现了 SortedSet 和 NavigableSet 接口，并且按照您可能对列表所期望的方式工作:

TreeSetset = new TreeSet();set.add("大声笑");set.add("猫");//添加时自动排序自然顺序for (String s : set) {System.out.println(s);}//打印出cat"和lol"

如果您不想要自然顺序，您可以使用带有 比较器.

或者，您可以使用 Multisets(也称为Bags)，即允许重复元素的Set，取而代之的是第三方它们的实现.最值得注意的是 Guava 库 中有一个 TreeMultiset，很像 TreeSet.

2.使用 Collections.sort()

对您的列表进行排序

如上所述，List的排序是对数据结构的一种操作.因此，对于需要以多种方式排序的单一事实来源"的情况，手动排序是可行的方法.

您可以使用 java.util.Collections.sort() 方法.这是有关如何操作的代码示例:

List字符串 = 新的 ArrayList()字符串.添加(大声笑")；字符串.添加(猫")；Collections.sort(strings);for (String s : 字符串) {System.out.println(s);}//打印出cat"和lol"

使用比较器

一个明显的好处是您可以使用 sort 方法中的 >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 在 Ordering 类，是一个简单的单行:

Listsorted = Ordering.natural().sortedCopy(strings);

3.用 java.util.PriorityQueue

包裹你的列表

虽然在 Java 中没有排序列表，但是有一个排序队列，它可能对您同样有效.它是 java.util.PriorityQueue 类.

Nico Haase 在评论中链接到一个相关问题，也回答了这个问题.>

在排序集合中您很可能不想操作内部数据结构，这就是 PriorityQueue 不实现 List 接口的原因(因为这可以让您直接访问其元素).

关于 PriorityQueue 迭代器的警告

PriorityQueue 类实现了 Iterable 和 Collection 接口，因此它可以像往常一样迭代.但是，迭代器不能保证按排序顺序返回元素.相反(正如 Alderath 在评论中指出的那样)您需要 poll() 队列直到为空.

请注意，您可以通过 接受任何集合的构造函数:

List字符串 = 新的 ArrayList()字符串.添加(大声笑")；字符串.添加(猫")；PriorityQueuesortedStrings = new PriorityQueue(strings);while(!sortedStrings.isEmpty()) {System.out.println(sortedStrings.poll());}//打印出cat"和lol"

4.编写自己的 SortedList 类

注意:您不应该这样做.

您可以编写自己的 List 类，在每次添加新元素时进行排序.根据您的实现，这可能会导致计算量很大并且毫无意义，除非您想将其作为练习来进行，主要有两个原因:

  1. 它违反了 List 接口的约定，因为 add 方法应该确保元素将驻留在用户指定的索引中.
  2. 为什么要重新发明轮子?您应该使用 TreeSet 或 Multisets 代替上面第一点中指出的那样.

但是，如果您想将其作为练习，这里是一个帮助您入门的代码示例，它使用了 AbstractList 抽象类:

公共类SortedList扩展 AbstractList{私有 ArrayListinternalList = new ArrayList();//注意 AbstractList 中的 add(E e) 调用的是这个@覆盖public void add(int position, E e) {internalList.add(e);Collections.sort(internalList, null);}@覆盖公共 E 获取(int i){返回 internalList.get(i);}@覆盖公共整数大小(){返回 internalList.size();}}

请注意，如果您尚未覆盖所需的方法，则 AbstractList 的默认实现将抛出 UnsupportedOperationExceptions.

In Java there are the SortedSet and SortedMap interfaces. Both belong to the Java 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 a 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 its 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屋！

查看全文
相关文章
Java开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆