前言

C++ STL 六组件介绍。

---

概念

• C++：编程语言

• STL（Standard Template Library，标准模板库）：C++ 标准库的一部分，提供相关工具（函数模板、类模板和函数等）

“函数模板” 和 “类模板” 是“抽象”概念，“模板函数” 和 “模板类” 是“具体”概念。

• 六组件：容器，算法，迭代器，适配器，仿函数，分配器

• 基础（常用） 三组件：容器，算法，迭代器

• 拓展（少用） 三组件：适配器，仿函数，分配器

---

容器（container）

概念

• 组织数据的结构（所以称作：容纳物体的器具 -> 容器）
• 特性：静态
• 类比：数组

类型

顺序容器

• 数组/向量
• 链表
• 队列
• 栈

关联容器

• 图/映射
• 集合
• 对组
• 元组

数组/向量

名称	底层原理	说明
array	静态数组	C++11 标准
vector	动态数组

链表

名称	底层原理	说明
list	双向链表
forward_list	单向链表	C++11 标准

队列

名称	底层原理	说明
deque	管理数组+多个被管理数组
queue	deque	容器适配器
priority_queue	vector；堆（完全二叉树）	容器适配器

栈

名称	底层原理	说明
stack	deque	容器适配器

图/映射

名称	底层原理	说明
map	红黑树
multimap	红黑树
unordered_map	哈希表	C++11 标准
unordered_multimap	哈希表	C++11 标准

集合

名称	底层原理	说明
set	红黑树
multiset	红黑树
unordered_set	哈希表	C++11 标准
unordered_multiset	哈希表	C++11 标准

对组

名称	底层原理	说明
pair	结构体struct

元组

名称	底层原理	说明
tuple	递归继承类	C++11 标准

总表

名称	底层原理	说明
array	静态数组	C++11 标准
vector	动态数组
list	双向链表
forward_list	单向链表	C++11 标准
deque	管理数组+多个被管理数组
queue	deque	容器适配器
priority_queue	vector；堆（完全二叉树）
stack	deque	容器适配器
map	红黑树
multimap	红黑树
unordered_map	哈希表	C++11 标准
unordered_multimap	哈希表	C++11 标准
set	红黑树
multiset	红黑树
unordered_set	哈希表	C++11 标准
unordered_multiset	哈希表	C++11 标准
pair	结构体 struct
tuple	递归继承类	C++11 标准

---

代码示例

#include <vector> // vector<>
#include <iostream>using std::cout;
using std::endl;
using std::vector;int main()
{// 容器vector<int> vec{0, 1, 2}; // 存储“0、1和2”3个数据cout << vec.at(0) << endl; // 访问索引“0”的数据“0”return 0;
};
// 输出：0

---

作用（为什么需要）

• 可以高效地组织数据
• 如：直接使用 vector<> 存储数据，而无需自己编写与数组类似并比数组“高级”的“顺序表”数据结构
• 如：直接使用 list<> 存储数据，而无需自己编写“双向链表”数据结构

---

算法（algorithm）

概念

• 处理数据的操作（所以称作：算术的法门 -> 算法）
• 特性：动态
• 类比：函数

类型

这里只列举部分算法，更多参见：算法库 - cppreference.com

不修改序列的操作

• count()
• find()

修改序列的操作

• copy()
• swap()

划分操作

• partition()
• stable_partition()

排序操作

• sort()
• stable_sort()

二分搜索操作（在已排序范围上）

• lower_bound()
• binary_search()

其他已排序范围上的操作

• merge()
• inplace_merge()

集合操作（在已排序范围上）

• includes()
• set_difference()

堆操作

• is_heap()
• sort_heap()

最小/最大操作

• max()
• min()

比较操作

• equal()
• lexicographical_compare()

排列操作

• is_permutation()
• next_permutation()

数值运算

• iota()
• accumulate()

未初始化内存上的操作

• destroy_at()
• construct_at()

C 库

• qsort()
• bsearch()

---

代码示例

#include <iostream>
// #include <algorithm>	// max()using std::cout;
using std::endl;int main()
{int num1 = 1;int num2 = 2;// 算法cout << std::max(num1, num2) << endl; // 获取最大值return 0;
};
// 输出：2

---

作用（为什么需要）

• 可以高效地处理数据
• 如：直接使用 max() 比较数据，而无需自己编写比较并返回数据的比较函数算法
• 如：直接使用 find() 查找数据，而无需自己编写遍历、比较并返回数据的查找函数算法

---

迭代器（iterator）

概念

• 连接容器和算法
• 代表容器组织的数据：无需关心数据的内部实现细节，以统一的方式表示数据
• 通过算法处理数据：操作数据时，以“逐一访问”/遍历的表现形式（所以称作：迭代物品的器具 -> 迭代器）
• 特性：静 -> 动态
• 类比：数组下标/索引/位置/指针/地址

常用迭代器

• 正向迭代器：iterator<>
• 常量正向迭代器：const_iterator<>
• 反向迭代器：reverse_iterator<>
• 常量反向迭代器：const_reverse_iterator<>

类型和代码示例

类型

• 输入迭代器
• 输出迭代器
• 前向迭代器
• 双向迭代器
• 随机访问迭代器
• 连续迭代器

输入迭代器

• 从输入流中逐个读出数据
• 支持单次遍历
• istream_iterator<>

将“流”看作是一种容器，迭代器可以作用于它。

#include <iterator>
#include <iostream>using std::cin;
using std::cout;
using std::endl;
using std::istream_iterator;int main()
{// 输入迭代器istream_iterator<int> input_it(cin);int num = *input_it; // 注意：“*”解引用操作就是输入操作cout << num << endl;++input_it; // 迭代器需要“前进”偏移，否则会指向同一个“位置”num = *input_it;cout << num << endl;return 0;
}
// 输入：123
// 输出：123
// 输入：456
// 输出：456

输出迭代器

• 向输出流中逐个写入数据
• 支持单次遍历
• ostream_iterator<>

#include <iterator>
#include <iostream>using std::cout;
using std::ostream_iterator;int main()
{// 输出迭代器// ostream_iterator<int> output_it(cout);ostream_iterator<int> output_it(cout, " ");	// 第二个参数：每数据的分隔符int num = 123;*output_it = num; // 注意：“*”解引用操作就是输出操作num = 456;*output_it = num;return 0;
}
// 输出：123 456

前向迭代器

• 支持逐个前进，不支持逐个后退

“前进”指“增加”即“++/+1”操作，“后退”指“减少”即“–/-1”操作。

• 支持多次遍历
• 没有特定的类模板， 是 符合前向迭代器特性的 容器 对应的 迭代器的 类型（如 forward_list<> ，其底层原理是单向链表，支持单向前进顺序访问，不支持反向后退顺序访问，不支持随机访问，是 符合前向迭代器特性的 容器，其对应的 迭代器的 类型 是前向迭代器）

#include <forward_list>
// #include <iterator>
#include <iostream>using std::cout;
using std::endl;
using std::forward_list;int main()
{forward_list<int> for_list{0, 1, 2};// 前向迭代器forward_list<int>::const_iterator it_beg = for_list.begin(); // 数据“0”的“位置”forward_list<int>::const_iterator it_end = for_list.end();   // 数据“2”的后一个“位置”for (forward_list<int>::const_iterator it = it_beg; it != it_end; ++it){cout << *it << " ";}cout << endl;return 0;
}
// 输出：0 1 2

双向迭代器

• 支持逐个前进，支持逐个后退

• 支持多次遍历

• 没有特定的类模板， 是 符合双向迭代器特性的 容器 对应的 迭代器的 类型（如 list<> ，其底层原理是双向链表，支持单向前进顺序访问，支持反向后退顺序访问，不支持随机访问，是 符合双向迭代器特性的 容器，其对应的 迭代器的 类型 是双向迭代器）

#include <list>
// #include <iterator>
#include <iostream>using std::cout;
using std::endl;
using std::list;int main()
{list<int> li = {0, 1, 2};// 双向迭代器list<int>::const_iterator it_beg = li.begin(); // 数据“0”的“位置”list<int>::const_iterator it_end = li.end();   // 数据“2”的后一个“位置”for (list<int>::const_iterator it = it_beg; it != it_end; ++it) // 前进遍历{cout << *it << " ";}cout << endl;list<int>::const_reverse_iterator it_rbeg = li.rbegin(); // 数据“2”的“位置”list<int>::const_reverse_iterator it_rend = li.rend();   // 数据“0”的前一个“位置”for (list<int>::const_reverse_iterator it = it_rbeg; it != it_rend; ++it) // 后退遍历{cout << *it << " "; }cout << endl;return 0;
}
// 输出：0 1 2
// 输出：2 1 0

随机访问迭代器

• 支持任意前进和后退
• 支持多次遍历
• 没有特定的类模板， 是 符合随机访问迭代器特性的 容器 对应的 迭代器的 类型（如 vector<> ，其底层原理是动态数组，支持随机访问，是 符合随机访问迭代器特性的 容器，其对应的 迭代器的 类型 是随机访问迭代器）

#include <vector>
// #include <iterator>
#include <iostream>using std::cout;
using std::endl;
using std::vector;int main()
{vector<int> vec = {0, 1, 2};// 随机访问迭代器vector<int>::const_iterator it_beg = vec.begin(); // 数据“0”的“位置”cout << *(it_beg + 2) << endl; // 数据“2”的“位置”   随机访问return 0;
}
// 输出：2

连续迭代器

• C++17 标准引入
• 支持任意前进和后退
• 支持多次遍历
• 与随机访问迭代器不同，连续迭代器保证数据在内存中是连续存储的，可以提供更高效的内存访问
• 没有特定的类模板， 是 符合连续迭代器特性的 容器 对应的 迭代器的 类型（如 vector<> ，其底层原理是动态数组，支持随机访问，数据连续存储，是 符合连续迭代器特性的 容器，其对应的 迭代器的 类型 是连续迭代器）

#include <vector>
// #include <iterator>
#include <iostream>using std::cout;
using std::endl;
using std::vector;int main()
{vector<int> vec = {0, 1, 2};// 连续迭代器vector<int>::const_iterator it_beg = vec.begin(); // 数据“0”的“位置”cout << *(it_beg + 2) << endl; // 数据“2”的“位置”   随机访问return 0;
}
// 输出：2

---

容器对应的迭代器的类型

数组/向量

容器	对应的迭代器的类型
array	随机访问迭代器
vector	随机访问迭代器

链表

容器	对应的迭代器的类型
list	双向迭代器
forward_list	前向迭代器

栈

容器	对应的迭代器的类型
stack	不支持迭代器

队列

容器	对应的迭代器的类型
deque	随机访问迭代器
queue	不支持迭代器
priority_queue	不支持迭代器

图/映射

容器	对应的迭代器的类型
map	双向迭代器
multimap	双向迭代器
unordered_map	前向迭代器
unordered_multimap	前向迭代器

集合

容器	对应的迭代器的类型
set	双向迭代器
multiset	双向迭代器
unordered_set	前向迭代器
unordered_multiset	前向迭代器

对组

容器	对应的迭代器的类型
pair	不支持迭代器

元组

容器	对应的迭代器类型
tuple	不支持迭代器

总表

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

---

作用（为什么需要）

• 连接容器和算法
• 代表容器组织的数据：无需关心数据的内部实现细节，以统一的方式表示数据
• 通过算法处理数据：操作数据时，以“逐一访问”/遍历的表现形式
• 类比：容器 -> 数组，算法 -> 遍历，迭代器 ->数组下标。为了实现遍历，需要通过数组下标获取数组的数据 -> 为了实现算法，需要通过迭代器获取容器的数据

---

容器，算法，迭代器代码示例

#include <vector>    // vector<>
#include <algorithm> // find()
#include <iostream>using std::cout;
using std::endl;
using std::vector;int main()
{// 容器vector<int> vec{0, 1, 2}; // 有“0、1和2”3个数据// 迭代器vector<int>::const_iterator it_beg = vec.begin(); // 数据“0”的“位置”vector<int>::const_iterator it_end = vec.end();   // 数据“2”的后一个“位置”vector<int>::const_iterator it_res = vec.end();// 算法it_res = std::find(it_beg, it_end, 1); // 查找数据“1”if (it_res != it_end){cout << "查找到数据" << endl;}else{cout << "未查找到数据" << endl;}return 0;
};
// 输出：查找到数据

---

适配器（adapter）

概念

• 封装已有目标（容器、迭代器和函数），提供不同形式的接口（特性和函数等）
• 类比：电源适配器将 220V 的交流电转换成 20V 的直流电提供给笔记本电脑；设计模式的适配器模式

类型和代码示例

类型

• 容器适配器
• 迭代器适配器 （少用）
• 函数适配器 （少用）

容器适配器

• stack<>
• queue<>
• priority_queue<>

#include <stack> // stack<>
#include <iostream>using std::cout;
using std::endl;
using std::stack;int main()
{// 容器适配器stack<int> st{};st.push(0); // 入栈st.push(1);cout << st.top() << endl; // 获取栈顶数据st.pop(); // 出栈cout << st.top() << endl;return 0;
}
// 输出：1
// 输出：0

迭代器适配器

• 反向迭代器：reverse_iterator<>
• 插入迭代器：back_insert_iterator<>，front_insert_iterator<>，insert_iterator<>
• 流迭代器：istream_iterator<>，ostream_iterator<>
• 流缓冲迭代器：istreambuf_iterator<>，ostreambuf_iterator<>
• 移动迭代器：move_iterator<>

注意：“迭代器”和“迭代器适配器”的类型中有重叠的类型。如：stream_iterator<>，从“输入”的角度， 是“迭代器”的“输入迭代器”类型；从“流”的角度，是“迭代器适配器”的“流迭代器”类型。

一般不区分容器和容器适配器，迭代器和迭代器适配器。

代码示例见“迭代器”内容。

函数（普通函数、类方法、 仿函数和 Lambda 表达式等） 适配器

注意：很多函数适配器已不推荐/过时/弃用：bind1st()、std::bind2nd() 和 mem_fun() 等，请注意甄别

• 改变函数参数：bind()

#include <functional> // bind()，placeholders
#include <iostream>using std::cout;
using std::endl;int add(int num1, int num2) // add()
{return num1 + num2;
}int main()
{// 函数适配器auto add_bind = std::bind(add, 1, std::placeholders::_1); // 绑定 add() 的第一个参数为数据“1”int result = add_bind(2); // 调用 add_bind(x)，实际上是调用 add(1, x)cout << result << endl;return 0;
}
// 输出：3

• 封装函数：function<>

#include <functional> // function<>
#include <iostream>using std::cout;
using std::endl;int add(int num1, int num2) // add()
{return num1 + num2;
}int main()
{// 函数适配器std::function<int(int, int)> add_func = add; // 封装 add()int result = add_func(1, 2); // 调用 add_func(x, y)，实际上是调用 add(x, y)cout << result << endl;return 0;
}
// 输出：3

---

作用（为什么需要）

适配器

• 可以在已有目标（容器、迭代器和函数）的基础上提供不同形式的接口（特性和函数等），以满足特定场景需求
• 如：已有容器不满足栈数据结构的特性，封装双端队列 deque<> 容器形成 stack<> 容器适配器。直接使用 stack<> 存储数据，而无需自己编写“栈”数据结构
• 如：已有容器不满足队列数据结构的特性，封装双端队列 deque<> 容器形成 queue<> 容器适配器。直接使用 queue<> 存储数据，而无需自己编写“队列”数据结构

---

仿函数（functor）

概念

• 重载调用运算符（小括号“()”）的类的对象。（所以又称：函数对象）
• 重载调用运算符（小括号“()”）的类的对象 使用调用运算符时，表现形式和普通函数调用一样（所以称作：仿造的函数 -> 仿函数）
• 类比：函数指针；Lambda 表达式

代码示例

一般使用

#include <iostream>using std::cout;
using std::endl;// 仿函数类
class Add_functor // add()
{
public:int operator()(int num1, int num2){return num1 + num2;}
};int main()
{// 仿函数（对象）Add_functor add_functor;int result = add_functor(1, 2);cout << result << endl;return 0;
}
// 输出：3

算法使用

#include <vector>
#include <algorithm>
#include <iostream>using std::cout;
using std::endl;
using std::vector;// 仿函数类
class Comp
{
public:inline bool operator()(const int &num1, const int &num2) const{return num1 > num2; // 左数比右数大则返回 true}
};int main()
{vector<int> vec{0, 1, 2};//  仿函数（对象）Comp comp;std::sort(vec.begin(), vec.end(), comp); // std::sort() 默认从小到大排序，使用仿函数（对象）定制从大到小排序for (const int &v : vec){cout << v << " ";}cout << endl;return 0;
}
// 输出：2 1 0

---

作用（为什么需要）

• 可以代替函数指针（函数指针的签名复杂）

函数指针：指向函数的指针

• 可以通过类的特性封装更多信息，执行更多操作

参见：为什么要用仿函数？_为什么要把函数写成仿函数-CSDN博客

---

分配器（allocator）

概念

• 为容器提供自定义的内存分配和释放，对象构造和析构功能（所以称作：分配空间的器具 -> 分配器）

一般类型（内置类型和自定义类型等）内存分配（在堆上的动态内存分配）不推荐使用分配器（难用），容器分配内存可以使用分配器（少用，有需求才用）

分配器本质： 将 1. 内存分配和对象构造 和 2. 对象析构和内存释放 两个过程 拆分成 1. 内存分配 2. 对象构造 3. 对象析构 4. 内存释放 四个过程，通过定制内存管理策略提高灵活性和效率

• 类比：malloc() - free()；构造函数 - 析构函数；new - delete

---

代码示例

一般类型（内置类型和自定义类型等）

#include <memory> // allocator<>
#include <iostream>using std::allocator;
using std::cout;
using std::endl;int main()
{// 分配器allocator<int> allo;// 1. 内存分配int *int_ptr = allo.allocate(1); // 分配1个原始的/未初始化的 int 类型数据的内存// 2. 对象构造allo.construct(int_ptr, 3); // 构造对象数据为“3”cout << *int_ptr << endl;// 3. 对象析构allo.destroy(int_ptr); // 析构对象数据// 4. 内存释放allo.deallocate(int_ptr, 1); // 释放1个原始的/未初始化的 int 类型数据的内存return 0;
}
// 输出：3

容器类型

• 大多数（vector<> 和 list<> 等）容器的实现中，形参有一个默认分配器，其设计得足够安全和高效，一般不需要定制， 容器自动调用该默认分配器管理空间

// vector<> 的声明
template <class T, class Allocator = std::allocator<T>>
class vector;

• 有需求时需要自定义分配器

#include <iostream>
#include <vector>
// #include <memory>// （自定义）分配器
template <typename T>
class CustomAllocator
{
public:// 容器的设计要求：分配器必须提供一个“value_type”的类型别名，以便容器使用分配器时知道数据的类型using value_type = T;// 构造CustomAllocator() noexcept {}// 内存分配// 可能失败，不声明为 noexceptT *allocate(std::size_t n){std::cout << "Allocating memory for " << n << " objects." << std::endl; // 定制化体现return std::allocator<T>{}.allocate(n); // 使用标准分配器分配内存}// 内存释放void deallocate(T *p, std::size_t n) noexcept{std::cout << "Deallocating memory for " << n << " objects." << std::endl;std::allocator<T>{}.deallocate(p, n); // 使用标准分配器释放内存}// 对象构造// 可能失败，不声明为 noexcept// typename...：声名可变参数模板// Args：类型参数包的名称；包含零或多个类型参数；指的是类型// args：值参数包的名称；包含零或多个值参数；指的是值// Args：可变参数的类型// &&：（右值引用）保留传递给函数的 参数的 值的 特性（常量/引用左值/右值）// ...：折叠运算符（在参数左边）// args：可变参数的值// new：new 运算符：1. 内存分配 2. 对象构造// new：placement new 运算符：对象构造// placement new 运算符需要一个 void* 参数，以指定在哪个内存地址上构造对象// forward<>()：完美转发：1. 类型（Args） 2. 值的特性（&&） 3. 值（args）// ...：展开运算符（在参数右边）// (args...)：展开所有参数并作为 forward<>() 的参数 ×// (args)...：分别展开所有参数并分别作为 forward<>() 的参数 √// 使用搭配// malloc() - free()// 构造 - 析构// new - delete// 内存分配 - placement new - 析构 - deletetemplate <typename U, typename... Args>void construct(U *p, Args &&...args){std::cout << "Constructing object." << std::endl;new ((void *)p) U(std::forward<Args>(args)...); // 使用对象的构造函数构造对象}// 析构函数，用于在分配的内存上销毁对象// 没有 placement detele 运算符template <typename U>void destroy(U *p){std::cout << "Destroying object." << std::endl;p->~U(); // 使用对象的析构函数析构对象}
};int main()
{// （自定义）分配器std::vector<int, CustomAllocator<int>> vec;// 1. 内存分配// 2. 对象构造// 3. 对象析构// 4. 内存释放for (int i = 0; i < 2; ++i){vec.push_back(i);}return 0;
}
/* 输出：
Allocating memory for 1 objects.
Constructing object.
Allocating memory for 2 objects.
Constructing object.
Constructing object.
Destroying object.
Deallocating memory for 1 objects.
Destroying object.
Destroying object.
Deallocating memory for 2 objects.
*/
/* 逐行分析：
1.1 第一个容器内存分配
1.2 第一个容器第一个对象构造
2.1 第二个容器内存分配（容器扩容）
2.2 第二个容器第一个对象构造
2.2 第二个容器第二个对象构造
1.3 第一个容器第一个对象析构
1.4 第一个容器内存释放
2.3 第二个容器第二个对象析构
2.3 第二个容器第一个对象析构
2.4 第二个容器内存释放
*/

---

作用（为什么需要）

• 可以为容器提供自定义的内存分配和释放，对象构造和析构功能

分配器本质： 将 1. 内存分配和对象构造 和 2. 对象析构和内存释放 两个过程 拆分成 1. 内存分配 2. 对象构造 3. 对象析构 4. 内存释放 四个过程，通过定制内存管理策略提高灵活性和效率

• 可以先进行内存分配（占位置），有数据时再进行对象构造，以避免对象构造（二次赋值/拷贝）开销
• 可以先进行对象析构，不需要空间时再进行内存释放，以避免内存释放开销

参见：C++:allocator 学习整理 - 简书 (jianshu.com)

---

总结

C++ STL 六组件介绍。

---

参考资料

• C++ STL基本组成（6大组件+13个头文件） (biancheng.net)

• C++的基于对象编程范式、常用STL容器和C++11标准_基于对象的编程范式_夜悊的博客-CSDN博客

• cppreference.com

• 【STL十三】适配器——迭代器适配器_郑同学的笔记的博客-CSDN博客

• C++ STL：适配器 - 知乎 (zhihu.com)

• C++ STL迭代器适配器完全攻略 (biancheng.net)

• 为什么要用仿函数？_为什么要把函数写成仿函数-CSDN博客

• C++:allocator 学习整理 - 简书 (jianshu.com)

• C/C++内存申请和释放(二) - 知乎 (zhihu.com)

---

作者的话

• 感谢参考资料的作者/博主
• 作者：夜悊
• 版权所有，转载请注明出处，谢谢~
• 如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
• 文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
• 文章在认识上有错误的地方, 敬请批评指正
• 望读者们都能有所收获

---