Difference between revisions of "cpp/container/deque"

Revision as of 04:06, 22 January 2020

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, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one.

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. On the other hand, deques typically have large minimal memory cost; a deque holding just one element has to allocate its full internal array (e.g. 8 times the object size on 64-bit libstdc++; 16 times the object size or 4096 bytes, whichever is larger, on 64-bit libc++).

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)

std::deque meets the requirements of Container, AllocatorAwareContainer, SequenceContainer and ReversibleContainer.

Template parameters

Iterator invalidation

There are still a few inaccuracies in this section, refer to individual member function pages for more detail

Invalidation notes

• When inserting at either end of the deque, references are not invalidated by insert and emplace.
• push_front, push_back, emplace_front and emplace_back do not invalidate any references to elements of the deque.
• When erasing at either end of the deque, references to non-erased elements are not invalidated by erase, pop_front and pop_back.
• A call to resize with a smaller size does not invalidate any references to non-erased elements.
• A call to resize with a bigger size does not invalidate any references to elements of the deque.
• Assuming position is a valid iterator not equal to the past-the-end iterator and result is the result of calling insert or emplace with first parameter being position, if &*result is equal to the prior value of &*position then references to elements before the prior value of position should still be valid, otherwise references to elements from the prior value of position to end() should still be valid.
• Assuming position is a valid iterator not equal to begin() and result is the result of calling insert or emplace with first parameter being position, if &*(result-1) is equal to the prior value of &*(position-1) then references to elements before the prior value of position should still be valid, otherwise references to elements from the prior value of position to end() should still be valid.
• Assuming position is a valid iterator not equal to the past-the-end iterator and result is the result of calling erase with parameter position and is not equal to the past-the-end iterator, if &*result is equal to the prior value of &*position then references to elements before the prior value of position should still be valid, otherwise references to elements from the prior value of position to end() should still be valid.
• Assuming position is a valid iterator not equal to begin() and result is the result of calling erase with parameter position, if &*(result-1) is equal to the prior value of &*(position-1) then references to elements before the prior value of position should still be valid, otherwise references to elements from the prior value of position to end() should still be valid.
• Assuming first and last are valid iterators and last is not equal to the past-the-end iterator and result is the result of calling erase with first and last parameters, if &*result is equal to the prior value of &*first then references to elements before the prior value of first should still be valid, otherwise references to elements from the prior value of last to end() should still be valid.
• Assuming first and last are valid iterators and first is not equal to begin()and result is the result of calling erase with first and last parameters, if &*(result-1) is equal to the prior value of &*(first-1) then references to elements before the prior value of first should still be valid, otherwise references to elements from the prior value of last to end() should still be valid.

Member types

Member functions

Non-member functions

Deduction guides(since C++17)

Example

#include <iostream>
#include <deque>
 
int main()
{
    // Create a deque containing integers
    std::deque<int> d = {7, 5, 16, 8};
 
    // Add an integer to the beginning and end of the deque
    d.push_front(13);
    d.push_back(25);
 
    // Iterate and print values of deque
    for(int n : d) {
        std::cout << n << '\n';
    }
}

13
7
5
16
8
25