The Standard Template Library defines powerful, template-based, reusable components that implement many common data structures, and algorithms used to process those data structures.

The STL has three key componentscontainers, iterators and algorithms.

The STL containers are data structures capable of storing objects of any data type. There are three container categoriesfirst-class containers, adapters and near containers.

STL algorithms are functions that perform such common data manipulations as searching, sorting and comparing elements or entire containers.

The containers are divided into three major categoriessequence containers, associative containers and container adapters.

The sequence containers represent linear data structures, such as vectors and linked lists.

Associative containers are nonlinear containers that quickly locate elements stored in them, such as sets of values or key/value pairs.

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

First-class container function `begin` returns an iterator pointing to the first element of a container. Function end returns an iterator pointing to the first element past the end of the container (an element that doesn't exist and is typically used in a loop to indicate when to terminate processing of the container's elements).

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

Input and output iterators can move only in the forward direction (i.e., from the beginning of the container to the end) one element at a time.

A forward iterator combines the capabilities of input and output iterators.

A bidirectional iterator has the capabilities of a forward iterator and the ability to move in the backward direction (i.e., from the end of the container toward the beginning).

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

Containers that support random-access iterators, such as `vector`, can be used with all algorithms in the STL.

The STL provides three sequence containers`vector`, `list` and `deque`. Class template `vector` and class template `deque` both are based on arrays. Class template `list` implements a linked-list data structure.

Function `capacity` 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` adds an element to the end of a container.

[Page 1193]To use the algorithms of the STL, you must include the header file `<algorithm>`.

Algorithm copy copies each element in a container starting with the location specified by the iterator in its first argument and up tobut not includingthe location specified by the iterator in its second argument.

Function `front` 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` returns a reference to the last element in a sequence container. Function `end` returns an iterator pointing to the element one past the end of a sequence container.

Sequence container function `insert` inserts value(s) before the element at a specific location.

Function `erase` (available in all first-class containers) removes specific element(s) from the container.

Function `empty` (available in all containers and adapters) returns `true` if the container is empty.

Function `clear` (available in all first-class containers) empties the container.

The `list` sequence container provides an efficient implementation for insertion and deletion operations at any location in the container. Header file `<list>` must be included to use class template `list`.

The `list` member function `push_front` inserts values at the beginning of a list.

The `list` member function `sort` arranges the elements in the list in ascending order.

The `list` member function `splice` removes elements in one `list` and inserts them into another `list` at a specific position.

The `list` member function `unique` removes duplicate elements in a `list`.

The `list` member function `assign` replaces the contents of one `list` with the contents of another.

The `list` member function `remove` deletes all copies of a specified value from a `list`.

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

The STL's associative containers provide direct access to store and retrieve elements via keys.

The four associative containers are `multiset`, `set`, `multimap` and `map`.

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

The primary difference between a `multiset` and a `set` is that a `multiset` allows duplicate keys and a `set` does not.

Class templates `multimap` and `map` provide operations for manipulating values associated with keys.

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.

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

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

Functions `lower_bound` and `upper_bond` (available in all associative containers) locate the earliest occurrence of the specified value in a container and the element after the last occurrence of the specified value in a container, respectively.

Function `equal_range` (available in all associative containers) returns a `pair` containing the results of both a `lower_bound` and an `upper_bound` operation.

[Page 1194]The `multimap` associative container is used for fast storage and retrieval of keys and associated values (often called 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 file `<map>` must be included to use class templates `map` and `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.

A `map` is commonly called an associative array.

The STL provides three container adapters`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` that properly insert an element into and remove an element from each adapter data structure, respectively.

Class template `stack` enables insertions into and deletions from the underlying data structure at one end (commonly referred to as a last-in, first-out data structure). Header file `<stack>` must be included to use class template `stack`.

The `stack` member function `top` 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 get the number of elements in the `stack` (implemented by calling function `size` of the underlying container).

Class template `queue` enables insertions at the `back` of the underlying data structure and deletions from the `front` of the underlying data structure (commonly referred to as a first-in, first-out data structure). Header file `<queue>` must be included to use a `queue` or a `priority_queue`.

The `queue` member function `front` returns a reference to the first element in the `queue` (implemented by calling function `front` of the underlying container).

The `queue` member function `back` returns a reference to the last element in the `queue` (implemented by calling function `back` of the underlying container).

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

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

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` operations are `push`, `pop`, `top`, `empty` and `size`.

Algorithms `fill` and `fill_n` set every element in a range of container elements to a specific value.

Algorithms `generate` and `generate_n` use a generator function to create values for every element in a range of container elements.

Algorithm `equal` compares two sequences of values for equality.

Algorithm `mismatch` compares two sequences of values and returns a pair of iterators indicating the location in each sequence of the mismatched elements.

Algorithm `lexicographical_compare` compares the contents of two character arrays.

Algorithm `remove` eliminates all elements with a specific value in a certain range.

[Page 1195]Algorithm `remove_copy` copies all elements that do not have a specific value in a certain range.

Algorithm `remove_if` deletes all elements that satisfy the `if` condition in a certain range.

Algorithm `remove_copy_if` copies all elements that satisfy the `if` condition in a certain range.

Algorithm `replace` replaces all elements with a specific value in certain range.

Algorithm `replace_copy` copies all elements with a specific value in a certain range.

Algorithm `replace_if` replaces all elements that satisfy the `if` condition in a certain range.

Algorithm `replace_copy_if` copies all elements that satisfy the `if` condition in a certain range.

Algorithm `random_shuffle` reorders randomly the elements in a certain range.

Algorithm `count` counts the elements with a specific value in a certain range.

Algorithm `count_if` counts the elements that satisfy the `if` condition in a certain range.

Algorithm `min_element` locates the smallest element in a certain range.

Algorithm `max_element` locates the largest element in a certain range.

Algorithm `accumulate` sums the values in a certain range.

Algorithm `for_each` applies a general function to every element in a certain range.

Algorithm `transform` applies a general function to every element in a certain range and replaces each element with the result of the function.

Algorithm `find` locates a specific value in a certain range.

Algorithm `find_if` locates the first value in a certain range that satisfies the `if` condition.

Algorithm `sort` arranges the elements in a certain range in ascending order or an order specified by a predicate.

Algorithm `binary_search` determines whether a specific value is in a certain range.

Algorithm `swap` exchanges two values.

Algorithm `iter_swap` exchanges the two elements.

Algorithm `swap_ranges` exchanges the elements in a certain range.

Algorithm `copy_backward` copies elements in a certain range and places the elements in results backward.

Algorithm `merge` combines two sorted ascending sequences of values into a third sorted ascending sequence.

Algorithm `unique` removes duplicated elements in a sorted sequence of elements in a certain range.

Algorithm `reverse` reverses all the elements in a certain range.

Algorithm `inplace_merge` merges two sorted sequences of elements in the same container.

Algorithm `unique_copy` makes a copy of all the unique elements in the sorted sequence of values in a certain range.

Algorithm `reverse_copy` makes a reversed copy of the elements in a certain range.

The `set` function `includes` compares two `sets` of sorted values to determine whether every element of the second `set` is in the first `set`.

The `set` function `set_difference` finds the elements from the first `set` of sorted values that are not in the second `set` of sorted values (both `sets` of values must be in ascending order).

The `set` function `set_intersection` determines the elements from the first `set` of sorted values that are in the second `set` of sorted values (both `sets` of values must be in ascending order).

The `set` function `set_symmetric_difference` determines the elements in the first `set` that are not in the second `set` and the elements in the second `set` that are not in the first `set` (both `sets` of values must be in ascending order).

[Page 1196]The `set` function `set_union` creates a `set` of all the elements that are in either or both of the two sorted `sets` (both `sets` of values must be in ascending order).

Algorithm `lower_bound` finds the first location in a sorted sequence of values at which the third argument could be inserted in the sequence such that the sequence would still be sorted in ascending order.

Algorithm `upper_bound` finds the last location in a sorted sequence of values at which the third argument could be inserted in the sequence such that the sequence would still be sorted in ascending order.

Algorithm `make_heap` takes a sequence of values in a certain range and creates a heap that can be used to produce a sorted sequence.

Algorithm `sort_heap` sorts a sequence of values in a certain range that are already arranged in a heap.

Algorithm `pop_heap` removes the top heap element.

Algorithms `min` and `max` determine the minimum of two elements and the maximum of two elements, respectively.

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

A function object is an instance of a class that overloads `operator()`.

STL provides many predefined function objects, which can be found in header `<functional>`.

Binary function objects are function objects that take two arguments and return a value. Class template `binary_function` is an empty base class for creating binary function objects.