capacity() and reserve()

Vector and string provide the functions capacity() and reserve(). They are the only STL containers that have these functions.

Reference: The C++ Standard Library by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 163.

at() and operator[]() Functions

Vectors and deques provide the at() and operator[]() functions. Having these functions happens to correspond with containers that have Random Access Iterators, with one exception. map has operator[](), but does not have a random access iterator. Map's operator[]() does not execute in constant time, O(1); whereas containers with random access iterators are able to execute in constant time.

Reference: The C++ Standard Library by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 162.

List front() and back()

On a list, el, if the element el.front() exists, then el.back() also exists.

Reference: The C++ Standard Library by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 168.

C++ Containers

C++ set, multiset, list, map, and multimap are node-based containers. The other kind of container is the array-based container. String, vector, and deque are arry-based containers.

Node-based iterators only become invalid when the item they point to is erased.

Reference: The C++ Standard Library by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 185.

Random Access Iterators

Pointers are random access iterators.

Reference: The C++ Standard Library by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 218.

Iterator Categories

Vector, deque, and string have random access iterators; list, set, multiset, map and multimap have bidirectional iterators.

The C++ Standard Library by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 239.

Reverse Iterators

All of the following have reverse iterators: vector, deque, list, set, multiset, map, multimap, and string.

Reference: The C++ Standard Library by Nicolai M. Josuttis. Addison-Wesley, 1999, p. 240.