|
VMS Help CXXLSTD, Containers, deque *Conan The Librarian |
Standard C++ Library
Copyright 1996, Rogue Wave Software, Inc.
NAME
deque - 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 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<T> >
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>&);
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 AND DESTRUCTOR
explicit
deque(const Allocator& alloc = Allocator());
The default constructor. Creates a deque of zero elements. The
deque will use the allocator alloc for all storage management.
explicit
deque(size_type n, const Allocator& alloc = Allocator());
Creates a list of length n, containing n copies of the default
value for type T. Requires that T have a default constructor.
The deque will use the allocator alloc 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 will use the allocator alloc for all
storage management.
deque(const deque<T, Allocator>& x);
Copy constructor. 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 will use the allocator
alloc for all storage management.
~deque();
The destructor. Releases any allocated memory for self.
ALLOCATOR
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 OPERATOR
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 less one.
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).
template <class Size, class T>
void
assign(Size n);
Erases all elements contained in self, then inserts n instances
of the default value of type T.
template <class Size, class T>
void
assign(Size n, const T& t);
Erases all elements contained in self, then inserts n instances
of the value of t.
reference
at(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
at(size_type) const;
Returns a constant reference to element n of self. The index n
must be between 0 and the size() - 1.
reference
back();
Returns a reference to the last element.
const_reference
back() const;
Returns a constant reference to the last element.
void
clear();
Erases all elements from the self.
bool
empty() const;
Returns true if the size of self is zero.
reference
front();
Returns a reference to the first element.
const_reference
front() const;
Returns a constant reference to the first element.
iterator
erase(iterator first, iterator last);
Deletes the elements in the range (first, last). Returns an
iterator pointing to the element following the last deleted
element, or end() if there were no elements after the deleted
range.
iterator
erase(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 elements after the deleted range.
iterator
insert(iterator position);
Inserts a copy of the default value of type T before position.
The return value points to the inserted element. Requires that
type T have a default constructor.
iterator
insert(iterator position, const T& x);
Inserts x before position. The return value points to the
inserted x.
void
insert(iterator position, size_type n, const T& x);
Inserts n copies of x before position.
template <class InputIterator>
void
insert(iterator position, InputIterator first,
InputIterator last);
Inserts copies of the elements in the range (first, last]
before position.
size_type
max_size() const;
Returns size() of the largest possible deque.
void
pop_back();
Removes the last element. Note that this function does not return
the element.
void
pop_front();
Removes the first element. Note that this function does not return
the element
void
push_back(const T& x);
Appends a copy of x to the end.
void
push_front(const T& x);
Inserts a copy of x at the front.
void
resize(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.
Otherwise, no action is taken. Requires that type T have a
default constructor.
void
resize(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_type
size() const;
Returns the number of elements.
void
swap(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);
Inequality operator. 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 lexico-
graphically 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 lexico-
graphically 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 lexico-
graphically greater than or equal to the elements con-
tained 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 lexico-
graphically less than the elements contained in y.
SPECIALIZED ALGORITHMS
template <class T, class Allocator>
void swap(deque<T, Allocator>& a, deque<T, Allocator>& b);
Efficiently swaps the contents of a and 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 C++ 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> 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 need to always supply the
Allocator template argument. For instance, you'll have to write:
deque<int, allocator<int> >
instead of:
deque<int>
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
|
|