deque(3C++) - deque(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMEdeque
- A sequence that supports random access iterators and efficient
insertion/deletion at both beginning and end.
SYNOPSIS
#include <deque>
template <class T, class Allocator = allocator<T> >
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 mid‐
dle take linear time. Storage management is handled by the Allocator
template parameter.
Any type used for the template parameter T must include the following
(where T is the type, t is a value of T and u is a const value of 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<T> >
class deque {
public:
// Types
class iterator;
class const_iterator;
typedef T value_type;
typedef Allocator allocator_type;
typedef typename
Allocator::reference reference;
typedef typename
Allocator::const_reference const_reference;
typedef typename
Allocator::size_type size_type;
typedef typename
Allocator::difference_type difference_type;
typedef typename
std::reverse_iterator<iterator> reverse_iterator;
typedef typename
std::reverse_iterator<const_iterator>
const_reverse_iterator;
// Construct/Copy/Destroy
explicit deque (const Allocator& = Allocator());
explicit deque (size_type);
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);
void assign (size_type, 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, 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>&);
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>&);
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
explicit
deque(const Allocator& alloc = Allocator());
The default constructor. Creates a deque of zero elements. The deque uses
the allocator alloc for all storage management.
explicitdeque(size_type n);
Creates a list of length n, containing n copies of the default value for
type T. T must have a default constructor. The deque uses the allocator
Allocator() for all storage management.
deque(size_type n, const T& value,
const Allocator& alloc = Allocator());
Creates a list of length n, containing n copies of value. The deque uses
the allocator alloc for all storage management.
deque(const deque<;T, Allocator>& x);
Creates a copy of x.
template <;class InputIterator>
deque(InputIterator first, InputIterator last,
const Allocator& alloc = Allocator());
Creates a deque of length last - first, filled with all values obtained by
dereferencing the InputIterators on the range [first, last). The deque uses
the allocator alloc for all storage management.
DESTRUCTORS
~deque();
Releases any allocated memory for self.
ALLOCATORS
allocator
allocator_type get_allocator() const;
Returns a copy of the allocator used by self for storage management.
ITERATORS
iterator begin();
Returns a random access iterator that points to the first element.
const_iterator begin() const;
Returns a constant random access iterator that points to the first element.
iterator end();
Returns a random access iterator that points to the past-the-end value.
const_iterator end() const;
Returns a constant random access iterator that points to the past-the-end
value.
reverse_iterator rbegin();
Returns a random access reverse_iterator that points to the past-the-end
value.
const_reverse_iterator rbegin() const;
Returns a constant random access reverse iterator that points to the past-
the-end value.
reverse_iterator rend();
Returns a random access reverse_iterator that points to the first element.
const_reverse_iterator rend() const;
Returns a constant random access reverse iterator that points to the first
element.
ASSIGNMENT OPERATORS
deque<T, Allocator>&
operator=(const deque<T, Allocator>& x);
Erases all elements in self, then inserts into self a copy of each element
in x. Returns a reference to self.
REFERENCE OPERATORS
reference operator[](size_type n);
Returns a reference to element n of self. The result can be used as an
lvalue. The index n must be between 0 and the size() - 1..
const_reference operator[](size_type n) const;
Returns a constant reference to element n of self. The index n must be
between 0 and the size() - 1.
MEMBER FUNCTIONS
template <class InputIterator>
void
assign(InputIterator first, InputIterator last);
Erases all elements contained in self, then inserts new elements from the
range [first, last).
voidassign(size_type n, const T& t);
Erases all elements contained in self, then inserts n instances of the
value of t.
referenceat(size_type n);
Returns a reference to element n of self. The result can be used as an
lvalue. The index n must be between 0 and the size() - 1.
const_referenceat(size_type) const;
Returns a constant reference to element n of self. The index n must be
between 0 and the size() - 1.
referenceback();
Returns a reference to the last element.
const_referenceback() const;
Returns a constant reference to the last element.
voidclear();
Erases all elements from the self.
boolempty() const;
Returns true if the size of self is zero.
referencefront();
Returns a reference to the first element.
const_referencefront() const;
Returns a constant reference to the first element.
iteratorerase(iterator first, iterator last);
Deletes the elements in the range (first, last). Returns an iterator point‐
ing to the element following the last deleted element, or end() if there
were no elements after the deleted range.
iteratorerase(iterator position);
Removes the element pointed to by position. Returns an iterator pointing to
the element following the deleted element, or end() if there were no ele‐
ments after the deleted range.
iteratorinsert(iterator position, const T& x);
Inserts x before position. The return value points to the inserted x.
voidinsert(iterator position, size_type n, const T& x);
Inserts n copies of x before position.
template <;class InputIterator>
voidinsert(iterator position, InputIterator first,
InputIterator last);
Inserts copies of the elements in the range (first, last] before position.
size_typemax_size() const;
Returns size() of the largest possible deque.
voidpop_back();
Removes the last element. Note that this function does not return the ele‐
ment.
voidpop_front();
Removes the first element. Note that this function does not return the ele‐
ment.
voidpush_back(const T& x);
Appends a copy of x to the end.
voidpush_front(const T& x);
Inserts a copy of x at the front.
voidresize(size_type sz);
Alters the size of self. If the new size (sz) is greater than the current
size, then sz-size() copies of the default value of type T are inserted at
the end of the deque. If the new size is smaller than the current capacity,
then the deque is truncated by erasing size()-sz elements off the end. Oth‐
erwise, no action is taken. Type T must have a default constructor.
voidresize(size_type sz, T c);
Alters the size of self. If the new size (sz) is greater than the current
size, then sz-size() c's are inserted at the end of the deque. If the new
size is smaller than the current capacity, then the deque is truncated by
erasing size()-sz elements off the end. Otherwise, no action is taken.
size_typesize() const;
Returns the number of elements.
voidswap(deque<;T,Allocator>& x);
Exchanges self with x.
NON-MEMBER FUNCTIONS
template <class T, class Allocator>
bool operator==(const deque<T, Allocator>& x,
const deque<T, Allocator>& y);
Equality operator. Returns true if x is the same as y.
template <;class T, class Allocator>
bool operator!=(const deque<T, Allocator>& x,
const deque<T, Allocator>& y);
Returns true if x is not the same as y.
template <;class T, class Allocator>
bool operator<;(const deque<T, Allocator>& x,
const deque<T, Allocator>& y);
Returns true if the elements contained in x are lexicographically less than
the elements contained in y.
template <;class T, class Allocator>
bool operator>(const deque<T, Allocator>& x,
const deque<T, Allocator>& y);
Returns true if the elements contained in x are lexicographically greater
than the elements contained in y.
template <;class T, class Allocator>
bool operator<;=(const deque<T, Allocator>& x,
const deque<T, Allocator>& y);
Returns true if the elements contained in x are lexicographically less than
or equal to the elements contained in y.
template <;class T, class Allocator>
bool operator>=(const deque<T, Allocator>& x,
const deque<T, Allocator>& y);
Returns true if the elements contained in x are lexicographically greater
than or equal to the elements contained in y.
template <;class T, class Allocator>
bool operator<;(const deque<T, Allocator>& x,
const deque<T, Allocator>& y);
Returns true if the elements contained in x are lexicographically less than
the elements contained in y.
SPECIALIZED ALGORITHMStemplate <;class T, class Allocator>
void swap(deque<;T, Allocator>& a, deque<T, Allocator>& b);
Swaps the contents of a and b.
EXAMPLE
//
// deque.cpp
//
#include <deque>
#include <string>
#include <iostream>
using namespace std;
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;
}
Program OutputaceofspadeskingofspadesqueenofspadesjackofspadestenofspadesWARNINGS
Member function templates are used in all containers in by the Standard
Template Library. An example of this is the constructor for
deque<T,_Allocator>, which takes two templatized 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, substitute functions 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 tem‐
plates you can construct a deque in the following two ways:
int intarray[10];
deque<int> first_deque(intarray, intarray + 10);
deque<int> second_deque(first_deque.begin(),
first_deque.end());
But not this way:deque<;long> 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 always need to supply the Allocator tem‐
plate argument. For instance, you have to write:
deque<;int, allocator<int> >
instead of:deque<;int>
If your compiler does not support namespaces, then you do not need the using
declaration for std.Rogue Wave Software 02 Apr 1998 deque(3C++)
