c++ - programacion - insertar elemento en una cola

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

Question

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 sola 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 hacer estallar en un bucle, pero estoy buscando mejores maneras.

//Clears the job queue
void JobQueue ::clearJobs()
{
// I want to avoid pop in a loop
while (!m_Queue.empty())
{
m_Queue.pop();
}
}

Answer 1

''David Rodriguez'', ''anon'' El autor del tema preguntó cómo borrar la cola "de manera eficiente", así que supongo que quiere una mayor complejidad que la O lineal (tamaño de la cola). Los métodos que sirvió tienen la misma complejidad: de acuerdo con la referencia stl, el operador = 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 borrar stl::queue es una línea:

while(!Q.empty()) Q.pop();

Answer 2

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

Yo sugeriría usar la asignación porque simplemente es más rápida, más legible y no ambigua.

Medí el rendimiento usando un código simple y encontré 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;
}

Answer 3

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

std::queue<int> queue = {};

Answer 4

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

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

Answer 5

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 a también le permite a su objeto Queue (aquí JobQueue ) heredar std::queue<Job> lugar de tener la cola como una variable miembro. De esta forma, tendrías acceso directo a c.clear() en tus funciones de miembro.

Answer 6

Sí, una especie de error 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>();
}

Answer 7

Una expresión 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 manera de borrar la memoria contenida en algunos contenedores (std :: vector)

Answer 8

Usar un unique_ptr podría estar bien.
A continuación, lo restablece para obtener una cola vacía y liberar 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