Why is std::vector so much more popular than std::deque?

> Possible Duplicate:
> Why would I prefer using vector to deque

I am curious why is it that std::vector is so much more popular than std::deque. Deque is almost as efficient in lookup, more efficient in insert (without vector::reserve)and allows for inserting/deleting in the front.

Herb Sutter once recommended that if you want to use vector, just prefer deque (I am paraphrasing). However in a recent talk on Writing Modern C++ he again strongly recommends thinking of std::vector as a default container. According to the GOTW I linked earlier, even the standard has similar wording.

Is there a reason for this disparity? Is it just that vector is simpler and more well known, or is there a technical reason? Or is it that vector is just a cooler name .. ?

I can't speak for anybody else, but I can for myself.

When I first read about std::deque, I thought it was cool enough that for a while, I treated it not only as the default container, but as nearly the only container I used.

Then somebody asked about why, and I expounded at length on its virtues and why it was the best container to use for practically everything, and how it was much more versatile than std::vector.

Fortunately, the guy questioning my decision on it was persuasive enough that I did some testing. Testing showed that in nearly every case, std::deque was slower than std::vector -- often by a substantial factor (e.g., around 2). In fact, of the code I'd written using std::deque, just replacing std::deque with std::vector gave a speedup in all but a handful of cases.

I have used std::deque in a few cases since then, but definitely don't treat it as the default any more. The simple fact is that in the usual implementation it's noticeably slower than std::vector for most purposes.

I should add, however, that I'm reasonably certain that with the right implementation, it could be nearly equivalent to std::vector in virtually all cases. Most use a representation that's undoubtedly great from an asymptotic viewpoint, but doesn't work out quite so wonderfully (for many purposes) in the real world.

std::vector is very well understood, simple and is compatible with C (both in terms of the memory layout, and in terms of using pointers as iterators).

For some operations it is also more efficient than std::deque. Accessing elements by index is one example.

For a given task, it makes sense to use the simplest container that does the job well. In many cases that simplest container is std::vector.

Apart from std::vector being the most commonly known container class, it also has several advantages over std::deque, namely:

• A typical std::deque requires an additional indirection to access the elments unlike as in case of std::vector.
• Iterators in case of std::deque must be smart pointers and not pointers as in case of std::vector.
• Elements of an std::vector are guaranteed to be contiguous and hence it is compatible with c-style functions which take arrays as parameters.
• std::deque provide no support to control the capacity and the moment of reallocation.

Especially, the last point is noteworthy.

People use std::vector over std::deque for a simple reason. They interface with a lot of C libraries and they have functions with parameters which require a pointer to contiguous storage, which std::deque doesn't (can't) guarantee.

Another reason is when you build code according to std::deque and your requirements change so that you have to support contiguous access, you will have a bit of refactoring to do.

I am compelled to mention that there are libraries out there whose authors claim to have created more efficient vector implementations in order to overcome inefficiencies when capacity is increased.

The structure of std::deque is a bit more complex which makes naive iteration quite a bit more expensive than std::vector. The insertions into std::vector with its reallocations tend not to be big problem, especially when using reserve() and only appending to the end. Also, there are easier to understand invalidation rules for std::vector although it is actually an advantage of std::deque that objects stay put when inserting/removing only at either end (note that std::deque iterators get invalidate upon each insertion, independent of where the insertion happens). Another plus for std:vector is the guarantee that the values are contiguous in memory causing it to make fewer memory allocations.

I guess, I would recommend use of std::deque algorithms were consistently optimized to use segmented sequences (I'm not aware that any standard C++ library does this optimization) and users were accessing sequences consistently using algorithms (as far as I can tell, only a tiny fraction of users considers the option to use algorithms). Otherwise I would suspect that std::deque is the better option with respect to performance only if you take advantage of its specific properties (e.g., that objects stay put and that you can insert/remove at the end). It is worth profiling the two alternatives, though.