Sort from minor to major in priority_queue unpacking by second element, is it possible?

Question

I’m studying priority_queue and a question has arisen, if I want to insert in the priority queue a pair of elements, how do I so that the queue shows the element with the smallest number and if it has two equal numbers it unpacks by the second identifier?

Ex: I want to insert the items identified by (i,j): (5,1) (3,2) (6,3) (3,4)

I wanted my priority queue to always return the smallest element i and if it has two equal elements i, unpack by the second element j

Exit:

(3,2)
(3,4)
(5,1)
(6,3)

Note: There will never be an equal j

Does anyone have any tips ? I tried to pair, but I don’t know how to do it properly

Answer 1

It is possible to control how the elements are placed in a priority_queue if using a custom function in the third template parameter. This function has to be provided via the operator () of a class or through a loose function using std::function which is the example I will follow.

The function that compares the two points is that will make the logic you indicated when the two i are equal to be compared by j:

#include <iostream>
#include <vector>
#include <queue>
#include <functional>

typedef std::pair<int, int> parInts;

bool comparador (parInts ponto1, parInts ponto2){
    if (ponto1.first == ponto2.first){ //se o i é igual compara pelo j
        return ponto1.second > ponto2.second;
    }
    else { //se o i é diferente compara por esse i
        return ponto1.first > ponto2.first;
    }
}

I made use of a typedef to simplify somewhat the type and creation of the priority_queue that comes next.

The use in the main would be as follows:

int main () {
    std::priority_queue<parInts, std::vector<parInts>, std::function<bool(parInts, parInts)>> fila(comparador);
    //                   ^--tipo        ^--contentor              ^--tipo do comparador            ^--comparador

    fila.push(std::make_pair(5, 1));
    fila.push(std::make_pair(3, 2));
    fila.push(std::make_pair(6, 3));
    fila.push(std::make_pair(3, 4));

    while (!fila.empty()){
        std::pair<int, int> ponto = fila.top();
        std::cout << ponto.first << " " << ponto.second << std::endl;
        fila.pop();
    }

    return 0;
}

Queue created with 3 template parameters:

1. The guy
2. The container in which the
3. The type of comparator

Comparator type has been defined as:

std::function<bool(parInts, parInts)>

That would be equivalent to having written:

std::function<bool(std::pair<int, int>, std::pair<int, int>)>

Still in the same instruction the comparator is passed in the construction, at the end:

... std::function<bool(parInts, parInts)>> fila(comparador);
//                                                ^-- aqui

The result obtained:

3 2
3 4
5 1
6 3

Check it out at Ideone