C++ Standard Template Library (STL) 详解
一、概述：
STL（Standard Template Library，标准模板库） 是C++标准库的核心组成部分，它提供了一系列可复用的、通用的模板化的组件，用于解决常见的数据结构和算法问题。 STL的核心思想是通过C++的模板特性，将数据（容器） 和操作数据的算法分离开来，通过迭代器作为它们之间的粘合剂。这种分离使得算法可以独立于其所操作的数据结构，极大地提高了代码的通用性和可复用性。
STL主要由以下六大组件构成，它们协同工作： 容器 (Containers)：用于存放和管理数据的类模板。如 vector, list, map。 算法 (Algorithms)：用于操作容器中数据的函数模板。如 sort(), find(), copy()。 迭代器 (Iterators)：类似于指针的对象，是容器和算法之间的桥梁。 仿函数 (Functors)：行为类似函数的对象，重载了 operator()。可以使算法的行为参数化。 适配器 (Adapters)：修饰或改变其他组件接口的类模板。如 stack, queue（容器适配器）；reverse_iterator（迭代器适配器）。 分配器 (Allocators)：负责容器内存的分配与管理。通常无需关心，使用默认的即可。
算法通过迭代器访问和操作容器中的元素，有时会使用仿函数来定制操作逻辑。
二、容器 (Containers)
容器用于存储数据集合。STL容器分为两大类：序列式容器和关联式容器。
2.1 顺序容器 (Sequence Containers)
元素的位置取决于插入的时机和地点，与元素的值无关。
2.1.1 vector（动态数组）
特点：在内存中连续存储。支持随机访问（[]或.at()），在尾部插入/删除效率高（O(1)摊销），在中间或头部插入/删除效率低（O(n)）。 适用场景：需要频繁随机访问，大部分操作在尾部进行。默认首选的序列容器。 核心操作：
- vector初始化
vector<vector<int>> vec(m,vector<int>(n,0)); - push_back()
- pop_back()
- size()
- capacity()
- reserve()
2.1.2 deque（双端队列）
特点：由多个分段连续的内存块组成。支持随机访问（效率略低于vector）。在头部和尾部插入/删除效率都很高（O(1)）。 适用场景：既需要随机访问，又需要在头尾频繁插入删除。 核心操作：
- push_back()
- pop_back()
- push_front()
- pop_front()
- empty()
2.1.3 list（双向链表）
特点：非连续存储的双向链表。不支持随机访问（只能逐个遍历）。在任何位置插入/删除效率都很高（O(1)），但需要先找到位置（查找是O(n)）。 适用场景：需要频繁在任意位置进行插入删除，且不需要随机访问。 特殊操作：
- splice()
- merge()
- sort()（有自己的成员函数sort，比通用算法std::sort更高效）。
2.1.4 forward_list（C++11，单向链表）
特点：更节省空间的单向链表。功能比 list 少。 适用场景：对内存空间要求极高，只需要单向遍历。
2.1.5 array（C++11，静态数组）
特点：封装了静态数组，大小固定。支持随机访问，效率与原生数组相同，但更安全（知道自己的大小，不会退化成指针）。 适用场景：需要固定大小的数组，并希望享受STL容器的便利（如迭代器接口）。
2.1.6 string
特点：专门用于存储字符的容器，本质上是 vector
2.2关联式容器 (Associative Containers)
关联式容器分为有序关联容器（set/multiset/map/multimap）和无序关联容器（unordered_set/unordered_multiset/unordered_map/unordered_multimap）。
2.2.1有序关联式容器:
有序关联式容器的元素是排序的，插入位置取决于元素的值（键） 和容器特定的排序准则。通常使用红黑树实现，查找效率O(logn)。
2.2.1.1 set（集合）、multiset（多重集合）
特点：键（key）即值（value），元素唯一且自动排序。multiset（多重集合）类似 set，但允许重复的元素。 核心操作：
- insert()
- find()
- erase()
- count()
2.2.1.2 map（映射）、multimap（多重映射）
特点：存储键值对（pair<const Key, Value>），键唯一且自动根据键排序。支持通过键进行高效查找（[ ] 或 .at()）。
核心操作：
- insert({key, value})
- emplace(key, value)
- find(key), [key]（若key不存在则创建）
-
注意：map的每个元素是一个 std::pair。 pair是一个模板类，可以用来将两个元素打包成一个 pair使用emplace
- 构造
- std::pair<int, std::string> p1(1, “apple”);// 方法1：使用构造函数
- auto p2 = std::make_pair(2, “banana”);// 方法2：使用 make_pair 函数（自动推导类型）
- std::pair p3(3, “cherry”); //方法3：构造函数自动推导。C++17 起使用类模板参数推导,自动推导为 pair<int, const char*>
- std::pair<int, double> p4 = {4, 3.14};// 方法4：使用花括号初始化
- 访问 auto first = p.first(); auto second = p.second(); auto [first,end] = p;
- 构造
multimap（多重映射）· 特点：类似 map，但允许重复的键。
无序关联式容器：
无序关联式容器的元素不排序，而是根据元素的哈希值组织，使用哈希表实现。查找效率在平均情况下是O(1)。当不需要元素有序，但需要极快的查找速度时，应优先选择无序容器而非 map/set。
2.2.3 unordered_set / unordered_multiset
特点：和set/mutiset一样，但是查找速度更快（无序O(1),有序O(logn)）
2.2.4 unordered_map / unordered_multimap
特点：和set/mutiset一样，但是查找速度更快（无序O(1),有序O(logn)）
三、迭代器
迭代器 (Iterators)就像一种在各个容器都可以使用的“指针”，它提供了一种方法来顺序或随机访问容器中的元素，而无需暴露容器的内部结构。
迭代器分为几类，能力从弱到强是：
- 输入迭代器 (InputIterator)：只读，且只能前移（++）。（如：istream_iterator）
- 输出迭代器 (OutputIterator)：只写，且只能前移（++）。（如：ostream_iterator）
- 前向迭代器 (ForwardIterator)：可读写，只能前移（++）。（如：forward_list的迭代器）
- 双向迭代器 (BidirectionalIterator)：可读写，能前移（++）和后移（–）。（如：list, set, map的迭代器）
- 随机访问迭代器 (RandomAccessIterator)：可读写，支持所有指针算术运算（++, –, +, -, [n]）。（如：vector, deque, array, string的迭代器）
不同的容器对应的迭代器的迭代器类型不同，每个算法对于迭代器的级别也有着不同的要求。只有容器的迭代器级别满足算法的要求才能在该容器上使用这个算法。
迭代器类型 支持操作 典型容器 输入迭代器 只读，单次遍历 istream_iterator 输出迭代器 只写，单次遍历 ostream_iterator 前向迭代器 读写，多次遍历 forward_list, unordered_* 双向迭代器 双向移动 list, set, map 随机访问迭代器 任意跳转 vector, deque, array, string
四、算法
算法通过指定的迭代器操作容器。#include <algorithm>
常见的算法有：
sort
find
auto it = find(vec.begin(),vec.end(),target);返回一个迭代器
判断是否找到
if (it != vec.end()){
;//do sth
}
循环查找
auto it = vec.begin();
while (it = find(it,vec.end(),target) != vec.end()){
queue.push(it)//处理find结果
++it;
}
binary_search
transfrom
把输入的迭代器InputIt对应的序列中的每个元素，应用一个操作，然后保存到另一个输出迭代器OutputIt对应的序列之中
#include <algorithm>
// 版本1：一元操作
template<class InputIt, class OutputIt, class UnaryOperation>
OutputIt transform(InputIt first1, InputIt last1,
OutputIt d_first, UnaryOperation unary_op);
// 版本2：二元操作
template<class InputIt1, class InputIt2, class OutputIt, class BinaryOperation>
OutputIt transform(InputIt1 first1, InputIt1 last1,
InputIt2 first2, OutputIt d_first,
BinaryOperation binary_op);
transfrom的核心是需要指定一个函数对象， 可以是以下的几种：
- C/C++标准库函数
#include
,包括其中的： 算数运算函数对象：
std::plus() std::minus () std::multiplies std::divides () std::modulus () std::negate () 比较运算函数对象：
std::equal_to() std::not_equal_to () std::greater () std::less ()： std::greater_equal () std::less_equal () 逻辑操作函数对象：
std::logical_and() std::logical_or () std::logical_not () 位运算函数对象：
std::bit_and() std::bit_or () std::bit_not () std::bit_xor ()
-
函数指针
-
Lamda表达式
五、适配器