Java 列表排序 : Is there a way to keep a list permantly sorted automatically like 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 包装器，并实现将实际使用的方法。这样您就可以很好地了解集合的要求，并且可以确保它适合您。

EDIT(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;
    }
};