Top of document
©Copyright 1999 Rogue Wave Software

deque


     Container

Summary

A sequence that supports random access iterators and efficient insertion/deletion at both beginning and end.

Contents

Synopsis

#include <deque>
template <class T, class Allocator = allocator>
 class deque;

Description

deque<T, Allocator> is a type of sequence that supports random access iterators. It supports constant time insert and erase operations at the beginning or the end of the container. Insertion and erase in the middle take linear time. Storage management is handled by the Allocator template parameter.

Any type used for the template parameter T must provide the following (where T is the type, t is a value of T and u is a const value of T):

Default constructor T()
Copy constructors T(t) and T(u)
Destructor t.~T()
Address of &t and &u yielding T* and const T* respectively
Assignment t = a where a is a (possibly const) value of T

Interface

template <class T, class Allocator = allocator>
 class deque {
public:
 // Types
   class iterator; 
   class const_iterator;
   typedef T value_type;
   typedef Allocator allocator_type;
   typename  reference;
   typename  const_reference;
   typename  size_type;
   typename  difference_type;
   typename reverse_iterator;
   typename  const_reverse_iterator;
 // Construct/Copy/Destroy
   explicit deque (const Allocator& = Allocator());
   explicit deque (size_type, const Allocator& = Allocator ());
   deque (size_type, const T& value, 
          const Allocator& = Allocator ());
   deque (const deque<T,Allocator>&);
   template <class InputIterator>
    deque (InputIterator, InputIterator, 
           const Allocator& = Allocator ());
   ~deque ();
   deque<T,Allocator>& operator= (const deque<T,Allocator>&);
   template <class InputIterator>
    void assign (InputIterator, InputIterator);
   template <class Size, class T>
    void assign (Size);
   template <class Size, class T>
    void assign (Size, const T&);
   allocator_type get allocator () const;
 // Iterators
   iterator begin ();
   const_iterator begin () const;
   iterator end ();
   const_iterator end () const;
   reverse_iterator rbegin ();
   const_reverse_iterator rbegin () const;
   reverse_iterator rend ();
   const_reverse_iterator rend () const;
// Capacity
   size_type size () const;
   size_type max_size () const;
   void resize (size_type);
   void resize (size_type, T);
   bool empty () const;
// Element access
   reference operator[] (size_type);
   const_reference operator[] (size_type) const;
   reference at (size_type);
   const_reference at (size_type) const;
   reference front ();
   const_reference front () const;
   reference back ();
   const_reference back () const;
 // Modifiers
   void push_front (const T&);
   void push_back (const T&);
   iterator insert (iterator);
   iterator insert (iterator, const T&);
   void insert (iterator, size_type, const T&);
   template <class InputIterator>
    void insert (iterator, InputIterator, InputIterator);
   void pop_front ();
   void pop_back ();
   iterator erase (iterator);
   iterator erase (iterator, iterator);
   void swap (deque<T, Allocator>&);
   void clear();
};
 // Non-member Operators
template <class T, class Allocator>
 bool operator== (const deque<T, Allocator>&, 
                  const deque<T, Allocator>&);
template <class T, class Allocator>
 bool operator< (const deque<T, Allocator>&, 
                 const deque<T, Allocator>&);
// Specialized Algorithms
template <class T, class Allocator>
 voice swap (deque<T, Allocator>&, deque<T, Allocator>&);

Constructors and Destructor

explicit 
deque (const Allocator& alloc = Allocator());
explicit 
deque (size_type n, const Allocator& alloc = Allocator());
deque (size_type n, const T& value, 
       const Allocator& alloc = Allocator());
deque (const deque<T, Allocator>& x);
template <class InputIterator>
deque (InputIterator first, InputIterator last, 
       const Allocator& alloc = Allocator());
~deque ();

Allocator

allocator
allocator_type get_allocator () const;

Iterators

iterator begin ();
const_iterator begin () const;
iterator end ();
const_iterator end () const;
reverse_iterator rbegin ();
const_reverse_iterator rbegin () const;
reverse_iterator rend ();
const_reverse_iterator rend () const;

Assignment Operator

deque<T, Allocator>& 
operator= (const deque<T, Allocator>& x);

Reference Operators

reference operator[] (size_type n);
const_reference operator[] (size_type n) const;

Member Functions

template <class InputIterator>
void
assign (InputIterator first, InputIterator last);
template <class Size, class T>
void 
assign (Size n);
template <class Size, class T>
void 
assign (Size n, const T& t);
reference 
at (size_type n);
const_reference 
at (size_type) const;
reference 
back ();
const_reference 
back () const;
void
clear ();
bool 
empty () const;
reference 
front ();
const_reference 
front () const;
iterator
erase (iterator first, iterator last);
iterator
erase (iterator position);
iterator 
insert (iterator position);
iterator 
insert (iterator position, const T& x);
void 
insert (iterator position, size_type n, const T& x);
template <class InputIterator>
void 
insert (iterator position, InputIterator first,
        InputIterator last);
size_type 
max_size () const;
void 
pop_back ();
void 
pop_front ();
void
push_back (const T& x);
void 
push_front (const T& x);
void 
resize (size_type sz);
void 
resize (size_type sz, T c);
size_type 
size () const;
void 
swap (deque<T,Allocator>& x);

Non-member Functions

template <class T, class Allocator>
bool operator== (const deque<T, Allocator>& x,
                 const deque<T, Allocator>& y);
template <class T, class Allocator>
bool operator< (const deque<T, Allocator>& x,
                const deque<T, Allocator>& y);
template <class T, class Allocator>
void swap (deque<T, Allocator>& a, deque<T, Allocator>& b);

Example

//
// deque.cpp
//
 #include <deque>
 #include <string>
 deque<string, allocator> deck_of_cards; 
 deque<string, allocator> current_hand;
 void initialize_cards(deque<string, allocator>& cards) {
   cards.push_front("aceofspades");
   cards.push_front("kingofspades");
   cards.push_front("queenofspades");
   cards.push_front("jackofspades");
   cards.push_front("tenofspades");
   // etc.
 }
 template <class It, class It2> 
 void print_current_hand(It start, It2 end) 
 {
   while (start < end) 
   cout << *start++ << endl;
 }
 template <class It, class It2>
 void deal_cards(It, It2 end) {
   for (int i=0;i<5;i++) {
     current_hand.insert(current_hand.begin(),*end);
     deck_of_cards.erase(end++);
   }
 }
 void play_poker() {
   initialize_cards(deck_of_cards);
   deal_cards(current_hand.begin(),deck_of_cards.begin()); 
 }
 int main() 
 {
   play_poker();
   print_current_hand(current_hand.begin(),current_hand.end());
   return 0;
 }
Output :
aceofspades
kingofspades
queenofspades
jackofspades
tenofspades

Warnings

Member function templates are used in all containers provided by the Standard Template Library. An example of this is the constructor for deque<T, Allocator> that takes two templated iterators:

template <class InputIterator>
 deque (InputIterator, InputIterator);

deque also has an insert function of this type. These functions, when not restricted by compiler limitations, allow you to use any type of input iterator as arguments. For compilers that do not support this feature we provide substitute functions that allow you to use an iterator obtained from the same type of container as the one you are constructing (or calling a member function on), or you can use a pointer to the type of element you have in the container.

For example, if your compiler does not support member function templates you can construct a deque in the following two ways:

int intarray[10];
deque<int, allocator> first_deque(intarray, intarray + 10);
deque<int, allocator> second_deque(first_deque.begin(),  
                                   first_deque.end());

But not this way:

deque<long, allocator> long_deque(first_deque.begin(),
                                  first_deque.end());

since the long_deque and first_deque are not the same type.

Additionally, many compilers do not support default template arguments. If your compiler is one of these, you need to always supply the Allocator template argument. For instance, you'll have to write:

deque<int, allocator>
deque<int>

Top of document