Why would I prefer using vector to deque

Question

Since

1. they are both contiguous memory containers;
2. feature wise, deque has almost everything vector has but more, since it is more efficient to insert in the front.

Why whould anyone prefer std::vector to std::deque?

Answer 1

Elements in a deque are not contiguous in memory; vector elements are guaranteed to be. So if you need to interact with a plain C library that needs contiguous arrays, or if you care (a lot) about spatial locality, then you might prefer vector. In addition, since there is some extra bookkeeping, other ops are probably (slightly) more expensive than their equivalent vector operations. On the other hand, using many/large instances of vector may lead to unnecessary heap fragmentation (slowing down calls to new).

Also, as pointed out elsewhere on StackOverflow, there is more good discussion here: http://www.gotw.ca/gotw/054.htm .

Answer 2

To know the difference one should know how deque is generally implemented. Memory is allocated in blocks of equal sizes, and they are chained together (as an array or possibly a vector).

So to find the nth element, you find the appropriate block then access the element within it. This is constant time, because it is always exactly 2 lookups, but that is still more than the vector.

vector also works well with APIs that want a contiguous buffer because they are either C APIs or are more versatile in being able to take a pointer and a length. (Thus you can have a vector underneath or a regular array and call the API from your memory block).

Where deque has its biggest advantages are:

1. When growing or shrinking the collection from either end
2. When you are dealing with very large collection sizes.
3. When dealing with bools and you really want bools rather than a bitset.

The second of these is lesser known, but for very large collection sizes:

1. The cost of reallocation is large
2. The overhead of having to find a contiguous memory block is restrictive, so you can run out of memory faster.

When I was dealing with large collections in the past and moved from a contiguous model to a block model, we were able to store about 5 times as large a collection before we ran out of memory in a 32-bit system. This is partly because, when re-allocating, it actually needed to store the old block as well as the new one before it copied the elements over.

Having said all this, you can get into trouble with std::deque on systems that use "optimistic" memory allocation. Whilst its attempts to request a large buffer size for a reallocation of a vector will probably get rejected at some point with a bad_alloc, the optimistic nature of the allocator is likely to always grant the request for the smaller buffer requested by a deque and that is likely to cause the operating system to kill a process to try to acquire some memory. Whichever one it picks might not be too pleasant.

The workarounds in such a case are either setting system-level flags to override optimistic allocation (not always feasible) or managing the memory somewhat more manually, e.g. using your own allocator that checks for memory usage or similar. Obviously not ideal. (Which may answer your question as to prefer vector...)

Answer 3

I've implemented both vector and deque multiple times. deque is hugely more complicated from an implementation point of view. This complication translates to more code and more complex code. So you'll typically see a code size hit when you choose deque over vector. You may also experience a small speed hit if your code uses only the things the vector excels at (i.e. push_back).

If you need a double ended queue, deque is the clear winner. But if you're doing most of your inserts and erases at the back, vector is going to be the clear winner. When you're unsure, declare your container with a typedef (so it is easy to switch back and forth), and measure.

Answer 4

std::deque doesn't have guaranteed continuous memory - and it's often somewhat slower for indexed access. A deque is typically implemented as a "list of vector".

Answer 5

According to http://www.cplusplus.com/reference/stl/deque/, "unlike vectors, deques are not guaranteed to have all its elements in contiguous storage locations, eliminating thus the possibility of safe access through pointer arithmetics."

Deques are a bit more complicated, in part because they don't necessarily have a contiguous memory layout. If you need that feature, you should not use a deque.

(Previously, my answer brought up a lack of standardization (from the same source as above, "deques may be implemented by specific libraries in different ways"), but that actually applies to just about any standard library data type.)

Answer 6

Note that vector memory is re-allocated as the array grows. If you have pointers to vector elements, they will become invalid.

Also, if you erase an element, iterators become invalid (but not "for(auto...)").

Edit: changed 'deque' to 'vector'

Answer 7

You woudn't prefer vector to deque acording to these test results (with source).

Of course, you should test in your app/environment, but in summary:

• push_back is basically the same for all
• insert, erase in deque are much faster than list and marginally faster than vector

Some more musings, and a note to consider circular_buffer.

Answer 8

On the one hand, vector is quite frequently just plain faster than deque. If you don't actually need all of the features of deque, use a vector.

On the other hand, sometimes you do need features which vector does not give you, in which case you must use a deque. For example, I challenge anyone to attempt to rewrite this code, without using a deque, and without enormously altering the algorithm.

Answer 9

A deque is a sequence container which allows random access to it's elements but it is not guaranteed to have contiguous storage.

Answer 10

I think that good idea to make perfomance test of each case. And make decision relying on this tests.

I'd prefer std::deque than std::vector in most cases.