looping through a std::deque and remove entries

Question

I am trying to iterate through a std::deque and remove all of its content. I can do it along the way:

for(auto & x: myDeque)
{
    // do something
    myDeque.pop_front();
}

Or I can do myDeque.clear() at the end after the loop. I am wondering which way I should be using? Thanks!

Answer 1

It's almost certainly preferable to do the loop to process the data first, then separately do a myDeque.clear(); to empty it.

From a purely theoretical viewpoint, it's O(n) either way, but from a practical viewpoint, clear is almost always going to be at least as fast, and usually faster. The possible exception would be if you're dealing with a deque so large that it won't fit in the cache. In this case, doing everything you need to (including deleting) with a particular piece of data at once can avoid having to re-load that data into the cache twice: once for processing, and again to destroy it.

In particular, a deque is normally implemented as a two-level structure: something pretty much like a vector of pointers to blocks, where each block holds a fixed number of data items. When you do pop_front, it has to look at the first block, figure out whether this pop_front has emptied the first block or not. If it has, it deletes that block. If not, it just updates an index to tell it which location in that block is currently the front.

But when you do clear it can just walk through the data, and destroy all the contents.

Answer 2

myDeque.clear() will be much more easier as it'll destroy all of its nodes on itself. Use the features which they provide because most of the time, it does it much efficiently and takes the burden off of you.

Another plus for it is that it'll be easier for someone else who reads your code to understand what's going on.