Why do you prefer std :: vector over std :: deque?

Question

They have O (1) access complexity and random O (n) embedding / deleting complexity. But the vector costs more when expanded due to redistribution and copying, while deque does not have this problem.

Deque seems to have better performance, but why do most people use a vector instead of deque?

Answer 1

why most people use vector instead of deque? 

Because this is what they have been taught.

vector and deque serve slightly different purposes. They can be used as just a container of objects, if that's all you need. When you learn C ++ programming, that’s all most people need — a bucket to throw away material, get material, and go through.

When StackOverflow is asked a question like “which container should I use by default”, the answer is almost always vector . The question is usually asked from the context of teaching a C ++ program, and at the moment when the programmer asks such a question, they still do not know what they do not know. And a lot of them still do not know. So, we (StackOverflow) need a container that fits almost any need better or worse, can be used in almost any context and does not require the programmer to ask all the right questions before landing on something that comes close to the right answer . In addition, the standard recommends the use of vector . vector not suitable for all purposes, and in fact, deque better than vector for many common applications - but for a programmer-programmer this is not much better than we should vary from standard tips to beginners with C ++ programmers, so StackOverflow lands on vector .

Having studied the basics of syntax and, let's say, C ++ programming strategies, programmers are divided into two branches: those who study more and write better programs, and those who do not. Those who do not do this will forever remain on vector . I think many programmers fall into this camp.

Rare programmers who try to go beyond this stage begin to ask other questions - questions like you asked here. They know that there are many that they do not yet know, and they want to start figuring out what these things are. They quickly (or less quickly) discover that, choosing between vector and deque , some of the questions they did not think to ask before are the following:

• Do I need a memory to be funny?
• Do I need to avoid a lot of redistribution?
• Do I need to keep valid iterators after insertion?
• Do I need my collection to be compatible with some ancient C-like function?

Then they really start thinking about the code they write, discover even more material that they don’t know, and the rhythm continues ...

Answer 2

From the standard C ++ 23.1.1 section:

 vector is the type of sequence that should be used by default... deque is the data structure of choice when most insertions and deletions take place at the beginning or at the end of the sequence. 

However, there are some arguments in the opposite direction .

In theory, vector no less efficient than deque because it provides a subset of its functionality. If your task needs only a vector interface, prefer a vector - it cannot be worse than a deck.

Answer 3

But a vector costs more when expanded due to redistribution and copying

Although it is true that vector sometimes has to redistribute its array as it grows, it will grow exponentially, so the amortized complexity is still O (1). Often you can avoid redistribution by using reserve() .

Deque seems to have better performance

There are many aspects to performance; the time spent on push_back is only one. In some applications, the container may be changed rarely or filled at startup, and then never be changed. In such cases, iteration and access speed may be more important.

vector is the easiest possible container: an adjacent array. This means that iteration and random access can be achieved using simple pointer arithmetic, and access to an element can be as fast as dereferencing a pointer.

deque has additional requirements: it must not move elements. This means that a typical implementation requires an additional level of indirection - it is usually implemented as something like an array of pointers to arrays. This means that accessing an element requires dereferencing of two pointers, which will be slower than one.

Of course, often speed is not a critical issue, and you choose containers according to their behavioral properties rather than their performance. You can choose vector if you want the elements to be contiguous, perhaps to work with APIs based on pointers and arrays. You can choose deque or list if you want to guarantee that the elements will not move, so you can keep pointers to them.

Answer 4

For cplusplus:

Therefore, they provide similar functionality as vectors, but with effective insertion and deletion of elements also at the beginning of a sequence, not only at its end. But, unlike vectors, it is not guaranteed that all of its elements will be stored in continuous storage in this way, not allowing direct access by shifting pointers to elements.

Answer 5

Personally, I prefer to use deque (I always mess up myself and should use push_front for one reason or another), but vector has its uses / differences, the main one being:

vector has continuous memory, and deque allocates pages / chunks. Please note: pages / chunks are quite useful: inserting / deleting a time constant on the front of the container. It is also typical that a large memory block, divided into several smaller blocks, is more efficient than a single memory block.

You can also argue that since deque are methods for “missing” the capacity / reserve size, you have nothing to worry about.

I highly recommend you read GotW Sutters on this topic.