如何直观理解C++优先级队列容器comparator中large than/less than operator

Question

我总是对为优先级队列容器定义比较器感到困惑，不知道如何理解它。例如，我有一个 vector 的 pair<int,int>，我想按其第二个字段值对这些对进行降序排序。

因此代码如下所示：

 struct Compare
    {
        bool operator()(pair<int,int> const &p1, pair<int,int> const &p2) const
        {
            return p1.second < p2.second;
        }
    };



priority_queue<pair<int,int>,vector<pair<int,int> >, Compare> pqueue;

这里的运算符"<"怎么理解，因为我第一次觉得应该是">"，只好根据结果改了。为什么降序是 "<" 而不是 ">"？我只是想在下次使用 priority_queue 时在第一次拍摄时就把它弄好。谢谢你。

Answer 1

优先级队列 returns top 元素基于比较运算符，意思是当你一项一项检索时，你在降序顺序。

比较运算符的含义始终停留在"less than"，意思是当compare(A, B)为真时，B的优先级高于A，并且会更早地从优先队列中返回。

反转比较函数会反转您从优先队列中获取项目的顺序。具体来说，使用 > 代替 < 会将顺序反转为升序。

Answer 2

在某种程度上，您感到有点不安是对的，因为我们可以将最高优先级与更高的值相关联，这可能是违反直觉的。

但是在优先级队列中，通常假定优先级顺序是从最低值到最高值。即集合中最小的元素优先级最高，依此类推

我认为这个 "inversion" 的直观原因与许多贪婪算法优先考虑较低成本的事实有关，为了管理它，这些算法可以使用成本优先级队列。

如何直观理解C++优先级队列容器comparator中large than/less than operator

How to intuitively understand larger than/less than operator in comparator of C++ priority queue container

c++

priority-queue