I was refreshing some algorithm knowledge and implementing djikstra in c++ and saw this seemingly broken behavior in std::priority_queue. Can anyone shed some light on why I might be seeing this?

I created a priority_queue with a custom comparator, to allow me to insert indices into the priority_queue and prioritize them based on the minimum values in another vector dist. There is no easy/cheap way to remove elements and reinsert them, so when a distance is updated, I’m just reinserting the index into the queue and will have multiple entries for it (which I can skip as I visit them later, if I’ve seen them already).

However, when I update a dist and reinsert the index it is not correctly ending up on top of the queue.

I’ve pasted a minimal repro below. Does anyone see anything that might be causing this? I am building this with clang 14.0.6 x86_64-pc-windows-msvc in VS Code.

#include <cassert>
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    const int N = 9;
    
    // create d vector with INT_MAX, but last will be 0  
    vector<int> dist(N, INT_MAX);
    dist.back() = 0;

    // cmp for indices, so that index with lowest d element gets pri
    auto cmp = [&](int a, int b) { return dist[a] > dist[b]; };
    priority_queue<int, vector<int>, decltype(cmp)> q(cmp);

    // fill q with indices 0-(N-1), should be prioritized by d
    for (int i = 0; i < N; ++i) { q.push(i); }

    // start state seen in debugger
    // dist = {MAX, MAX, MAX, MAX, MAX, MAX, MAX, MAX, 0}
    // q.c = {8, 0, 2, 1, 4, 5, 6, 7, 3}

    // 8 is top index, since d[8] is 0, everything else is INT_MAX
    // This assert is passing
    assert(q.top() == 8);
    q.pop();

    // set d[0] to 0 and add another 0 entry to the queue
    // this should end on top, b/c d[0] == 0 and others are INT_MAX
    dist[0] = 0;
    q.push(0);

    // final state seen in debugger
    // dist = {0, MAX, MAX, MAX, MAX, MAX, MAX, MAX, 0}
    // q.c = {2, 0, 6, 0, 4, 5, 3, 7, 1}

    // THIS FAILS! because q.top() returns 2
    assert(q.top() == 0);

    return 0;
}

>Solution :

A comparison function is required to be a predicate. And a predicate is required to return the same answer for comparing a and b. Always, no matter what. So if you do something that changes the result of that answer, you get undefined behavior.

If you want to do this, then you’re going to need to explicitly use a container (like vector) and re-sort it every time your sort criteria changes. priority_queue doesn’t give you that power.