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?

Sledge

The Visual C++ implementation of std::deque has a very small maximum block size (~16 bytes, if I recall correctly; maybe 32), and as such doesn't perform very well for realistic applications. A deque<T> where sizeof(T) > 8 (or 16? It's a small number) has about the same performance characteristics as a vector<T*>, where each element is allocated dynamically. Other implementations have different maximum block sizes, so writing code that has relatively the same performance characteristics on different platforms is difficult with deque. – Galinagalindo

Deque is not a continuous memory container. – Arne

@ravil No, that is the duplicate, pointing at this question. – Babu

I wanted to edit "deque has almost vector has but more" so it would make sense, but I'm not sure what it's supposed to mean. – Colligan

hard to believe a question with an unfixed blatant factual error was sitting at a balance of 34 votes – Dynatron

@Dynatron that's why it's a question. Different story if it was an answer ;) – Marquetry

Pretty good explanation by Bo Qian: Vector Vs Deque - I and Vector Vs Deque - II – Brindled

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 .

Secunderabad

It appears that the link to "elsewhere" is now dead (due to moderation?). – Woolpack

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...)

Vulcanism

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.

Hames

Question -- has the committee considered adding a hybrid of the two (say, a "deck") to C++? (i.e. a double-ended vector.) I have written an implementation linked to below in my answer. It can be as fast as a vector but much more widely applicable (e.g., when making a fast queue). – Moina

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".

Bridge

I don't think a "list of vector" is correct: my understanding was that most implementations were a "vector of pointers to arrays," though it depends on your definition of "list" (I read "list" as "linked list," which wouldn't meet the complexity requirements.) – Galinagalindo

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.)

Lapstrake

std::deque is no less standardized than std::vector. I don't believe the complexity requirements for std::deque can be met with contiguous storage. – Garnish

Perhaps my phrasing was poor: although it is true that standardization is not thorough, as I understand it, vectors are standardized to be a conitugous sequence, and deques are not. That seems to be the one deciding factor. – Lapstrake

vector wasn't originally required to be contiguous either -- that was added later. vector is more limited, and generally a bit faster. deque gives up a bit of speed to allow slightly greater flexibility. – Garnish

@JerryCoffin: Which complexity requirements of deque can't met with contiguous storage? – Moina

@Mehrdad: To be honest, I don't remember what I had in mind. I haven't looked at that part of the standard recently enough that I feel comfortable stating categorically that my earlier comment was wrong, but looking at it right now, I can't think of how it would be right either. – Garnish

@JerryCoffin: The complexity requirements are actually trivial: you could allocate a large array and start pushing your sequence from the middle outwards (I guess this is what Mehrdad implementation does), then reallocate when you get to the ends. The problem with this approach is that it does not satisfy one of the requirements of deque, namely that insertion at the ends shall not invalidate referenced to the existing elements. This requirement implies discontinuous memory. – Coricoriaceous

@ybungalobill you could reallocate only when full and alternatively shift the data towards the middle if it hits one end (you'd have to move it anyway) but it would invalidate references, as would a reallocation if you did actually get full. For a FIFO queue you can use a vector and implement as a ring. (Fixed-length FIFO queue) – Vulcanism

@CashCow: When shifting, just be careful to guarantee O(1) amortized insertion at both ends. – Coricoriaceous

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'

Bohs

-1: Insert and erase at begin or end does NOT invalidate references and pointers to other elements. (Although insert and erase in the middle does) – Butterandeggs

@Butterandeggs I changed it to 'vector'. – Bohs

Pointer stability of std::deque on push_back() and emplace_back() is one reason I'd consider it over std::vector, for example when inserting pointers to those elements into a map as values. – Cymene

Answer 7

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

Peeper

Answer 8

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.

Redwood

The question, if any can be distilled from among the factual errors and missing words, was why someone would prefer vector. We can infer that why not is a corollary. Saying that you prefer deque, for unknown reasons, from unspecified tests, is not an answer. – Dynatron

Answer 9

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.

Interminable

Answer 10

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.

Zelazny

Actually, on the same series of push_back and pop_back operations, deque<int> is always at least 20% faster than vector<int> in my tests (gcc with O3). I guess that's why deque is the standard choice for things like std::stack... – Underhung

Answer 11

Here is a performance comparison (Vector vs. Deque) building on a response by John dibling : you can try it on your machine and fiddle with the code :

when choosing between vector and deque, some questions to ask before are:

1. Do I need the memory to be contiguous?
2. Do I need to avoid lots of reallocations?
3. Do I need to keep valid iterators after insertions?

Case 1: Do I need the memory to be Contiguous :

Take a vector and a deque and iteratively fill them with int and compare the performance :

int main() {
    const int numElements = 1000000;

    // Vector
    {
        std::vector<int> myVector;
        auto start = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < numElements; ++i) {
            myVector.push_back(i);
        }
        auto end = std::chrono::high_resolution_clock::now();
        std::cout << "Vector insertion time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms\n";
    }

    // Deque
    {
        std::deque<int> myDeque;
        auto start = std::chrono::high_resolution_clock::now();
        for (int i = 0; i < numElements; ++i) {
            myDeque.push_back(i);
        }
        auto end = std::chrono::high_resolution_clock::now();
        std::cout << "Deque insertion time: "
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()
                  << " ms\n";
    }

    return 0;
}

Vector insertion time: 41 ms ; Deque insertion time: 37 ms

if you increase the number of elements to one hundred million the vector insertion will perform better because of the contiguous memory and since a deque would have to make additional reallocations.

Case 1.1 : Adding Elements in the middle

int main() {
    const int numElements = 1000000;

    // Initialize a std::vector and a std::deque with values from 1 to numElements
    std::vector<int> myVector;
    std::deque<int> myDeque;
    for (int i = 1; i <= numElements; ++i) {
        myVector.push_back(i);
        myDeque.push_back(i);
    }

    // Insert elements between the 50,000th and 100,000th positions in the vector
    auto vectorStart = std::chrono::high_resolution_clock::now();
    for (int i = 50000; i < 100000; ++i) {
        myVector.insert(myVector.begin() + i, i);
    }
    auto vectorEnd = std::chrono::high_resolution_clock::now();

    // Insert elements between the 50,000th and 100,000th positions in the deque
    auto dequeStart = std::chrono::high_resolution_clock::now();
    for (int i = 50000; i < 100000; ++i) {
        myDeque.insert(myDeque.begin() + i, i);
    }
    auto dequeEnd = std::chrono::high_resolution_clock::now();

    std::cout << "Vector insertion time: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(vectorEnd - vectorStart).count()
              << " ms\n";
    std::cout << "Deque insertion time: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(dequeEnd - dequeStart).count()
              << " ms\n";

    return 0;
}

Vector insertion time: 25337 ms ; Deque insertion time: 8942 ms

Case 2 Do I need to avoid lots of reallocations?

Reallocation happens when the vector exceeds its capacity.

a deque’s reallocation strategy involves allocating new blocks as needed, copying elements, and "preserving iterator validity"

int main() {
    const int numElements = 1000000;

    // Initialize a std::vector and a std::deque
    std::vector<int> myVector;
    std::deque<int> myDeque;

    // Reserve initial capacity for both containers
    myVector.reserve(numElements);
    myDeque.resize(numElements);

    // Add elements until reallocation occurs
    auto vectorStart = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < numElements; ++i) {
        myVector.push_back(i);
    }
    auto vectorEnd = std::chrono::high_resolution_clock::now();

    auto dequeStart = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < numElements; ++i) {
        myDeque[i] = i;
    }
    auto dequeEnd = std::chrono::high_resolution_clock::now();

    std::cout << "Vector reallocation time: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(vectorEnd - vectorStart).count()
              << " ms\n";
    std::cout << "Deque reallocation time: "
              << std::chrono::duration_cast<std::chrono::milliseconds>(dequeEnd - dequeStart).count()
              << " ms\n";

    return 0;
}

Vector reallocation time: 39 ms ; Deque reallocation time: 182 ms

Deques don't need reallocation when adding elements at the beginning or end, but they might perform more poorly when they do require reallocation, especially in scenarios with large data sizes. Therefore, if avoiding frequent reallocations is crucial, vectors with appropriate capacity reservation are preferred.

Case 3 : Do I need to keep valid iterators after insertions?

std::vector: Imagine a vector as a dynamic array with contiguous memory locations. When elements are added, the vector grows by allocating a new, larger chunk of memory and copying existing elements to the new location.

Original vector:
+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |   |
+---+---+---+---+---+---+
^                   ^
|                   |
begin()              end()

After reallocation:
+---+---+---+---+---+---+---+---+---+---+
| 1 | 2 | 3 | 4 | 5 |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+---+
^                               ^
|                               |
begin()                          end()

When reallocation occurs, all iterators are invalidated because the memory location changes. You need to obtain new iterators after reallocation.

std::deque: The deque uses a segmented memory structure. It consists of chunks (pages) that store elements. When elements are added, the deque allocates new chunks as needed. Existing chunks remain unaffected.

Original deque:
Chunk 1:   +---+---+---+
           | 1 | 2 | 3 |
           +---+---+---+
Chunk 2:   +---+---+---+
           | 4 | 5 |   |
           +---+---+---+
^                   ^
|                   |
begin()              end()

After reallocation (adding more elements):
Chunk 1:   +---+---+---+
           | 1 | 2 | 3 |
           +---+---+---+
Chunk 2:   +---+---+---+---+
           | 4 | 5 | 6 | 7 |
           +---+---+---+---+
^                           ^
|                           |
begin()                      end()

In a deque, only iterators pointing to the modified chunk are invalidated. Iterators to other chunks remain valid. You can continue using existing iterators for chunks that were not affected by reallocation.

When you insert or erase elements in a deque, iterators pointing to elements before the modification remain valid, regardless of the modification's position within the deque. This behavior applies to both the front and back of the deque. Iterators to elements in the unaffected parts of the deque (i.e., not near the insertion or deletion) also remain valid.

However, if you insert or erase elements at positions within the deque that are between its beginning and end, iterators that point to elements in the modified section might become invalidated. Specifically:

Insertions and erasures at the beginning of a deque invalidate iterators that point to elements before the insertion or erasure point.

Insertions and erasures at the end of a deque do not invalidate any iterators.

Insertions and erasures in the middle of a deque invalidate iterators that point to elements after the insertion or erasure point in the same chunk of memory where the modification occurred.

Splotch

I am getting different benchmark results using MSVC compiler : Vector insertion time: 200 ms. Deque insertion time: 4701 ms . (Vector is always faster). – Whodunit