Reference: Invariant for comparators in collections

Question

Consider the following Java example:

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

So, we insert elements into the queue, and then change the result of their comparison (initially 0 is less than 1, and after a[1] = 0 we have that 1 is less than 0). As I understand, in this case the behavior of the priority queue is unspecified (this is a typical mistake in implementation of the Dijkstra's algorithm). I say that the following invariant (contract?) is violated:

If x and y are in the priority queue, then the result of their comparison must remain unchanged until one of these elements is removed from the priority queue.

What concerns me is that I can't find any mention of this in either C++ or Java documentation. I guess both documentations assume that comparators are "immutable", i.e. the result of comparison of x and y never changes. "Immutable" comparators are certainly a good practice (although I also didn't find any mention of that in the documentation), but not what happens in the above example.

I request a reference to either C++ or Java documentation which discusses the issue. I expect documentation to specify all the requirements to guarantee that the data structures works correctly, so it is very weird that I can't find this one. To conform with the SO expectations (namely that the answer still remains valid after the link dies), I think it also makes sense to paste the text from the link into the answer.

Answer 1

For c++, the operations of std::priority_queue are defined in terms of std::make_heap, std::push_heap, std::pop_heap. See basically all of [priority.queue] 24.6.7.

The comparison you provide must be a strict weak ordering (in the mathematical sense); if it breaks said ordering, it isn't a valid strict weak ordering.

push/pop in turn specifies that the range it is operating on is a valid heap (with an extra element for push) with respect to that strict weak ordering.

As an example, [push.heap] 27.8.8.2/2 says the preconditions for push_heap are:

Preconditions: The range [first, last - 1) is a valid heap with respect to comp and proj. For the overloads in namespace std, RandomAccessIterator meets the Cpp17ValueSwappable requirements ([swappable.requirements]) and the type of *first meets the Cpp17MoveConstructible requirements (Table 31) and the Cpp17MoveAssignable requirements (Table 33).

So if you make the container not be a valid heap by modifying the elements mid-way through using a priority queue, you violate the preconditions of push/pop, and the C++ standard does not constrain the behavior of the program anymore. (Undefined behavior escape clause!)

If you modify the elements in such a way that the container still contains a valid heap, but one that is utterly different than the heap it was on the last time you interacted with it, you are 100% ok.

This is different than how std::map/set and std::unordered_map/set are defined, where it explicitly disallows messing with the ordering.

Container adapters in C++ are a bit strange. It does mean they can be wrapped around your own utterly strange container and nothing strange happens.