Containers(3C++) - Containers(3C++)
Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.
NAMEContainers
- A standard template library (STL) collection.
DESCRIPTION
Within the standard template library, collection classes are often
described as containers. A container stores a collection of other
objects and includes basic functions that support 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 val‐
ues based on the keys. The STL includes the map, multimap, set, and
multiset associative 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 allow‐
ing fast retrieval of the key itself.
CONTAINER REQUIREMENTSContainers within the STL must meet the following requirements.
Sequences and associative containers must also meet their own separate
sets of requirements. The requirements for containers are:
· A container allocates all storage for the objects it holds.
· A container X of objects of type T includes the following 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_itera‐
tor)
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 ele‐
ments stored in the container
· A container includes a default constructor, a copy constructor, an
assignment operator, and a full complement of comparison operators
(==, !=, <, >, <=, >=).
· 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 otherwise
get_allocator() Returns the allocator used by this container
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 con‐
tainer must meet the following requirements in addition to those listed
above:
· 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
· 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 point‐
ing to the first element in the collection
SEQUENCES
In addition to the requirements for containers, the following require‐
ments hold for sequences:
· iterator and const_iterator must be forward iterators, bidirec‐
tional iterators or random access iterators.
· 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)
· 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 position identi‐
fied 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)
· A sequence may also include the following member functions 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 following require‐
ments hold for associative containers:
· For an associative container iterator and const_iterator must be
bidirectional iterators. Associative 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).
· 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
· The default constructor and copy constructor for associative con‐
tainers use the template parameter comparison class.
· An associative container includes the following additional con‐
structors:
X(c) Constructs an empty container using c as the comparison 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
· An associative container includes the following member functions:
key_comp() Returns the comparison object used in constructing 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 element 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, allowing 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 iterators 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 ele‐
ment 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
Rogue Wave Software 02 Apr 1998 Containers(3C++)