Блог

Я реализовывал пользовательскую функцию сравнения для очереди приоритетов и увидел разницу между функцией сравнения сортировки и STL очереди приоритетов.

Предположим, у нас есть пара точек (x, y), и для этих точек у нас есть определенный пользователем класс.

 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 Pointamp; p1, const Pointamp; p2)
    {
        return p1.getX() > p2.getX();
    }
};
 

Теперь, если мы передадим функцию сравнения для сортировки 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)

Теперь, если я применю ту же функцию сравнения для приоритетной очереди, у нее будут точки в порядке убывания. По сути, он работает как минимальная куча.

 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()
 

Почему функция сравнения работает по-разному в очереди приоритетов?

std::priority_queue

Обратите внимание, что параметр сравнения определен таким образом, что он возвращает true, если его первый аргумент предшествует второму аргументу в слабом порядке. Но поскольку приоритетная очередь выводит самые большие элементы первыми, элементы, которые «приходят раньше», фактически выводятся последними. То есть передняя часть очереди содержит «последний» элемент в соответствии со слабым порядком, налагаемым Compare .