C++ 标准模板库STL

前言

一、STL简介

二、STL的组件

三、STL头文件与命名空间

四、STL三大组件之 —— 容器

4.1 容器概述

4.2 序列式容器

4.3 排序式容器

4.4 哈希容器

五、STL三大组件之 —— 迭代器

5.1 迭代器概述

5.2 五种迭代器

5.3 迭代器的定义

5.4 迭代器的使用方法

六、STL三大组件之 —— 算法

6.1 查找算法

6.2 排序算法

6.3 删除/替换算法

6.4 累加 / 内积算法

6.5 赋值算法

6.6 关系运算算法

6.7 交 / 并 / 补算法

致谢

前言

本文近万字，不过每一句话都经过了我仔细斟酌，同时参阅了大量资料及底层代码。读完本文，你可以全面的掌握STL的设计思想、使用方法以及一些关键的底层实现。另外，本文可能并不适合 C++ 初学者，你可以当做字典使用。

一、STL简介

STL(Standard Template Library)标准模板库，最早由惠普实验室开发，是一个基于泛型编程思想（模板）的程序库，内嵌于C++编译器中。它提供了几乎所有常见的数据结构类型及其算法，是对基础数据结构的补充与强化。它有两个特征：

特性1：数据结构与算法的分离。基于泛型编程思想，STL中算法并不依赖于数据结构进行实现。换句话说，STL中的一个算法可以操作几种不同的容器数据。例如，sort()可作用于动态数组、栈和队列，甚至是链表。实际上，这主要是通过迭代器实现的。

特性2：STL并非面向对象(OOP)。STL中的数据结构与算法皆不具有明显的继承关系，各部分之间相互独立。“采用非面向对象的方法在逻辑上降低了各部分之间的耦合关系，以提升各自的独立性、弹性、交互操作性”。这符合泛型编程设计原理。不过，STL也采纳了一些封装的思想，令使用者不必知晓其底层实现也能应用自如。

常用的STL手册：Containers - C++ Reference、STL教程：C++ STL快速入门

二、STL的组件

要设计一个复杂的系统，当然不是用一个 .cpp 就能完成的。工程师的方法当然是将其拆分成组件，从而分别进行设计，再将这些组件按照一定规则组合起来。STL在整体上就遵循这样的设计思路。STL由6个组件组成：容器、算法、迭代器、仿函数、容器适配器、空间配置器；

容器：各种数据结构，如vector、list、deque、set、map。以模板类的方式提供。
算法：对容器中的数据执行操作的模板函数，如sort()、find()。在 std 命名空间中定义。
迭代器：一种访问容器的方法，可理解为指针。算法对容器的操作要借助迭代器才能实现。
仿函数：一种类，可以像使用函数一样使用它，可理解为更高级的运算符重载。
容器适配器：一种接口类，封装了一些基本容器，如stack、queue等。
空间配置器：自动配置与管理内存空间。使用STL时无需手动管理内存。

* 实际使用时，我们只要掌握前三个即可！

STL组件的交互关系：容器通过空间配置器取得数据存储空间，算法通过迭代器操作容器中的内容，仿函数可以协助算法，适配器可以修饰仿函数。如图： (了解即可)

三、STL头文件与命名空间

STL被定义在命名空间 std 中，头文件如下：

头文件	作用	头文件	作用
<vector>	提供 vector向量容器	<iterator>	为迭代器提供支持
<deque>	提供 deque双端队列容器	<functional>	为仿函数提供支持
<list>	提供 list列表容器	<algorithm>	为大量算法提供支持
<queue>	提供 queue队列适配器	<numeric>	为部分算法提供支持
<stack>	提供 stack栈适配器	<memory>	为配置器提供支持
<set>	提供 set集合容器	<utility>	重载关系运算符定义pair类型
<map>	提供 map 映射容器	<utility>	重载关系运算符定义pair类型

详细文档链接：STL 头文件一览表_ba_jie的博客-CSDN博客_stl头文件

四、STL三大组件之 —— 容器

4.1 容器概述

要操作任何数据，首先要解决数据的存储问题。简单地说，容器就是一个能够容纳各种数据的“桶”。不过，容器中不仅储存数据，还用各种组织方式将数据组织起来，就形成了数据结构。容器就是一个高级的桶，它里面还存放了成员函数。

根据组织数据的方式不同，STL 提供的标准容器可分为 3 类：序列容器、排序容器、哈希容器。其中后两类容器也统称为关联容器。

序列容器：主要包括 vector 向量容器、list 列表容器以及 deque 双端队列容器。元素在容器中的位置同元素的值无关，即容器不是排序的。类似数组，序列容器随机存储性能较好。
排序容器：包括 set 集合容器、multiset多重集合容器、map映射容器以及 multimap 多重映射容器。排序容器中的元素是排序好的（按键排序）。类似函数映射，排序容器查找性能较好。
哈希容器：C++11 新加入 4 种关联式容器，分别是 unordered_set 哈希集合、unordered_multiset 哈希多重集合、unordered_map 哈希映射以及 unordered_multimap 哈希多重映射。哈希容器中的元素是未排序的，元素的位置由哈希函数决定。哈希容器查找性能比排序容器更好，而遍历效果较差。

4.2 序列式容器

array<T,N> (数组容器)：可以存储 N 个元素的高级数组。容器一旦建立，其长度就固定不变；STL array容器用法详解
vector<T> (向量容器)：一个长度可变的序列容器，你常常会在LeetCode使用它。使用此容器，在尾部增加或删除元素的效率最高O(1) ，在其它位置插入或删除元素效率一般O(n) ；STL vector容器详解
deque<T> (双端队列容器)：和 vector 非常相似，区别在其在头部插入或删除元素也同样高效O(1)；STL deque容器详解
list<T> (链表容器)：一个长度可变的序列容器，底层为双向链表。在这个序列的任何地方都可以高效地增加或删除元素O(1)，但随机访问的效率一般O(n)；STL list容器详解
forward_list<T> (正向链表容器)：和 list 容器非常类似，但底层为单链表，只能正向进行访问。它比链表容器快、更节省内存。STL forward_list容器详解

4.3 排序式容器

pair<T, T> (键值对类模板)：一个类模板，用以创建键值对。STL pair用法详解
map<T, T> (映射容器)：其中存储pair对象，存储时会自动根据键的大小进行排序 (内部排序，对使用者是不可见的，除非用迭代器遍历)。容器中的键都是唯一不重复的，且不能被修改。STL map容器详解
multimap<T, T> (多重映射容器)：与map容器非常相似，区别在于multimap容器可以同时存储多个键相同的键值对。STL multimap容器用法详解
set<T> (集合容器) ：类似于map，set容器也存储pair对象，但要求键值对的键与值必须相等，故只需一个参数T。STL set容器详解
multiset<T> (多重集合容器)：与set容器非常相似，区别在于multiset容器可以同时存储多个键相同的键值对。STL multiset容器详解

4.4 哈希容器

哈希容器与排序式容器类似，但其底层依靠哈希表实现；它不会对键值对进行排序，元素的位置由哈希函数决定；

unordered_map<T, T> (哈希映射)：STL unordered_map容器用法详解
unordered_multimap<T, T> (哈希多重集合)：STL unordered_multimap容器详解
unordered_set<T> (哈希映射)：STL unordered_set容器详解
unordered_multise<T> (多重哈希映射)：STL unordered_multiset容器详解

五、STL三大组件之 —— 迭代器

5.1 迭代器概述

我们前面说到 “...分别进行设计，再将这些组件按照一定规则组合起来” ，那么，怎么将容器与算法组合起来？算法应该如何去操作容器这种复杂的组件？需要为每个容器都定制算法吗？

首先，算法要操作容器，需要有一个类似中介的装置。这个中介需要能阅读 (遍历) 容器内的数据，然后提供给算法使用。另外，它还要能对外隐藏容器的内部差异，从而以统一的界面向算法传送数据 (泛型)。在这样的思想下，迭代器应运而生。

其次，我们不需要为每个容器都定制算法。尽管不同容器的内部结构各异，但它们本质上都是用来存储大量数据的，换句话说，都是一串能存储多个数据的存储单元。因此，诸如数据的排序、查找、求和等操作方法应该在逻辑上是类似的。既然类似，完全可以利用泛型技术，将它们设计成适用所有容器的通用算法，而算法的具体化交给迭代器完成，这将大大降低我们的使用难度。
总的来说，你可以将迭代器看做适用于所有容器的强大指针，它给算法提供支持。实际上，指针就是一种迭代器。

* 以下内容不需要记忆，但要理解

STL标准库为每一种标准容器定义了一种迭代器类型，常见的有：前向迭代器、双向迭代器、随机访问迭代器、输入迭代器、输出迭代器。要注意的是，这五种迭代器都用同一语法定义：

容器类型::iterator it

而 it 具体是哪种迭代器，是由容器类型决定的；不同容器的对应的迭代器类型如下：

容器	对应的迭代器类型
array	随机访问迭代器
vector	随机访问迭代器
deque	随机访问迭代器
list	双向迭代器
set / multiset	双向迭代器
map / multimap	双向迭代器
forward_list	前向迭代器
unordered_map / unordered_multimap	前向迭代器
unordered_set / unordered_multiset	前向迭代器
stack	不支持迭代器
queue	不支持迭代器

5.2 五种迭代器

* 详细文档：迭代器是什么，C++ STL迭代器（iterator）用法详解

前向迭代器：ForwardIterator

ForwardIterator 支持 ++、* 操作，还可以被复制或赋值，可以用 == 和 != 运算符进行比较。此外，两个正向迭代器可以互相赋值；

双向迭代器：BidirectionalIterator

BidirectionalIterator 在正向迭代器的基础上，添加了 -- 操作；

随机访问迭代器：RandomAccessIterator

RandomAccessIterator 具有双向迭代器的全部功能，与指针极其相似。它支持以下操作：( i 为整数)

RandomAccessIterator += i	迭代器往后移动 i 个元素
RandomAccessIterator -= i	迭代器往前移动 i 个元素
RandomAccessIterator + i	返回后面第 i 个元素的迭代器
RandomAccessIterator - i	返回前面第 i 个元素的迭代器
RandomAccessIterator[i]	返回后面第 i 个元素的引用

另外，RandomAccessIterator 还支持 <、>、<=、>= 比较运算符。表达式 p2-p1 也是有定义的，其返回值表示 p2 所指向元素和 p1 所指向元素的序号之差。

输入迭代器

将输入流作为操作对象，了解即可

输出迭代器

将输出流作为操作对象，了解即可

5.3 迭代器的定义

前面说到，五种迭代器都是用同一语法定义的，迭代器 it 的类型由容器类型决定。不过，定义迭代器的语法不止 iterator 这一个，还有：

定义	迭代器
容器类型::iterator it	正向迭代器
容器类型::const_iterator it	常量正向迭代器
容器类型::reverse_iterator it	反向迭代器
容器类型::const_reverse_iterator it	常量反向迭代器

常量迭代器和非常量迭代器的分别在于：

非常量迭代器能修改其指向的元素

反向迭代器和正向迭代器的区别在于：

对 iterator 进行 ++ 操作时，迭代器会指向容器中的后一个元素
对 reverse_iterator 进行 ++ 操作时，迭代器会指向容器中的前一个元素

另外，以上 4 种定义迭代器的方式，并不是每种容器都适用，我们最常用的还是正向迭代器。

5.4 迭代器的使用方法

一般来说，算法常用 first、last 迭代器作为参数，其作用请顾名思义。另外，你常见到的 a.begin()、a.end()、a.begin() + 1 甚至是 a + 1，它们通通都是迭代器。

如果你不幸需要用迭代器遍历容器，你完全可以将迭代器看做指针， *it 就表示迭代器所指向的元素，使用方法如下：

    // 用 iterator 遍历数组vector<int> v = {1,2,3,4,5,6,7,8,9,10};vector<int>::iterator it;for (it = v.begin(); it != v.end(); ++it)cout << *i << " ";// 用 reverse_iterator 反向遍历数组std::reverse_iterator<std::list<int>::iterator> rbegin = values.rbegin();std::reverse_iterator<std::list<int>::iterator> rend = values.rend();while (rbegin != rend) {cout << *rbegin << " ";++rbegin;    // 反向迭代器 ++ 向前移动}

* 这里的 v.begin() 以及 v.end() 是 vector<int> 类型的迭代器，故可以相比较；

* 请不要用 it < v.end() 来代替 it != v.end() ，虽然这是正确的；

* 反向迭代器的语法特殊，详见：STL 反向迭代器适配器（reverse_iterator）详解