0

El objetivo es crear una cola de prioridad de pares de enteros ( pair<int,int> ) que ordene de menor a mayor mirando el segundo elemento del par ( second() )

INPUT:

<5,8>
<2,4>
<3,9>

Estado de la cola de prioridad deseada después de insertar los elementos:

top -> <2,4> , <5,8> , <3,9>

Estado real de la cola al ejecutar el código:

top -> <5,8> , <3,9> , <2,4>

Como se puede observar, el criterio que sigue la cola para ordenar no tiene en cuenta el segundo elemento. Mas bien ordena como hacen por defecto las colas de prioridad.

Por que no tiene en cuenta la sobrecarga del operador '<' ? Como podría solucionarlo?

Código:

#include<bits/stdc++.h>
using namespace std;


bool operator<(pair<int, int> const& c1, pair<int, int> const& c2) {
    if (c1.second < c2.second) return true;
    else if (c2.second < c1.second) return false;
    else return c1.first < c2.first;
}

int main() {
    int n, a, b;

    cin >> n;
    priority_queue<pair<int, int>> pq;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        pq.push({ a,b });
    }

    
    cout << pq.top().first << pq.top().second << endl;
    pq.pop();
    cout << pq.top().first << pq.top().second << endl;
    pq.pop();
    cout << pq.top().first << pq.top().second << endl;
    pq.pop();
}

1 respuesta 1

2

Si observamos cómo se define la std::priority_queue:

std::priority_queue

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

Vemos que el comparador usado por defecto es std::less. En otras palabras: no está usando un operador definido externamente si no que usa un comparador interno. Para que use un comparador personalizado se lo debes pasar:

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

using namespace std;

// Alias del tipo de dato almacenado, por comodidad.
using pair_i = pair<int, int>;
// Función de comparación.
bool compare(const pair_i &c1, const pair_i &c2) {
    if (c1.second < c2.second) return true;
    else if (c2.second < c1.second) return false;
    else return c1.first < c2.first;
}

int main() {
    // Alias de la queue, por comodidad
    using pq_pair_i = priority_queue<pair_i, vector<pair_i>, decltype(compare)*>;
    //   Tipo de dato almacenado --> ^^^^^^  ^^^^^^^^^^^^^^  ^^^^^^^^^^^^^^^^^^
    //                     Contenedor subyacente____/                /
    //                                    Función de comparación____/

    pq_pair_i pq(compare);

    pq.push({5,8});
    pq.push({2,4});
    pq.push({3,9});
    
    cout << pq.top().first << pq.top().second << endl;
    pq.pop();
    cout << pq.top().first << pq.top().second << endl;
    pq.pop();
    cout << pq.top().first << pq.top().second << endl;
    pq.pop();

    return 0;
}

Por cierto, comprueba tu función de comparación pues ordena a la inversa de como describes.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.