Introduction to STL Containers

Classification

Sequence Containers

• Vector (vector) A sequential table that can efficiently add elements at the back.
• Array (array) C++11, a fixed-length sequential table and a simple wrapper around C-style arrays.
• Deque (deque) A sequential table that can efficiently add elements at both ends.
• List (list) A linked list that can be traversed in both directions.
• Forward list (forward_list) A linked list that can only be traversed in one direction.

Associative Containers

• Set (set) A container for storing distinct elements in order. Its implementation is a red-black tree composed of nodes. Each node contains an element, and the nodes are ordered by a predicate that compares element sizes.
• Multiset (multiset) A container for storing elements in order. Equal elements are allowed.
• Map (map) A set composed of {key, value} pairs, ordered by a predicate that compares key relationships.
• Multimap (multimap) A multiset composed of {key, value} pairs; that is, a map that allows equal keys.

Unordered (Associative) Containers

• Unordered (multi)set (unordered_set/unordered_multiset) C++11, unlike set/multiset, elements are unordered; it only cares whether an element exists and uses hashing.
• Unordered (multi)map (unordered_map/unordered_multimap) C++11, unlike map/multimap, keys are unordered; it only cares about the correspondence between keys and values and uses hashing.

Container Adapters

Container adapters are not actually containers. They do not have some characteristics of containers (such as iterators and a clear() function...).

"An adapter is a mechanism that makes one thing behave like another thing." An adapter wraps a container so that it exhibits another behavior.

• Stack (stack) A last-in-first-out (LIFO) container, by default a wrapper around a deque (deque).
• Queue (queue) A first-in-first-out (FIFO) container, by default a wrapper around a deque (deque).
• Priority queue (priority_queue) A queue whose element order is determined by a predicate applied to the stored values, by default a wrapper around a vector (vector).

Common Features

Container Declaration

All have the form containerName<typeName,...> name, but the number and form of the template parameters (the parameters inside <>) vary according to the specific container.

The fundamental reason is that STL is the "Standard Template Library", so containers are all template classes.

Iterators

See Iterators.

Common Functions

=: Has an assignment operator and a copy constructor.

begin(): Returns an iterator pointing to the first element.

end(): Returns an iterator pointing to the element after the last element. end() does not point to an element, but it is the successor of the last element.

size(): Returns the number of elements in the container.

max_size(): Returns the theoretical maximum number of elements that the container can store. It varies with the container type and the type of the stored variable.

empty(): Returns whether the container is empty.

swap(): Swaps two containers.

clear(): Clears the container.

==/!=/</>/<=/>=: Compares the sizes of two containers in lexicographical order. (When comparing element sizes, each element of a map is equivalent to set<pair<key, value>>; unordered containers do not support </>/<=/>=.)