< cpp‎ | container
Revision as of 19:00, 6 November 2012 by Nate (Talk | contribs)

Defined in header <deque>

    class T,
    class Allocator = std::allocator<T>

> class deque;

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 - amortized constant O(1)
  • Insertion or removal of elements - linear O(n)

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


Member types

Template:cpp/container/dcl list value typeTemplate:cpp/container/dcl list allocator typeTemplate:cpp/container/dcl list size typeTemplate:cpp/container/dcl list difference typeTemplate:cpp/container/dcl list referenceTemplate:cpp/container/dcl list const referenceTemplate:cpp/container/dcl list pointerTemplate:cpp/container/dcl list const pointerTemplate:cpp/container/dcl list iteratorTemplate:cpp/container/dcl list const iteratorTemplate:cpp/container/dcl list reverse iteratorTemplate:cpp/container/dcl list const reverse iterator
Member type Definition

Member functions

Template:cpp/container/dcl list constructorTemplate:cpp/container/dcl list destructorTemplate:cpp/container/dcl list operator=Template:cpp/container/dcl list assignTemplate:cpp/container/dcl list get allocatorTemplate:cpp/container/dcl list atTemplate:cpp/container/dcl list operator atTemplate:cpp/container/dcl list frontTemplate:cpp/container/dcl list backTemplate:cpp/container/dcl list beginTemplate:cpp/container/dcl list endTemplate:cpp/container/dcl list rbeginTemplate:cpp/container/dcl list rendTemplate:cpp/container/dcl list emptyTemplate:cpp/container/dcl list sizeTemplate:cpp/container/dcl list max sizeTemplate:cpp/container/dcl list shrink to fitTemplate:cpp/container/dcl list clearTemplate:cpp/container/dcl list insertTemplate:cpp/container/dcl list emplaceTemplate:cpp/container/dcl list eraseTemplate:cpp/container/dcl list push backTemplate:cpp/container/dcl list emplace backTemplate:cpp/container/dcl list pop backTemplate:cpp/container/dcl list push frontTemplate:cpp/container/dcl list emplace frontTemplate:cpp/container/dcl list pop frontTemplate:cpp/container/dcl list resizeTemplate:cpp/container/dcl list swap
Element access

Non-member functions

Template:cpp/container/dcl list operator cmpTemplate:cpp/container/dcl list swap2