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或其他一个有序集合编写一个List包装器,并实现实际使用的方法.这样您就可以很好地理解集合的要求,并确保它可以正常工作.

编辑(2):因为对使用binarySearch非常感兴趣.;)

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.但是,重要的是要意识到,如果迭代 a的内容PriorityQueue,元素将不按排序顺序排列.你只能保证从方法获得了"最低"的元素peek(),poll()等等.

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

Answer 3

评论

可能有一个很好的理由是SortedListJDK中没有实现.我个人无法想到在JDK中进行一次自动排序的原因.

它过早优化出了问题.如果列表不是经常插入的那样读取,那么你就是在无缘无故地浪费循环排序.在读取之前进行排序会更加反应并且在boolean某个地方指示列表在读取之前是否需要进行排序会更好.

问题是你在使用Iteratoror for each循环遍历列表时只关心顺序,因此Collections.sort()在迭代任何代码之前调用可能比在每次插入时始终对列表进行排序更有效.

List由于重复,有些含糊不清,你如何确定性地订购重复？有SortedSet,因为独特性,这是有道理的.但是,排序a List可能会因重复的副作用和其他约束而产生更多复杂因素,例如制作每个对象Comparable或者我在代码中显示的必须具有Comparator可以完成工作的其他约束.

排序 .add()

如果你有一些非常特殊的情况,自动排序List会很有用,那么你可能要做的一件事就是将一个List实现子类化,并覆盖你.add()做一个Collections.sort(this, comparator)传递给自定义构造函数的实现.我使用LinkedList而不是ArrayList出于某种原因,ArrayList是一个自然的插入排序顺序List开始..add()如果你想要一个经常排序的List,那么它也有能力处理一个非常无用的索引,这个索引必须在某种程度上处理,这可能不太理想.根据Javadoc;

void    add(int index, Object element)

将指定元素插入此列表中的指定位置(可选操作).

所以它只是抛出UnSupportedOperationException是可以接受的,或者如果你在方法的JavaDoc中记录它,你可以忽略index和委托.add(Object element);.

通常当你想要大量的插入/删除和排序时,你会使用a,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;
    }
}

最有效的解决方案:

或者你只能在获得时进行排序,Iterator如果排序顺序在迭代时非常重要,那么这将更加注重性能List.这将涵盖客户端代码的用例,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或不是和做什么,如果是这样的话,但是这给你的想法.你仍然没有任何确定的方法来处理重复.

番石榴解决方案:

如果您使用的是番石榴,而您应该使用它,您可以使用

Ordering.immutableSortedCopy() 只有当你需要迭代并完成它时.

Answer 4

像 TreeSet（或 TreeMultiset，以防您需要重复）之类的具有更高效随机访问的东西是可能的，但我怀疑它是在 Java 中实现的。使树的每个节点记住其左子树的大小允许按时间索引访问元素，O(log(size))这还不错。

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

Answer 5

公共收藏有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验证集合是否未更改。

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