Difference between revisions of "cpp/container/deque"

Revision as of 14:03, 23 February 2017

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

• 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.
• If a method is common to both deque and std::vector then the run-time complexity of deque's method is no worse than the complexity of std::vector's method (and in the case of inserting to the front, deque's complexity is better).
• Despite the run-time complexity advantage of deque over std::vector described above, the std::vector container does have some advantages over the deque container:
  • Implementations of deque typically have a large overhead memory cost. For instance, the 64-bit GNU (resp. Apache, Microsoft) standard library implementation of deque uses a minimum of 656 (resp. 832, 128) bytes to store 1 object in a deque. This variability may also negatively affect portability.
  • deque typically doesn't store its elements contiguously in memory, which may make interacting with older C or C++ code more difficult. This also means that std::vectors typically have better locality in memory. This lack of locality in space, however, may give deque an advantage when dealing with a large collection of objects.
  • The better run-time complexity of some of deque's operations comes at the expense of additional book-keeping. In particular, many popular implementations of deque often store objects via an array of pointers-to-array so that accessing an element by passing an index to operator[], for instance, requires first finding the pointer that points to the array holding this element and then secondly finding the location of this element within this array.

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