Why is an STL deque not implemented as just a circ

问题:

I always thought that in C++ standard template library (STL), a double-ended queue (deque) is a size-variable array (like a vector) with circular boundary conditions, meaning there's a head pointer i and a tail pointer j both pointing to some position of an array a[0..L-1]. A push_front is i--, a push_back is j++, a pop_front is i++, and a pop_back is j--. When either pointer i or j reaches L or -1, it reappears on the other end of the array (0 and L-1 respectively). If the array size gets exhausted (pointers i==j after insering a new element), a larger space with double the original size is reallocated to a[] and data gets copied just like in a vector. There's also O(1) time random access taking into account the circular boundary condition. But someone tells me that inside an STL deque there's actually a pointer array pointing to many fixed-length array segments. It's much more complicated than a circular vector. What's the benefit of not using a simple circular vector to implement the functions of a deque? Will the random access get slower?

回答1:

As cppreference writes

As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.

This means that the large internal reallocations std::vector occasionally does, are not performed by std::deque. When space runs out, only a small fixed-size array is added. (The same but reverse happens when space becomes too large because of erasing.)

Here is a small test:

#include <vector>
#include <deque>
#include <string>
#include <iostream>
#include <chrono>


using namespace std;


int main()
{
    {
        const auto start = chrono::high_resolution_clock::now();

        vector<string> v;
        for(size_t i = 0; i < 9999999; ++i)
            v.push_back(string("hello"));

        cout << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << endl;
    }

    {
        const auto start = chrono::high_resolution_clock::now();

        deque<string> v;
        for(size_t i = 0; i < 9999999; ++i)
            v.push_back(string("hello"));

        cout << chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - start).count() << endl;
    }

    return 0;
}

On my machine, it shows deque is twice as fast as vector for this case:

$ ./a.out 
301
164

回答2:

The main advantage of the std::deque approach is that elements once inserted in the container are never moved if you add or remove elements from either of the two ends. Thus references (and pointers) to elements are not invalidated when performing those operations (note that, quite surprisingly, iterators to deque elements are instead invalidated when doing insertions or deletions on the ends).

This, while making the implementation more complex, can be done without affecting the formal big-O complexity and makes std::deque a very useful container.

You can have an std::deque of "fat" objects without having to use an extra level of indirection to avoid moving operations and maintain efficiency.

回答3:

23.3.8.4 [deque.modifiers] (emphasis is mine)

An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque.

This is not possible with a circular-vector-like implementation.

回答4:

std::deque (double-ended queue) is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. In addition, insertion and deletion at either end of a deque never invalidates pointers or references to the rest of the elements.

As opposed to std::vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays.

The storage of a deque is automatically expanded and contracted as needed. Expansion of a deque is cheaper than the expansion of a std::vector because it does not involve copying of the existing elements to a new memory location.

The complexity (efficiency) of common operations on deques is as follows:

• Random access - constant O(1)
• Insertion or removal of elements at the end or beginning - constant O(1)
• Insertion or removal of elements - linear O(n)

Source : std::deque