I am using std::queue for implementing JobQueue class. ( Basically this class process each job in FIFO manner). In one scenario, I want to clear the queue in one shot( delete all jobs from the queue). I don't see any clear method available in std::queue class.
How do I efficiently implement the clear method for JobQueue class ?
I have one simple solution of popping in a loop but I am looking for better ways.
//Clears the job queue
void JobQueue ::clearJobs()
{
// I want to avoid pop in a loop
while (!m_Queue.empty())
{
m_Queue.pop();
}
}
This question is related to
c++
data-structures
stl
queue
You could create a class that inherits from queue and clear the underlying container directly. This is very efficient.
template<class T>
class queue_clearable : public std::queue<T>
{
public:
void clear()
{
c.clear();
}
};
Maybe your a implementation also allows your Queue object (here JobQueue
) to inherit std::queue<Job>
instead of having the queue as a member variable. This way you would have direct access to c.clear()
in your member functions.
Author of the topic asked how to clear the queue "efficiently", so I assume he wants better complexity than linear O(queue size). Methods served by David Rodriguez, anon have the same complexity:
according to STL reference, operator =
has complexity O(queue size).
IMHO it's because each element of queue is reserved separately and it isn't allocated in one big memory block, like in vector. So to clear all memory, we have to delete every element separately. So the straightest way to clear std::queue
is one line:
while(!Q.empty()) Q.pop();
Apparently, there are two most obvious ways to clear std::queue
: swapping with empty object and assignment to empty object.
I would suggest using assignment because it simply faster, more readable, and unambiguous.
I measured performance using following simple code and I found that swapping in C++03 version works 70-80% slower than assignment to an empty object. In C++11 there is no difference in performance, however. Anyway, I would go with assignment.
#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;
}
Assuming your m_Queue
contains integers:
std::queue<int>().swap(m_Queue)
Otherwise, if it contains e.g. pointers to Job
objects, then:
std::queue<Job*>().swap(m_Queue)
This way you swap an empty queue with your m_Queue
, thus m_Queue
becomes empty.
In C++11 you can clear the queue by doing this:
std::queue<int> queue;
// ...
queue = {};
Using a unique_ptr
might be OK.
You then reset it to obtain an empty queue and release the memory of the first queue.
As to the complexity? I'm not sure - but guess it's O(1).
Possible code:
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
I'd rather not rely on swap()
or setting the queue to a newly created queue object, because the queue elements are not properly destroyed. Calling pop()
invokes the destructor for the respective element object. This might not be an issue in <int>
queues but might very well have side effects on queues containing objects.
Therefore a loop with while(!queue.empty()) queue.pop();
seems unfortunately to be the most efficient solution at least for queues containing objects if you want to prevent possible side effects.
Another option is to use a simple hack to get the underlying container std::queue::c
and call clear
on it. This member must be present in std::queue
as per the standard, but is unfortunately protected
. The hack here was taken from this answer.
#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';
}
I do this (Using C++14):
std::queue<int> myqueue;
myqueue = decltype(myqueue){};
This way is useful if you have a non-trivial queue type that you don't want to build an alias/typedef for. I always make sure to leave a comment around this usage, though, to explain to unsuspecting / maintenance programmers that this isn't crazy, and done in lieu of an actual clear()
method.
Yes - a bit of a misfeature of the queue class, IMHO. This is what I do:
#include <queue>
using namespace std;;
int main() {
queue <int> q1;
// stuff
q1 = queue<int>();
}
Source: Stackoverflow.com