deque vs vector guidance after C++11 enhancements [duplicate]

Question

Back in the pre-C++11 days, many book authors recommended the use of deque for situations that called for a dynamically sized container with random access. This was in part due to the fact that deque is a move versatile data structure than vector, but also it was due to the fact that vector in the pre-C++11 world did not offer a convenient way to size down its capacity via "shrink to fit." The greater deque overhead of indirect access to elements via the brackets operator and iterators seemed to be subsumed by the greater vector overhead of reallocation.

On the other hand, some things haven't changed. vector still uses a geometric (i.e., size*factor) scheme for reallocation and stil must copy (or move if possible) all of its elements into the newly allocated space. It is still the same old vector with regard to insertion/removal of elements at the front and/or middle. On the other hand, it offers better locality of reference, although if the blocks used by deque are a "good large" size, the benefit with regard to caching can be argued for many apps.

So, my question is if in light of the changes that came with C++11, deque should continue to remain the go to / first choice container for dynamically sized / random access needs.

Answer 1

Josuttis's The C++ Standard Library states: (When to use which container Sec 7.12)

By default, you should use a vector. It has the simplest internal data structure and provides random access. Thus, data access is convenient and flexible, and data processing is often fast enough.

If you insert and/or remove elements often at the beginning and the end of a sequence, you should use a deque. You should also use a deque if it is important that the amount of internal memory used by the container shrinks when elements are removed. Also, because a vector usually uses one block of memory for its elements, a deque might be able to contain more elements because it uses several blocks.