Estoy creando un std::priority_queue usando std::vector como contenedor.

Parece que la cola de prioridad crea una copia del contenedor que se le pasa en su constructor, ya que los cambios realizados en el contenedor después de construir la cola no se reflejan en el contenedor de la cola.

Por ejemplo, si llamo a clear() en mi contenedor, la cola de prioridad permanece llena.

¿Hay alguna forma de mantener una referencia al contenedor interno de la cola de prioridad después de la construcción?

1
Tyson 25 jul. 2017 a las 19:13

2 respuestas

La mejor respuesta

std::priority_queue es uno de los pocos contenedores estándar diseñados para derivarse.

Tiene un miembro protegido c que es el contenedor.

Puede derivar de la cola y usar c en su clase derivada.

Si mutas el contenedor, recuerda que en realidad es un heap y necesita que se le apliquen las funciones de montón apropiadas antes de dejar tu método.

#include <queue>
#include <algorithm>

struct my_special_queue : std::priority_queue<int>
{
    using underlying_queue = std::priority_queue<int>;

    // re-use all constructors
    using underlying_queue::underlying_queue;

    // add a clear method

    void clear()
    {
        underlying_queue::c.clear();
    }

    void remove_all_odd_numbers()
    {
        c.erase(std::remove_if(c.begin(), c.end(), 
                                [](auto&&x) { return (x % 2) == 1; }), 
                                c.end());
        std::make_heap(c.begin(), c.end(), 
                        underlying_queue::comp);
    }

};

int main()
{
    my_special_queue q;

    // standard priority_queue methods
    q.push(1);
    q.push(2);
    q.push(9);
    q.push(6);
    q.push(4);
    q.push(7);

    if (not q.empty()) {
        q.top();
        q.pop();
    }

    // apply our custom functions    
    q.clear();
    q.remove_all_odd_numbers();
}
1
Richard Hodges 25 jul. 2017 a las 16:59

No, no hay forma de hacer eso. La razón es que si tuviera acceso al contenedor subyacente, podría acceder a él y modificarlo como si no fuera una cola de prioridad, lo que sería muy confuso y contrario al caso de uso deseado de std::priority_queue, que es para proporcionar una cola.

Esto es desde el punto de vista de los Estándares, tal vez su implementación tenga una extensión que permita ese acceso, pero eso sería muy sorprendente, y no conozco ninguna implementación que lo haga. Debe consultar la documentación apropiada para estar seguro.

Habiendo dicho eso, siempre puede proporcionar un contenedor alrededor de std::priority_queue, que almacena el contenedor. Pero no lo recomendaría, (como se dijo anteriormente) podría cambiarlo sin la semántica de la cola.

5
Rakete1111 25 jul. 2017 a las 16:18