Sort from lowest to highest in priority_queue by breaking second element, is it possible?

1

I am studying priority_queue and a question has arisen, if I want to insert a pair of elements in the priority queue, how do I make the queue show the element with the lowest number and if it has two numbers, does it break the second identifier?

Ex: I want to insert in the queue the elements 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, jump to the second element that is j

Output:

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

Note: There will never be an equal j

Does anyone have any tips? I tried pair , but I'm not sure how to do it correctly

    
asked by anonymous 16.12.2018 / 15:00

1 answer

1

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

The function that compares the two points is that it will do the logic that indicated when the two i are equal compare 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 the priority_queue creation that comes next.

The usage in 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;
}

The queue was created with 3 template parameters:

  • The type
  • The container where the elements will be placed
  • The comparator type
  • Comparator type was 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:

    3 2
    3 4
    5 1
    6 3
    

    See it on Ideone

        
    17.12.2018 / 01:14