Java中的排序数组列表

Sorted array list in Java

提问by Chris Knight

I'm baffled that I can't find a quick answer to this. I'm essentially looking for a datastructure in Java which implements the java.util.Listinterface, but which stores its members in a sorted order. I know that you can use a normal ArrayListand use Collections.sort()on it, but I have a scenario where I am occasionally adding and often retrieving members from my list and I don't want to have to sort it every time I retrieve a member in case a new one has been added. Can anyone point me towards such a thing which exists in the JDK or even 3rd party libraries?

我很困惑我找不到对此的快速答案。我本质上是在 Java 中寻找一种数据结构，它实现了java.util.List接口，但以排序的顺序存储其成员。我知道您可以使用普通ArrayList并使用Collections.sort()它，但我有一个场景，我偶尔会添加并经常从我的列表中检索成员，我不想每次检索成员时都必须对其进行排序，以防万一添加了新的。谁能指出我存在于 JDK 甚至 3rd 方库中的这种东西？

EDIT: The datastructure will need to preserve duplicates.

编辑：数据结构将需要保留重复项。

ANSWER's SUMMARY: I found all of this very interesting and learned a lot. Aioobe in particular deserves mention for his perseverance in trying to achieve my requirements above (mainly a sorted java.util.List implementation which supports duplicates). I have accepted his answer as the most accurate for what I asked and most thought provoking on the implications of what I was looking for even if what I asked wasn't exactly what I needed.

答案摘要：我发现所有这些都非常有趣并且学到了很多东西。特别值得一提的是，Aioobe 坚持不懈地努力实现我的上述要求（主要是支持重复的排序 java.util.List 实现）。我接受了他的回答，认为他的回答对我所问的问题最准确，并且即使我问的不是我所需要的，也最能激发我所寻找的含义。

The problem with what I asked for lies in the List interface itself and the concept of optional methods in an interface. To quote the javadoc:

我所要求的问题在于 List 接口本身和接口中可选方法的概念。引用 javadoc：

The user of this interface has precise control over where in the list each element is inserted.

此界面的用户可以精确控制每个元素在列表中的插入位置。

Inserting into a sorted list doesn't have precise control over insertion point. Then, you have to think how you will handle some of the methods. Take addfor example:

插入排序列表无法精确控制插入点。然后，您必须考虑如何处理某些方法。就拿add例如：

public boolean add(Object o)

 Appends the specified element to the end of this list (optional operation).

公共布尔添加（对象 o）

 Appends the specified element to the end of this list (optional operation).

You are now left in the uncomfortable situation of either 1) Breaking the contract and implementing a sorted version of add 2) Letting addadd an element to the end of the list, breaking your sorted order 3) Leaving addout (as its optional) by throwing an UnsupportedOperationExceptionand implementing another method which adds items in a sorted order.

你现在处于不舒服的境地 1)add违反合同并实施一个排序版本的 add 2) 让一个元素添加到列表的末尾，打破你的排序顺序 3) 通过 throws 离开add（作为它的可选）一UnsupportedOperationException和实施这增加了在一个有序的物品的另一种方法。

Option 3 is probably the best, but I find it unsavory having an add method you can't use and another sortedAdd method which isn't in the interface.

选项 3 可能是最好的，但我发现有一个你不能使用的 add 方法和另一个不在界面中的 sortedAdd 方法是令人讨厌的。

Other related solutions (in no particular order):

其他相关解决方案（排名不分先后）：

• java.util.PriorityQueuewhich is probably closest to what I needed than what I asked for. A queue isn't the most precise definition of a collection of objects in my case, but functionally it does everything I need it to.
• net.sourceforge.nite.util.SortedList. However, this implementation breaks the contract of the List interface by implementing the sorting in the add(Object obj)method and bizarrely has a no effect method for add(int index, Object obj). General consensus suggests throw new UnsupportedOperationException()might be a better choice in this scenario.
• Guava's TreeMultiSetA set implementation which supports duplicates
• ca.odell.glazedlists.SortedListThis class comes with the caveat in its javadoc: Warning: This class breaks the contract required by List

• java.util.PriorityQueue可能比我要求的更接近我需要的。在我的例子中，队列不是对象集合的最精确定义，但在功能上它可以完成我需要的一切。
• net.sourceforge.nite.util.SortedList。然而，这个实现打破了 List 接口的约定，在add(Object obj)方法中实现了排序，奇怪的是对add(int index, Object obj). 普遍共识表明，throw new UnsupportedOperationException()在这种情况下可能是更好的选择。
• Guava 的 TreeMultiSet支持重复的集合实现
• ca.odell.glazedlists.SortedList此类在其 javadoc 中带有警告：Warning: This class breaks the contract required by List

采纳答案by aioobe

Minimalistic Solution

极简解决方案

Here is a "minimal" solution.

这是一个“最小”解决方案。

class SortedArrayList<T> extends ArrayList<T> {

    @SuppressWarnings("unchecked")
    public void insertSorted(T value) {
        add(value);
        Comparable<T> cmp = (Comparable<T>) value;
        for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
            Collections.swap(this, i, i-1);
    }
}

The insert runs in linear time, but that would be what you would get using an ArrayList anyway (all elements to the right of the inserted element would have to be shifted one way or another).

插入以线性时间运行，但这将是您使用 ArrayList 无论如何都会得到的（插入元素右侧的所有元素都必须以一种或另一种方式移动）。

Inserting something non-comparable results in a ClassCastException. (This is the approach taken by PriorityQueueas well: A priority queue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).)

插入不可比较的内容会导致 ClassCastException。（这也是采用的方法PriorityQueue：依赖于自然排序的优先级队列也不允许插入不可比较的对象（这样做可能会导致 ClassCastException）。）

Overriding List.add

覆盖 List.add

Note that overriding List.add(or List.addAllfor that matter) to insert elements in a sorted fashion would be a direct violation of the interface specification. What you coulddo, is to override this method to throw an UnsupportedOperationException.

请注意，覆盖List.add（或List.addAll就此而言）以排序方式插入元素将直接违反接口规范。您可以做的是覆盖此方法以抛出UnsupportedOperationException.

From the docs of List.add:

来自以下文档List.add：

boolean add(E e)
    Appends the specified element to the end of this list (optional operation).

boolean add(E e)
    将指定的元素附加到此列表的末尾（可选操作）。

Same reasoning applies for both versions of add, both versions of addAlland set. (All of which are optional operations according to the list interface.)

同样的道理也适用于这两个版本add，两个版本的addAll和set。（根据列表界面，这些都是可选操作。）

Some tests

一些测试

SortedArrayList<String> test = new SortedArrayList<String>();

test.insertSorted("ddd");    System.out.println(test);
test.insertSorted("aaa");    System.out.println(test);
test.insertSorted("ccc");    System.out.println(test);
test.insertSorted("bbb");    System.out.println(test);
test.insertSorted("eee");    System.out.println(test);

....prints:

....印刷：

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]

回答by Jon Skeet

Lists typically preserve the order in which items are added. Do you definitely need a list, or would a sorted set(e.g. TreeSet<E>) be okay for you? Basically, do you need to need to preserve duplicates?

列表通常保留添加项目的顺序。你肯定需要一个列表，或者一个有序的集合（例如TreeSet<E>）适合你吗？基本上，您是否需要保留重复项？

回答by Jigar Joshi

Have a look at SortedList

看看SortedList

This class implements a sorted list. It is constructed with a comparator that can compare two objects and sort objects accordingly. When you add an object to the list, it is inserted in the correct place. Object that are equal according to the comparator, will be in the list in the order that they were added to this list. Add only objects that the comparator can compare.

这个类实现了一个排序列表。它由一个比较器构成，可以比较两个对象并相应地对对象进行排序。当您将一个对象添加到列表中时，它会被插入到正确的位置。根据比较器相等的对象将按照它们添加到此列表的顺序出现在列表中。仅添加比较器可以比较的对象。

---

---

When the list already contains objects that are equal according to the comparator, the new object will be inserted immediately after these other objects.

当列表已经包含根据比较器相等的对象时，新对象将立即插入在这些其他对象之后。

回答by Gadolin

Use java.util.PriorityQueue.

使用java.util.PriorityQueue.

回答by codeporn

I think the choice between SortedSets/Lists and 'normal' sortable collections depends, whether you need sorting only for presentation purposes or at almost every point during runtime. Using a sorted collection may be much more expensive because the sorting is done everytime you insert an element.

我认为 SortedSets/Lists 和“普通”可排序集合之间的选择取决于您是否需要仅出于演示目的或运行时几乎每个点的排序。使用排序集合可能会更昂贵，因为每次插入元素时都会进行排序。

If you can't opt for a collection in the JDK, you can take a look at the Apache Commons Collections

如果您不能选择 JDK 中的集合，您可以查看Apache Commons Collections

回答by Tom Anderson

You could subclass ArrayList, and call Collections.sort(this) after any element is added - you would need to override two versions of add, and two of addAll, to do this.

您可以继承 ArrayList，并在添加任何元素后调用 Collections.sort(this) - 您需要覆盖 add 的两个版本和 addAll 的两个版本才能执行此操作。

Performance would not be as good as a smarter implementation which inserted elements in the right place, but it would do the job. If addition to the list is rare, the cost amortised over all operations on the list should be low.

性能不如在正确位置插入元素的更智能的实现好，但它可以完成这项工作。如果很少加入列表，则列表中所有操作的摊销成本应该很低。

回答by I82Much

It might be a bit too heavyweight for you, but GlazedListshas a SortedListthat is perfect to use as the model of a table or JList

对你来说可能有点太重量级了，但是GlazedLists有一个SortedList非常适合用作表格或 JList 的模型

回答by Emil

You can try Guava'sTreeMultiSet.

你可以试试番石榴的TreeMultiSet。

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
 System.out.println(ms);

回答by Omnaest

Since the currently proposed implementations which do implement a sorted list by breaking the Collection API, have an own implementation of a tree or something similar, I was curios how an implementation based on the TreeMap would perform. (Especialy since the TreeSet does base on TreeMap, too)

由于当前提出的实现通过破坏集合 API 来实现排序列表，有自己的树实现或类似的东西，我很好奇基于 TreeMap 的实现将如何执行。（特别是因为 TreeSet 也基于 TreeMap）

If someone is interested in that, too, he or she can feel free to look into it:

如果有人对此也感兴趣，他或她可以随意查看：

TreeList

树列表

Its part of the core library, you can add it via Maven dependency of course. (Apache License)

它是核心库的一部分，您当然可以通过 Maven 依赖项添加它。（Apache 许可证）

Currently the implementation seems to compare quite well on the same level than the guava SortedMultiSet and to the TreeList of the Apache Commons library.

目前，该实现似乎在同一级别上与 guava SortedMultiSet 和 Apache Commons 库的 TreeList 相比相当不错。

But I would be happy if more than only me would test the implementation to be sure I did not miss something important.

但是，如果不仅仅是我来测试实现以确保我没有遗漏一些重要的东西，我会很高兴。

Best regards!

此致！

回答by Vitaly Sazanovich

I had the same problem. So I took the source code of java.util.TreeMap and wrote IndexedTreeMap. It implements my own IndexedNavigableMap:

我有同样的问题。于是我拿了 java.util.TreeMap 的源码，写了IndexedTreeMap。它实现了我自己的IndexedNavigableMap：

public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
   K exactKey(int index);
   Entry<K, V> exactEntry(int index);
   int keyIndex(K k);
}

The implementation is based on updating node weights in the red-black tree when it is changed. Weight is the number of child nodes beneath a given node, plus one - self. For example when a tree is rotated to the left:

该实现基于在更改时更新红黑树中的节点权重。权重是给定节点下的子节点数加上一个 - self。例如，当一棵树向左旋转时：

    private void rotateLeft(Entry<K, V> p) {
    if (p != null) {
        Entry<K, V> r = p.right;

        int delta = getWeight(r.left) - getWeight(p.right);
        p.right = r.left;
        p.updateWeight(delta);

        if (r.left != null) {
            r.left.parent = p;
        }

        r.parent = p.parent;


        if (p.parent == null) {
            root = r;
        } else if (p.parent.left == p) {
            delta = getWeight(r) - getWeight(p.parent.left);
            p.parent.left = r;
            p.parent.updateWeight(delta);
        } else {
            delta = getWeight(r) - getWeight(p.parent.right);
            p.parent.right = r;
            p.parent.updateWeight(delta);
        }

        delta = getWeight(p) - getWeight(r.left);
        r.left = p;
        r.updateWeight(delta);

        p.parent = r;
    }
  }

updateWeight simply updates weights up to the root:

updateWeight 只是将权重更新到根：

   void updateWeight(int delta) {
        weight += delta;
        Entry<K, V> p = parent;
        while (p != null) {
            p.weight += delta;
            p = p.parent;
        }
    }

And when we need to find the element by index here is the implementation that uses weights:

当我们需要按索引查找元素时，这里是使用权重的实现：

public K exactKey(int index) {
    if (index < 0 || index > size() - 1) {
        throw new ArrayIndexOutOfBoundsException();
    }
    return getExactKey(root, index);
}

private K getExactKey(Entry<K, V> e, int index) {
    if (e.left == null && index == 0) {
        return e.key;
    }
    if (e.left == null && e.right == null) {
        return e.key;
    }
    if (e.left != null && e.left.weight > index) {
        return getExactKey(e.left, index);
    }
    if (e.left != null && e.left.weight == index) {
        return e.key;
    }
    return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
}

Also comes in very handy finding the index of a key:

查找键的索引也非常方便：

    public int keyIndex(K key) {
    if (key == null) {
        throw new NullPointerException();
    }
    Entry<K, V> e = getEntry(key);
    if (e == null) {
        throw new NullPointerException();
    }
    if (e == root) {
        return getWeight(e) - getWeight(e.right) - 1;//index to return
    }
    int index = 0;
    int cmp;
    index += getWeight(e.left);

    Entry<K, V> p = e.parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    if (cpr != null) {
        while (p != null) {
            cmp = cpr.compare(key, p.key);
            if (cmp > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    } else {
        Comparable<? super K> k = (Comparable<? super K>) key;
        while (p != null) {
            if (k.compareTo(p.key) > 0) {
                index += getWeight(p.left) + 1;
            }
            p = p.parent;
        }
    }
    return index;
}

You can find the result of this work at http://code.google.com/p/indexed-tree-map/

您可以在http://code.google.com/p/indexed-tree-map/ 上找到这项工作的结果

TreeSet/TreeMap (as well as their indexed counterparts from the indexed-tree-map project) do not allow duplicate keys , you can use 1 key for an array of values. If you need a SortedSet with duplicates use TreeMap with values as arrays. I would do that.

TreeSet/TreeMap（以及来自 indexed-tree-map 项目的索引对应项）不允许重复键，您可以将 1 个键用于值数组。如果您需要带有重复项的 SortedSet，请使用带有值作为数组的 TreeMap。我会那样做。