Cppin a Nutshell-13.22 <deque>

13.22 <deque>

The <deque> header is one of the standard container template headers. It declares the deque class template and a few global functions that operate on deque objects.

A deque, short for double-ended queue, is similar to a vector, but the performance is constant when adding to or removing from the collection at the beginning and at the end.

If you need a vector of bool that behaves as a normal C++ container, you should use deque<bool> instead of vector<bool>. See <vector> later in this chapter for an explanation.

See Chapter 10 for information about containers in general.

deque class template

Double-ended queue

template <class T, class Alloc = allocator<T> >
class deque {
public:
  typedef typename Alloc::reference reference;
  typedef typename Alloc::const_reference const_reference;
  typedef  . . .  iterator;
  typedef  . . .  const_iterator;
  typedef  . . .  size_type;
  typedef  . . .  difference_type;
  typedef T value_type;
  typedef Alloc allocator_type;
  typedef typename Alloc::pointer pointer;
  typedef typename Alloc::const_pointer const_pointer;
  typedef std::reverse_iterator<iterator> reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

  explicit deque(const Alloc& = Alloc(  ));
  explicit deque(size_type n, const T& value = T(  ), const Alloc& = Alloc(  ));
  template <class InputIterator>
  deque(InputIterator first, InputIterator last, const Alloc& = Alloc(  ));
  deque(const deque<T,Alloc>& x);
   
  ~deque(  );
   
  deque<T,Alloc>& operator=(const deque<T,Alloc>& x);
  template <class InputIterator>
  void assign(InputIterator first, InputIterator last);
  void assign(size_type n, const T& t);
  allocator_type get_allocator(  ) const;
   
  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;
   
  size_type size(  ) const;
  size_type max_size(  ) const;
  void resize(size_type sz, T c = T(  ));
  bool empty(  ) const;
   
  reference operator[](size_type n);
  const_reference operator[](size_type n) const;
  reference at(size_type n);
  const_reference at(size_type n) const;
  reference front(  );
  const_reference front(  ) const;
  reference back(  );
  const_reference back(  ) const;
   
  void push_front(const T& x);
  void push_back(const T& x);
  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);
  void pop_front(  );
  void pop_back(  );
  iterator erase(iterator position);
  iterator erase(iterator first, iterator last);
  void swap(deque<T,Alloc>&);
  void clear(  );
};

The deque class template represents a double-ended queue. It is one of the standard container types, like list and vector. Like a list, a deque yields amortized, constant performance when adding and removing items from the beginning and end of the container. Like a vector, performance is constant when accessing items at any index in the deque. Performance for inserting or removing items not at the start or end is linear with respect to the size of the container.

After inserting items at the beginning or end of the deque, all iterators become invalid. All references and pointers to items in the deque remain valid. After inserting in the middle of the deque, all iterators, references, and pointers to items in the deque become invalid.

After erasing an element from the beginning or end of the deque, all iterators and references remain valid, except those pointing to the erased element. After erasing an element from the middle of the deque, all iterators, references, and pointers to items in the deque become invalid.

explicit deque(const Alloc& = Alloc( ))

Constructs an empty deque.

explicit deque(size_type n, const T& value = T( ), const Alloc& = Alloc( ))

Constructs a deque with n copies of value.

template <class InputIterator>

deque(InputIterator first, InputIterator last, const Alloc& alloc = Alloc( ))

Constructs a deque with copies of the elements in [first, last), unless InputIterator is an integral type, in which case the deque is constructed as though the arguments were cast as follows:

deque(static_cast<size_type>(first), static_cast<value_type>(last),
      alloc);

template <class InputIterator>

void assign(InputIterator first, InputIterator last)

Erases the current contents of the deque and inserts the elements in [first, last), unless InputIterator is an integral type, in which case the arguments are interpreted as though they were cast as follows:

assign(static_cast<size_type>(first), static_cast<value_type>(last));

void assign(size_type n, const T& t)

Erases the current contents of the deque and inserts n copies of t.

allocator_type get_allocator( ) const

Returns the allocator object.

reference operator[](size_type n)

const_reference operator[](size_type n) const

Returns the element at index n. If n >= size( ), the behavior is undefined.

reference at(size_type n)

const_reference at(size_type n) const

Returns the element at index n. If n >= size( ), it throws out_of_range.

reference back( )

const_reference back( ) const

Returns the last element in the deque. The behavior is undefined if the deque is empty.

iterator begin( )

const_iterator begin( ) const

Returns an iterator that points to the first element of the deque.

void clear( )

Erases all elements from the deque.

bool empty( ) const

Returns size( ) == 0.

iterator end( )

const_iterator end( ) const

Returns an iterator that points to the last element of the deque.

iterator erase(iterator position)

Erases the element at position.

iterator erase(iterator first, iterator last)

Erases all the elements in the range [first, last).

reference front( )

const_reference front( ) const

Returns the first element of the deque. The behavior is undefined if the deque is empty.

iterator insert(iterator position, const T& x)

Inserts x at position. If position is begin( ) or end( ), the performance is constant; at any other position, the performance is linear.

void insert(iterator pos, size_type n, const T& x)

Inserts n copies of x at pos.

template <class InputIterator>

void insert (iterator position, InputIterator first, InputIterator last)

Inserts the elements in the range [first, last) starting at position, unless InputIterator is an integral type, in which case the arguments are interpreted as though they were cast:

insert(position, static_cast<size_type>(first),
                 static_cast<value_type>(last));

If an exception is thrown, such as bad_alloc when there is insufficient memory for a new element, the deque is unchanged, and all iterators and references remain valid. If the exception is thrown from an element's copy constructor or assignment operator, however, the behavior is unspecified.

size_type max_size( ) const

Returns the size of the largest possible deque.

void pop_front( )

Erases the first element of the deque. The behavior is undefined if the deque is empty.

void pop_back( )

Erases the last element of the deque. The behavior is undefined if the deque is empty.

void push_front(const T& x)

Inserts x as the new first element of the deque.

void push_back(const T& x)

Inserts x as the new last element of the deque.

reverse_iterator rbegin( )

const_reverse_iterator rbegin( ) const

Returns a reverse iterator that points to the last element of the deque.

reverse_iterator rend( )

const_reverse_iterator rend( ) const

Returns a reverse iterator that points to one position before the first element of the deque.

size_type size( ) const

Returns the number of elements in the deque.

void resize(size_type n, T c = T( ))

Changes the size of the deque to n. If n > size( ), one or more copies of c are added to the end of the deque to reach the desired size. If the new size is smaller than the current size, the first n elements are unchanged, and elements are erased from the end to reach the new size.

void swap(deque<T,Alloc>& that)

Exchanges all the elements in the deque with all the elements in that.

13.22 <deque>

See Also

See Also

See Also

See Also