|
VMS Help CXXLSTD, Containers *Conan The Librarian |
Standard C++ Library
Copyright 1996, 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 collection of other
objects and provides certain basic functionality that supports the
use of generic algorithms. Containers come in two basic flavors:
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 provides efficient retrieval
of the values based on the keys. The STL provides 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 allowing fast retrieval of the key
itself.
CONTAINER REQUIREMENTS
Containers 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 provides 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_iterator
X::size_type an unsigned integral type representing any non-
negative value of difference_type
X::allocatr_type type of allocator used to obtain storage for
elements stored in the container
+ A container provides a default constructor, a copy
constructor, an assignment operator, and a full complement of
comparison operators (==, !=, <, >, <=, >=).
+ A container provides 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
provides a reverse iterator that allows traversal of the collection
in a direction opposite that of the default iterator. A reversible
container must meet the following requirements in addition to those
listed above:
+ A reversible container provides 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 provides 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 element in the collection.
SEQUENCES
In addition to the requirements for containers, the following
requirements hold for sequences:
+ iterator and const_iterator must be forward iterators,
bidirectional iterators or random access iterators.
+ A sequence provides 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 provides 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
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).
+ A sequence may also provide 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()
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
ASSOCIATIVE CONTAINERS
In addition to the requirements for a container, the following
requirements 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 nondescending order of keys (where
non-descending order is defined by the comparison object
that was used to construct the container).
+ An associative container provides 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 containers use the template parameter
comparison class.
+ An associative container provides the following
additional constructors:
X(c) Construct 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 provides 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) Inserts t if and only if there is no element in
the container with key equal to the key of 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).
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 less than or equal to 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
STANDARDS CONFORMANCE
ANSI X3J16/ISO WG21 Joint C++ Committee
Additional Information (explode) :
|
|