参考：集合中比较器的不变性

Question

考虑以下 Java 示例：

int[] a = new int[]{1, 2};
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Comparator.comparingInt(i -> a[i]));
pq.add(0);
pq.add(1);
a[1] = 0;
System.out.println(pq.peek()); // Prints 0

因此，我们将元素插入到队列中，然后更改它们比较的结果（最初

0

小于

1

，在

a[1] = 0

之后，

1

小于

0

）。 据我了解，在这种情况下，优先级队列的行为是未指定的（这是迪杰斯特拉算法实现中的典型错误）。 我说违反了以下不变量（合同？）：

如果

x

和

y

在优先级队列中，那么它们的比较结果必须保持不变，直到其中一个元素从优先级队列中移除。

令我担心的是，我在 C++ 或 Java 文档中都找不到任何提及这一点的内容。 我想这两个文档都假设比较器是“不可变的”，即

x

和

y

的比较结果永远不会改变。 “不可变”比较器当然是一个很好的实践（尽管我在文档中也没有找到任何提及），但不是上面示例中发生的情况。

我请求参考讨论该问题的 C++ 或 Java 文档。我希望文档能够指定所有要求，以保证数据结构正常工作，所以我找不到这个，这很奇怪。为了符合 SO 期望（即链接失效后答案仍然有效），我认为将链接中的文本粘贴到答案中也是有意义的。

Answer 1

对于 c++，

std::priority_queue

的操作是根据

std::make_heap

、

std::push_heap

、

std::pop_heap

定义的。

您提供的比较必须是严格的弱排序（在数学意义上）；如果它破坏了所述顺序，则它不是有效的严格弱顺序。

push/pop 反过来指定它正在操作的范围是一个有效的堆（带有用于推送的额外元素），相对于严格的弱排序。

因此，如果通过修改元素使容器不再是有效的堆，则违反了push/pop的前提条件，并且C++标准不再约束程序的行为。

如果您修改元素的方式使容器仍然包含有效的堆，但与您上次与之交互时所在的堆完全不同，则 100% 没问题。

这与

std::map

/

set

和

std::unordered_map

/

set

的定义方式不同，它明确禁止打乱顺序。

C++ 中的容器适配器有点奇怪。这确实意味着它们可以包裹在您自己完全陌生的容器中，并且不会发生任何奇怪的事情。