The C++ Standard Library defines powerful, template-based, reusable components for common data structures and defines algorithms used to process those data structures.

There are three container-class categories—first-class containers, container adapters and near containers.

Iterators, which have properties similar to those of pointers, are used to manipulate container elements.

Standard Library algorithms are function templates that perform such common data manipulations as searching, sorting and comparing elements or entire containers.

Linked lists are collections of data items logically “lined up in a row”—insertions and removals are made anywhere in a linked list.

Stacks are important in compilers and operating systems: Insertions and removals are made only at one end of a stack—its top.

Queues represent waiting lines; insertions are made at the back (also referred to as the tail) of a queue and removals are made from the front (also referred to as the head) of a queue.

Binary trees are nonlinear, hierarchical data structures that facilitate searching and sorting data, duplicate elimination and compiling expressions into machine code.

Containers are divided into sequence containers, ordered associative containers, unordered associative containers and container adapters (p. 658).

The sequence containers (p. 658) represent linear data structures.

Associative containers are nonlinear containers that quickly locate elements stored in them, such as sets of values or key–value pairs (p. 658).

Sequence containers and associative containers are collectively referred to as first-class containers.

Class templates stack, queue and priority_queue are container adapters that enable a program to view a sequence container in a constrained manner.

Near containers (p. 659; built-in arrays, bitsets and valarrays) exhibit capabilities similar to those of the first-class containers, but do not support all the first-class-container capabilities.

Most containers provide similar functionality. Many operations apply to all containers, and other operations apply to subsets of similar containers.

First-class containers define many common nested types that are used in template-based declarations of variables, parameters to functions and return values from functions.

Iterators have many similarities to pointers and are used to point to first-class container elements.

First-class container function begin (p. 662) returns an iterator pointing to the first element of a container. Function end (p. 662) returns an iterator pointer after the container’s last element (one past the end)—typically used in a loop to indicate when to terminate processing of the container’s elements.

An istream_iterator (p. 662) is capable of extracting values in a type-safe manner from an input stream. An ostream_iterator (p. 662) is capable of inserting values in an output stream.

Input and output iterators (p. 664) can move only in the forward direction one element at a time.

A forward iterator (p. 664) combines the capabilities of input and output iterators.

A bidirectional iterator (p. 664) has the capabilities of a forward iterator and can move backward.

A random-access iterator (p. 664) has the capabilities of a bidirectional iterator and the ability to directly access any element of the container.

The Standard Library algorithms operate on container elements only indirectly through iterators.

Many algorithms operate on sequences of elements defined by iterators pointing to the first element of the sequence and to one element past the last element.

The Standard Library provides sequence containers array, vector, forward_list, list and deque. Class templates array, vector and deque are based on built-in arrays. Class templates forward_list and list implement a linked-list data structure.

Function capacity (p. 669) returns the number of elements that can be stored in a vector before the vector dynamically resizes itself to accommodate more elements.

Sequence container function push_back (p. 670) adds an element to the end of a container.

vector member function cbegin (p. 671; C++11) returns a const_iterator to the vector’s first element.

vector member function cend (p. 671; C++11) returns a const_iterator to the location past the last element of the vector.

C++14’s global cbegin and cend functions work the same way as functions begin and end, but return const iterators that cannot be used to modify the data.

C++14’s global rbegin, rend, crbegin and crend functions support iterating through a built-in array or a container from back to front. Functions rbegin and rend return iterators that can be used to modify data, and crbegin and crend return const iterators that cannot be used to modify data.

Functions begin and end and their C++14 const and reverse versions may also receive container objects as arguments—each function calls the corresponding member function in its container argument.

vector member function crbegin (p. 672; C++11) returns a const_reverse_iterator to the vector’s last element.

vector member function crend (p. 672; C++11) returns a const_reverse_iterator to the location before the first element of the vector.

As of C++11, you can ask a vector or deque to return unneeded memory to the system by calling member function shrink_to_fit (p. 672).

As of C++11, you can use list initializers to initialize the elements of vectors and other containers.

Algorithm copy (p. 674; from header <algorithm>) copies each element in a range starting with the location specified by its first iterator argument up to, but not including, the one specified by its second iterator argument.

Function front (p. 674) returns a reference to the first element in a sequence container. Function begin returns an iterator pointing to the beginning of a sequence container.

Function back (p. 674) returns a reference to the last element in a sequence container (except forward_list). Function end returns an iterator pointing to the element one past the end of a sequence container.

Sequence container function insert (p. 675) inserts value(s) before the element at a specific location and returns an iterator pointing to the inserted item or the first of the inserted items.

Function erase (p. 675; in all first-class containers except forward_list) removes specific element(s) from the container.

Function empty (p. 675; in all containers and adapters) returns true if the container is empty.

Function clear (p. 675; in all first-class containers) empties the container.

The list sequence container (p. 675; from header <list>) implements a doubly linked list that provides an efficient implementation for inserting and deleting anywhere in the container.

The forward_list sequence container (p. 676; from header <forward_list>) implements a singly linked list that supports only forward iterators.

list member function push_front (p. 678) inserts values at the beginning of a list.

list member function sort (p. 679) arranges the elements in the list in ascending order.

list member function splice (p. 679) removes elements in one list and inserts them into another list at a specific position.

list member function unique (p. 679) removes duplicate elements in a list.

list member function assign (p. 679) replaces the contents of one list with those of another.

list member function remove (p. 680) deletes all copies of a specified value from a list.

Class template deque (p. 680) provides the same operations as vector, but adds member functions push_front and pop_front (p. 679) to allow insertion and deletion at the beginning of a deque, respectively. Header <deque> must be included to use class template deque.

The Standard Library’s associative containers provide direct access to store and retrieve elements via keys (p. 681).

The four ordered associative containers are multiset, set, multimap and map. The four unordered associative containers are unordered_multiset, unordered_set, unordered_multimap and unordered_map. These are nearly identical to their ordered counterparts, but do not maintain keys in sorted order.

Class templates multiset and set provide operations for manipulating sets of values where the values are the keys—there is not a separate value associated with each key. Header <set> must be included to use class templates set and multiset.

A multiset allows duplicate keys and a set does not.

The multiset associative container (p. 682) provides fast storage and retrieval of keys and allows duplicate keys. The key order is determined by a comparator function object. If the order of the keys is not important, you can use unordered_multiset (header <unordered_set>) instead.

A multiset’s keys can be sorted in ascending order by ordering the keys with comparator function object less<T> (p. 682).

The type of the keys in all associative containers must support comparison properly based on the comparator function object specified.

A multiset supports bidirectional iterators.

Header <set> (p. 682) must be included to use class multiset.

Function count (p. 684; available to all associative containers) counts the number of occurrences of the specified value currently in a container.

Function find (p. 684; available to all associative containers) locates a specified value in a container.

Associative container functions lower_bound and upper_bound (p. 685) locate the earliest occurrence of the specified value in a container and the element after the value’s last occurrence, respectively.

Associative container function equal_range (p. 685) returns a pair containing the results of both a lower_bound and an upper_bound operation.

C++ also includes class template tuple, which is similar to pair, but can hold any number of items of various types.

As of C++14, the argument to find (and other similar functions) can be of any type, provided that there are overloaded comparison operators that can compare values of the argument’s type to values of the container’s key type.

The set associative container is used for fast storage and retrieval of unique keys. If the order of the keys is not important, you can use unordered_set (header <unordered_set>) instead.

If an attempt is made to insert a duplicate key into a set, the duplicate is ignored.

A set supports bidirectional iterators.

Header <set> must be included to use class set.

Containers multimap and map provide operations for manipulating key–value pairs. If the order of the keys is not important, you can use unordered_multimap and unordered_map instead (header <unordered_map>).

The primary difference between a multimap and a map is that a multimap allows duplicate keys with associated values to be stored and a map allows only unique keys with associated values.

The multimap associative container is used for fast storage and retrieval of key–value pairs.

Duplicate keys are allowed in a multimap, so multiple values can be associated with a single key. This is called a one-to-many relationship.

Header <map> (p. 687) must be included to use class templates map and multimap.

Function make_pair creates a pair using the types specified in the multimap’s declaration.

In C++11, if you know the key–value pairs in advance, you can use list initialization when you create a multimap.

Duplicate keys are not allowed in a map, so only a single value can be associated with each key. This is called a one-to-one mapping (p. 689). If the order of the keys is not important, you can use unordered_map (header <unordered_map>) instead.

The container adapters are stack, queue and priority_queue.

Adapters are not first-class containers, because they do not provide the actual data structure implementation in which elements can be stored and they do not support iterators.

All three adapter class templates provide member functions push and pop (p. 691) that properly insert an element into and remove an element from each adapter data structure, respectively.

Class template stack (p. 691) is a last-in, first-out data structure. Header <stack> (p. 691) must be included to use class template stack.

The stack member function top (p. 691) returns a reference to the top element of the stack (implemented by calling function back of the underlying container).

The stack member function empty determines whether the stack is empty (implemented by calling function empty of the underlying container).

The stack member function size returns the number of elements in the stack (implemented by calling function size of the underlying container).

Class template queue (p. 693) implements a FIFO data structure. Header <queue> (p. 693) must be included to use a queue or a priority_queue.

The queue member function front (p. 693) returns a reference to the first element in the queue.

The queue member function back (p. 693) returns a reference to the last element in the queue.

The queue member function empty determines whether the queue is empty.

The queue member function size returns the number of elements in the queue.

Class template priority_queue provides functionality that enables insertions in sorted order into the underlying data structure and deletions from the front of the underlying data structure.

The common priority_queue (p. 694) operations are push, pop, top, empty and size.

Class template bitset (p. 695) makes it easy to create and manipulate bit sets, which are useful for representing a set of bit flags.