优先级队列的自定义比较函数

Question

我正在为优先队列实现自定义比较函数，发现 sort 和 priority queue STL 的比较函数之间存在差异。

假设，我们有几个点 (x, y)，对于这些点，我们有一个用户定义的 class。

class Point
{
   int x;
   int y;
public:
   Point(int _x, int _y)
   {
      x = _x;
      y = _y;
   }
   int getX() const { return x; }
   int getY() const { return y; }
};

自定义比较函数：

class myComparator
{
public:
    int operator() (const Point& p1, const Point& p2)
    {
        return p1.getX() > p2.getX();
    }
};

现在，如果我们将比较函数传递给 sort STL，那么它将按照 x 坐标的降序对点进行排序。

int main ()
{
    vector<Point>v;

    v.push_back(Point(10, 1));
    v.push_back(Point(1, 5));
    v.push_back(Point(2, 1));

    sort(v.begin(), v.end(), myComparator());

    for(auto p: v)
    {
        cout << "(" << p.getX() << ", " << p.getY() << ")"<<endl;
    }

    return 0;
}

输出:

(10, 1)
(2, 1)
(1, 5)

现在，如果我对优先级队列应用相同的比较函数，它将按降序排列分数。基本上，它作为 min heap.

工作

int main ()
{
    priority_queue <Point, vector<Point>, myComparator > pq;

    pq.push(Point(10, 2));
    pq.push(Point(2, 1));
    pq.push(Point(1, 5));

    while (pq.empty() == false)
    {
        Point p = pq.top();
        cout << "(" << p.getX() << ", " << p.getY() << ")";
        cout << endl;
        pq.pop();
    }

    return 0;
}

输出：

(1, 5)
(2, 1)
(10, 2)

我原以为这些点会像我在下面编写的自定义比较函数中的排序函数一样排序：

p1.getX() > p2.getX()

为什么比较函数在优先级队列中的工作方式不同？

Answer 1

std::priority_queue

Note that the Compare parameter is defined such that it returns true if its first argument comes before its second argument in a weak ordering. But because the priority queue outputs largest elements first, the elements that "come before" are actually output last. That is, the front of the queue contains the "last" element according to the weak ordering imposed by Compare.

优先级队列的自定义比较函数

Custom Compare Function for Priority Queue

c++

stl

priority-queue