2

Estou estudando priority_queue e surgiu uma duvida, caso eu queira inserir na fila de prioridade um par de elementos, como faço para que a fila mostra o elemento com menor numero e se tiver dois números iguais ele desempate pelo segundo identificador?

Ex: Quero inserir na fila os elementos identificados por (i,j): (5,1) (3,2) (6,3) (3,4)

Eu queria que minha fila de prioridade retornasse sempre o menor elemento i e caso tenha dois elementos i iguais, desempatasse pelo segundo elemento que é o j

Saída:

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

Obs: Nunca irá existir um j igual

Alguém tem alguma dica ? tentei por pair, mas não estou sabendo fazer corretamente

2
  • O que é inserido na queue ? Esses valores fazem parte de alguma classe ou estrutura ? Tem como colocar o código que está a usar ?
    – Isac
    16/12/2018 às 16:49
  • Na queue é inserido um pair<int,int>, os valores não fazem parte de uma estrutura. Eu não tenho o código, pois estou criando ainda, como surgiu essa duvida, eu travei
    – user103010
    16/12/2018 às 19:22

1 Resposta 1

1

É possivel de controlar a forma como os elementos são colocados numa priority_queue se utilizar uma função personalizada no terceiro parametro de template. Essa função tem de ser fornecida por meio do operador () de uma classe ou através de uma função solta utilizando std::function que é o exemplo eu vou seguir.

A função que compara os dois pontos é que vai fazer a lógica que indicou de quando os dois i forem iguais comparar pelo 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;
    }
}

Fiz uso de um typedef para simplificar um pouco o tipo e a criação da priority_queue que vem agora a seguir.

A utilização no main seria da seguinte forma:

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;
}

A fila foi criada com 3 parametros do template:

  1. O tipo
  2. O contentor onde serão colocados os elementos
  3. O tipo do comparador

O tipo do comparador foi definido como:

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

Que seria equivalente a ter escrito:

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

Ainda na mesma instrução o comparador é passado na construção, no fim:

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

O resultado obtido:

3 2
3 4
5 1
6 3

Veja no Ideone

2
  • Muito obrigado !!
    – user103010
    17/12/2018 às 2:47
  • Usar std::function aqui não tem vantagem alguma sobre usar um functor. 19/12/2018 às 16:41

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .