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

Question

Possible duplicate:
Why do I prefer to use vector for deque

I am curious why std::vector much more popular than std::deque . Deque is almost as effective in searching, more efficient when inserting (without vector :: reserve) and allows you to insert / delete in front.

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

Is there a reason for this discrepancy? Is it just that vector is simpler and more famous, or is there a technical reason? Or is it that vector is just a colder name ..?

Answer 1

I cannot speak for anyone else, but I can for myself.

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

Then someone asked why, and I described in detail its advantages and why it was the best container to use for almost everything and how it was much more universal than std::vector .

Fortunately, the guy who was interrogating my decision on this was convincing enough that I did some testing. Testing showed that almost every case of std::deque was slower than std::vector - often with a significant factor (for example, around 2). In fact, the code I wrote using std::deque , just replacing std::deque with std::vector gave acceleration in all cases, except for a few cases.

I have used std::deque on several occasions since then, but I definitely don't see it as the default. The simple fact is that in a regular implementation this is noticeably slower than std::vector for most purposes.

I must add, however, that I am sure that, if implemented correctly, it is almost equivalent to std::vector almost all cases. Most of them use a representation that, undoubtedly, is of great importance from the point of view of asymptotics, but does not work so well (for many purposes) in the real world.

Answer 2

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

For some operations, it is also more efficient than std::deque . One example is accessing items by index.

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

Answer 3

Besides std::vector , which is the most famous container class, it also has several advantages over std::deque , namely:

• A typical std::deque requires additional indirectness to access the els, unlike, as in the case of std::vector .
• Iterators in the case of std::deque should be smart pointers, not pointers, as in the case of std::vector .
• The std::vector elements ensure that they are continuous and therefore compatible with c-style functions that take arrays as parameters.
• std::deque does not provide support for monitoring capacity and timing of redistribution.

In particular, the last point is noteworthy.

Answer 4

People use std :: vector for std :: deque for a simple reason. They interact with a large number of C libraries and have functions with parameters that require a pointer to continuous storage, which std :: deque does not (cannot) guarantee.

Another reason is that when you create code in accordance with the std :: deque standard and change the requirements so that you have to maintain continuous access, you will have to do some refactoring.

I have to mention that there are libraries whose authors claim to have created more efficient vector implementations in order to overcome inefficiency when capacity .

Answer 5

The structure of std::deque bit more complicated, which makes a naive iteration quite expensive than std::vector . Insertions into std::vector with its redistribution, as a rule, are not a big problem, especially when using reserve() and only adding to the end. In addition, it is easier to understand the invalidation rules for std::vector , although in fact the advantage of std::deque is that objects remain included when inserting / deleting from both ends only (note that std::deque iterators become invalid at each insertion, regardless of where the insertion occurs). Another plus for std:vector is the guarantee that values ​​are contiguous in memory, resulting in less memory allocation.

I think I would recommend using std::deque algorithms that have been sequentially optimized to use segmented sequences (I don't know that any standard C ++ library does this optimization), and users consistently access sequences using algorithms (as far as I can say, only a small part of users are considering using algorithms). Otherwise, I would suspect that std::deque is the best option in terms of performance only if you use its specific properties (for example, that objects remain in place and that you can insert / remove at the end). However, it is worth profiling two alternatives.