Container Classes of the Standard Template Library
This is a brief overview of STL's container classes. For a more
comprehensive discussion see
D.R. Musser and Atul Saini, STL Tutorial and Reference
Guide: C++ Programming with the Standard Template Library,
Addison-Wesley, Reading, MA, 1996 (available now).
- Sequence Containers are objects that store collections
of other objects in a strictly linear arrangement.
- vector<T>, which provides array-like random
access to a sequence of varying length, with constant time insertions
and deletions at the end
- deque<T>, which provides random access to a sequence of
varying length, with constant time insertions and deletions at both ends
- list<T>, which provides linear time access to a
sequence of varying length, with constant time insertions and deletions anywhere
- Associative Containers provide for fast retrieval of objects
from the collection based on keys. The size of the collection can vary
at runtime. The collection is maintained in order, based on a comparison
function object of type Compare (a default template parameter
according to the STL standard, but a non-default template parameter
in the current implementation).
- set<T, Compare>, which supports unique keys (contains at
most one of each key value) and provides for fast retrieval of the keys
themselves.
- multiset<T, Compare>, which supports duplicate keys (possibly
contains multiple copies of the same key value)
and provides for fast retrieval of the keys themselves.
- map<Key, T, Compare>, which supports unique keys (contains at
most one of each key value) and provides for fast retrieval of another
type T based on the keys
- multimap<Key, T, Compare>, which supports duplicate
keys (possibly contains multiple copies of the same key value) and
provides for fast retrieval of another type T based on the
keys
All supported operations on associative containers have logarithmic
time bounds (or in some cases amortized constant bounds).