Приоритетная очередь пар в обратном порядке

Я хочу сделать что-то вроде этого:

priority_queue< pair<int, int>, vector<int>, greater<int> > Q;

Это отлично работает, если тип, который я сравниваю, int, то есть:

priority_queue< int, vector<int>, greater<int> > Q;

однако, очевидно, с pair<int, int>, нет способа сравнения пар в очереди со стандартным >. Мне было интересно, что я должен делать? Как реализовать перегруженный > или есть ли другой способ создать очередь приоритетов пар с наименьшим pair.second, находящимся в верхней части очереди?

Ответ 1

Вы пробовали это?

typedef pair<int, int> P;
priority_queue< P, vector<P>, greater<P> > Q;

Это даст обратный порядок нормального operator< для pair<int, int>, который начнется с наименьшего first, связанного с наименьшим second.

Если вы хотите отсортировать по наименьшему second и first second (!), то вам понадобится новый сортирующий функтор:

struct Order
{
    bool operator()(P const& a, P const& b) const
    {
        return a.second < b.second || a.second == b.second && a.first < b.first;
    }
}

Затем используйте:

priority_queue< P, vector<P>, Order > Q;

Ответ 2

Вы должны создать свой собственный класс домена, а не использовать pair<int, int> здесь, насколько я могу судить. Затем вы можете перегрузить > по своему усмотрению.