218

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();
    }
}
Improve this question
1
  • 4
    Note deque supports clear Commented May 24, 2013 at 0:37

12 Answers 12

Reset to default
330

A common idiom for clearing standard containers is swapping with an empty version of the container:

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

It is also the only way of actually clearing the memory held inside some containers (std::vector)

Improve this answer
Sign up to request clarification or add additional context in comments.

19 Comments

Better yet is std::queue<int>().swap(q). With copy and swap idiom, all this should be equivalent to q = std::queue<int>().
While std::queue<int>().swap(q) is equivalent to the code above, q = std::queue<int>() need not be equivalent. Since there is no transfer of ownership in the assignment of the allocated memory some containers (like vector) might just call the destructors of the previously held elements and set the size (or equivalent operation with the stored pointers) without actually releasing the memory.
queue doesn't have a swap(other) method, so queue<int>().swap(q) doesn't compile. I think you have to use the generic swap(a, b).
@ThorbjørnLindeijer: In C++03 you are right, in C++11 queues do have swap as a member function, and additionally there is a free function overload that will swap two queues of the same type.
@ThorbjørnLindeijer: From the perspective of the users of the original queue, those elements do not exist. You are correct in that they will be destroyed one after the other and the cost is linear, but they are not accessible by anyone else other than the local function. In a multithreaded environment, you would lock, swap a non-temporary queue with the original one, unlock (to allow for concurrent accesses) and let the swapped queue die. This way you can move the cost of destruction outside of the critical section.
|
56

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>();  
}
Improve this answer

9 Comments

@Naszta Please elaborate how swap is "more effective"
@bobobobo: q1.swap(queue<int>());
q1=queue<int>(); is both shorter, and clearer (you're not really trying to .swap, you're trying to .clear).
With the new C++, just q1 = {} is enough
@Ari syntax (2) at list_initialization and (10) at operator_assignment. Default queue<T> constructor matches empty argument list {} and is implicit, so it is called, then q1.operator=(queue<T>&&) consumes the newly created queue
|
41

In C++11 you can clear the queue by doing this:

std::queue<int> queue;
// ...
queue = {};
Improve this answer

2 Comments

hey am just wondering if its O(n) or O(1) ?
@TilakMadichetti In the general case O(n) because the destructor has to be called for each contained element. This is also the case for clear() methods such as in std::vector. For POD elements, no element-wise destructor call is necessary, it should then be O(1) for vector but for queue it depends on the underlying container. The default std::deque reserves M chunks of memory where M is proportional to n (number of elements). So for default std::queue this it still O(n).
34

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();
Improve this answer

3 Comments

You can't just look at the O complexity of the operation if you are operating on real data. I would take a O(n^2) algorithm over a O(n) algorithm if the constants on the linear operation make it slower than the quadratic for all n < 2^64, unless I had some strong reason to believe I had to search the IPv6 address space or some other specific problem. Performance in reality is more important to me than performance at the limit.
This better answer than accepted answer because internally queue does this anyway when getting destroyed. So the accepted answer is O(n) plus it does extra allocations and initializations for brand new queue.
Remember, O(n) means less than or equal to n complexity. So, yes, in some cases like queue<vector<int>>, it will need to destroy each element 1 by 1, which will be slow either way, but in queue<int>, memory actually is allocated in one big block, and so it does not need to destroy the internal elements, and so queue's destructor can use a single efficient free() operation which almost certainly takes less than O(n) time.
19

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;
}
Improve this answer

4 Comments

Results with C++11: queues[i] = std::queue<int>();: 1.168, std::queue<int>().swap(queues[i]);: 1.151, std::queue<int> empty; std::swap(empty, queues[i]);: 1.164, while (!queues[i].empty()) queues[i].pop();: 0.189. Last one is the fastest by far. Thanks for the test code!
Tested with gcc and clang on godbolt.org; The results were very different than what @Burak commented above. Iterating pop() was significantly slower than the other methods, even if using auto & q=queues[i]; to make sure the lookup happens once(usually the compiler would optimize though). Other methods, including queues[i]={};, were not very different in terms of speed.
@Burak The popping version is the slowest one in both gcc and clang. Make sure you benchmark properly
@TedLyngmo Sure, but that comment is from 4 years ago. A lot can change in compiler implementations. I suggest using queues[i]={}; to make the intention clear, and of course benchmark.
8

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.

Improve this answer

1 Comment

STL containers are not designed to be inherited from. In this case you're probably okay because you're not adding any additional member variables, but it's not a good thing to do in general.
3

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.

Improve this answer

1 Comment

Why do you explicitly state the type at the assignment operator? I assume that myqueue = { }; will work just fine.
2

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.

Improve this answer

2 Comments

swap() or assignment calls the destructor on the now-defunct queue, which calls the destructors of all objects on the queue. Now, if your queue has objects that are actually pointers, that's a different issue -- but a simple pop() won't help you there, either.
Why unfortunately? It's elegant and simple.
2

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.

Improve this answer

Comments

0

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
Improve this answer

1 Comment

If you choose to empty the queue by deleting it, that's OK, but that's not what the question is about, and I don't see why unique_ptr comes in.
0

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';
}
Improve this answer

Comments

-1

swap is not more efficient than "=". .

template <class T> void swap (T& a, T& b)
{
  T c(std::move(a)); a=std::move(b); b=std::move(c);
}

swap just use std::move. but for empty queue, std::move is useless.

my_queue = empty_queue; or my_queue = std::move(empty_queue);

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.