C++ STL 总结：容器、函数、算法与竞赛用法

适用范围：以 C++17 为主，完整列出这一版本的标准 STL 容器类别，按功能汇总成员函数名，以及 <algorithm>、<numeric> 的算法函数名；补充 OI 常用的 string、bitset、pair、tuple。C++20/23 新增内容单独标注。

这是学习与查阅用的总结，同名函数的多种重载合并介绍，不逐条展开模板签名、分配器重载和标准约束。STL 不等于全部 C++ 标准库，本文不展开输入输出、文件系统、线程、正则等模块。默认复杂度按元素比较、移动、哈希等单次操作为常数计算。

参考入口：OI Wiki：C++ 标准库。本文用自己的表格与示例归纳；版本、边界与复杂度同时参照对应 C++ 标准草案。

一、STL 的组成与约定

1.1 记号

• c：容器；s：字符串；b：bitset。
• first、last：迭代器；[first, last) 表示左闭右开区间。
• pos：位置，下标还是迭代器由具体函数决定。
• n：容器或输入区间大小；m：另一输入区间大小；k：匹配或处理的元素数。
• pred：返回真假值的条件；comp(a, b)：判断 a 是否排在 b 前。
• 除特别说明外，函数位于 std 命名空间。

1.2 基本规则

#include <algorithm>
#include <vector>

std::vector<int> a = {4, 1, 3, 2};
std::sort(a.begin(), a.end());             // 整个数组
std::sort(a.begin() + 1, a.begin() + 3);  // 只处理下标 1、2

end() 指向最后一个元素之后，不能解引用。空容器的 begin() == end()。<bits/stdc++.h> 是部分 GCC 环境的扩展头文件，不属于标准 C++；跨编译器时应包含各自的标准头文件。

二、容器总览与选型

2.1 序列容器

2.2 关联容器

有序容器通常由平衡搜索树实现，标准规定的是行为与复杂度，不强制使用红黑树。无序容器不保证遍历顺序，也不提供有序边界查询。来源：OI Wiki：关联式容器、无序关联式容器。

2.3 容器适配器与常用辅助类型

string、bitset 等经常与 STL 一起学习；其中 bitset 不提供普通 STL 容器的迭代器接口。它们在本文作为相关标准库工具单列。

2.4 怎么选

三、通用成员函数

这些是通用接口家族，不代表每个容器都具有全部函数。 后续表格指出重要例外。

常用初始化：

std::vector<int> a;                  // 空数组
std::vector<int> b(5);               // 5 个 0
std::vector<int> c(5, 7);            // 5 个 7
std::vector<int> d{5, 7};            // 两个元素：5、7
std::vector<int> e(c.begin(), c.end());
std::vector<int> f = c;              // 复制
std::vector<int> g = std::move(f);   // 移动；不要假定 f 一定为空

() 与 {} 可能选择不同构造函数。容器复制通常随元素数线性增长；移动的复杂度会受构造/赋值形式和分配器条件影响。

四、序列容器

参考：OI Wiki：序列式容器。

4.1 vector：动态数组

std::vector<int> v = {10, 20, 30};

v.reserve(100);                   // 只是预留空间
v.push_back(40);
v.insert(v.begin() + 1, 15);
v.erase(v.begin() + 2);           // 删除第三个元素
v.erase(v.begin(), v.begin() + 2);

vector<bool> 是位压缩特化，v[i] 可能是代理对象，不能把它当作普通 bool&；它还有 flip()，用于翻转所有位。需要普通布尔数组行为时可考虑 vector<char>。容量与重分配规则参照 C++17 vector 条款。

4.2 array：固定长度数组

std::array<int, 4> a = {1, 2, 3, 4};

没有 push_back、insert、erase、resize、clear、reserve。使用 std::array<int, 4> a{}; 可把整数元素零初始化。

4.3 deque：双端队列

支持通用的大小查询、正反向迭代、分配器与交换接口。没有 data()、capacity()、reserve()；能随机访问不代表内存连续。

4.4 list：双向链表

支持 size()、正反向迭代。没有下标与 data()。sort、merge、splice 通过链表节点操作完成；跨容器拼接/合并需满足分配器相等等前置条件，且不要给出重叠的非法目标位置。

不能 std::sort(l.begin(), l.end())，应使用 l.sort()。 定位到某个下标本身要 O(n)，因此“链表插删 O(1)”的前提是已经知道节点位置。

4.5 forward_list：单向链表

没有 size()、back()、反向迭代器、push_back()、普通 insert/erase。已知前驱时单节点插删 O(1)，需要扫描节点的操作按扫描数量计算；整条单链表拼接可能需要找尾节点，不能直接套用 list::splice 的常数复杂度。

std::forward_list<int> f = {1, 2, 3};
auto before = f.before_begin();
f.insert_after(before, 0);  // 0, 1, 2, 3
f.erase_after(before);     // 1, 2, 3

前驱及删除区间规则参照 C++17 forward_list 条款。

五、有序关联容器

5.1 set / multiset

std::set<int> s = {3, 1, 2};         // 遍历得到 1, 2, 3
std::multiset<int> ms = {1, 1, 2};   // 保留重复值

自定义比较器时，“相等”按 !comp(a,b) && !comp(b,a) 判断，不一定是 a == b。lower_bound、upper_bound 也按比较器定义边界，表中的 >=、> 仅适用于默认升序。

auto it = ms.find(1);
if (it != ms.end()) ms.erase(it);  // 只删除一个 1
ms.erase(1);                      // 删除剩余的所有 1

有序集合中的键不能通过迭代器直接修改，否则会破坏排序。extract() 取出的非空节点句柄可以修改值，再插回。

5.2 map / multimap

map<K, V> 的元素类型是 pair<const K, V>：键不可直接改，值可改。

除了上面差异，还支持有序关联容器的提示插入、迭代器与管理接口。按键访问通常 O(log n)；multimap 的计数和按键删除要额外处理 k 个匹配项。

std::map<std::string, int> cnt;
++cnt["apple"];                         // 缺失时先创建 0，再加 1
cnt.insert({"apple", 9});               // 已存在，不覆盖
cnt.insert_or_assign("apple", 9);       // 更新为 9

auto it = cnt.find("pear");             // 查询不会插入
if (it != cnt.end()) {
    int value = it->second;
    (void)value;
}

for (const auto& [key, value] : cnt) {   // C++17 结构化绑定
    // 按键升序遍历
}

multimap 没有 operator[]、at、try_emplace、insert_or_assign。同键的全部元素用 equal_range(key) 遍历；单次 find 不会返回全部重复项。关联容器的精确接口约束见 C++17 关联容器要求。

六、无序关联容器

6.1 四种类型

支持 insert、提示插入、emplace、emplace_hint、find、count、equal_range、erase、clear、swap、begin/end、cbegin/cend、大小与分配器接口。

仅 unordered_map 有 operator[]、at、try_emplace、insert_or_assign；四类都有 C++17 的 extract、节点插入、merge，以及 C++20 的 contains。

没有 lower_bound、upper_bound、反向迭代接口和排序比较器。 equal_range 只是返回等价键所在区间，不表示有序边界。

6.2 哈希专属函数

std::unordered_map<int, int> cnt;
cnt.max_load_factor(0.7f);
cnt.reserve(100000);
++cnt[42];

键相等时必须有相同哈希值。重哈希平均 O(n)、最坏 O(n²)，可能使迭代器失效，但不会使存活元素的引用或指针失效。预留容量有助于减少重哈希次数，不能保证消除哈希冲突。来源：C++17 无序容器要求。

七、容器适配器

参考：OI Wiki：容器适配器。三个适配器都不公开迭代器，也没有 clear()。

7.1 stack：栈

std::stack<int> st;  // 默认底层容器 deque<int>

默认底层 deque 时，单元素操作 O(1)。可用 vector 或 list 等满足接口的容器作为底层；若用 vector，尾插为均摊 O(1)。

7.2 queue：队列

std::queue<int> q;  // 默认底层容器 deque<int>

默认单元素操作 O(1)。底层需支持 pop_front，所以不能直接使用 vector。

7.3 priority_queue：优先队列

std::priority_queue<int> big;  // 默认大根堆
std::priority_queue<int, std::vector<int>, std::greater<int>> small;

不能直接删除任意位置，也没有标准的 decrease_key。Dijkstra 常用“插入新状态，弹出时跳过旧状态”。默认比较器 less<T> 使最大的元素优先，greater<T> 使最小的元素优先。

三个适配器的 pop() 都不返回元素，取值要先访问再删除：

if (!q.empty()) {
    int x = q.front();
    q.pop();
    (void)x;
}

八、string、string_view、bitset

8.1 string：字符串

std::string 是 std::basic_string<char> 的别名。参考：OI Wiki：string。

std::string s = "hello";
std::string t(3, 'a');  // "aaa"

字符串查找不要一概当作 O(log n) 或 O(n)：朴素子串匹配可能 O(nm)，具体标准复杂度保证与函数/重载有关；需要稳定线性上界的长串匹配可使用 KMP 等算法。

auto pos = s.find("ll");
if (pos != std::string::npos) {
    std::string part = s.substr(pos, 2);  // "ll"
    (void)part;
}
s.erase(1, 2);  // "hello" -> "hlo"

相关非成员函数：

转换失败可抛 invalid_argument，超范围可抛 out_of_range。stoi("123abc") 可只解析前缀，若要确认整串合法需检查解析终点。

8.2 string_view：字符串视图，C++17

string_view 只保存指针与长度，不管理原字符串的生命周期。

std::string owner = "abcdef";
std::string_view view(owner);
view.remove_prefix(2);  // view 是 "cdef"，owner 仍为 "abcdef"

不要把临时字符串的结果留给 view，例如 std::string_view v = owner.substr(1); 在该语句结束后就悬空；应先让 string 保存子串，或对 string_view(owner) 调用 substr。

8.3 bitset：固定大小位集合

参考：OI Wiki：bitset。

std::bitset<8> b(std::string("00001101"));
// 下标 0 是最低位，即显示字符串最右边的位

没有 push_back、动态 resize 或普通迭代器。批量位运算在常见实现中约需 O(ceil(N / W)) 个机器字操作，W 常为 32/64；这不是标准对具体存储布局的保证。_Find_first()、_Find_next() 是部分实现的扩展，不属于标准接口。

九、pair、tuple 与实用工具

9.1 pair

参考：OI Wiki：pair。

std::pair<int, int> p = {2, 5};
auto [x, y] = p;  // C++17；按值拆开，改变 x 不改变 p
auto& [a, b] = p; // 按引用绑定，可修改 p

9.2 tuple

int x = 0, y = 0;
std::tie(x, y) = std::make_pair(3, 4);
auto t = std::make_tuple(2, 3);
int sum = std::apply([](int a, int b) { return a + b; }, t);

9.3 <utility> 常用函数

十、迭代器

参考：OI Wiki：迭代器。迭代器像指针，但通常不会自动替你检查所有越界或失效情况。

10.1 分类

输入与输出不是简单的同一条继承链；输出迭代器不保证可读取。vector<bool> 不满足普通连续容器的元素引用要求。

10.2 <iterator> 函数与适配器

advance、next、prev、distance 对随机访问迭代器通常 O(1)，对链表等通常 O(步数)。负向移动需要双向能力且不能越界；distance 用于非随机访问迭代器时，last 必须可由 first 向前到达。

std::vector<int> src = {1, 2, 3}, dst;
std::copy(src.begin(), src.end(), std::back_inserter(dst));

back_inserter 自动调用 push_back，不用事先给 dst 调整长度。反向迭代器 rit 的 base() 指向其正向后继：rbegin().base() == end()。

十一、algorithm 函数分类表

头文件：<algorithm>。以下列出 C++17 的普通算法函数名，默认不展开执行策略重载；swap 的基础声明属于 <utility>，这里随交换算法一起列出。

表中 out 表示可写输出迭代器。普通复制/转换算法不会自动扩容目标容器；目标必须有足够的已有元素，或使用 back_inserter。如果存在允许的输入输出重叠，需要遵守对应算法的方向和重叠约束。

11.1 判断、遍历与计数

空区间上 all_of 和 none_of 返回 true，any_of 返回 false。

11.2 查找、匹配与比较

equal、mismatch、is_permutation 也有只给第二段起点的旧重载；使用时必须保证第二段足够长。find_end 的目标是完整子序列最后一次出现，find_first_of 的目标是任意一个候选元素，二者不同。

相关接口依据：C++17 非修改算法。

11.3 复制、移动、交换与变换

区间算法通常 O(n)，swap/iter_swap 的成本由元素类型决定。std::move(x) 是 <utility> 的类型转换函数；std::move(first,last,out) 是 <algorithm> 的区间移动算法。

11.4 填充、生成与替换

均按处理元素数线性计；带 copy 的版本返回输出尾后位置，普通 replace 返回 void。

11.5 移除与去重

这些操作通常 O(n)。remove、unique 不会改变容器 size，逻辑新终点之后的元素不要作为有效结果使用。

std::vector<int> v = {3, 1, 1, 2, 3};
v.erase(std::remove(v.begin(), v.end(), 2), v.end());
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());  // 1, 3

list::remove 是真正删除节点的成员函数；std::remove 是压紧区间的通用算法。相关语义依据：C++17 修改序列算法。

11.6 反转、旋转、随机化

std::mt19937 rng(std::random_device{}());  // <random>
std::shuffle(v.begin(), v.end(), rng);

sample 有迭代器类别约束：若输入不是前向迭代器，输出必须支持随机访问。random_shuffle 在 C++14 被弃用、C++17 移除。来源：OI Wiki：STL 算法。

11.7 排序与部分排序

前三种原地排序与 nth_element 要求随机访问迭代器。partial_sort_copy 的输出要求随机访问，输入可以更弱。nth_element 在有重复值时允许左右出现与 nth 等价的元素，不能理解成“左侧全严格小于、右侧全严格大于”。

int k = 2;  // 求第 2 小，1 <= k <= v.size()
std::nth_element(v.begin(), v.begin() + (k - 1), v.end());
int answer = v[k - 1];

11.8 二分查找

都可给比较器。对完整升序数组直接使用最容易保证正确；标准的精确前提是按相关比较表达式分区。比较次数 O(log n)，但对非随机访问迭代器可能发生 O(n) 次迭代器移动。

set/map 使用 s.lower_bound(x) 这类成员函数，可保持 O(log n)；不要为了查树容器写通用 std::lower_bound(s.begin(), s.end(), x)。

std::vector<int> a = {1, 2, 2, 4, 7};
auto l = std::lower_bound(a.begin(), a.end(), 2);
auto r = std::upper_bound(a.begin(), a.end(), 2);
auto number = r - l;  // 2

11.9 分区

普通分区类操作一般线性。stable_partition 谓词调用 O(n)，无足够辅助空间时交换可达 O(n log n)。partition_point 判断次数 O(log n)，非随机访问迭代器仍可能线性移动。

11.10 合并与有序集合运算

以下输入区间需按同一比较规则排序；集合运算也允许重复元素，按重复次数处理。

除 inplace_merge 外一般 O(n + m)；inplace_merge 有足够辅助空间时线性，否则 O(n log n) 比较。四种 set_ 算法返回输出尾后位置；名称中的 set 不要求输入来自 std::set。

11.11 堆操作

这些算法把随机访问区间当作堆。默认大根堆，可用 greater<T> 构造小根堆。

前四个返回 void。pop_heap 不删除元素，vector 上还要 pop_back()；push_heap 也不添加元素，要先 push_back()。

11.12 最值与区间限制

区间版本 O(n)，两参数版本 O(1)。min_element/max_element 返回首次最值；minmax_element 返回首次最小值和最后一次最大值。初始化列表最值要求非空；不要把临时对象参与的引用返回值保存成长期引用。

11.13 排列

单次 O(n)，至少双向迭代器。从升序排列开始循环 next_permutation，可枚举全部不同排列；空序列在 do-while 写法中也会执行一次循环体。

std::sort(v.begin(), v.end());
do {
    // 处理当前排列
} while (std::next_permutation(v.begin(), v.end()));

排序、二分、分区、集合、堆、最值与排列的精确保证参照 C++17 排序及相关算法。

十二、numeric 数值算法

头文件：<numeric>。

前十一种区间算法通常线性；写输出的扫描、差分、前缀和函数返回输出尾后位置，iota 返回 void，归约类返回计算值。gcd/lcm 的复杂度标准未规定，常见实现基于欧几里得算法。

std::vector<int> a = {1, 2, 3};
long long sum = std::accumulate(a.begin(), a.end(), 0LL);
std::vector<long long> prefix(a.size());
std::partial_sum(a.begin(), a.end(), prefix.begin());  // 1, 3, 6

partial_sum 的内部累积类型取自输入元素类型，仅把输出改成 long long 不足以防止 int 累加溢出。需要大数前缀和时，用 long long 输入，或自己用 long long 累加器循环。

accumulate(..., 0) 可能在 int 中溢出，应按需求使用 0LL 或 0.0。reduce 不是简单改名的 accumulate：非结合或非交换运算，以及浮点运算，可能得到不同结果；并行时还要注意函数对象的线程安全。来源：C++17 数值算法。

十三、函数对象与分配器

13.1 <functional> 函数对象

这些对象通常通过 operator() 调用。C++14 的 less<> 等透明版本可以比较不同但可比较的类型。less_equal 不能直接用作 sort/set 的排序比较器，因为 comp(x,x) 必须为 false。

空的 std::function 被调用会抛 bad_function_call。旧 unary_function、binary_function、bind1st、bind2nd 等已在 C++17 移除；旧 not1/not2、ptr_fun 等也不适合作为新代码模板。工具接口来源：C++17 函数对象。

13.2 lambda 与排序比较器

std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;  // 降序
});

排序比较器必须形成严格弱序：自身不小于自身，比较规则一致且具有必要的传递性。例如按分数降序、同分编号升序：

struct Student { int id, score; };
std::vector<Student> students = {{2, 90}, {1, 90}, {3, 95}};
std::sort(students.begin(), students.end(), [](const Student& a, const Student& b) {
    if (a.score != b.score) return a.score > b.score;
    return a.id < b.id;
});

13.3 <memory> 分配器与底层算法

allocator::construct/destroy/max_size/address 等旧成员在 C++17 弃用、C++20 移除；泛型代码通过 allocator_traits 操作更合适。std::pmr 是 C++17 的多态内存资源设施，见 <memory_resource>。

这些是对象生命周期管理接口，不能与对已构造元素赋值的 copy/fill 混用。常规竞赛代码使用容器自动管理内存即可。参照 C++17 allocator、标准草案：特殊内存算法。

13.4 <execution> 执行策略

部分算法提供策略重载，例如 sort(std::execution::par, first, last)。实现是否实际并行取决于标准库支持；竞赛中普通重载通常足够。并行/无序策略下，回调不可随意修改共享状态或使用不允许的同步操作；标准执行策略下回调异常可能导致 terminate。

十四、C++20/23 补充

本章为新标准常用接口补充，不声称覆盖 C++20/23 的整个标准库。 使用前确认评测环境的编译选项和标准库支持。

14.1 C++20 常用新增

span 常用接口：begin/end/rbegin/rend、front/back、operator[]、data、size、size_bytes、empty、first、last、subspan；另有非成员 as_bytes、as_writable_bytes。C++20/23 的 span 没有 at()，也不拥有底层数据。

14.2 ranges 与 views，C++20

std::ranges 提供带范围概念约束的算法，许多函数可直接接收容器：

// C++20，需要 <algorithm> 与 <ranges>
std::ranges::sort(v);
auto it = std::ranges::find(v, 3);
auto even = v | std::views::filter([](int x) { return x % 2 == 0; });

不是所有旧算法都有同名 ranges 版本，例如 C++20 没有 ranges::accumulate。range 算法可能返回 subrange 或带多个字段的结果结构，而不是旧版相同返回类型；ranges::remove/unique 同样不真正删除容器元素。

views 通常惰性处理，也不一定拥有底层数据；底层对象失效后不能继续访问视图。来源：C++23 草案中的范围适配器。

14.3 C++23 常用新增

本章的新算法和视图属于 std::ranges 或 std::views，不要擅自去掉命名空间改写成同名 std 算法。

14.4 C++23 平坦关联容器

头文件：<flat_set>、<flat_map>。默认用 vector 家族存储有序数据，查找 O(log n)，单次插删通常 O(n)，迭代器失效规则与树容器不同。

这些 extract() 是取出整个底层存储，并非 C++17 树容器的 extract(key) 节点句柄操作；它们有右值限定，通常写作 std::move(c).extract()。不要假设 replace 会自动修复未排序、键值长度不一致或非法重复的数据；需满足对应前置条件。来源：C++23 flat_map、flat_set。

十五、迭代器失效与常见坑

15.1 迭代器失效速查

下表聚焦增删操作；clear、赋值、swap、移动及分配器有关操作需再查对应规则。

extract、节点转移和拼接还有各自规则，不属于普通“删除后对象销毁”的情况。保留某个旧迭代器后再修改容器时，要先确认规则。

15.2 容易写错的代码

15.3 边遍历边删除

std::vector<int> a = {1, 2, 3, 4};
for (auto it = a.begin(); it != a.end(); ) {
    if (*it % 2 == 0) it = a.erase(it);
    else ++it;
}

对 vector 大量逐个删除可能 O(n²)，可优先使用 erase-remove 或 C++20 erase_if。树/哈希容器也可使用返回后继迭代器的 erase 循环；forward_list 需要记录前驱，并调用 erase_after。

十六、竞赛常用模板

下面前三个例子是完整 C++17 程序，可以独立编译运行。

16.1 排序、去重与离散化

离散化保留大小关系，不保留原值差。

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a = {100, 20, 100, 50};
    std::vector<int> xs = a;
    std::sort(xs.begin(), xs.end());
    xs.erase(std::unique(xs.begin(), xs.end()), xs.end());

    std::vector<int> ranks;
    for (int x : a) {
        int id = static_cast<int>(
            std::lower_bound(xs.begin(), xs.end(), x) - xs.begin());
        ranks.push_back(id);  // 从 0 开始
    }
    assert((ranks == std::vector<int>{2, 0, 2, 1}));
    for (int id : ranks) std::cout << id << ' ';
    std::cout << '\n';
}

复杂度 O(n log n)，xs[id] 是对应原值；如果需要从 1 开始的编号，在使用 id 时加 1。

16.2 deque：滑动窗口最大值

队列存下标，队首始终对应当前窗口最大值。

#include <cassert>
#include <deque>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    assert(k >= 1 && k <= static_cast<int>(a.size()));
    std::deque<int> q;
    std::vector<int> result;

    for (int i = 0; i < static_cast<int>(a.size()); ++i) {
        while (!q.empty() && q.front() <= i - k) q.pop_front();
        while (!q.empty() && a[q.back()] <= a[i]) q.pop_back();
        q.push_back(i);
        if (i >= k - 1) result.push_back(a[q.front()]);
    }
    assert((result == std::vector<int>{3, 3, 5, 5, 6, 7}));
    for (int x : result) std::cout << x << ' ';
    std::cout << '\n';
}

每个下标最多入队、出队一次，总时间 O(n)，额外空间 O(k)。

16.3 priority_queue + pair：Dijkstra

仅用于非负边权，小根堆保存 (当前距离, 节点)，跳过过期状态。

#include <cassert>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <utility>
#include <vector>

int main() {
    using ll = long long;
    using State = std::pair<ll, int>;
    int n = 4, source = 0;
    std::vector<std::vector<std::pair<int, ll>>> graph(n);
    graph[0] = {{1, 5}, {2, 1}};
    graph[2] = {{1, 1}, {3, 10}};
    graph[1] = {{3, 2}};

    const ll INF = std::numeric_limits<ll>::max() / 4;
    std::vector<ll> dist(n, INF);
    std::priority_queue<State, std::vector<State>, std::greater<State>> pq;
    dist[source] = 0;
    pq.emplace(0, source);

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d != dist[u]) continue;
        for (const auto& [v, w] : graph[u]) {
            // 输入须保证 0 <= w，且最短路小于 INF
            if (w >= INF || d > INF - w) continue;
            ll nd = d + w;
            if (nd < dist[v]) {
                dist[v] = nd;
                pq.emplace(nd, v);
            }
        }
    }
    assert((dist == std::vector<ll>{0, 2, 1, 4}));
    for (ll d : dist) std::cout << d << ' ';
    std::cout << '\n';
}

懒删除堆实现的保守时间上界 O(n + m log(m + 1))，其中 m 为边数；简单图中常写为 O((n + m) log n)。若存在负边权，不能直接使用此模板。

16.4 动态前驱与后继

std::set<int> s = {2, 5, 8};
int x = 5;
auto successor = s.upper_bound(x);    // 严格大于 x 的最小值
if (successor != s.end()) {
    int value = *successor;
    (void)value;
}
auto it = s.lower_bound(x);
if (it != s.begin()) {
    auto predecessor = std::prev(it); // 严格小于 x 的最大值
    int value = *predecessor;
    (void)value;
}

查询 O(log n)。prev(begin()) 非法；若 lower_bound 返回 end，非空集合上仍可 prev(end) 取得最大元素。

16.5 计数与最大/最小堆

std::unordered_map<int, int> cnt;
for (int x : v) ++cnt[x];

std::priority_queue<int> max_heap;
std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

16.6 bitset：0/1 子集和

// 要统计的和必须落在 [0, MAX_SUM]，物品值 x 为非负整数
constexpr int MAX_SUM = 100000;
std::bitset<MAX_SUM + 1> possible;
possible.set(0);
for (int x : v) possible |= (possible << x);

移位结果先形成，再并入旧状态，所以每个物品只使用一次。超出 bitset 上限的状态被丢弃；不能据此回答上限之外的可达性。

十七、复习清单

17.1 优先熟练

• vector：[]、push_back、pop_back、size、resize、reserve、insert、erase。
• set/map：insert、find、count、erase、lower_bound、upper_bound、equal_range。
• map：[]、at、try_emplace、insert_or_assign 的差异。
• unordered_*：平均/最坏复杂度、reserve、重哈希后的迭代器失效。
• stack/queue/priority_queue：push、pop、top/front/back、判空。
• sort、stable_sort、nth_element、二分四函数。
• find/count、reverse/rotate、remove/unique、min/max、next_permutation。
• accumulate、partial_sum、iota、gcd/lcm。
• string：find、substr、insert、erase、replace、npos。
• bitset：set/reset/flip、count、移位与按位运算。

17.2 六条最关键规则

1. 区间一般是 [first, last)，end 不能解引用。
2. 插入删除后检查迭代器失效，不要继续使用失效位置。
3. 二分与集合运算要满足分区/排序前提。
4. 排序比较器必须是严格弱序，不用 <=。
5. remove/unique/pop_heap 不会缩短容器。
6. 复杂度要区分最坏、平均、均摊，也要计算元素复制与比较的实际成本。

参考资料与进一步查阅

• OI Wiki：STL 容器简介
• OI Wiki：序列式容器
• OI Wiki：关联式容器
• OI Wiki：无序关联式容器
• OI Wiki：容器适配器
• OI Wiki：迭代器
• OI Wiki：STL 算法
• OI Wiki：string
• OI Wiki：bitset
• OI Wiki：pair
• C++17 草案 N4659：algorithm 函数声明总表
• C++17 草案 N4659：numeric 算法
• C++23 草案 N4950

版本标注以标准引入时间为准，不等于任意编译器都已实现。若题目明确限制 C++14，需要避开本文标为 C++17 及以上的接口与结构化绑定。