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( ) == .

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