deque vs vector guidance after C++11 enhancements

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.

It seems to me that many or most people changed their tune on that debate after a while, long before C++11. Data locality is just too damn good. — Benjamin Lindley, Aug 07 '13 at 15:39
`vector::shrink_to_fit` is still a non-binding call; implementations are free to ignore it. — Praetorian, Aug 07 '13 at 15:39
Despite this advice, I primarily use vector unless the size will be 100's mb or the objects very expensive to copy. — Neil Kirk, Aug 07 '13 at 15:40
To follow up on @Praetorian from 21.4.4/13: `Remarks: shrink_to_fit is a non-binding request to reduce capacity() to size().` — Mark B, Aug 07 '13 at 15:42
vector was always my first choice... btw the A to your Q is : use vector by default, dq if you have need for it. :) OFc there is a perf diff, but most of the time you dont care... When you do - measure :) — NoSenseEtAl, Aug 07 '13 at 15:54
I found it. Herb Sutter's [GotW #54](http://www.gotw.ca/gotw/054.htm) is probably the most widely known source of the advice to prefer `deque` over `vector`. But even he changed his mind. http://www.cpptalk.net/image-vp323385.html -- search for his post there — Benjamin Lindley, Aug 07 '13 at 15:55
*Use vectors whenever you can. If you cannot use vectors, redesign your solution so that you can use vectors.* --Alexander Stepanov — David Rodríguez - dribeas, Aug 07 '13 at 16:12
@BenjaminLindley: it's interesting that he changed his mind really. Personally, I sometimes wonder if using (by default) a random access container is such a good idea because if you start relying on random access (rather than thinking about something else), then finding a replacement is either complicated or leads to a lot of necessary refactoring. — Matthieu M., Aug 07 '13 at 18:08
There is a video by Bjarne Stroustrup (creator of C++) on this subjet: https://www.youtube.com/watch?v=YQs6IC-vgmo — BlakBat, Apr 07 '14 at 10:13

Nevin · Answer 1 · 2013-08-07T16:07:55.243

4

The one language + library change which does make a difference is when you have a non-copyable + non-moveable type (such as a type which contains a mutex or an atomic variable). You can store those in a deque (via one of the emplace_* methods) but cannot store them in a vector.

edited Aug 07 '13 at 16:07

answered Aug 07 '13 at 15:45

Nevin

4,595
18
24

4

via `emplace_front` or `emplace_back`. `emplace` can not be used for this purpose. – Howard Hinnant Aug 07 '13 at 15:57
I guess for stable_vector storing nonmovable elements will also work, right ? – NoSenseEtAl Aug 07 '13 at 15:59
1

@NoSenseEtAl: It would depend on the specific implementation, I know not whether it's been upgraded to C++11 already. – Matthieu M. Aug 07 '13 at 18:03

score 4 · Answer 2 · answered Aug 07 '13 at 15:49

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.

deque vs vector guidance after C++11 enhancements

2 Answers2