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