Standard C++ Library
Copyright 1998, Rogue Wave Software, Inc.
NAME
Containers
- A standard template library (STL) collection.
DESCRIPTION
Within the standard template library, collection classes are
often described as containers. A container stores a collec-
tion of other objects and includes basic functions that sup-
port the use of generic algorithms. Containers come in two
types: sequences and associative containers. They are
further distinguished by the type of iterator they support.
A sequence supports a linear arrangement of single elements.
vector, list, deque, bitset, and string fall into this
category. Associative containers map values onto keys, which
allows for retrieval of the values based on the keys. The
STL includes the map, multimap, set, and multiset associa-
tive containers. map and multimap store the value and the
key separately, and allow for fast retrieval of the value,
based upon fast retrieval of the key. set and multiset store
only keys allowing fast retrieval of the key itself.
CONTAINER REQUIREMENTS
Containers within the STL must meet the following require-
ments. Sequences and associative containers must also meet
their own separate sets of requirements. The requirements
for containers are:
o A container allocates all storage for the objects it
holds.
o A container X of objects of type T includes the follow-
ing types:
X::value_type a T
X::reference lvalue of T
X::const_reference const lvalue of T
X::iterator an iterator type pointing to T. X::iterator
cannot be an output iterator
X::const_iterator an iterator type pointing to const T.
X::iterator cannot be an output iterator
X::difference_type a signed integral type (must be the
same as the distance type for
X::iterator and X::const_iterator)
X::size_type an unsigned integral type representing any
non-negative value of difference_type
X::allocator_type type of allocator used to obtain storage
for elements stored in the container
o A container includes a default constructor, a copy con-
structor, an assignment operator, and a full complement
of comparison operators (==, !=, <, >, <=, >=).
o A container includes the following member functions:
begin() Returns an iterator or a const_iterator pointing
to the first element in the collection
end() Returns an iterator or a const_iterator pointing
just beyond the last element in the collection
swap(container) Swaps elements between this container and
the swap's argument
clear() Deletes all the elements in the container
size() Returns the number of elements in the collection as
a size_type
max_size() Returns the largest possible number of elements
for this type of container as a size_type
empty() Returns true if the container is empty, false oth-
erwise
get_allocator() Returns the allocator used by this con-
tainer
REVERSIBLE CONTAINERS
A container may be reversible. Essentially, a reversible
container includes a reverse iterator that allows traversal
of the collection in a direction opposite that of the
default iterator. A reversible container must meet the fol-
lowing requirements in addition to those listed above:
o A reversible container includes the following types:
X::reverse_iterator An iterator type pointing to T
X::const_reverse_iterator An iterator type pointing to
const T
o A reversible container includes the following member
functions:
rbegin() Returns a reverse_iterator or a
const_reverse_iterator pointing past the end of
the collection
rend() Returns a reverse_iterator or a
const_reverse_iterator pointing to the first ele-
ment in the collection
SEQUENCES
In addition to the requirements for containers, the follow-
ing requirements hold for sequences:
o iterator and const_iterator must be forward iterators,
bidirectional iterators or random access iterators.
o A sequence includes the following constructors:
X(n, t) Constructs a container with n copies of t
X(i, j) Constructs a container with elements from the
range [i,j)
o A sequence includes the following member functions:
insert(p,t) Inserts the element t in front of the position
identified by the iterator p
insert(p,n,t) Inserts n copies of t in front of the posi-
tion identified by the iterator p
insert(p,i,j) Inserts elements from the range [i,j) in
front of the position identified by the
iterator p
erase(q) Erases the element pointed to by the iterator q
erase(q1,q2) Erases the elements in the range [q1,q2)
o A sequence may also include the following member func-
tions if they can be implemented with constant time
complexity.
front() Returns the element pointed to by begin()
back() Returns the element pointed to by end() - 1
push_front(x) Inserts the element x at begin()
push_back(x) Inserts the element x at end()
pop_front() Erases the element at begin()
pop_back() Erases the element at end() - 1
operator[](n) Returns the element at a.begin() + n
at(n) Returns the element at a.begin() + n; throws
out_of_range if n is invalid
ASSOCIATIVE CONTAINERS
In addition to the requirements for a container, the follow-
ing requirements hold for associative containers:
o For an associative container iterator and
const_iterator must be bidirectional iterators. Associ-
ative containers are inherently sorted. Their iterators
proceed through the container in the non-descending
order of keys (where non-descending order is defined by
the comparison object that was used to construct the
container).
o An associative container includes the following types:
X::key_type the type of the Key
X::key_compare the type of the comparison to use to put
the keys in order
X::value_compare the type of the comparison used on values
o The default constructor and copy constructor for asso-
ciative containers use the template parameter com-
parison class.
o An associative container includes the following addi-
tional constructors:
X(c) Constructs an empty container using c as the com-
parison object
X(i,j,c) Constructs a container with elements from the
range [i,j) and the comparison object c
X(i, j) Constructs a container with elements from the
range [i,j) using the template parameter
comparison object
o An associative container includes the following member
functions:
key_comp() Returns the comparison object used in con-
structing the associative container
value_comp() Returns the value comparison object used in
constructing the associative container
insert(t) If the container does NOT support redundant key
values, then this function only inserts t if
there is no key present that is equal to the key
of t. If the container DOES support redundant
keys, then this function always inserts the ele-
ment t. Returns a pair<iterator,bool>. The bool
component of the returned pair indicates the
success or failure of the operation and the
iterator component points to the element with
key equal to key of t.
insert(p,t) If the container does NOT support redundant
key values, then this function only inserts t
if there is no key present that is equal to
the key of t. If the container DOES support
redundant keys, then this function always
inserts the element t. The iterator p serves
as a hint of where to start searching, allow-
ing for some optimization of the insertion. It
does not restrict the algorithm from inserting
ahead of that location if necessary.
insert(i,j) Inserts elements from the range [i,j). A
prerequisite is that i and j cannot be itera-
tors into the container.
erase(k) Erases all elements with key equal to k. Returns
number of erased elements.
erase(q) Erases the element pointed to by q
erase(q1,q2) Erases the elements in the range [q1,q2)
find(k) Returns an iterator pointing to an element with
key equal to k or end(), if such an element is not
found
count(k) Returns the number of elements with key equal to
k
lower_bound(k) Returns an iterator pointing to the first
element with a key greater than or equal to
k
upper_bound(k) Returns an iterator pointing to the first
element with a key greater than k
equal_range(k) Returns a pair of iterators such that the
first element of the pair is equivalent to
lower_bound(k) and the second element
equivalent to upper_bound(k)
SEE ALSO
bitset, deque, list, map, multimap, multiset,
priority_queue, queue, set, stack, vector