I have a priority queue and the compare function references a value accessed by multiple threads. So it has to be protected by a mutex. Except I don't know when this compare function is ran. Is it ran when I push a value or when I pop a value? Example code below.

#include <iostream>
#include <queue>
#include <mutex>


using namespace std;


int main()
{   
    int compare = 7;
    mutex compare_m;


    auto cmp = [&](int a, int b) {return abs(compare - a)>=abs(compare-b);};
    priority_queue<int, vector<int>, decltype(cmp)> x(cmp);
    mutex x_m;

    //in thread
    {   
        scoped_lock m1(x_m);
        //do I need this?
        scoped_lock m(compare_m);
        x.push(6);
    }

    //in thread
    {   
        scoped_lock m1(x_m);
        //do I need this?
        scoped_lock m(compare_m);
        x.pop();
    }

}

CodePudding user response：

To answer the question, if it is not documented anything can happen (and then we cannot then reason about when comparator is invoked).

If we take a look into cppreference, push is defined in terms of push_heap, which then reorganizes the elements into a heap. Given it then needs to reorganize, we can reason that it invokes the comparator. A similar situation happens with pop, that invokes pop_heap, which again modifies the underlying heap. So again, invoking comparator.

So the above implies you need a critical section on both (however please notice the comments regarding whether it is actually safe to change the behaviour of comparison function while the pq contains elements).