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
.