添加不可比较的对象时，PriorityQueue 的大小会增加

Question

考虑以下代码：

import java.util.PriorityQueue;

public class Test {

    public static void main(String argv[]) {
        PriorityQueue<A> queue = new PriorityQueue<>();
        System.out.println("Size of queue is " + queue.size()); // prints 0
        queue.add(new A()); // does not throw an exception
        try {
            queue.add(new A()); // this time, an exception is thrown
        } catch (ClassCastException ignored) {
            System.out.println("An exception was thrown");
        }
        System.out.println("Size of queue is " + queue.size()); // prints 2
    }

} 

class A { } // non-comparable object

在此代码中，首先将不可比较的对象添加到 PriorityQueue。此代码工作正常，。

然后，第二个对象被添加到这个队列中。根据 PriorityQueue.add Javadoc 的预期，抛出 ClassCastException 因为第二个对象与第一个对象不可比。

然而，尽管抛出异常，但似乎队列的大小增加了：第二个打印语句输出 2 而不是 1。

这种行为是预期的吗？如果是这样，这背后的原因是什么？记录在哪里？

Answer 1

offer 的源代码（由 add 调用）揭示了将非 Comparable 对象传递给 PriorityQueue 时出现的无效状态没有 Comparator.

public boolean More offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

在调用 siftUp 之前修改了大小。 siftUp 方法，通常负责将元素插入队列，（最终）抛出 ClassCastException，但大小已被修改，导致大小不正确。

似乎没有记录表明 size 即使出现 ClassCastException 也会递增。一个简单的修复方法是将行 size = i + 1; 放在 if/else 之后和 return 语句之前。

Answer 2

根据 GrepCode.com 的 version of the source，看起来这可能是他们实现中的一个错误。

add 函数所做的就是调用

public boolean add(E e) {
    return offer(e);
}

报价函数如下所示

public boolean offer(E e) {
    if (e == null)
        throw new NullPointerException();
    modCount++;
    int i = size;
    if (i >= queue.length)
        grow(i + 1);
    size = i + 1;
    if (i == 0)
        queue[0] = e;
    else
        siftUp(i, e);
    return true;
}

您会注意到在通过 siftUp 实际插入项目之前调用了 size = i + 1。调用 siftUp 时，它做的第一件事是尝试转换为 Comparable 并在实际插入项目之前抛出异常。因此它会增加大小而不实际插入项目。

添加不可比较的对象时，PriorityQueue 的大小会增加

Size of PriorityQueue increases when non-comparable objects are added

java

priority-queue