> For the complete documentation index, see [llms.txt](https://mqjyl2012.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mqjyl2012.gitbook.io/algorithm/c-cpp/stl-basics.md). # STL基础 对C++11标准下的STL的使用方法进行学习和总结。（涉及到C++14标准和C++17标准的新特性会说明） `STL`，英文全称 `standard template library`，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，是 C++ 提供的一个基础模板的集合，用于完成诸如输入/输出、数学计算等功能。`STL` 最初由惠普实验室开发，1998 年C++的第一个国际标准定案时，正式将`STL`纳入该标准。如今 `STL` 已完全被内置到支持 C++ 的编译器中，无需额外安装，这可能也是 `STL` 被广泛使用的原因之一。 > STL 就位于各个 C++ 的头文件中，即它并非以二进制代码的形式提供，而是以源代码的形式提供。 从根本上说，`STL` 是一些容器、算法和其他一些组件的集合，所有容器和算法都是总结了几十年来算法和数据结构的研究成果，汇集了许多计算机专家学者经验的基础上实现的，因此可以说，`STL` 基本上达到了各种存储方法和相关算法的高度优化。 ## :pencil2: 发展历程 Alexander Stepanov（后被誉为 `STL` 标准模板库之父，后简称 Stepanov），1950 年出生与前苏联的莫斯科， 他曾在莫斯科大学研究数学，此后一直致力于计算机语言和泛型库研究。 1987 年，在贝尔实验室工作的 Stepanov 开始首次采用 C++ 语言进行泛型软件库的研究。由于当时的 C++ 语言还没有引入模板的编程技术，泛型库只能是通过 C++ 的继承机制来开发，代码表达起来非常笨拙。但尽管如此，Stepanov 还是开发出了一个庞大的算法库。与此同时，在与 Andrew Koenig（前 `ISO C++` 标准化委员会主席）和 Bjarne Stroustrup（C++ 语言的创始人）等顶级大师们的共事过程中，Stepanov 开始注意到 C/C++ 语言在实现其泛型思想方面所具有的潜在优势。就拿 `C/C++` 中的指针而言，它的灵活与高效运用使后来的`STL` 在实现泛型化的同时更是保持了高效率。另外，在 `STL` 中占据极其重要地位的迭代器概念便是源自于 `C/C++` 中原生指针的一般化推广。 1988 年，进入惠普的 `Palo Alto` 实验室工作，1992 年，他参加并主持了实验室主任 Bill Worley 所建立的一个有关算法的研究项目，项目自建立之后，参与者从最初的 8 人逐渐减少，最后只剩下 Stepanov 和 Meng Lee 两个人，经过长时间的努力，最终完成了一个包含有大量数据结构和算法部件的庞大运行库（HP 版本的 `C++ STL`），这便是现在 `STL` 的雏形。 1993 年，当时在贝尔实验室的 Andrew Koenig 看到了 Stepanov 的研究成果，在他的鼓励与帮助下，Stepanov 于 1993 年 9 月在圣何塞为 `ANSI/ISO C++` 标准委员会做了一个题为`“The Science of C++ Programming”` 的演讲，向委员们讲述了他的观念。然后又于 1994 年 3 月，在圣迭戈会议上向委员会提交了一份建议书，以期将 `STL` 通用库纳入 C++ 标准。 尽管这一建议十分庞大，以至于降低了被通过的可能性，但其所包含的新思想吸引了许多人的注意力。随后在众人的帮助之下，包括 Bjame Stroustrup 在内，Stepanov 又对 STL 进行了改进，同时加入了一个封装内存模式信息的抽象模块，也就是现在 STL 中的 `allocator`（内存分配器），它使 STL 的大部分实现都可以独立于具体的内存模式，从而独立于具体平台。 最终在 1994 年的滑铁卢会议上，委员们通过了提案，决定将 STL 正式纳入 C++ 标准化进程之中，随后 STL 便被放进了会议的工作文件中。自此，STL 终于成为 C++ 家族中的重要一员。此后，随者 C++ 标准的不断改进，STL 也在不断地做着相应的演化。直至 1998 年，`ANSI/ISO C++` 标准正式定案，STL 成为 C++ 标准库的重要组成部分。 ## :pencil2: 实现版本 自 1998 年 `ANSI/ISO C++` 标准正式定案，`C++ STL` 规范版本正式通过以后，由于其实开源的，各个 C++ 编译器厂商在此标准的基础上，实现了满足自己需求的 `C++ STL` 泛型库，主要包括 `HP STL、SGI STL、STLport、PJ STL、Rouge Wave STL` 等。 ### HP STL HP STL 是 Alexandar Stepanov 在惠普 Palo Alto 实验室工作时，与 Meng Lee 合作完成的。`HP STL` 是开放源码的，即任何人都可以免费使用、复制、修改、发布和销售该软件以及相关文档，但前提是必须在相关文档中，加入 `HP STL` 版本信息和授权信息。`HP STL` 是 `C++ STL` 的第一个实现版本，其它版本的 `C++ STL` 一般是以 `HP STL` 为蓝本实现出来的。不过，现在已经很少直接使用此版本的 `STL` 了。 ### SGI STL Stepanov 在离开 HP 之后，就加入到了 SGI 公司，并和 Matt Austern 等人开发了 `SGI STL`。严格意义上来说，它是 `HP STL` 的一个继承版本。和 `HP STL` 一样，`SGI STL` 也是开源的，其源代码的可读性可非常好，并且任何人都可以修改和销售它。和`STL` 官方版本来说，`SGI STL` 只能算是一个“民间”版本，因此并不是所有支持 C++ 的编译器都支持使用 `SGI STL` 模板库，唯一能确定的是，GCC 是支持这一版本的，所以 `SGI STL` 在 Linux 平台上的性能非常出色。 ### STLport 为了使 `SGI STL` 的基本代码都适用于 `VC++` 和 `C++ Builder` 等多种编译器，俄国人 Boris Fomitchev 建立了一个开源项目来开发 `STLport`，此版本 `STL` 是开放源码的。 ### PJ STL `PJ STL`（全称为 P.J. Plauger STL）是由 P.J.Plauger（美国人，1965 年毕业于普林斯顿大学，物理专业学士）参照 `HP STL` 实现出来的，也是 `HP STL` 的一个继承版本，因此该头文件中不仅含有 `HP STL` 的相关授权信息，同时还有 P.J.Plauger 本人的版权信息。其实 `PJ STL` 是 P.J.Plauger 公司的产品，尽管该公司当时只有 3 个人。`PJ STL` 被 `Visual C++` 编译器所采用，但和 `PH STL、SGI STL` 不同的是，`PJ STL` 并不是开源的。 ### Rouge Wave STL 该版本的 `STL` 是由 Rouge Wave 公司开发的，也是继承 `HP STL` 的一个版本，它也不是开源的。`Rouge Wave STL` 用于 `Borland C++ Builder` 编译器中，我们可以在 `C++ Builder` 的 `Inculde` 子目录中找到该 `STL` 的所有头文件。值得一提的是，尽管 `Rouge Wave STL` 的性能不是很好，但 `C++ Builder` 对 C++ 语言标准的支持还算不错，所以在一定程度上使 `Rouge Wave STL` 的表现得以改善。遗憾的是，由于 `Rouge Wave STL` 长期没有更新且不完全符合标准，因此 `C++ Builder` 在 6.0 版本时改用了 `STLport` 版本（之后的版本也都采用了 `STLport`），不过考虑到和之前版本的兼容，6.0 版本中依旧保留了 `Rouge Wave STL`。 ## :pencil2: 内容 通常认为，`STL` 是由**容器（`container`）、算法（`algorithm`）、迭代器（`iterator`）、函数对象（`functor`）、适配器（`adapter`）、内存分配器（`allocator`）**这 6 部分构成，其中后面 4 部分是为前 2 部分服务的，它们各自的含义如表下表所示： | `STL`的组成 | 含义 | | ---------------- | ---------------------------------------------------------------------------------------------------------------------- | | 容器（container） | 一些封装数据结构的模板类，例如 `vector` 向量容器、`list` 列表容器等。 | | 算法（algorithm） | `STL` 提供了非常多（大约 100 个）的数据结构算法，它们都被设计成一个个的模板函数，这些算法在 std 命名空间中定义，其中大部分算法都包含在头文件 `` 中，少部分位于头文件 `` 中。 | | 迭代器（iterator） | 在 `C++ STL` 中，对容器中数据的读和写，是通过迭代器完成的，扮演着容器和算法之间的胶合剂。 | | 函数对象（functor） | 如果一个类将 `()` 运算符重载为成员函数，这个类就称为函数对象类，这个类的对象就是函数对象（又称仿函数）。 | | 适配器（adapter） | 可以使一个类的接口（模板的参数）适配成用户指定的形式，从而让原本不能在一起工作的两个类工作在一起。值得一提的是，容器、迭代器和函数都有适配器。 | | 内存分配器（allocator） | 为容器类模板提供自定义的内存申请和释放功能，由于往往只有高级用户才有改变内存分配策略的需求，因此内存分配器对于一般用户来说，并不常用。 | 在惠普实验室最初发行的版本中，`STL` 被组织成 48 个头文件；但在 C++98 标准中，它们被重新组织为 13 个头文件：``、``、``、``、``、``、``、``、``、``、``、``和``。 按照 C++ 标准库的规定，所有标准头文件都不再有扩展名。以 `` 为例，此为无扩展名的形式，而 `` 为有扩展名的形式。但是，或许是为了向下兼容，或许是为了内部组织规划，某些 `STL` 版本同时存储具备扩展名和无扩展名的两份文件（例如 `Visual C++` 支持的 `PJ STL` 版本同时具备 `` 和 ``）；甚至有些 `STL` 版本同时拥有 3 种形式的头文件（例如 `SGI` 版本同时拥有 ``、`` 和 ``）；但也有个别的 `STL` 版本只存在包含扩展名的头文件（例如 `C++ Builder` 的 `Rauge Ware STL` 版本只有``）。
### **一、容器** #### **1、序列容器：** | 标准库容器类 | 描述 | | -------------- | -------------------------- | | `array` | 固定大小，直接访问任意元素 | | `deque` | 从前部或后部进行快速插入和删除操作，直接访问任何元素 | | `forward_list` | 单链表，在任意位置快速插入和删除 | | `list` | 双向链表，在任意位置进行快速插入和删除操作 | | `vector` | 从后部进行快速插入和删除操作，直接访问任意元素 | #### **2、有序关联容器（键按顺序保存）：** | 标准库容器类 | 描述 | | ---------- | -------------------- | | `set` | 快速查找，无重复元素 | | `multiset` | 快速查找，可有重复元素 | | `map` | 一对一映射，无重复元素，基于键快速查找 | | `multimap` | 一对一映射，可有重复元素，基于键快速查找 | #### **3、无序关联容器：** | 标准库容器类 | 描述 | | -------------------- | -------------------- | | `unordered_set` | 快速查找，无重复元素 | | `unordered_multiset` | 快速查找，可有重复元素 | | `unordered_map` | 一对一映射，无重复元素，基于键快速查找 | | `unordered_multimap` | 一对一映射，可有重复元素，基于键快速查找 | #### **4、容器适配器：** | 标准库容器类 | 描述 | | ---------------- | ---------- | | `stack` | 后进先出（LIFO） | | `queue` | 先进先出（FIFO） | | `priority_queue` | 优先级最高的元素先出 | 序列容器描述了线性的数据结构（也就是说，其中的元素在概念上” 排成一行")，例如数组、向量和链表。关联容器描述非线性的容器，它们通常可以快速锁定其中的元素。这种容器可以存储值的集合或 者键－值对。C++11中，关联容器中的键是不可变的（不能被修改）。序列容器和关联容器一起称为首类 容器。栈和队列都是在序列容器的基础上加以约束条件得到的，因此`STL`把stack和queue作为容器适配 器来实现，这样就可以使程序以一种约束方式来处理线性容器。类型string支持的功能跟线性容器一样， 但是它只能存储字符数据。 除此之外，有一些其他的容器种类被称为“ 近容器" （`near con`即`ner`）：C类型的基于指针的数组用于维护标志位的 `bitset`，以及用于高速向量运算的 `valarray`（这个类对运算进行了优化，也不像首类容器那么复杂）。 这些类型称为“近容器”，是因为它们展现出来的功能与首类容器类似，但是不支持所有的首类容器的功能。 ### **二、迭代器** 迭代器在很多方面与指针类似，也是用于指向首类容器中的元素（还有一些其他用途，后面将会提到）。 迭代器存有它们所指的特定容器的状态信息，即迭代器对每种类型的容器都有一个实现。 有些迭代器的操作在不同容器间是统一的。 例如，＊运算符间接引用一个迭代器，这样就可以使用它所指向的元素。++运算符使得迭代器指向容器中的下一个元素（和数组中指针递增后指向数组的下一个元素类似）。 `STL` 首类容器提供了成员函数 begin 和 end。函数 begin 返回一个指向容器中第一个元素的迭代器，函数 end 返回一个指向容器中最后一个元素的下一个元素（这个元素并不存在，常用于判断是否到达了容器的结束位仅）的迭代器。 如果迭代器 i 指向一个特定的元素，那么 `++i` 指向这个元素的下一个元素。`* i` 指代的是i指向的元素。 从函数 end 中返回的迭代器只在相等或不等的比较中使用，来判断这个“移动的迭代器” （在这里指i)是否到达了容器的末端。 使用一个 iterator 对象来指向一个可以修改的容器元素，使用一个 const\_iterator 对象来指向一个不能修改 的容器元素。 | 类型 | 描述 | | ---------------------- | ------------------------------------------------------------------- | | 随机访问迭代器(random access) | 在双向迭代湍基础上增加了直接访问容器中任意元素的功能， 即可以向前或 向后跳转任意个元素 | | 双向迭代器(bidirectional) | 在前向迭代器基础上增加了向后移动的功能。支持多遍扫描算法 | | 前向迭代器(forword) | 综合输入和输出迭代器的功能，并能保持它们在容器中的位置（作为状态信息），可以使用同一个迭代器两次遍历一个容器（称为多遍扫描算法） | | 输出迭代器(output) | 用于将元素写入容器。 输出迭代楛每次只能向前移动一个元索。 输出迭代器只支持一遍扫描算法，不能使用相同的输出迭代器两次遍历一个序列容器 | | 输入迭代器(input) | 用于从容器读取元素。 输入迭代器每次只能向前移动一个元素。 输入迭代器只支持一遍扫描算法，不能使用相同的输入迭代器两次遍历一个序列容器 | 每种容器所支持的迭代器类型决定了这种容器是否可以在指定的 `STL` 算 法中使用。 支持随机访问迭代器的容器可用于所有的 `STL` 算法（除了那些需要改变容器大小的算法，这样的算法不能在数组和 array 对象中使用）。 指向数组的指针可以代替迭代器用于几乎所有的 `STL` 算法中，包括那些要求随机访问迭代器的算法。 下表显示了每种 `STL` 容器所支持的迭代器类型。 注意， vector 、 deque 、 list 、 set 、 multiset 、 map 、 multimap( 首类容器）以及 string 和数组都可以使用迭代器遍历。 | 容器 | 支持的迭代器类型 | 容器 | 支持的迭代器类型 | | --------------- | -------- | ------------------- | -------- | | vector | 随机访问迭代器 | set | 双向迭代器 | | array | 随机访问迭代器 | multiset | 双向迭代器 | | deque | 随机访问迭代器 | map | 双向迭代器 | | list | 双向迭代器 | multimap | 双向迭代器 | | forword\_list | 前向迭代器 | unordered\_set | 双向迭代器 | | stack | 不支持迭代器 | unordered\_multiset | 双向迭代器 | | queue | 不支持迭代器 | unordered\_map | 双向迭代器 | | priority\_queue | 不支持迭代器 | unordered\_multimap | 双向迭代器 | 下表显示了在 `STL`容器的类定义中出现的儿种预定义的迭代器 `typedef`。不是每种 `typedef` 都出现在每个容器中。 我们使用常量版本的迭代器来访问只读容器或不应该被更改的非只读容器，使用反向迭代器来以相反的方向访问容器。 | 为迭代器预先定义的`typedef` | ++的方向 | 读写能力 | | ------------------------ | ----- | ---- | | iterator | 向前 | 读/写 | | const\_iterator | 向前 | 读 | | reverse\_iterator | 向后 | 读/写 | | const\_reverse\_iterator | 向后 | 读 | 下表显示了可作用在每种迭代器上的操作。 除了给出的对于所有迭代器都有的运算符，迭代器还必须提供默认构造函数、拷贝构造函数和拷贝赋值操作符。 前向迭代器支持 `++` 和所有的输入和输出迭代器的功能。 双向迭代器支持`--`操作和前向迭代器的功能。 随机访问迭代器支持所有在表中给出的操作。 另外， 对于输入迭代器和输出迭代器，不能在保存迭代器之后再使用保存的值。 | 迭代器操作 | 描述 | | -------------- | ----------------------------------------------------- | | **适用所有迭代器的操作** | | | `++p` | 前置自增迭代器 | | `p++` | 后置自增迭代器 | | `p=p1` | 将一个迭代器赋值给另一个迭代器 | | **输入迭代器** | | | `*p` | 间接引用一个迭代器 | | `p->m` | 使用迭代器读取元素 m | | `p==p1` | 比较两个迭代器是否相等 | | `p!=p1` | 比较两个迭代器是否不相等 | | **输出迭代器** | | | `*p` | 间接引用一个迭代器 | | `p=p1` | 把一个迭代器赋值给另一个 | | **前向迭代器** | 前向迭代器提供了输入和输出迭代器的所有功能 | | **双向迭代器** | | | `--p` | 前置自减迭代器 | | `p--` | 后置自减迭代器 | | **随机访问迭代器** | | | `p+=i` | 迭代器 p 前进 i 个位置 | | `p-=i` | 迭代器 p 后退 i 个位置 | | `p+i` | 在迭代器 p 的位置上前进 i 个位置 | | `p-i` | 在迭代器 p 的位置上后退 i 个位置 | | `p-q` | 表达式的值是一个整数，它代表同一个容器中两个元素间的距离 | | `p[i]` | 返回与迭代器 p 的位置相距 i 的元素 | | `pq` | 若迭代器 p 大于 q (即容器中 p 在 q 后）则返回true，否则返回false | | `p>=q` | 若迭代器 p 大于或等于 q (即容楛中 p 在 q 后或位置相同）则返回 true，否则返回 false | ### **三、算法** `STL`提供了可以用于多种容器的算法，其中很多算法都是常用的。插入、删除、搜索、排序及其他一些对部分或全部序列容器和关联容器适用的算法。 作用在容器元素上的算法只是间接地通过迭代器来实现。很多作用在序列元素上的算法通过一对迭代器定义：第一个迭代器指向这列元素的第一个，第二个迭代器指向最后一个元素之后的位置。 另外，还可以使用相似的方法创建自己的算法，这样它们就能和`STL`容器及迭代器一起使用了。 `STL`包含了大约70个标准算法，大致分为四类：\ 1、非可变序列算法：指不直接修改其所操作的容器内容的算法。\ 2、可变序列算法：指可以修改它们所操作的容器内容的算法。\ 3、排序算法：包括对序列进行排序和合并的算法、搜索算法以及有序序列上的集合操作。\ 4、数值算法：对容器内容进行数值计算。 以下对所有算法进行细致分类并标明功能： #### 1、查找算法(13个)：判断容器中是否包含某个值 * **adjacent\_find:** 在iterator对标识元素范围内，查找一对相邻重复元素，找到则返回指向这对元素的第一个元素的`ForwardIterator`。否则返回last。重载版本使用输入的二元操作符代替相等的判断。 * **binary\_search:** 在有序序列中查找value，找到返回true。重载的版本实用指定的比较函数对象或函数指针来判断相等。 * **count:** 利用等于操作符，把标志范围内的元素与输入值比较，返回相等元素个数。 * **count\_if:** 利用输入的操作符，对标志范围内的元素进行操作，返回结果为true的个数。 * **equal\_range:** 功能类似equal，返回一对iterator，第一个表示lower\_bound，第二个表示upper\_bound。 * **find:** 利用底层元素的等于操作符，对指定范围内的元素与输入值进行比较。当匹配时，结束搜索，返回该元素的一个`InputIterator`。 * **find\_end:** 在指定范围内查找"由输入的另外一对iterator标志的第二个序列"的最后一次出现。找到则返回最后一对的第一个`ForwardIterator`，否则返回输入的"另外一对"的第一个`ForwardIterator`。重载版本使用用户输入的操作符代替等于操作。 * **find\_first\_of:** 在指定范围内查找"由输入的另外一对iterator标志的第二个序列"中任意一个元素的第一次出现。重载版本中使用了用户自定义操作符。 * **find\_if:** 使用输入的函数代替等于操作符执行find。 * **lower\_bound:** 返回一个`ForwardIterator`，指向在有序序列范围内的可以插入指定值而不破坏容器顺序的第一个位置。重载函数使用自定义比较操作。 * **upper\_bound:** 返回一个`ForwardIterator`，指向在有序序列范围内插入value而不破坏容器顺序的最后一个位置，该位置标志一个大于value的值。重载函数使用自定义比较操作。 * **search:** 给出两个范围，返回一个`ForwardIterator`，查找成功指向第一个范围内第一次出现子序列(第二个范围)的位置，查找失败指向`last1`。重载版本使用自定义的比较操作。 * **search\_n:** 在指定范围内查找val出现n次的子序列。重载版本使用自定义的比较操作。 #### 2、排序和通用算法(14个)：提供元素排序策略 * **inplace\_merge:** 合并两个有序序列，结果序列覆盖两端范围。重载版本使用输入的操作进行排序。 * **merge:** 合并两个有序序列，存放到另一个序列。重载版本使用自定义的比较。 * **nth\_element:** 将范围内的序列重新排序，使所有小于第n个元素的元素都出现在它前面，而大于它的都出现在后面。重载版本使用自定义的比较操作。 * **partial\_sort:** 对序列做部分排序，被排序元素个数正好可以被放到范围内。重载版本使用自定义的比较操作。 * **partial\_sort\_copy:** 与partial\_sort类似，不过将经过排序的序列复制到另一个容器。 * **partition:** 对指定范围内元素重新排序，使用输入的函数，把结果为true的元素放在结果为false的元素之前。 * **random\_shuffle:** 对指定范围内的元素随机调整次序。重载版本输入一个随机数产生操作。 * **reverse:** 将指定范围内元素重新反序排序。 * **reverse\_copy:** 与reverse类似，不过将结果写入另一个容器。 * **rotate:** 将指定范围内元素移到容器末尾，由middle指向的元素成为容器第一个元素。 * **rotate\_copy:** 与rotate类似，不过将结果写入另一个容器。 * **sort:** 以升序重新排列指定范围内的元素。重载版本使用自定义的比较操作。 * **stable\_sort:** 与sort类似，不过保留相等元素之间的顺序关系。 * **stable\_partition:** 与partition类似，不过不保证保留容器中的相对顺序。 #### 3、删除和替换算法(15个) * **copy:** 复制序列 * **copy\_backward:** 与copy相同，不过元素是以相反顺序被拷贝。 * **iter\_swap:** 交换两个`ForwardIterator`的值。 * **remove:** 删除指定范围内所有等于指定元素的元素。注意，该函数不是真正删除函数。内置函数不适合使用remove和remove\_if函数。 * **remove\_copy:** 将所有不匹配元素复制到一个制定容器，返回`OutputIterator`指向被拷贝的末元素的下一个位置。 * **remove\_if:** 删除指定范围内输入操作结果为true的所有元素。 * **remove\_copy\_if:** 将所有不匹配元素拷贝到一个指定容器。 * **replace:** 将指定范围内所有等于`vold`的元素都用`vnew`代替。 * **replace\_copy:** 与replace类似，不过将结果写入另一个容器。 * **replace\_if:** 将指定范围内所有操作结果为true的元素用新值代替。 * **replace\_copy\_if:** 与replace\_if，不过将结果写入另一个容器。 * **swap:** 交换存储在两个对象中的值。 * **swap\_range:** 将指定范围内的元素与另一个序列元素值进行交换。 * **unique:** 清除序列中重复元素，和remove类似，它也不能真正删除元素。重载版本使用自定义比较操作。 * **unique\_copy:** 与unique类似，不过把结果输出到另一个容器。 #### 4、排列组合算法(2个)：提供计算给定集合按一定顺序的所有可能排列组合 * **next\_permutation:** 取出当前范围内的排列，并重新排序为下一个排列。重载版本使用自定义的比较操作。 * **prev\_permutation:** 取出指定范围内的序列并将它重新排序为上一个序列。如果不存在上一个序列则返回false。重载版本使用自定义的比较操作。 #### 5、算术算法(4个) * **accumulate:** iterator对标识的序列段元素之和，加到一个由val指定的初始值上。重载版本不再做加法，而是传进来的二元操作符被应用到元素上。 * **partial\_sum:** 创建一个新序列，其中每个元素值代表指定范围内该位置前所有元素之和。重载版本使用自定义操作代替加法。 * **inner\_product:** 对两个序列做内积(对应元素相乘，再求和)并将内积加到一个输入的初始值上。重载版本使用用户定义的操作。 * **adjacent\_difference:** 创建一个新序列，新序列中每个新值代表当前元素与上一个元素的差。重载版本用指定二元操作计算相邻元素的差。 #### 6、生成和异变算法(6个) * **fill:** 将输入值赋给标志范围内的所有元素。 * **fill\_n:** 将输入值赋给first到first+n范围内的所有元素。 * **for\_each:** 用指定函数依次对指定范围内所有元素进行迭代访问，返回所指定的函数类型。该函数不得修改序列中的元素。 * **generate:** 连续调用输入的函数来填充指定的范围。 * **generate\_n:** 与generate函数类似，填充从指定iterator开始的n个元素。 * **transform:** 将输入的操作作用与指定范围内的每个元素，并产生一个新的序列。重载版本将操作作用在一对元素上，另外一个元素来自输入的另外一个序列。结果输出到指定容器。 #### 7、关系算法(8个) * **equal:** 如果两个序列在标志范围内元素都相等，返回true。重载版本使用输入的操作符代替默认的等于操作符。 * **includes:** 判断第一个指定范围内的所有元素是否都被第二个范围包含，使用底层元素的<操作符，成功返回true。重载版本使用用户输入的函数。 * **lexicographical\_compare:** 比较两个序列。重载版本使用用户自定义比较操作。 * **max:** 返回两个元素中较大一个。重载版本使用自定义比较操作。 * **max\_element:** 返回一个`ForwardIterator`，指出序列中最大的元素。重载版本使用自定义比较操作。 * **min:** 返回两个元素中较小一个。重载版本使用自定义比较操作。 * **min\_element:** 返回一个`ForwardIterator`，指出序列中最小的元素。重载版本使用自定义比较操作。 * **mismatch:** 并行比较两个序列，指出第一个不匹配的位置，返回一对iterator，标志第一个不匹配元素位置。如果都匹配，返回每个容器的last。重载版本使用自定义的比较操作。 #### 8、集合算法(4个) * **set\_union:** 构造一个有序序列，包含两个序列中所有的不重复元素。重载版本使用自定义的比较操作。 * **set\_intersection:** 构造一个有序序列，其中元素在两个序列中都存在。重载版本使用自定义的比较操作。 * **set\_difference:** 构造一个有序序列，该序列仅保留第一个序列中存在的而第二个中不存在的元素。重载版本使用自定义的比较操作。 * **set\_symmetric\_difference:** 构造一个有序序列，该序列取两个序列的对称差集(并集-交集)。 #### 9、堆算法(4个) * **make\_heap:** 把指定范围内的元素生成一个堆。重载版本使用自定义比较操作。 * **pop\_heap:** 并不真正把最大元素从堆中弹出，而是重新排序堆。它把first和last-1交换，然后重新生成一个堆。可使用容器的back来访问被"弹出"的元素或者使用pop\_back进行真正的删除。重载版本使用自定义的比较操作。 * **push\_heap:** 假设first到last-1是一个有效堆，要被加入到堆的元素存放在位置last-1，重新生成堆。在指向该函数前，必须先把元素插入容器后。重载版本使用指定的比较操作。 * **sort\_heap:** 对指定范围内的序列重新排序，它假设该序列是个有序堆。重载版本使用自定义比较操作。