Java 列表排序：有没有办法像 TreeMap 一样让列表自动永久排序？

Question

在Java中，您可以构建一个包含项目的ArrayList，然后调用：

Collections.sort(list, comparator);

是否可以像使用TreeMap那样在创建列表时传入比较器？

目标是能够将元素添加到列表中，而不是将其自动附加到列表末尾，列表将根据 Comparator 保持自身排序，并将新元素插入到列表中索引由Comparator确定。因此基本上列表可能必须根据添加的每个新元素重新排序。

无论如何，是否可以通过 Comparator 或其他类似的方式来实现此目的？

Answer 1

您可以更改 ArrayList 的行为

List<MyType> list = new ArrayList<MyType>() {
    public boolean add(MyType mt) {
         super.add(mt);
         Collections.sort(list, comparator);
         return true;
    }
}; 

注意：PriorityQueue 不是 List，如果您不关心它是什么类型的集合，最简单的方法是使用 TreeSet，它就像 TreeMap 一样，但它是一个集合。 PriorityQueue 的唯一优点是允许重复。

注意：对于大型集合来说，重新排序并不是很有效，使用二分搜索并插入条目会更快。 （但更复杂）

编辑：很大程度上取决于您需要“列表”做什么。我建议您为 ArrayList、LinkedList、PriorityQueue、TreeSet 或其他排序集合之一编写一个列表包装器，并实现实际使用的方法。这样您就可以很好地了解集合的要求，并确保它适合您。

编辑（2）：因为人们对使用二进制搜索非常感兴趣。 ;)

List<MyType> list = new ArrayList<MyType>() {
    public boolean add(MyType mt) {
        int index = Collections.binarySearch(this, mt);
        if (index < 0) index = ~index;
        super.add(index, mt);
        return true;
    }
};

Answer 2

每个人都在建议 PriorityQueue。但是，重要的是要认识到，如果您 迭代 PriorityQueue 的内容，元素将不按排序顺序排列。您只能保证从 peek()、poll() 等方法中获得“最小”元素。

TreeSet 似乎是更合适。需要注意的是，作为 Set，它不能包含重复的元素，并且不支持使用索引进行随机访问。

Answer 3

注释

JDK 中没有 SortedList 实现可能是有充分理由的。我个人想不出在 JDK 中进行自动排序的理由。

它散发出过早优化出错的味道。如果读取列表的频率不如插入列表的频率，那么您就无缘无故地浪费了重复排序的周期。在读取之前进行排序会更具反应性，并且在某处使用一个布尔值来指示列表在读取之前是否需要进行排序会更好。

问题是，当使用 Iterator 或 foreach 循环遍历列表时，您只真正关心顺序，因此在之前调用 Collections.sort()任何迭代的代码可能比尝试在每次插入时始终保持列表排序更高效。

由于重复，List 存在歧义，如何确定性地对重复项进行排序？有 SortedSet，由于其唯一性，这是有意义的。但是，对 List 进行排序可能会因重复项和其他约束的副作用而变得更加复杂，例如使每个对象 Comparable 或如我在代码中所示必须具有 比较器可以代替完成这项工作。

对 .add() 进行排序

如果您遇到一些非常特殊的情况，自动排序 List 会很有用，那么您可以做的一件事就是对 进行子类化List 实现并重写 .add() 来执行传递给自定义构造函数的 Collections.sort(this, comparator)。我使用 LinkedList 而不是 ArrayList 是有原因的，ArrayList 是一种自然的插入排序顺序 List。它还具有在索引处进行 .add() 的能力，如果您想要一个不断排序的 List，则该功能非常无用，必须以某种方式处理，这可能会不太理想。根据 Javadoc；

void    add(int index, Object element)

将指定元素插入到
此列表中的指定位置
（可选操作）。

因此，它只是抛出 UnSupportedOperationException 是可以接受的，或者您可以忽略 index 并委托给 .add(Object element); 如果您记录它在方法的 JavaDoc 中。

通常，当您需要大量插入/删除和排序时，您会使用LinkedList，因为使用“List”可以获得更好的性能特征。

这是一个简单的示例：

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

public class SortedList<E> extends LinkedList<E>
{
    private Comparator<E> comparator;

    public SortedList(final Comparator<E> comparator)
    {
        this.comparator = comparator;
    }

    /**
    * this ignores the index and delegates to .add() 
    * so it will be sorted into the correct place immediately.
    */
    @Override
    public void add(int index, Object element)
    {
        this.add(element);     
    }

    @Override
    public boolean add(final E e)
    {
        final boolean result = super.add(e);
        Collections.sort(this, this.comparator);
        return result;
    }
}

最有效的解决方案：

或者，您只能在获取迭代器时进行排序，如果排序顺序仅在迭代列表时才真正重要，那么这将更加注重性能。 /代码>。这将涵盖客户端代码的用例，无需在每次迭代之前调用 Collections.sort() 并将该行为封装到类中。

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;

public class SortedList<E> extends LinkedList<E>
{
    private Comparator<E> comparator;

    public SortedList(final Comparator<E> comparator)
    {
        this.comparator = comparator;
    }

    @Override
    public Iterator<E> iterator()
    {
        Collections.sort(this, this.comparator);
        return super.iterator();
    }
}

当然，需要进行错误检查和处理，以查看 Comparator 是否为 null 以及如果是这种情况该怎么办，但这给了您想法。您仍然没有任何确定的方法来处理重复项。

Guava 解决方案：

如果您正在使用 Guava 并且您应该使用 Guava，则可以使用

Ordering.immutableSortedCopy() 。

Answer 4

像 TreeSet（或者 TreeMultiset，如果你需要重复）这样的具有更高效随机访问的东西是可能的，但我怀疑它是用 Java 实现的。让树的每个节点记住其左子树的大小允许在 O(log(size)) 时间内通过索引访问元素，这还不错。

为了实现它，您需要重写底层 TreeMap 的很大一部分。

Answer 5

SortedSet 和 List 之间的主要区别是：

• SortedSet 使其元素保持正确的顺序，但您无法真正通过索引访问特定元素。
• 列表允许索引访问和元素的任意排序。它还允许将任何元素（通过索引或迭代器）更改为另一个元素，而无需更改位置。

您似乎想要两者的融合：自动排序和允许（合理的快速）索引访问。根据数据的大小以及索引读取或添加新元素的频率，这些是我的想法：

• 包装的 ArrayList，其中 add 方法使用 ListIterator 来查找插入点，然后在那里插入元素。插入的时间复杂度为 O(n)，索引访问的时间复杂度为 O(1)。
• 一个包装的 LinkedList，其中 add 方法使用 ListIterator 来查找插入点，然后在那里插入元素。 （这对于插入来说仍然是 O(n)（有时与 ArrayList 相比，因子相当小，有时甚至更大），以及索引访问。）
• 修改后的二叉树跟踪每个级别上两半的大小，从而启用索引使用权。 （每次访问的时间复杂度为 O(log n)，但需要一些额外的编程，因为它尚未包含在 Java SE 中。或者您可以找到一些可以实现此目的的库。）

在任何情况下，SortedSet 的接口和契约和 List 并不真正兼容，因此您希望 List 部分是只读的（或只读和删除），不允许设置和添加，并有一个额外的对象（可能实现 Collection 接口）用于添加对象。

Answer 6

我会使用 Guava TreeMultiset 假设您需要一个 List 因为您可能有重复的元素。它会做你想做的一切。它不会有的一件事是基于索引的访问，考虑到您无论如何都没有将元素放在您选择的索引处，这没有多大意义。另一件需要注意的事情是，它实际上不会存储 equal 对象的重复项......只是对它们的总数进行计数。

Answer 7

commons-collections 有 TreeBag

最初我建议使用 PriorityQueue，但它的迭代顺序是未定义的，所以它没有用，除非你通过获取队列克隆的头部来迭代它，直到它变空。

由于您很可能关心迭代顺序，因此我相信您可以覆盖 iterator() 方法：

public class OrderedIterationList<E> extends ArrayList<E> {
    @Override
    public Iterator<E> iterator() {
        Object[] array = this.toArray(); // O(1)
        Arrays.sort(array);
        return Arrays.asList(array).iterator(); // asList - O(1)
    }
}

您可以通过存储排序集合的快照来改进这一点，并使用 modCount 验证集合是否未更改。

根据用例，这可能比彼得的建议更有效或更有效。例如，如果您添加多个项目并进行迭代。 （无需在迭代之间添加项目），那么这可能会更有效。

Answer 8

显而易见的解决方案是创建您自己的类，该类实现 java.util.List 接口并采用 Comparator 作为构造函数的参数。您将在正确的位置使用比较器，即 add 方法将迭代现有项目并在正确的位置插入新项目。您将禁止调用诸如 add(int index, Object obj) 等方法。

事实上，有人已经创建了这个......快速谷歌搜索揭示了至少一个例子：

http://www.ltg.ed.ac.uk/NITE/nxt/apidoc/net/sourceforge/nite/util/SortedList.html

Answer 9

拥有任何排序结构且添加/indexOf/删除/获取元素的时间少于 O(n) 的唯一方法是使用树。在这种情况下，操作通常具有 O(log2n)，而遍历类似于 O(1)。

O(n) 只是一个链表。

---

编辑：使用二分搜索插入链表。对于插入操作，不使用二进制结构，也不使用小尺寸，这应该是最佳的。

@彼得：
有一个算法，需要 O(log2n) 比较（很慢）来插入和 O(n) 移动。
如果您需要重写 LinkedList，那就这样吧。但这已经是最简洁的了。我尽可能保持算法简洁，以便于理解，可以稍微优化一下。

package t1;

import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;

public class SortedList {


    private static <T> int binarySearch(ListIterator<? extends Comparable<? super T>> i, T key){
        int low = 0;
        int high= i.previousIndex();
        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = get(i, mid);
            int cmp = midVal.compareTo(key);

            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid;
        }
        return -(low + 1);  // key not found
    }

    private static <T> T get(ListIterator<? extends T> i, int index) {
        T obj = null;
        int pos = i.nextIndex();
        if (pos <= index) {
            do {
                obj = i.next();
            } while (pos++ < index);
        } else {
            do {
                obj = i.previous();
            } while (--pos > index);
        }
        return obj;
    }
    private static void move(ListIterator<?> i, int index) {        
        int pos = i.nextIndex();
        if (pos==index)
            return;

        if (pos < index) {
            do {
                i.next();
            } while (++pos < index);
        } 
        else {
            do {
                i.previous();
            } while (--pos > index);
        }
    }
    @SuppressWarnings("unchecked")
    static  <T> int insert(List<? extends Comparable<? super T>> list, T key){
        ListIterator<? extends Comparable<? super T>> i= list.listIterator(list.size());
        int idx = binarySearch(i, key); 
        if (idx<0){
            idx=~idx;
        }
        move(i, idx);
        ((ListIterator<T>)i).add(key);
        return i.nextIndex()-1;
    }

    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        LinkedList<Integer> unsorted = new LinkedList<Integer>();
        Random r =new Random(11);
        for (int i=0;i<33;i++){
            Integer n = r.nextInt(17);
            insert(list, n);
            unsorted.add(n);            
        }

        System.out.println("  sorted: "+list);
        System.out.println("unsorted: "+unsorted);
    }

Answer 10

考虑一下我在面临类似问题时创建的 indexed-tree-map，您将能够通过索引访问元素并获取元素的索引，同时保持排序顺序。重复项可以作为同一键下的值放入数组中。

Answer 11

在 JavaFX TransformationList 层次结构中，有一个称为 SortedList 的东西。该列表是完全可观察的，因此添加/删除将通知观看该列表的任何其他侦听器。

执行此操作的基本方法是观察另一个 ObservableList 的更改，并策略性地使用 Collections.binarySearch() ，正如其他人建议的那样，在 Olog(n) 时间内找到添加或删除的索引。

有一个问题我在这里没有看到提到，那就是跟踪具有相同 compareTo 签名的添加项的能力，即 T1.compareTo(T2) == 0。在这种情况下，排序的list（我将在下面发布我自己的源代码）必须有一个包装元素类型，我将其称为 Element。这与 JavaFX 的创建者对 SortedList 所做的类似。造成这种情况的原因完全是由于删除操作，如果存在compareTo重复项，则无法找到原始元素。通常在像TreeSet这样的NavigableSet实现中，这些重复项永远不会进入Set。清单是不同的。

我有一个可观察列表库，可以有效地链接在一起（与 Java Streams 非常相似），当链中的前一个源更新时，它可以将结果完全传播到下游。

类层次结构

接口

/**
 * Binds the elements of this list to the function application of each element of a
 * source observable list.
 * <p>
 * While a {@code IListContentBinding} is bound, any attempt to modify its contents
 * will result in an {@code UnsupportedOperationException}. To unbind the list, call
 * {@link #unbind() unbind}.
 *
 * @param <S> The element type of the input source list that will generate change
 *            events.
 * @param <T> The element type of this output list.
 */
public interface IListContentBinding<S, T> extends ObservableList<T>, ObservableListValue<T>, IContentBinding {... details not shown ....}

所有绑定类型（Sort、Distinct、Map、FlatMap 等）的抽象基类

/**
 * Binds the elements of this list to the function application of each element of a
 * source observable list.
 * <p>
 * While a {@code ListContentBinding} is bound, any attempt to modify its contents
 * will result in an {@code UnsupportedOperationException}. To unbind the list, call
 * {@link #unbind() unbind}.
 *
 * @param <S> The element type of the source list that will generate change events.
 * @param <T> The element type of this binding.
 */
public abstract class ListContentBinding<S, T> extends ObservableListWrapper<T>
    implements IListContentBinding<S, T> {.... details not shown ....}

排序绑定类< /strong>

/**
 * A {@code ListContentBinding} implementation that generates sorted elements from a
 * source list. The comparator can be set to another {@code Comparator} function at
 * any time through the {@link #comparatorProperty() comparator} property.
 * <p>
 * Unlike the Collections {@link Collections#sort(List) list sort} or Arrays
 * {@link Arrays#sort(Object[]) array sort}, once this binding has been added to the
 * order of duplicate elements cannot be guaranteed to match the original order of
 * the source list. That is the insertion and removal mechanism do not guarantee that
 * the original order of duplicates (those items where T1.compareTo(T2) == 0) is
 * preserved. However, any removal from the source list is <i>guaranteed</i> to
 * remove the exact object from this sorted list. This is because an int <i>ID</i> field
 * is added to the wrapped item through the {@link Element} class to ensure that
 * matching duplicates can be further compared.
 * <p>
 * Added/Removed objects from the source list are placed inside this sorted list
 * through the {@link Arrays#binarySearch(Object[], Object, Comparator) array binary
 * search} algorithm. For any duplicate item in the sorted list, a further check on
 * the ID of the {@code Element} corresponding to that item is compared to the
 * original, and that item. Each item added to this sorted list increases the
 * counter, the maximum number of items that should be placed in this list should be
 * no greater than {@code Integer.MAX_VALUE - Integer.MIN_VALUE}, or 4,294,967,295
 * total elements. Sizes greater than this value for an instance of this class
 * may produce unknown behavior.
 * <p>
 * Removal and additions to this list binding are proportional to <i>O(logn)</i>
 * runtime, where <i>n</i> is the current total number of elements in this sorted
 * list.
 *
 * @param <T> The element type of the source and this list binding.
 */
class ListContentSortBinding<T> extends ListContentBinding<T, T> implements IListContentSortBinding<T> {

    /**
     * Each location in the source list has a random value associated it with to deal
     * with duplicate elements that would return T1.compareTo(T2) == 0.
     */
    private Element[] elements = newElementArray(10);

    /**
     * The same elements from {@link #elements} but placed in their correct sorted
     * position according to the {@link #elementComparator element comparator}.
     */
    protected Element[] sortedElements = newElementArray(10);

    /**
     * Create a new instance.
     *
     * @param source The source observable list. Sorted elements will be generated
     *            from the source and set as the content of this list binding.
     * @param comparator The sorter. An observable that will update the comparator of
     *            this binding when invalidated. The sorter can be set to another
     *            {@code Comparator} function at anytime through the
     *            {@link #comparatorProperty() comparator} property.
     * @param options The options of this binding. Considers {@code DependencyOption}
     *            instances.
     *            <p>
     *            All bindings consider {@code BeforeChangeOption} and
     *            {@code AfterChangeOption}.
     */
    @SafeVarargs
    ListContentSortBinding(ObservableList<T> source, ObservableObjectValue<Comparator<? super T>> comparator,
        BindingOption<T, T>... options) {
        this(source, comparator.get(), options);

        comparatorProperty().bind(comparator);
    }

    /**
     * Create a new instance.
     *
     * @param source The source observable list. Sorted elements will be generated
     *            from the source and set as the content of this list binding.
     * @param comparator The sorter. The sorter can be set to another
     *            {@code Comparator} function at anytime through the
     *            {@link #comparatorProperty() comparator} property.
     * @param options The options of this binding. Considers {@code DependencyOption}
     *            instances.
     *            <p>
     *            All bindings consider {@code BeforeChangeOption} and
     *            {@code AfterChangeOption}.
     */
    @SafeVarargs
    ListContentSortBinding(ObservableList<T> source, Comparator<? super T> comparator,
        BindingOption<T, T>... options) {
        super(new ArrayList<>(), options);

        List<Observable> observables = new ArrayList<>(
            Arrays.asList(BindingOptionBuilder.extractDependencies(options)));

        setComparator(comparator);
        observables.add(comparatorProperty());

        bind(source, observables.toArray(new Observable[observables.size()]));
    }

    @Override
    protected void sourceChanged(Change<? extends T> change) {
        List<? extends T> source = change.getList();

        while (change.next()) {
            int from = change.getFrom();

            if (change.wasPermutated() || change.wasUpdated()) {
                List<? extends T> srcMod = source.subList(from, change.getTo());

                removed(source, from, srcMod.size());
                added(source, from, srcMod);
            } else {
                List<? extends T> removed = change.getRemoved();
                List<? extends T> added = change.getAddedSubList();

                if (change.wasReplaced()) {
                    int min = Math.min(added.size(), removed.size());
                    replaced(source, from, added.subList(0, min));

                    added = added.subList(min, added.size());
                    removed = removed.subList(min, removed.size());
                }

                if (removed.size() > 0) {
                    removed(source, from, removed.size());
                }

                if (added.size() > 0) {
                    if (source.size() >= elements.length) {
                        ensureSize(source.size());
                    }

                    added(source, from, added);
                }

                ensureSize(source.size());
            }
        }
    }

    /**
     * Replace the items in this sorted list binding resulting from a replacement
     * operation in the source list. For each of the items added starting at the
     * <i>from</i> index in the source list, and items was removed at the same source
     * position.
     *
     * @param source The source list.
     * @param from The index of where the replacement started in the source
     *            (inclusive). The removed and added elements occurred starting at
     *            the same source position.
     * @param added The added source elements from the change.
     */
    @SuppressWarnings({})
    private void replaced(List<? extends T> source, int from, List<? extends T> added) {
        int oldSize = size();

        for (int i = 0; i < added.size(); i++) {
            int index = from + i;
            Element e = elements[index];

            // Find the old element and remove it
            int pos = findPosition(e, index, oldSize);

            System.arraycopy(sortedElements, pos + 1, sortedElements, pos, oldSize - pos - 1);

            remove(pos);

            T t = added.get(i);

            // Create a new element and add it
            e = new Element(t);

            elements[index] = e;

            pos = findPosition(e, index, oldSize - 1);

            if (pos < 0) {
                pos = ~pos;
            }

            System.arraycopy(sortedElements, pos, sortedElements, pos + 1, oldSize - pos - 1);
            sortedElements[pos] = e;

            add(pos, t);
        }
    }

    /**
     * Add the elements from the source observable list to this binding.
     *
     * @param source The source list.
     * @param from The index of where the addition started in the source (inclusive).
     * @param added The added source elements from the change.
     */
    @SuppressWarnings({})
    private void added(List<? extends T> source, int from, List<? extends T> added) {
        if (size() == 0) {
            int size = added.size();
            Element[] temp = newElementArray(size);

            for (int i = 0; i < added.size(); i++) {
                T t = added.get(i);
                Element e = new Element(t);

                elements[i] = e;
                temp[i] = e;
            }

            if (elementComparator == null) {
                addAll(added);
                return;
            }

            Arrays.sort(temp, elementComparator);
            System.arraycopy(temp, 0, sortedElements, 0, temp.length);

            addAll(Arrays.stream(temp).map(e -> (T) e.t).collect(Collectors.toList()));

            return;
        }

        int size = size();
        System.arraycopy(elements, from, elements, from + added.size(), size - from);

        for (int i = 0; i < added.size(); i++) {
            int index = from + i;

            T t = added.get(i);
            Element e = new Element(t);

            int pos = findPosition(e, index, size);

            if (pos < 0) {
                pos = ~pos;
            }

            elements[index] = e;

            if (pos < size) {
                System.arraycopy(sortedElements, pos, sortedElements, pos + 1, size - pos);
            }

            sortedElements[pos] = e;

            add(pos, t);
            size++;
        }
    }

    /**
     * Remove the elements from this binding that were removed from the source list.
     * Update the {@link #elements} mapping.
     *
     * @param source The source list.
     * @param from The index of where the removal started in the source (inclusive).
     * @param removedSize The total number of removed elements from the source list
     *            for the change.
     */
    @SuppressWarnings({})
    private void removed(List<? extends T> source, int from, int removedSize) {
        if (source.size() == 0) {
            elements = newElementArray(10);
            sortedElements = newElementArray(10);
            elementCounter = Integer.MIN_VALUE;
            clear();
            return;
        }

        int oldSize = size();
        int size = oldSize;

        for (int i = 0; i < removedSize; i++) {
            int index = from + i;

            Element e = elements[index];

            int pos = findPosition(e, index, size);

            System.arraycopy(sortedElements, pos + 1, sortedElements, pos, size - pos - 1);

            remove(pos);
            sortedElements[--size] = null;
        }

        System.arraycopy(elements, from + removedSize, elements, from, oldSize - from - removedSize);

        for (int i = size; i < oldSize; i++) {
            elements[i] = null;
        }
    }

    /**
     * Locate the position of the element in this sorted binding by performing a
     * binary search. A binary search locates the index of the add in Olog(n) time.
     *
     * @param e The element to insert.
     * @param sourceIndex The index of the source list of the modification.
     * @param size The size of the array to search, exclusive.
     *
     * @return The position in this binding that the element should be inserted.
     */
    private int findPosition(Element e, int sourceIndex, int size) {
        if (size() == 0) {
            return 0;
        }

        int pos;

        if (elementComparator != null) {
            pos = Arrays.binarySearch(sortedElements, 0, size, e, elementComparator);
        } else {
            pos = sourceIndex;
        }

        return pos;
    }

    /**
     * Ensure that the element array is large enough to handle new elements from the
     * source list. Also shrinks the size of the array if it has become too large
     * with respect to the source list.
     *
     * @param size The minimum size of the array.
     */
    private void ensureSize(int size) {
        if (size >= elements.length) {
            int newSize = size * 3 / 2 + 1;

            Element[] replacement = newElementArray(newSize);
            System.arraycopy(elements, 0, replacement, 0, elements.length);
            elements = replacement;

            replacement = newElementArray(newSize);
            System.arraycopy(sortedElements, 0, replacement, 0, sortedElements.length);
            sortedElements = replacement;

        } else if (size < elements.length / 4) {
            int newSize = size * 3 / 2 + 1;

            Element[] replacement = newElementArray(newSize);
            System.arraycopy(elements, 0, replacement, 0, replacement.length);
            elements = replacement;

            replacement = newElementArray(newSize);
            System.arraycopy(sortedElements, 0, replacement, 0, replacement.length);
            sortedElements = replacement;
        }
    }

    /**
     * Combines the {@link #comparatorProperty() item comparator} with a secondary
     * comparison if the items are equal through the <i>compareTo</i> operation. This
     * is used to quickly find the original item when 2 or more items have the same
     * comparison.
     */
    private Comparator<Element> elementComparator;

    /**
     * @see #comparatorProperty()
     */
    private ObjectProperty<Comparator<? super T>> comparator =
        new SimpleObjectProperty<Comparator<? super T>>(this, "comparator") {
            @Override
            protected void invalidated() {
                Comparator<? super T> comp = get();

                if (comp != null) {
                    elementComparator = Comparator.nullsLast((e1, e2) -> {
                        int c = comp.compare(e1.t, e2.t);
                        return c == 0 ? Integer.compare(e1.id, e2.id) : c;
                    });
                } else {
                    elementComparator = null;
                }
            }
        };

    @Override
    public final ObjectProperty<Comparator<? super T>> comparatorProperty() {
        return comparator;
    }

    @Override
    public final Comparator<? super T> getComparator() {
        return comparatorProperty().get();
    }

    @Override
    public final void setComparator(Comparator<? super T> comparator) {
        comparatorProperty().set(comparator);
    }

    @Override
    protected void onInvalidating(ObservableList<T> source) {
        clear();
        ensureSize(source.size());
        added(source, 0, source);
    }

    /**
     * Counter starts at the Integer min value, and increments each time a new
     * element is requested. If this list becomes empty, the counter is restarted at
     * the min value.
     */
    private int elementCounter = Integer.MIN_VALUE;

    /**
     * Generate a new array of {@code Element}.
     *
     * @param size The size of the array.
     *
     * @return A new array of null Elements.
     */
    @SuppressWarnings("unchecked")
    private Element[] newElementArray(int size) {
        return new ListContentSortBinding.Element[size];
    }

包装元素类

    /**
     * Wrapper class to further aid in comparison of two object types <T>. Since
     * sorting in a list allows duplicates we must assure that when a removal occurs
     * from the source list feeding this binding that the removed element matches. To
     * do this we add an arbitrary <i>int</i> field inside this element class that
     * wraps around the original object type <T>.
     */
    final class Element {
        /** Object */
        private final T t;
        /** ID helper for T type duplicates */
        private int id;

        Element(T t) {
            this.t = Objects.requireNonNull(t);
            this.id = elementCounter++;
        }

        @Override
        public String toString() {
            return t.toString() + " (" + id + ")";
        }
    }
}

JUNIT VERIFICATION TEST

@Test
public void testSortBinding() {
    ObservableList<IntWrapper> source = FXCollections.observableArrayList();

    int size = 100000;

    for (int i = 0; i < size / 2; i++) {
        int index = (int) (Math.random() * size / 10);
        source.add(new IntWrapper(index));
    }

    ListContentSortBinding<IntWrapper> binding =
        (ListContentSortBinding<IntWrapper>) CollectionBindings.createListBinding(source).sortElements();

    Assert.assertEquals("Sizes not equal for sorted binding | Expected: " +
        source.size() + ", Actual: " + binding.size(),
        source.size(), binding.size());

    List<IntWrapper> sourceSorted = new ArrayList<>(source);
    Collections.sort(sourceSorted);

    for (int i = 0; i < source.size(); i++) {
        IntWrapper expected = sourceSorted.get(i);
        IntWrapper actual = binding.get(i);

        Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
            expected.value + ", Actual: " + actual.value,
            expected.value, actual.value);
    }

    System.out.println("Sorted Elements Equal: Complete.");

    // Randomly add chunks of elements at random locations in the source

    int addSize = size / 10000;

    for (int i = 0; i < size / 4; i++) {
        List<IntWrapper> added = new ArrayList<>();
        int toAdd = (int) (Math.random() * addSize);

        for (int j = 0; j < toAdd; j++) {
            int index = (int) (Math.random() * size / 10);
            added.add(new IntWrapper(index));
        }

        int atIndex = (int) (Math.random() * source.size());
        source.addAll(atIndex, added);
    }

    sourceSorted = new ArrayList<>(source);
    Collections.sort(sourceSorted);

    for (int i = 0; i < source.size(); i++) {
        IntWrapper expected = sourceSorted.get(i);
        IntWrapper actual = binding.get(i);

        Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
            expected.value + ", Actual: " + actual.value,
            expected.value, actual.value);
    }

    System.out.println("Sorted Elements Equal - Add Multiple Elements: Complete.");

    // Remove one element at a time from the source list and compare
    // to the elements that were removed from the sorted binding
    // as a result. They should all be identical index for index.

    List<IntWrapper> sourceRemoved = new ArrayList<>();
    List<IntWrapper> bindingRemoved = new ArrayList<>();

    ListChangeListener<IntWrapper> bindingListener = change -> {
        while (change.next()) {
            if (change.wasRemoved()) {
                bindingRemoved.addAll(change.getRemoved());
            }
        }
    };

    // Watch the binding for changes after the upstream source changes

    binding.addListener(bindingListener);

    for (int i = 0; i < size / 4; i++) {
        int index = (int) (Math.random() * source.size());
        IntWrapper removed = source.remove(index);
        sourceRemoved.add(removed);
    }

    for (int i = 0; i < bindingRemoved.size(); i++) {
        IntWrapper expected = bindingRemoved.get(i);
        IntWrapper actual = sourceRemoved.get(i);

        Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
            expected + ", Actual: " + actual,
            expected.value, actual.value);

        Assert.assertEquals("Element refs not equal in expected sorted lists | Expected: " +
            expected.value + ", Actual: " + actual.value,
            expected.r, actual.r, 0);
    }

    System.out.println("Sorted Remove Single Element: Complete.");

    // Replace random elements from the source list

    bindingRemoved.clear();
    sourceRemoved.clear();
    int removeSize = size / 10000;

    for (int i = 0; i < size / 1000; i++) {
        int replaceIndex = (int) (Math.random() * source.size());

        int index = (int) (Math.random() * size / 10);
        IntWrapper replace = new IntWrapper(index);

        source.set(replaceIndex, replace);
    }

    sourceSorted = new ArrayList<>(source);
    Collections.sort(sourceSorted);

    for (int i = 0; i < source.size(); i++) {
        IntWrapper expected = sourceSorted.get(i);
        IntWrapper actual = binding.get(i);

        Assert.assertEquals("Elements not equal in expected sorted lists | Expected: " +
            expected.value + ", Actual: " + actual.value,
            expected.value, actual.value);
    }

    System.out.println("Sorted Elements Replace: Complete.");

    // Remove random chunks from the source list

    bindingRemoved.clear();
    sourceRemoved.clear();
    Set<IntWrapper> sourceRemovedSet =
        Collections.newSetFromMap(new IdentityHashMap<>()); // set for speed

    while (source.size() > 0) {
        int index = (int) (Math.random() * source.size());
        int toRemove = (int) (Math.random() * removeSize);
        toRemove = Math.min(toRemove, source.size() - index);

        List<IntWrapper> removed = source.subList(index, index + toRemove);
        sourceRemovedSet.addAll(new ArrayList<>(removed));

        removed.clear(); // triggers list change update to binding
    }

    Assert.assertEquals(bindingRemoved.size(), sourceRemovedSet.size());

    // The binding removed will not necessarily be placed in the same order
    // since the change listener on the binding will make sure that the final
    // order of the change from the binding is in the same order as the binding
    // element sequence. We therefore must do a contains() to test.

    for (int i = 0; i < bindingRemoved.size(); i++) {
        IntWrapper expected = bindingRemoved.get(i);

        Assert.assertTrue("Binding Removed Did Not Contain Source Removed",
            sourceRemovedSet.contains(expected));
    }

    System.out.println("Sorted Removed Multiple Elements: Complete.");
}

JUNIT BENCHMARK TEST

  @Test
public void sortBindingBenchmark() {
    ObservableList<IntWrapper> source = FXCollections.observableArrayList();

    ObservableList<IntWrapper> binding =
        (ListContentSortBinding<IntWrapper>) CollectionBindings.createListBinding(source).sortElements();

    int size = 200000;

    Set<IntWrapper> toAdd = new TreeSet<>();

    while (toAdd.size() < size) {
        int index = (int) (Math.random() * size * 20);
        toAdd.add(new IntWrapper(index));
    }

    // Randomize the order
    toAdd = new HashSet<>(toAdd);

    System.out.println("Sorted Binding Benchmark Setup: Complete.");

    long time = System.currentTimeMillis();

    for (IntWrapper w : toAdd) {
        source.add(w);
    }

    long bindingTime = System.currentTimeMillis() - time;

    System.out.println("Sorted Binding Time: Complete.");

    source.clear(); // clear the list and re-add

    ObservableList<IntWrapper> sortedList = new SortedList<>(source);

    time = System.currentTimeMillis();

    for (IntWrapper w : toAdd) {
        source.add(w);
    }

    long sortedListTime = System.currentTimeMillis() - time;

    System.out.println("JavaFX Sorted List Time: Complete.");

    // Make the test "fair" by adding a listener to an observable
    // set that populates the sorted set

    ObservableSet<IntWrapper> obsSet = FXCollections.observableSet(new HashSet<>());
    Set<IntWrapper> sortedSet = new TreeSet<>();

    obsSet.addListener((SetChangeListener<IntWrapper>) change -> {
        sortedSet.add(change.getElementAdded());
    });

    time = System.currentTimeMillis();

    for (IntWrapper w : toAdd) {
        obsSet.add(w);
    }

    long setTime = System.currentTimeMillis() - time;

    System.out.println("Sorted Binding Benchmark Time: Complete");

    Assert.assertEquals(sortedSet.size(), binding.size());

    System.out.println("Binding: " + bindingTime + " ms, " +
        "JavaFX Sorted List: " + sortedListTime + " ms, " +
        "TreeSet: " + setTime + " ms");
}

仅用于测试的包装类

    /**
     * Wrapper class for testing sort bindings. Verifies that duplicates were sorted
     * and removed correctly based on the object instance.
     */
private static class IntWrapper implements Comparable<IntWrapper> {
    static int counter = Integer.MIN_VALUE;
    final int value;
    final int id;

    IntWrapper(int value) {
        this.value = value;
        this.id = counter++;
    }

Answer 12

我还发现令人难以置信的是，Java 标准库中不存在这种情况。 （但是祝你好运，向 JDK 团队提议添加任何新类！我从来没有这样的运气。）

假设你的 compareTo 函数是一个适当的传递关系，那么最快的算法（假设列表的读取次数与写入次数大致相同）的方法是使用执行二分搜索的方法覆盖 List.add，以在插入新项目之前找到新项目的插入点。添加元素的数量为 O(log(N))。

Answer 13

最好的方法是重写列表的 add 实现。
我将使用 LinkedList 来演示它，因为它允许高效插入。

public boolean add(Integer e)
{
    int i = 0;
    for (Iterator<Integer> it = this.iterator(); it.hasNext();)
    {
        int current = it.next();
        if(current > e)
        {
            super.add(i, e);
            return true;
        }
        i++;
    }
    return super.add(e);
}

上面的代码创建了一个整数的排序列表，该列表始终是排序的。它可以轻松修改以与任何其他数据类型一起使用。但是，在这里您必须避免使用 add(index, value) 函数，因为这显然会破坏排序。

尽管上面的人建议使用 Arrays.sort()，但我会避免这样做，因为它可能是一种效率明显较低的方法，特别是因为每次添加到列表时都必须调用排序方法。

Answer 14

ListIterator 接口的约定使其有点麻烦，但此方法将使用列表的单次扫描（直到插入点）来执行插入：

private void add(Integer value) {
    ListIterator<Integer> listIterator = list.listIterator();

    Integer next = null;

    while (listIterator.hasNext()) {
        next = listIterator.next();

        if (next.compareTo(value) > 0) {                
            break;
        }
    }

    if (next == null || next.compareTo(value) < 0) {
        listIterator.add(value);
    } else {
        listIterator.set(value);
        listIterator.add(next);
    }
}

Answer 15

SortedSet

SortedSet 接口的任何实现都可以实现您想要的行为。

默认情况下，添加的对象按其自然顺序排序，即基于其 Comparable::compareTo 接口方法。

或者，您可以传递 Comparator实现确定排序。

TreeSet

TreeSet 是 SortedSet 的常用植入。您还可以找到其他人。

重复

List 和 SortedSet 之间的主要区别在于重复，即比较相等的对象。 List 允许重复，而 SortedSet 与任何 Set 一样不允许重复。

通过索引访问

另一个区别是Set 不能通过索引访问。您无法通过对象在集合中的位置编号来定位对象。

如果您在构建 SortedSet 后需要此类访问，请创建一个 List。有多种方法可以做到这一点，例如将 SortedSet 传递给 ArrayList 的构造函数。从 Java 10 开始，最近的一种方法是通过将 SortedSet 传递给 List.copyOf 来创建可修改的 List。

Answer 16

正如之前明确指出的，对 SortedSet 上的排序列表的需求是对索引和重复项的需求。我两者都需要。

从 Java8 开始，java.util.List 具有“尽责” List.sort()方法。

此实现是一种稳定、自适应、迭代的合并排序，当输入数组部分排序时，需要的比较次数远少于 n lg(n)。

我的列表在被引用之前已预先加载，并且加载顺序几乎总是顺序；参考文献需要非常快。因此，对 user177800 的答案 的唯一更改是我遵循现在提供的sort：

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;

public class SortedList<E> extends LinkedList<E>
{
    private Comparator<E> comparator;

    public SortedList(final Comparator<E> comparator)
    {
        this.comparator = comparator;
    }

    /**
    * this ignores the index and delegates to .add() 
    * so it will be sorted into the correct place immediately.
    */
    @Override
    public void add(int index, Object element)
    {
        this.add(element);     
    }

    @Override
    public boolean add(final E e)
    {
        final boolean result = super.add(e);
        this.sort(this, this.comparator);
        return result;
    }
}

我不知道前面会保留多少项，所以LinkedList。

Aaa现在我注意到 Collections.sort(Listlist, Comparator c) 现在遵循 List.sort(c)。

Answer 17

我相信 优先级队列 就可以了工作。

警告（来自同一文档页面）：

该类及其迭代器实现
的所有可选方法
Collection 和 Iterator 接口。
方法中提供的Iterator
iterator() 不保证
遍历优先级的元素
以任何特定顺序排队。如果你
需要有序遍历，可以考虑使用
Arrays.sort(pq.toArray()).