C++ STL集成了常用数据结构和算法，以模板实现泛型，以迭代器做中间层，迭代器实现共同的算法操作容器的接口，避开了虚继承的性能损耗。

1 容器分类

容器是STL的数据结构部分，实现了不同的逻辑结构、存储结构及与数据结构结合紧密的运算（与数据结构相关的小算法）。

A map can also be used as an associative array, an array that has an arbitrary index type.

A multimap can also be used as dictionary.

All these associative container classes have an optional template argument for the sorting criterion. The default sorting criterion is the operator <. The sorting criterion is also used as the test for equivalence; that is, two elements are duplicates if neither of their values/keys is less than the other.

In unordered containers, elements have no defined order. Thus, if you insert three elements, they might have any order when you iterate over all the elements in the container. If you insert a fourth element, the order of the elements previously inserted might change. The only important fact is that a specific element is somewhere in the container.

Unordered containers are typically implemented as a hash table. Thus, internally, the container is an array of linked lists. Using a hash function, the position of an element in the array gets processed. The goal is that each element has its own position so that you have fast access to each element, provided that the hash function is fast. But because such a fast perfect hash function is not always possible or might require that the array consumes a huge amount of memory, multiple elements might have the same position. For this reason, the elements in the array are linked lists so that you can store more than one element at each array position. The major advantage of unordered containers is that finding.

All these unordered container classes have a couple of optional template arguments to specify a hash function and an equivalence criterion. The equivalence criterion is used to find specific values and to identify duplicates. The default equivalence criterion is the operator ==.

2 迭代器种类

STL迭代器是STL容器和算法的中间层。迭代器是容器内部实现的模板类，不同容器提供的迭代器的接口相同，包括通过更多一层的类型萃取器提供相同类型别名的抽象。

根据访问修改权限分类

Input iterators are able to read/process some values while iterating forward. Input stream iterators are an example of such iterators.

Output iterators are able to write some values while iterating forward.

输出迭代器（output iterator，记为：OutIt）可以修改它所指向的容器元素间接访问操作（*）++操作输入迭代器（input iterator，记为：InIt）只能读取它所指向的容器元素间接访问操作（*）和元素成员间接访问（->）++、==、!=操作。

根据迭代方式分类

前向迭代器（forward iterator，记为：FwdIt）可以读取/修改它所指向的容器元素元素间接访问操作（*）和元素成员间接访问操作（->）++、==、!=操作双向迭代器（bidirectional iterator，记为：BidIt）可以读取/修改它所指向的容器元素元素间接访问操作（*）和元素成员间接访问操作（->）++、--、==、!=操作随机访问迭代器（random-access iterator，记为：RanIt）可以读取/修改它所指向的容器元素元素间接访问操作（*）、元素成员间接访问操作（->）和下标访问元素操作（[]）++、--、+、-、+=、-=、==、!=、<、>、<=、>=操作3 算法种类

在STL中，除了用容器类模板自身提供的成员函数来操作容器元素外，还提供了一系列通用的对容器中元素进行操作的函数模板，称为算法。

STL算法实现了对序列元素的一些常规操作，用函数模板实现的。

算法与容器之间的关系

在STL中，不是把容器传给算法，而是把容器的某些迭代器传给它们，在算法中通过迭代器来访问和遍历相应容器中的元素。这样做的好处是：使得算法不依赖于具体的容器，提高了算法的通用性。

虽然容器各不相同，但它们的迭代器往往具有相容关系，一个算法往往可以接受相容的多种迭代器。

算法接受的迭代器类型

一个算法能接收的迭代器的类型是通过算法模板参数的名字来体现的。例如：

template <class InIt, class OutIt>OutIt copy(InIt src_first, InIt src_last, OutIt dst_first) {...}

src_first和src_last是输入迭代器，算法中只能读取它们指向的元素。

dst_first是输出迭代器，算法中可以修改它指向的元素。

以上参数可以接受其它相容的迭代器。

算法的操作范围

用算法对容器中的元素进行操作时，大都需要用两个迭代器来指出要操作的元素的范围。

例如：

void sort(RanIt first, RanIt last);

first是第一个元素的位置

last是最后一个元素的下一个位置

有些算法可以有多个操作范围，这时，除第一个范围外，其它范围可以不指定最后一个元素位置，它由第一个范围中元素的个数决定。例如：

OutIt copy(InIt src_first, InIt src_last, OutIt dst_first);

一个操作范围的两个迭代器必须属于同一个容器，而不同操作范围的迭代器可以属于不同的容器。

算法的自定义操作条件

有些算法可以让使用者提供一个函数或函数对象来作为自定义操作条件（或称为谓词），其参数类型为相应容器的元素类型，返回值类型为bool。

自定义操作条件可分为：

Pred：一元“谓词”，需要一个元素作为参数

BinPred：二元“谓词”，需要两个元素作为参数

算法的自定义操作

有些算法可以让使用者提供一个函数或函数对象作为自定义操作，其参数和返回值类型由相应的算法决定。

自定义操作可分为：

Op或Fun：一元操作，需要一个参数

BinOp或BinFun：二元操作，需要两个参数

算法主要由头文件<algorithm><functional><numeric>组成

<algorithm> 是所有STL头文件中最大的一个，其中常用的功能涉及到比较、交换、查找、遍历、复制、修改、反转、排序、合并等<numeric> 体积很小，只包括在几个序列容器上进行简单运算的模版函数<functional> 定义了一些模版类，用以声明函数对象

自定义的类如果想要直接使用算法库，则需补全默认构造函数、拷贝构造函数、析构函数、赋值操作符、小于操作符、等于操作符。

4 When to Use Which Container

The C++ standard library provides different container types with different abilities. The question now is: When do you use which container type? The table below provides an overview.

However, it contains general statements that might not fit in reality. For example, if you manage only a few elements, you can ignore the complexity because short element processing with linear complexity is better than long element processing with logarithmic complexity (in practice, “few” might become very large here).

As a supplement to the table, the following rules of thumb might help:

By default, you should use a vector. It has the simplest internal data structure and provides random access. Thus, data access is convenient and flexible, and data processing is often fast enough.

If you insert and/or remove elements often at the beginning and the end of a sequence, you should use a deque. You should also use a deque if it is important that the amount of internal memory used by the container shrinks when elements are removed. Also, because a vector usually uses one block of memory for its elements, a deque might be able to contain more elements because it uses several blocks.

If you insert, remove, and move elements often in the middle of a container, consider using a list. Lists provide special member functions to move elements from one container to another in constant time. Note, however, that because a list provides no random access, you might suffer significant performance penalties on access to elements inside the list if you have only the beginning of the list.

Like all node-based containers, a list doesn’t invalidate iterators that refer to elements, as long as those elements are part of the container. Vectors invalidate all their iterators, pointers, and references whenever they exceed their capacity and part of their iterators, pointers, and references on insertions and deletions. Deques invalidate iterators, pointers, and references when they change their size, respectively.

If you need a container that handles exceptions so that each operation either succeeds or has no effect, you should use either a list (without calling assignment operations and sort() and, if comparing the elements may throw, without calling merge(), remove(), remove_if(), and unique();) or an associative/unordered container (without calling the multiple-element insert operations and, if copying/assigning the comparison criterion may throw, without calling swap() or erase()).

If you often need to search for elements according to a certain criterion, use an unordered set or multiset that hashes according to this criterion. However, hash containers have no ordering, so if you need to rely on element order, you should use a set or a multiset that sorts elements according to the search criterion.

To process key/value pairs, use an unordered (multi)map or, if the element order matters, a (multi)map.

If you need an associative array, use an unordered map or, if the element order matters, a map.

If you need a dictionary, use an unordered multimap or, if the element order matters, a multimap.

序列容器选择流程图：

容器适配器选择流程图：

ref:

Nicolai M. Josuttis 《The C++ Standard Library》

-End-