¿Cómo borro la cola std :: de manera eficiente?

166

Estoy usando std :: queue para implementar la clase JobQueue. (Básicamente, esta clase procesa cada trabajo de manera FIFO). En un escenario, quiero borrar la cola de una vez (eliminar todos los trabajos de la cola). No veo ningún método claro disponible en la clase std :: queue.

¿Cómo implemento eficientemente el método claro para la clase JobQueue?

Tengo una solución simple de aparecer en un bucle pero estoy buscando mejores formas.

//Clears the job queue
void JobQueue ::clearJobs()
 {
  // I want to avoid pop in a loop
    while (!m_Queue.empty())
    {
        m_Queue.pop();
    }
}
aJ.
fuente
3
Nota dequeadmite clear
bobobobo

Respuestas:

257

Un modismo común para borrar contenedores estándar es intercambiar con una versión vacía del contenedor:

void clear( std::queue<int> &q )
{
   std::queue<int> empty;
   std::swap( q, empty );
}

También es la única forma de borrar realmente la memoria contenida en algunos contenedores (std :: vector)

David Rodríguez - dribeas
fuente
41
Mejor aún es std::queue<int>().swap(q). Con copiar y cambiar idioma, todo esto debería ser equivalente a q = std::queue<int>().
Alexandre C.
12
Si bien std::queue<int>().swap(q)es equivalente al código anterior, q = std::queue<int>()no es necesario que sea equivalente. Dado que no hay transferencia de propiedad en la asignación de la memoria asignada, algunos contenedores (como el vector) podrían simplemente llamar a los destructores de los elementos previamente almacenados y establecer el tamaño (u operación equivalente con los punteros almacenados) sin liberar realmente la memoria.
David Rodríguez - dribeas
66
queueno tiene un swap(other)método, por lo queue<int>().swap(q)que no compila. Creo que tienes que usar el genérico swap(a, b).
Dustin Boswell
3
@ ThorbjørnLindeijer: en C ++ 03 tiene razón, en C ++ 11 las colas tienen swap como función miembro, y además hay una sobrecarga de función libre que intercambiará dos colas del mismo tipo.
David Rodríguez - dribeas
10
@ ThorbjørnLindeijer: Desde la perspectiva de los usuarios de la cola original, esos elementos no existen. Tiene razón en que serán destruidos uno tras otro y el costo es lineal, pero nadie más que la función local no puede acceder a ellos. En un entorno multiproceso, bloquearía, intercambiaría una cola no temporal con la original, desbloquearía (para permitir accesos concurrentes) y dejaría morir la cola intercambiada. De esta manera, puede mover el costo de destrucción fuera de la sección crítica.
David Rodríguez - dribeas
46

Sí, una mala característica de la clase de cola, en mi humilde opinión. Esto es lo que hago:

#include <queue>
using namespace std;;

int main() {
    queue <int> q1;
    // stuff
    q1 = queue<int>();  
}
Mark Ransom
fuente
8
@Naszta Por favor, explique cómo swapes "más efectivo"
bobobobo
@bobobobo:q1.swap(queue<int>());
Naszta
12
q1=queue<int>();es a la vez más corto y más claro (en realidad no lo estás intentando .swap, lo estás intentando .clear).
bobobobo
28
Con el nuevo C ++, solo q1 = {}es suficiente
Mykola Bogdiuk
2
@Ari sintaxis (2) en list_initialization y (10) en operator_assignment . El queue<T>constructor predeterminado coincide con la lista de argumentos vacía {}y es implícito, por lo que se llama, luego q1.operator=(queue<T>&&)consume el recién creadoqueue
Mykola Bogdiuk
26

El autor del tema preguntó cómo borrar la cola "eficientemente", por lo que supongo que quiere una mayor complejidad que el O lineal (tamaño de la cola) . Los métodos servidos por David Rodríguez , anon tienen la misma complejidad: de acuerdo con la referencia de STL, operator =tiene complejidad O (tamaño de la cola) . En mi humilde opinión es porque cada elemento de la cola se reserva por separado y no se asigna en un gran bloque de memoria, como en el vector. Entonces, para borrar toda la memoria, tenemos que eliminar cada elemento por separado. Entonces, la forma más directa de despejar std::queuees una línea:

while(!Q.empty()) Q.pop();
janis
fuente
55
No puede simplemente observar la complejidad O de la operación si está operando con datos reales. Tomaría un O(n^2)algoritmo sobre un O(n)algoritmo si las constantes en la operación lineal lo hacen más lento que el cuadrático para todos n < 2^64, a menos que tenga una buena razón para creer que tuve que buscar el espacio de direcciones IPv6 o algún otro problema específico. El rendimiento en realidad es más importante para mí que el rendimiento al límite.
David Stone
2
Esta respuesta mejor que la respuesta aceptada porque internamente hace esto de todas formas cuando se destruye. Por lo tanto, la respuesta aceptada es O (n) y además realiza asignaciones e inicializaciones adicionales para la nueva cola.
Shital Shah
Recuerde, O (n) significa menor o igual que n complejidad. Entonces, sí, en algunos casos como la cola <vector <int>>, tendrá que destruir cada elemento 1 por 1, lo que será lento de cualquier manera, pero en la cola <int>, la memoria en realidad se asigna en un gran bloque, y, por lo tanto, no necesita destruir los elementos internos, por lo que el destructor de la cola puede usar una sola operación eficiente () que casi seguramente toma menos de O (n) tiempo.
Benjamin
15

Aparentemente, hay dos formas más obvias de borrar std::queue: intercambiar con objeto vacío y asignar a objeto vacío.

Sugeriría usar la asignación porque es simplemente más rápida, más legible y sin ambigüedades.

Medí el rendimiento usando el siguiente código simple y descubrí que el intercambio en la versión C ++ 03 funciona un 70-80% más lento que la asignación a un objeto vacío. Sin embargo, en C ++ 11 no hay diferencia en el rendimiento. De todos modos, iría con la asignación.

#include <algorithm>
#include <ctime>
#include <iostream>
#include <queue>
#include <vector>

int main()
{
    std::cout << "Started" << std::endl;

    std::queue<int> q;

    for (int i = 0; i < 10000; ++i)
    {
        q.push(i);
    }

    std::vector<std::queue<int> > queues(10000, q);

    const std::clock_t begin = std::clock();

    for (std::vector<int>::size_type i = 0; i < queues.size(); ++i)
    {
        // OK in all versions
        queues[i] = std::queue<int>();

        // OK since C++11
        // std::queue<int>().swap(queues[i]);

        // OK before C++11 but slow
        // std::queue<int> empty;
        // std::swap(empty, queues[i]);
    }

    const double elapsed = double(clock() - begin) / CLOCKS_PER_SEC;

    std::cout << elapsed << std::endl;

    return 0;
}
tim
fuente
8

En C ++ 11 puede borrar la cola haciendo esto:

std::queue<int> queue;
// ...
queue = {};
kolage
fuente
4

Puede crear una clase que herede de la cola y borrar el contenedor subyacente directamente. Esto es muy eficiente.

template<class T>
class queue_clearable : public std::queue<T>
{
public:
    void clear()
    {
        c.clear();
    }
};

Tal vez su implementación también permita que su objeto Queue (aquí JobQueue) herede en std::queue<Job>lugar de tener la cola como una variable miembro. De esta manera, tendría acceso directo a c.clear()sus funciones de miembro.

typ1232
fuente
9
Los contenedores STL no están diseñados para ser heredados de. En este caso, probablemente esté bien porque no está agregando ninguna variable miembro adicional, pero no es algo bueno en general.
bstamour
2

Suponiendo que m_Queuecontiene enteros:

std::queue<int>().swap(m_Queue)

De lo contrario, si contiene, por ejemplo, punteros a Jobobjetos, entonces:

std::queue<Job*>().swap(m_Queue)

De esta manera, intercambia una cola vacía con su m_Queue, por lo tanto, m_Queuequeda vacía.

Dániel László Kovács
fuente
1

Prefiero no confiar swap()o configurar la cola en un objeto de cola recién creado, porque los elementos de la cola no se destruyen correctamente. Llamar pop()invoca al destructor para el objeto del elemento respectivo. Esto podría no ser un problema en las <int>colas, pero podría tener efectos secundarios en las colas que contienen objetos.

Por lo tanto, un bucle con while(!queue.empty()) queue.pop();parece ser, por desgracia, la solución más eficiente, al menos para las colas que contienen objetos si desea evitar posibles efectos secundarios.

Marste
fuente
3
swap()o la asignación llama al destructor en la cola ahora desaparecida, que llama a los destructores de todos los objetos en la cola. Ahora, si su cola tiene objetos que en realidad son punteros, ese es un problema diferente, pero un simple pop()tampoco lo ayudará allí.
jhfrontz
¿Por qué lamentablemente? Es elegante y simple.
OS2
1

Hago esto (usando C ++ 14):

std::queue<int> myqueue;
myqueue = decltype(myqueue){};

Esta forma es útil si tiene un tipo de cola no trivial para el que no desea construir un alias / typedef. Sin embargo, siempre me aseguro de dejar un comentario sobre este uso para explicar a los programadores desprevenidos / de mantenimiento que esto no es una locura y que se realiza en lugar de un clear()método real .

void.pointer
fuente
¿Por qué declara explícitamente el tipo en el operador de asignación? Supongo que myqueue = { };funcionará bien.
Joel Bodenmann
0

Usar un unique_ptrpodría estar bien.
Luego lo reinicia para obtener una cola vacía y libera la memoria de la primera cola. ¿En cuanto a la complejidad? No estoy seguro, pero supongo que es O (1).

Código posible:

typedef queue<int> quint;

unique_ptr<quint> p(new quint);

// ...

p.reset(new quint);  // the old queue has been destroyed and you start afresh with an empty queue
Ronnie
fuente
Si elige vaciar la cola eliminándola, está bien, pero esa no es la cuestión, y no veo por qué entra unique_ptr.
manuell
0

Otra opción es usar un truco simple para obtener el contenedor subyacente std::queue::cy llamarlo clear. Este miembro debe estar presente std::queuesegún el estándar, pero desafortunadamente está presente protected. El truco aquí fue tomado de esta respuesta .

#include <queue>

template<class ADAPTER>
typename ADAPTER::container_type& get_container(ADAPTER& a)
{
    struct hack : ADAPTER
    {
        static typename ADAPTER::container_type& get(ADAPTER& a)
        {
            return a .* &hack::c;
        }
    };
    return hack::get(a);
}

template<typename T, typename C>
void clear(std::queue<T,C>& q)
{
    get_container(q).clear();
}

#include <iostream>
int main()
{
    std::queue<int> q;
    q.push(3);
    q.push(5);
    std::cout << q.size() << '\n';
    clear(q);
    std::cout << q.size() << '\n';
}
Ruslan
fuente