Java中的排序集合

Sorted collection in Java

提问by

I'm a beginner in Java. Please suggest which collection(s) can/should be used for maintaining a sorted list in Java. I have tried Mapand Set, but they weren't what I was looking for.

我是 Java 的初学者。请建议可以/应该使用哪些集合来维护 Java 中的排序列表。我试过Map和Set，但它们不是我想要的。

回答by Michael Borgwardt

TreeMap and TreeSet will give you an iteration over the contents in sorted order. Or you could use an ArrayList and use Collections.sort() to sort it. All those classes are in java.util

TreeMap 和 TreeSet 将按排序顺序对内容进行迭代。或者您可以使用 ArrayList 并使用 Collections.sort() 对其进行排序。所有这些类都在 java.util 中

回答by cletus

You want the SortedSetimplementations, namely TreeSet.

您需要SortedSet实现，即TreeSet。

回答by BenM

There are a few options. I'd suggest TreeSet if you don't want duplicates and the objects you're inserting are comparable.

有几个选项。如果您不想重复并且您插入的对象具有可比性，我建议使用 TreeSet。

You can also use the static methods of the Collections class to do this.

您还可以使用 Collections 类的静态方法来执行此操作。

See Collections#sort(java.util.List)and TreeSetfor more info.

有关更多信息，请参阅Collections#sort(java.util.List)和TreeSet。

回答by Guillaume

If you just want to sort a list, use any kind of Listand use Collections.sort(). If you want to make sure elements in the list are unique and always sorted, use a SortedSet.

如果您只想对列表进行排序，请使用任何类型的List并使用Collections.sort()。如果要确保列表中的元素是唯一的且始终排序，请使用SortedSet。

回答by Neil Coffey

If you want to maintain a sorted listwhich you will frequently modify(i.e. a structure which, in addition to being sorted, allows duplicates and whose elements can be efficiently referenced by index), then use an ArrayList but when you need to insert an element, always use Collections.binarySearch() to determine the indexat which you add a given element. The latter method tells you the index you need to insert at to keep your list in sorted order.

如果你想维护一个你经常修改的排序列表（即一个结构，除了被排序，还允许重复并且可以通过索引有效地引用其元素），然后使用 ArrayList 但当你需要插入一个元素时，始终使用Collections.binarySearch() 来确定添加给定元素的索引。后一种方法告诉您需要插入的索引以保持列表的排序顺序。

回答by Martin Probst

This comes very late, but there is a class in the JDK just for the purpose of having a sorted list. It is named (somewhat out of order with the other Sorted*interfaces) "java.util.PriorityQueue". It can sort either Comparable<?>s or using a Comparator.

这来得很晚，但 JDK 中有一个类只是为了有一个排序列表。它被命名为（与其他Sorted*接口有点乱）“ java.util.PriorityQueue”。它可以对Comparable<?>s 或使用 a进行排序Comparator。

The difference with a Listsorted using Collections.sort(...)is that this will maintain a partial order at all times, with O(log(n)) insertion performance, by using a heap data structure, whereas inserting in a sorted ArrayListwill be O(n) (i.e., using binary search and move).

与Listsorted using的区别Collections.sort(...)在于，通过使用堆数据结构，这将始终保持偏序，插入性能为 O(log(n))，而在 sorted 中插入ArrayList将是 O(n)（即，使用二分查找和移动）。

However, unlike a List, PriorityQueuedoes not support indexed access (get(5)), the only way to access items in a heap is to take them out, one at a time(thus the name PriorityQueue).

但是，与List,PriorityQueue不支持索引访问 ( get(5))不同的是，访问堆中项目的唯一方法是一次取出一个项目（因此得名PriorityQueue）。

回答by jtb

Use Google Guava's TreeMultisetclass. Guavahas a spectacular collections API.

使用 Google Guava 的TreeMultiset类。Guava有一个壮观的集合 API。

One problem with providing an implementation of List that maintains sorted order is the promise made in the JavaDocs of the add()method.

提供维护排序顺序的 List 实现的一个问题是该add()方法的 JavaDocs 中做出的承诺。

回答by Giuseppe

TreeSet would not work because they do not allow duplicates plus they do not provide method to fetch element at specific position. PriorityQueue would not work because it does not allow fetching elements at specific position which is a basic requirement for a list. I think you need to implement your own algorithm to maintain a sorted list in Java with O(logn) insert time, unless you do not need duplicates. Maybe a solution could be using a TreeMap where the key is a subclass of the item overriding the equals method so that duplicates are allowed.

TreeSet 不起作用，因为它们不允许重复，而且它们不提供在特定位置获取元素的方法。PriorityQueue 不起作用，因为它不允许在特定位置获取元素，这是列表的基本要求。我认为你需要实现你自己的算法来维护一个带有 O(logn) 插入时间的 Java 排序列表，除非你不需要重复。也许解决方案可能是使用 TreeMap ，其中键是覆盖 equals 方法的项目的子类，以便允许重复。

回答by Jakub Zaverka

What you want is a binary search tree. It maintains sorted order while offering logarithmic access for searches, removals and insertions (unless you have a degenerated tree - then it's linear). It is quite easy to implement and you even can make it implement the List interface, but then the index-access gets complicated.

你想要的是一个二叉搜索树。它保持排序顺序，同时为搜索、删除和插入提供对数访问（除非您有退化的树 - 那么它是线性的）。它很容易实现，你甚至可以让它实现 List 接口，但是索引访问变得复杂。

Second approach is to have an ArrayList and then a bubble sort implementation. Because you are inserting or removing one element at a time, the access times for insertions and removals are linear. Searches are logarithmic and index access constant (times can get different for LinkedList). The only code you need is 5, maybe 6 lines of bubble sort.

第二种方法是先有一个 ArrayList，然后有一个冒泡排序实现。因为您一次插入或删除一个元素，所以插入和删除的访问时间是线性的。搜索是对数和索引访问常量（LinkedList 的时间可能不同）。您需要的唯一代码是 5 行，也许是 6 行冒泡排序。

回答by Carlos Verdes

What I have done is implement List having a internal instance with all the methods delegated.

我所做的是实现具有内部实例的 List，其中包含所有委托的方法。

 public class ContactList implements List<Contact>, Serializable {
    private static final long serialVersionUID = -1862666454644475565L;
    private final List<Contact> list;

public ContactList() {
    super();
    this.list = new ArrayList<Contact>();
}

public ContactList(List<Contact> list) {
    super();
    //copy and order list
    List<Contact>aux= new ArrayList(list);
    Collections.sort(aux);

    this.list = aux;
}

public void clear() {
    list.clear();
}

public boolean contains(Object object) {
    return list.contains(object);
}

After, I have implemented a new method "putOrdered" which insert in the proper position if the element doesn't exist or replace just in case it exist.

之后，我实现了一个新方法“putOrdered”，它在元素不存在时插入到适当的位置，或者在元素存在时进行替换。

public void putOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
        list.add(index, contact);
    }else{
        list.set(index, contact);
    }
}

If you want to allow repeated elements just implement addOrdered instead (or both).

如果您想允许重复元素，只需实现 addOrdered （或两者兼而有之）。

public void addOrdered(Contact contact) {
    int index=Collections.binarySearch(this.list,contact);
    if(index<0){
        index= -(index+1);
    }
    list.add(index, contact);
}

If you want to avoid inserts you can also throw and unsupported operation exception on "add" and "set" methods.

如果您想避免插入，您还可以在“add”和“set”方法上抛出和不受支持的操作异常。

public boolean add(Contact object) {
    throw new UnsupportedOperationException("Use putOrdered instead");
}

... and also You have to be careful with ListIterator methods because they could modify your internal list. In this case you can return a copy of the internal list or again throw an exception.

...而且您必须小心使用 ListIterator 方法，因为它们可能会修改您的内部列表。在这种情况下，您可以返回内部列表的副本或再次抛出异常。

public ListIterator<Contact> listIterator() {
    return (new ArrayList<Contact>(list)).listIterator();
}