Difference between revisions of "cpp/container/deque"

Revision as of 12:11, 1 February 2016

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)

std::deque meets the requirements of Template:concept, Template:concept, Template:concept and Template:concept.

Template parameters

Iterator invalidation

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

Notes

• Under some circumstances, references are not invalidated by insert and emplace.
• push_back and emplace_back do not invalidate any references.

Member types

Member functions

Non-member functions

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