std priority queue 什么时候比较值？

Question

我有一个优先级队列，比较函数引用了一个被多个线程访问的值。所以它必须由互斥锁保护。除了我不知道这个比较函数什么时候是运行。是运行当我压入一个值还是当我弹出一个值？下面的示例代码。

#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();
    }

}

Answer 1

要回答这个问题，如果没有记录任何事情都可能发生（然后我们就无法推断何时调用比较器）。

如果我们看一下 cppreference，push is defined in terms of push_heap，它会将元素重新组织到一个堆中。鉴于它随后需要重组，我们可以推断它调用了比较器。类似的情况发生在 pop 中，它调用 pop_heap，它再次修改底层堆。再次调用比较器。

所以上面暗示你需要一个关于两者的关键部分（但是请注意关于在 pq 包含元素时改变比较函数的行为是否真的安全的评论).

std priority queue 什么时候比较值？

When does std priority queue compare the values?

c++

multithreading

mutex

priority-queue