如何为可比较类和具有比较器的类编写有序集合

Question

我对在Java中实现一个特殊的优先级队列变体很感兴趣，我希望这个优先级队列能够与泛型类型一起工作。在Java的集合对象中，存储具有某种排序的对象（例如PriorityQueue、TreeSet等），可以使用实现Compariable的类以及不一定实现Compariable的类，因为类的比较器传递给构造函数。

如何在优先级队列类中实现此功能？如果给我一个比较器，我是否必须根据类是否实现Comparable vs重写所有方法？或者有没有一种方法可以从实现Comparable的类中获得一个比较器，所以我只需要处理比较器的情况？

Answer 1

内置的PriorityQueue具有构造函数，用于使用可比较对象创建队列，以及使用比较器创建队列：

• PriorityQueue（）根据元素的自然顺序对其进行排序

使用类似语义学实现您自己的类的最简单方法是始终使用比较器，并且在没有提供时仅使用自然比较器：

public class MyOrderedCollection<E> {

    private final Comparator<? super E> comparator;

    @SuppressWarnings("unchecked")
    public MyOrderedCollection() {
        this((Comparator<? super E>) Comparator.naturalOrder());
    }

    public MyOrderedCollection(Comparator<? super E> comparator) {
        this.comparator = comparator;
    }
}

如果要确保在不提供比较器的情况下在不可比较的对象上创建集合时出现编译错误，可以使用factory方法来防止：

public class MyOrderedCollection<E> {

    private final Comparator<? super E> comparator;

    public static <E extends Comparable<? super E>> MyOrderedCollection<E> of() {
        return new MyOrderedCollection<>(Comparator.naturalOrder());
    }

    public static <E> MyOrderedCollection<E> of(Comparator<? super E> comparator) {
        return new MyOrderedCollection<>(comparator);
    }

    private MyOrderedCollection(Comparator<? super E> comparator) {
        this.comparator = comparator;
    }
}

现在，您甚至不必抑制编译警告。

因此，它的工作原理如下：

MyOrderedCollection<String> x = MyOrderedCollection.of();

MyOrderedCollection<Object> y = MyOrderedCollection.of(Comparator.comparing(Object::toString));

MyOrderedCollection<Object> z = MyOrderedCollection.of(); // compilation error

Answer 2

首先，Java中的PriorityQueue已经具有采用比较器的构造函数。如果您尝试子类化PriorityQueue，那么没有必要确定是否应该使用比较器与依赖可比。提供调用匹配超类构造函数的构造函数。

但是，如果您正在创建自己的优先级队列，那么您可以在构建优先级队列时做出一次决定。

如果提供了比较器，请将其存储起来以备将来使用。如果未提供比较器，则（假设Java 8）使用比较器的实例。自然领主。

没有Java 8，实现比较器。使用适配器模式的naturalOrder。此适配器类的类型参数被限制为可比较，因此，如果添加的对象不可比较，并且未提供比较器，则可能会导致类异常。没关系；如果要允许传入比较器进行比较，则不能将优先级队列的类型参数约束为可比较，因为比较器不会以这种方式限制其类型参数。

“比较”方法只是将“比较”委托给“比较”方法。

class ComparableToComparator<T extends Comparable<? super T>> implements Comparator<T> {
    @Override
    public int compare(T a, T b) {
        return a.compareTo(b);
    }
}

（这几乎就是Comparator.naturalOrder所做的。）

无论是否传入了比较器，您都可以使用比较器。它要么是传入的对象，要么是试图将对象视为可比较对象的上述类的实例。