looping through a std::deque and remove entries

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!

Solution

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.