The C++ Standard Library(2012)学习:C++ 标准模板库 (STL)

虾球xz

298人浏览 · 2026-05-26 12:32:48

虾球xz · 2026-05-26 12:32:48 发布

本文基于《C++ 标准库》第六章，用最通俗的语言帮助你从零理解 STL 的核心思想与用法。

1. STL 是什么

一句话理解： STL 是 C++ 标准库的核心，它提供了一套现成的"数据收纳盒（容器）“和"处理工具（算法）”，让你不必自己从头造轮子。
想象你要管理一堆书：

不用 STL：你要自己设计书架（数组/链表），自己写查找/排序的逻辑
用 STL：直接拿现成的书架（vector/list），调用现成的工具（sort/find）
STL 的核心理念：数据与操作分离。数据放在容器里，操作由算法完成，迭代器是连接两者的桥梁。

2. STL 的三大核心组件

2.1 容器 (Container)

负责存储数据，就像各种类型的"盒子"：

数组型盒子 (vector/array)：连续内存，随机访问快
链式盒子 (list)：元素各自独立，插入删除快
有序盒子 (set/map)：自动排序，查找快
哈希盒子 (unordered_set/unordered_map)：查找最快

2.2 迭代器 (Iterator)

迭代器就像一根"指针"，让你能遍历容器里的每个元素，而不需要关心容器内部的具体结构。
关键操作：

操作	含义
`*it`	取当前位置的元素值
`++it`	移动到下一个元素
`--it`	移动到上一个元素（双向迭代器支持）
`it1 == it2`	判断两个迭代器是否在同一位置
`it1 != it2`	判断是否不在同一位置

2.3 算法 (Algorithm)

算法是独立的全局函数，通过迭代器操作容器，例如 sort、find、copy、reverse 等。
因为算法只依赖迭代器接口，所以一个算法可以适用于所有容器，无需为每种容器单独实现。

3. 容器 (Containers)

容器分三大类：

3.1 序列容器详解

vector —— 动态数组

特点： 元素在内存中连续排列，支持随机访问（用下标直接取任意元素），尾部插入/删除很快，中间插入/删除慢（要移动后面所有元素）。
复杂度：

尾部追加：均摊 $O (1)$
随机访问： $O (1)$
中间插入/删除： $O (n)$

// 文件：vector_demo.cpp
// 演示 vector 的基本用法
#include <vector>    // vector 容器头文件
#include <iostream>
int main()
{
    // 创建一个存放整数的 vector（初始为空）
    std::vector<int> coll;
    // 向尾部追加 1 到 6
    for (int i = 1; i <= 6; ++i) {
        coll.push_back(i);  // push_back：在末尾追加元素
    }
    // coll.size() 返回元素个数
    // coll[i] 用下标随机访问第 i 个元素（从 0 开始）
    for (int i = 0; i < (int)coll.size(); ++i) {
        std::cout << coll[i] << ' ';
    }
    std::cout << std::endl;
    // 输出：1 2 3 4 5 6
    return 0;
}

https://godbolt.org/z/E5bb5MrE1
内存布局示意：

下标:  [0] [1] [2] [3] [4] [5]
元素:   1   2   3   4   5   6
        ^                   ^
       头部               尾部（push_back 在这里追加）

deque —— 双端队列

特点： 两端都可以快速插入/删除，同样支持随机访问。内部不是单块连续内存，而是分块管理。
复杂度：

两端插入/删除： $O (1)$
随机访问： $O (1)$
中间插入/删除： $O (n)$

// 文件：deque_demo.cpp
// 演示 deque 的 push_front（前端插入）
#include <deque>
#include <iostream>
int main()
{
    std::deque<float> coll;  // 存放浮点数的双端队列
    // 每次都在前端插入，所以顺序是倒序
    for (int i = 1; i <= 6; ++i) {
        coll.push_front(i * 1.1f);  // push_front：在头部插入元素
    }
    for (int i = 0; i < (int)coll.size(); ++i) {
        std::cout << coll[i] << ' ';
    }
    std::cout << std::endl;
    // 输出：6.6 5.5 4.4 3.3 2.2 1.1
    // 解释：最后插入的 6*1.1=6.6 在最前面
    return 0;
}

https://godbolt.org/z/PEqKa68rM
插入过程演示（每次在头部插入）：

插入 1.1 后：  [1.1]
插入 2.2 后：  [2.2][1.1]
插入 3.3 后：  [3.3][2.2][1.1]
插入 4.4 后：  [4.4][3.3][2.2][1.1]
插入 5.5 后：  [5.5][4.4][3.3][2.2][1.1]
插入 6.6 后：  [6.6][5.5][4.4][3.3][2.2][1.1]

array —— 固定大小数组

特点： 大小在编译时确定，不能增删元素，只能修改值。比 C 风格数组更安全，但大小是类型的一部分。
注意：array<int,5> 和 array<int,10> 是两种不同的类型，不能互相赋值。
复杂度： 随机访问 $O (1)$ ，不支持插入删除。

// 文件：array_demo.cpp
// 演示 std::array 的基本用法
#include <array>
#include <string>
#include <iostream>
int main()
{
    // array<类型, 大小> — 大小必须在编译时确定
    // 初始化列表：前两个元素赋值，其余默认（空字符串）
    std::array<std::string, 5> coll = { "hello", "world" };
    // 用 size() 和 [] 遍历，和 vector 一样
    for (int i = 0; i < (int)coll.size(); ++i) {
        std::cout << i << ": " << coll[i] << std::endl;
    }
    // 输出：
    // 0: hello
    // 1: world
    // 2:
    // 3:
    // 4:
    return 0;
}

https://godbolt.org/z/3hzqndj5P

list —— 双向链表

特点： 每个元素独占一块内存，并保存前驱和后继的指针。不支持随机访问（没有 [] 运算符），但任意位置的插入/删除都是 $O (1)$ 。
复杂度：

任意位置插入/删除： $O (1)$ （已知位置时）
随机访问： $O (n)$ （需要从头遍历）

链表内存结构：
nullptr <-- [prev|'a'|next] <--> [prev|'b'|next] <--> [prev|'c'|next] --> nullptr
                节点1                   节点2                   节点3

// 文件：list_demo.cpp
// 演示 list 的基本用法及两种遍历方式
#include <list>
#include <iostream>
int main()
{
    std::list<char> coll;  // 存放字符的双向链表
    // 从 'a' 到 'z' 追加到链表尾部
    for (char c = 'a'; c <= 'z'; ++c) {
        coll.push_back(c);
    }
    // 方式一：范围 for 循环（C++11，推荐）
    // auto 自动推断 elem 类型为 char
    for (auto elem : coll) {
        std::cout << elem << ' ';
    }
    std::cout << std::endl;
    // 输出：a b c d e f ... z
    // 方式二：弹出遍历（会清空容器，仅作演示）
    // while (!coll.empty()) {
    //     std::cout << coll.front() << ' '; // front() 取第一个元素
    //     coll.pop_front();                 // pop_front() 移除第一个元素（不返回值）
    // }
    return 0;
}

https://godbolt.org/z/rbEh9ce6h

forward_list —— 单向链表

特点： 每个节点只保存后继指针（不保存前驱），比 list 更省内存，但不能反向遍历，也没有 size()、push_back() 等操作。

// 文件：forward_list_demo.cpp
// 演示 forward_list 的基本用法
#include <forward_list>
#include <iostream>
int main()
{
    // 用初始化列表创建，包含几个质数
    std::forward_list<long> coll = { 2, 3, 5, 7, 11, 13, 17 };
    // resize(n)：调整到 n 个元素（注意：性能差，需线性遍历到末尾）
    coll.resize(9);      // 扩展到 9 个，新元素默认为 0
    coll.resize(10, 99); // 扩展到 10 个，新元素值为 99
    for (auto elem : coll) {
        std::cout << elem << ' ';
    }
    std::cout << std::endl;
    // 输出：2 3 5 7 11 13 17 0 0 99
    return 0;
}

https://godbolt.org/z/KGv8exa13

3.2 关联容器详解

关联容器的内部实现通常是红黑树（一种平衡二叉树），元素自动排序。
查找复杂度： $O(\log n)$ （对比序列容器的 $O (n)$ ）
例如 1000 个元素时：

序列容器查找：平均比较 $\frac{1000}{2} = 500$ 次
关联容器查找： $\log_2{1000} \approx 10$ 次

容器	特点
`set`	无重复，按值排序
`multiset`	允许重复，按值排序
`map`	键值对，键唯一，按键排序
`multimap`	键值对，键可重复，按键排序

// 文件：multiset_demo.cpp
// 演示 multiset 的自动排序和允许重复
#include <set>
#include <string>
#include <iostream>
int main()
{
    // multiset 允许重复，自动排序（字典序）
    std::multiset<std::string> cities {
        "Braunschweig", "Hanover", "Frankfurt", "New York",
        "Chicago", "Toronto", "Paris", "Frankfurt"  // Frankfurt 出现两次
    };
    // 遍历时已经是排好序的（字典序）
    for (const auto& elem : cities) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    // 输出：Braunschweig Chicago Frankfurt Frankfurt Hanover New York Paris Toronto
    // 插入更多元素
    cities.insert({ "London", "Munich", "Hanover", "Braunschweig" });
    for (const auto& elem : cities) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;
    // 输出：Braunschweig Braunschweig Chicago Frankfurt Frankfurt Hanover
    //        Hanover London Munich New York Paris Toronto
    return 0;
}

https://godbolt.org/z/b6zajrare
内部二叉树结构示例（set 存 {1,2,3,4,5,6}）：

遍历（中序遍历）得到：1 2 3 4 5 6（自然有序）

// 文件：multimap_demo.cpp
// 演示 multimap（键值对，键可重复）
#include <map>
#include <string>
#include <iostream>
int main()
{
    // multimap<键类型, 值类型>
    std::multimap<int, std::string> coll;
    // 用嵌套初始化列表赋值
    // {键, 值} 形式，按键自动排序
    coll = {
        {5, "tagged"},
        {2, "a"},
        {1, "this"},
        {4, "of"},
        {6, "strings"},
        {1, "is"},       // 键 1 出现两次
        {3, "multimap"}
    };
    // 遍历时按键排序：1,1,2,3,4,5,6
    // elem 的类型是 pair<const int, string>
    for (auto elem : coll) {
        // elem.first  = 键
        // elem.second = 值
        std::cout << elem.second << ' ';
    }
    std::cout << std::endl;
    // 输出：this is a multimap of tagged strings
    return 0;
}

https://godbolt.org/z/4h7Pq95W1

3.3 无序容器详解

无序容器内部是哈希表，元素的位置由哈希函数决定，没有固定顺序。
查找复杂度：均摊 $O (1)$ （前提是哈希函数好）
哈希表结构示意：

哈希函数 hashfunc()
输入值          桶(Bucket)         链表
"Jack"   -->  [ 桶 0 ] --> [Jack] --> [Timothy] --> null
"Anica"  -->  [ 桶 1 ] --> [Anica] --> null
"Nico"   -->  [ 桶 2 ] --> [Nico] --> [George] --> null
"Fred"   -->  [ 桶 3 ] --> [Fred] --> null
              [ 桶 4 ] --> null
              ...

当两个不同的键映射到同一个桶（哈希冲突），它们会在同一个链表里。

// 文件：unordered_map_demo.cpp
// 演示 unordered_map 作为关联数组（字典）使用
#include <unordered_map>
#include <string>
#include <iostream>
int main()
{
    // unordered_map<键类型, 值类型>
    // 键是 string，值是 float
    std::unordered_map<std::string, float> coll;
    // 用 [] 运算符插入或访问元素
    // 如果键不存在，会自动创建并用默认值初始化（float 为 0）
    coll["VAT1"] = 0.16f;
    coll["VAT2"] = 0.07f;
    coll["Pi"]   = 3.1415f;
    coll["Null"] = 0.0f;
    // 修改已有元素
    coll["VAT1"] += 0.03f;  // VAT1 从 0.16 变为 0.19
    std::cout << "VAT difference: " << coll["VAT1"] - coll["VAT2"] << std::endl;
    // 输出：VAT difference: 0.12
    // 用 at() 访问：如果键不存在会抛出 std::out_of_range 异常
    // coll.at("NotExist");  // 会抛异常
    return 0;
}

https://godbolt.org/z/5ahWMEo9q

3.4 容器适配器

容器适配器是对基础容器的封装，提供受限的接口以满足特定需求：

适配器	策略	说明
`stack`	LIFO（后进先出）	像一摞盘子，只能从顶部取放
`queue`	FIFO（先进先出）	像排队，从后面进，从前面出
`priority_queue`	优先级最高先出	优先级队列，默认最大值优先

4. 迭代器 (Iterators)

4.1 迭代器是什么

迭代器就是一个"智能指针"，它知道如何在特定容器中从一个元素移动到下一个元素。
范围 for 循环 for (auto elem : coll) 其实是迭代器的语法糖，等价于：

// 范围 for 展开后的等价代码
for (auto pos = coll.begin(), end = coll.end(); pos != end; ++pos) {
    auto elem = *pos;  // 解引用得到当前元素
    // ... 循环体
}

4.2 begin() 和 end()

每个容器都提供 begin() 和 end()，定义一个半开区间 $[b e g in, e n d)$ ：

容器：  [ 元素0 | 元素1 | 元素2 | 元素3 ]
         ^                              ^
       begin()                        end()
       (指向第一个元素)           (指向最后一个元素的下一位，
                                   这个位置不存在实际元素！)

半开区间的好处：

循环终止条件简单：pos != end()
空容器时 begin() == end()，无需特殊处理

// 文件：iterator_demo.cpp
// 演示迭代器的各种用法
#include <list>
#include <iostream>
int main()
{
    std::list<char> coll;
    for (char c = 'a'; c <= 'z'; ++c) {
        coll.push_back(c);
    }
    // --- 方式一：显式迭代器（C++11 之前的风格）---
    // const_iterator：只读迭代器，不能通过它修改元素
    std::list<char>::const_iterator pos;
    for (pos = coll.begin(); pos != coll.end(); ++pos) {
        std::cout << *pos << ' ';  // * 解引用，取当前元素的值
    }
    std::cout << std::endl;
    // --- 方式二：用 auto 简化（C++11 推荐）---
    // cbegin() / cend() 返回 const_iterator，确保不会意外修改元素
    for (auto pos = coll.cbegin(); pos != coll.cend(); ++pos) {
        std::cout << *pos << ' ';
    }
    std::cout << std::endl;
    // --- 方式三：修改元素（用非 const 迭代器）---
    // iterator（非 const）可以修改元素
    for (std::list<char>::iterator it = coll.begin(); it != coll.end(); ++it) {
        // toupper 把小写字母转大写
        *it = static_cast<char>(toupper(*it));
    }
    for (auto elem : coll) {
        std::cout << elem << ' ';
    }
    std::cout << std::endl;
    // 输出：A B C D E ... Z
    return 0;
}

https://godbolt.org/z/nYz7zorTz

4.3 为什么用 `++pos` 而不是 `pos++`

++pos（前置递增）比 pos++（后置递增）性能更好：

++pos：直接修改 pos，移动到下一位，返回修改后的 pos（无额外开销）
pos++：需要先保存 pos 的副本（旧值），再移动 pos，返回旧值副本
对于复杂的迭代器类型，保存副本有额外开销。养成用 ++pos 的好习惯。

4.4 迭代器的分类

迭代器类型	容器	支持的操作
前向迭代器	`forward_list`, 无序容器	`++`, `*`, `->`, `==`, `!=`
双向迭代器	`list`, `set`, `map`	前向 + `--`
随机访问迭代器	`vector`, `deque`, `array`	双向 + `+n`, `-n`, `<`, `>`, `[]`

重要提示： 为了写出对所有容器都适用的泛型代码，应该用 != 而不是 < 来判断循环终止：

// 通用写法（适用于所有容器）：
for (auto pos = coll.begin(); pos != coll.end(); ++pos) { }
// 只适用于随机访问迭代器的容器（vector/deque/array）：
for (auto pos = coll.begin(); pos < coll.end(); ++pos) { }

5. 算法 (Algorithms)

5.1 算法的基本思想

STL 算法是全局函数，不是容器的成员函数。它们通过迭代器操作数据，与容器类型无关。

算法（全局函数）
      |
  通过迭代器访问
      |
    容器中的元素

这样的设计意味着：一个算法可以用于所有提供合适迭代器的容器。

5.2 算法示例

// 文件：algorithm_demo.cpp
// 演示常用 STL 算法：min_element, max_element, sort, find, reverse
#include <algorithm>   // 包含大部分 STL 算法
#include <vector>
#include <iostream>
int main()
{
    // 创建 vector 并初始化（C++11 初始化列表）
    std::vector<int> coll = { 2, 5, 4, 1, 6, 3 };
    // --- min_element / max_element ---
    // 返回指向最小/最大元素的迭代器
    // cbegin/cend：返回只读迭代器（const iterator）
    auto minpos = std::min_element(coll.cbegin(), coll.cend());
    auto maxpos = std::max_element(coll.cbegin(), coll.cend());
    std::cout << "min: " << *minpos << std::endl;  // 解引用取值
    std::cout << "max: " << *maxpos << std::endl;
    // 输出：min: 1，max: 6
    // --- sort ---
    // 原地排序，需要可写迭代器（不能用 cbegin/cend）
    std::sort(coll.begin(), coll.end());
    // 排序后：1 2 3 4 5 6
    // --- find ---
    // 查找第一个值为 3 的元素，返回其迭代器
    // 如果找不到，返回 end()
    auto pos3 = std::find(coll.begin(), coll.end(), 3);
    // 找到了，pos3 指向值为 3 的位置（第 3 个元素）
    // --- reverse ---
    // 翻转 [pos3, end) 范围内的元素
    std::reverse(pos3, coll.end());
    // 原来是：1 2 [3 4 5 6]
    // 翻转后：1 2 [6 5 4 3]
    for (auto elem : coll) {
        std::cout << elem << ' ';
    }
    std::cout << std::endl;
    // 输出：1 2 6 5 4 3
    return 0;
}

https://godbolt.org/z/f65e67466

5.3 范围（Range）的概念

所有算法处理的都是半开区间 $[b e g in, e n d)$ 。

范围 [pos25, pos35) 示意：
  pos25             pos35
    |                 |
[ 20 21 22 23 24 [25 26 27 28 29 30 31 32 33 34] 35 36 37 38 39 40 ]
                  包含                              不包含 pos35

一个常见陷阱：

// 文件：range_demo.cpp
// 演示半开区间的陷阱：max_element 不包含第二个参数指向的位置
#include <algorithm>
#include <list>
#include <iostream>
int main()
{
    std::list<int> coll;
    for (int i = 20; i <= 40; ++i) {
        coll.push_back(i);
    }
    // 找到 25 和 35 的位置
    auto pos25 = std::find(coll.begin(), coll.end(), 25);
    auto pos35 = std::find(coll.begin(), coll.end(), 35);
    // 陷阱：[pos25, pos35) 不包含 35 本身！
    // max_element 在 25..34 范围内找最大，结果是 34
    std::cout << "max: " << *std::max_element(pos25, pos35) << std::endl;
    // 输出：max: 34
    // 正确做法：用 ++pos35，让范围包含 35
    std::cout << "max: " << *std::max_element(pos25, ++pos35) << std::endl;
    // 输出：max: 35
    return 0;
}

https://godbolt.org/z/Me9csodf7

5.4 目标范围必须足够大

当算法向目标容器写入时，目标容器必须有足够空间，否则是未定义行为（程序可能崩溃）。

// 文件：copy_safe_demo.cpp
// 演示正确地为目标容器准备足够空间
#include <algorithm>
#include <list>
#include <vector>
#include <deque>
#include <iostream>
int main()
{
    std::list<int> coll1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    // --- 方式一：先 resize 再 copy ---
    std::vector<int> coll2;
    coll2.resize(coll1.size());  // 扩展到和 coll1 一样大，新元素默认为 0
    std::copy(coll1.cbegin(), coll1.cend(), coll2.begin());
    // --- 方式二：构造时指定大小 ---
    std::deque<int> coll3(coll1.size());  // 构造时就分配 9 个元素的空间
    std::copy(coll1.cbegin(), coll1.cend(), coll3.begin());
    for (auto elem : coll2) std::cout << elem << ' ';
    std::cout << std::endl;
    // 输出：1 2 3 4 5 6 7 8 9
    return 0;
}

https://godbolt.org/z/xb4rsadPq

6. 迭代器适配器

6.1 插入迭代器 (Insert Iterators)

插入迭代器让算法工作在插入模式而非覆盖模式，自动帮你扩展目标容器。

插入迭代器	函数	调用的成员函数	适用容器
尾部插入	`back_inserter(c)`	`push_back()`	vector, deque, list
头部插入	`front_inserter(c)`	`push_front()`	deque, list, forward_list
指定位置插入	`inserter(c, pos)`	`insert(pos, val)`	所有（除 array）

// 文件：inserter_demo.cpp
// 演示三种插入迭代器
#include <algorithm>
#include <iterator>   // 插入迭代器头文件
#include <list>
#include <vector>
#include <deque>
#include <set>
#include <iostream>
int main()
{
    std::list<int> coll1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    // --- back_inserter：在尾部追加 ---
    std::vector<int> coll2;
    // copy 会把 coll1 中的元素一个个"写"给 back_inserter
    // back_inserter 把每次"写"转为 push_back，让 coll2 自动增长
    std::copy(coll1.cbegin(), coll1.cend(), std::back_inserter(coll2));
    // coll2: 1 2 3 4 5 6 7 8 9（顺序不变）
    // --- front_inserter：在头部插入（顺序翻转！）---
    std::deque<int> coll3;
    std::copy(coll1.cbegin(), coll1.cend(), std::front_inserter(coll3));
    // 插入 1：[1]
    // 插入 2：[2, 1]  <- 2 在 1 前面
    // 插入 3：[3, 2, 1]
    // ...
    // coll3: 9 8 7 6 5 4 3 2 1（顺序翻转）
    // --- inserter：插入到关联容器（set 自动排序）---
    std::set<int> coll4;
    // 对关联容器，position 只是一个提示，实际插入位置由值决定
    std::copy(coll1.cbegin(), coll1.cend(), std::inserter(coll4, coll4.begin()));
    // coll4: 1 2 3 4 5 6 7 8 9（set 自动去重并排序）
    for (auto e : coll2) std::cout << e << ' '; std::cout << '\n';
    for (auto e : coll3) std::cout << e << ' '; std::cout << '\n';
    for (auto e : coll4) std::cout << e << ' '; std::cout << '\n';
    return 0;
}

https://godbolt.org/z/7b1rGWjxq

6.2 流迭代器 (Stream Iterators)

流迭代器让标准输入输出看起来像一个容器，可以用算法直接从键盘读取或向屏幕输出。

// 文件：stream_iterator_demo.cpp
// 演示 istream_iterator 和 ostream_iterator
// 功能：读取所有单词，排序，去重，输出
#include <iterator>    // 流迭代器头文件
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
int main()
{
    std::vector<std::string> coll;
    // istream_iterator<string>(cin)：从 cin 读取 string 类型数据
    //   - 每次 ++ 就读取下一个单词（用 >> 读取，以空白分隔）
    // istream_iterator<string>()：默认构造，代表"流结束"
    //   - 读到 EOF（文件结束/Ctrl+D）时，迭代器等于这个
    // back_inserter(coll)：把读到的每个单词追加到 coll 末尾
    std::copy(
        std::istream_iterator<std::string>(std::cin),  // 从这里开始读
        std::istream_iterator<std::string>(),           // 读到这里结束（EOF）
        std::back_inserter(coll)                        // 追加到 coll
    );
    // 对所有单词排序
    std::sort(coll.begin(), coll.end());
    // unique_copy：去除相邻重复元素后复制
    // ostream_iterator<string>(cout, "\n")：把每个 string 输出到 cout，后面跟 "\n"
    std::unique_copy(
        coll.cbegin(), coll.cend(),
        std::ostream_iterator<std::string>(std::cout, "\n")
    );
    return 0;
}
// 假设输入：hello world hello C++ world
// 输出（排序去重后）：
// C++
// hello
// world

https://godbolt.org/z/hrb5e6TKG

6.3 反向迭代器 (Reverse Iterators)

反向迭代器把 ++ 内部转换为 --，让算法从后往前遍历。

// 文件：reverse_iterator_demo.cpp
// 演示 crbegin() / crend() 反向遍历
#include <iterator>
#include <algorithm>
#include <vector>
#include <iostream>
int main()
{
    std::vector<int> coll;
    for (int i = 1; i <= 9; ++i) {
        coll.push_back(i);
    }
    // crbegin()：返回指向最后一个元素的只读反向迭代器
    // crend()：返回指向第一个元素之前位置的只读反向迭代器
    // copy + ostream_iterator：把元素输出到 cout，元素间用空格分隔
    std::copy(
        coll.crbegin(), coll.crend(),
        std::ostream_iterator<int>(std::cout, " ")
    );
    std::cout << std::endl;
    // 输出：9 8 7 6 5 4 3 2 1
    return 0;
}

https://godbolt.org/z/cbnW78843
反向迭代器示意：

正向：  begin() -->  [1][2][3][4][5][6][7][8][9]  --> end()
反向：  rend()  <--  [1][2][3][4][5][6][7][8][9]  <-- rbegin()
                      (虚拟位置)                   (实际最后一个元素)

7. 用户自定义泛型函数

你可以编写通用的模板函数，适用于任意 STL 容器：

// 文件：print_elements.hpp
// 通用打印函数：打印任意容器的所有元素
#include <iostream>
#include <string>
// T 是容器类型（如 vector<int>、list<string> 等）
// 用 const T& 避免拷贝容器
template <typename T>
inline void PRINT_ELEMENTS(const T& coll, const std::string& optstr = "")
{
    std::cout << optstr;  // 先输出可选前缀字符串
    // const auto& 避免拷贝每个元素，且不修改元素
    for (const auto& elem : coll) {
        std::cout << elem << ' ';
    }
    std::cout << std::endl;
}
// 用法示例：
// std::vector<int> v = {1, 2, 3};
// PRINT_ELEMENTS(v, "elements: ");
// 输出：elements: 1 2 3

8. 操纵型算法的陷阱

8.1 remove() 并不真正删除元素

这是 STL 中最让初学者困惑的地方。remove() 算法不会缩小容器，只是把不需要的元素"覆盖"掉，然后返回新的逻辑末尾。
remove() 的工作原理：

调用前：[ 6 | 5 | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 | 6 ]
移除值 3：
步骤：把非 3 的元素向前移动，覆盖 3 的位置
结果：[ 6 | 5 | 4 | 2 | 1 | 1 | 2 | 4 | 5 | 6 | 5 | 6 ]
                              ^新逻辑末尾          ^旧末尾
                         （remove 返回这里）  （容器 end() 还在这里）

// 文件：remove_demo.cpp
// 演示 remove() 的正确使用方式（erase-remove 惯用法）
#include <algorithm>
#include <iterator>
#include <list>
#include <iostream>
int main()
{
    std::list<int> coll;
    for (int i = 1; i <= 6; ++i) {
        coll.push_front(i);
        coll.push_back(i);
    }
    // coll: 6 5 4 3 2 1 1 2 3 4 5 6
    // 打印移除前的内容
    std::copy(coll.cbegin(), coll.cend(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    // remove() 返回新的逻辑末尾（指向第一个"被删除"的位置）
    // 注意：此时容器大小没变！
    auto logicalEnd = std::remove(coll.begin(), coll.end(), 3);
    // 打印逻辑上有效的部分：
    std::copy(coll.begin(), logicalEnd,
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    // 输出：6 5 4 2 1 1 2 4 5 6
    // 计算"被删除"的元素个数
    std::cout << "removed: " << std::distance(logicalEnd, coll.end()) << std::endl;
    // 输出：removed: 2
    // 真正从容器中删除多余的元素（erase-remove 惯用法）
    coll.erase(logicalEnd, coll.end());
    std::copy(coll.cbegin(), coll.cend(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    // 输出：6 5 4 2 1 1 2 4 5 6
    return 0;
}

https://godbolt.org/z/sjn5zYdTe
erase-remove 惯用法（一行搞定）：

// 这是最常见的"删除所有值为 val 的元素"写法：
coll.erase(std::remove(coll.begin(), coll.end(), val), coll.end());

8.2 为什么 remove() 不自己调用 erase()

因为算法通过迭代器工作，迭代器不知道自己属于哪个容器。算法设计为可以操作任意范围（甚至是数组的子范围），所以不应该假设有 erase() 成员函数。

8.3 关联容器和无序容器：用成员函数删除

关联容器和无序容器的迭代器是常量迭代器，不能通过它们修改元素（否则会破坏排序或哈希结构）。所以不能对它们使用 remove() 算法，要用成员函数 erase()：

// 文件：associative_remove_demo.cpp
// 演示关联容器的正确删除方式
#include <set>
#include <algorithm>
#include <iterator>
#include <iostream>
int main()
{
    std::set<int> coll = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    // 打印所有元素
    std::copy(coll.cbegin(), coll.cend(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    // 输出：1 2 3 4 5 6 7 8 9
    // 用成员函数 erase(值) 删除值为 3 的元素
    // 返回实际删除的元素个数（set 中最多为 1）
    int num = coll.erase(3);
    std::cout << "removed: " << num << std::endl;
    // 输出：removed: 1
    std::copy(coll.cbegin(), coll.cend(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    // 输出：1 2 4 5 6 7 8 9
    return 0;
}

remove() 与 erase() 详解

1. 算法与容器的设计边界

C++ 标准库把"算法"和"容器"分开设计：

算法通过迭代器操作数据，不依赖具体容器类型。
容器负责管理内存和结构。
这意味着算法只能通过迭代器读写元素，无法调用容器的成员函数（比如 erase()）。

2. 为什么 remove() 不自己调用 erase()

std::remove() 的函数签名：

template <typename ForwardIterator, typename T>
ForwardIterator remove(ForwardIterator first, ForwardIterator last, const T& value);

它接受的是两个迭代器，不知道这段范围属于哪个容器，甚至不知道有没有容器——操作对象可能是普通数组：

int arr[] = {1, 2, 3, 2, 4};
auto end = std::remove(arr, arr + 5, 2);
// 数组没有 erase()，算法不能假设有

所以算法的设计原则是：只做元素移动，不做内存管理。
remove() 实际做的事情是把不需要删除的元素依次移到前面，返回新的逻辑末尾迭代器，原来末尾的元素变成未定义状态，但内存并未释放：

原始：  1  2  3  2  4
remove(2) 后：
        1  3  4  ?  ?
                ^
                返回这里（新的逻辑末尾）

真正删除内存需要容器自己调用 erase()，这就是常见的 erase-remove 惯用法：

std::vector<int> coll = {1, 2, 3, 2, 4};
coll.erase(
    std::remove(coll.begin(), coll.end(), 2),
    coll.end()
);
// coll 现在是：1 3 4

3. 关联容器和无序容器：为什么不能用 remove()

关联容器（std::set、std::map 等）和无序容器（std::unordered_set 等）的迭代器是常量迭代器，不允许通过迭代器修改元素的值。
原因：这些容器依赖元素的值来维护内部结构（排序树或哈希桶）。如果允许随意修改元素值，结构会被破坏，容器的查找、插入等操作就会出错。
因此 std::remove() 无法对它们使用，因为 remove() 内部需要对迭代器赋值（移动元素），而常量迭代器不允许写操作。
正确做法是调用容器自己的成员函数 erase()。

4. 代码结构

#include <set>
#include <algorithm>
#include <iterator>
#include <iostream>
int main()
{
    std::set<int> coll = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    // 打印所有元素
    std::copy(coll.cbegin(), coll.cend(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    // 用成员函数 erase(值) 删除值为 3 的元素
    int num = coll.erase(3);
    std::cout << "removed: " << num << std::endl;
    // 打印删除后的结果
    std::copy(coll.cbegin(), coll.cend(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    return 0;
}

5. 逐步流程

第一步：初始化 set

std::set<int> coll = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

set 内部是红黑树，元素自动按升序排列，每个值唯一。

内部结构（逻辑上）：1 2 3 4 5 6 7 8 9

第二步：打印所有元素

std::copy(coll.cbegin(), coll.cend(),
          std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

cbegin() / cend() 返回常量迭代器，copy 从头到尾依次读取并输出：

输出：1 2 3 4 5 6 7 8 9

第三步：删除元素

int num = coll.erase(3);

set::erase(值) 的行为：

在树中查找值为 3 的节点。
找到则删除该节点，调整树结构，返回删除的元素个数（对 set 来说最多为 1，因为元素唯一）。
找不到则返回 0。

删除前：1 2 3 4 5 6 7 8 9
             ^
             找到并删除
删除后：1 2 4 5 6 7 8 9

std::cout << "removed: " << num << std::endl;
// 输出：removed: 1

第四步：打印删除后结果

std::copy(coll.cbegin(), coll.cend(),
          std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
// 输出：1 2 4 5 6 7 8 9

6. set::erase() 的三种重载

// 1. 按值删除，返回删除的元素个数
size_type erase(const key_type& key);
// 2. 按迭代器删除单个元素，返回下一个元素的迭代器
iterator erase(iterator pos);
// 3. 按范围删除，返回范围结束后的迭代器
iterator erase(iterator first, iterator last);

本例用的是第一种，按值删除，最简洁。

7. 与 vector 的对比

操作	vector	set
能否用 remove()	能（迭代器可写）	不能（常量迭代器）
删除指定值	erase(remove(…), end())	erase(值)
删除后内存	需要 erase 才真正释放	erase 直接释放节点
删除时间复杂度	O(n)	O(log n)

8. 核心规则总结

std::remove() 只移动元素，不释放内存，不能单独使用，需要配合 erase() 才能真正删除。
算法不依赖具体容器，所以无法调用 erase()，这是设计上的边界，不是缺陷。
关联容器和无序容器的迭代器是常量迭代器，remove() 无法对其赋值，必须用容器自身的 erase() 成员函数。
set::erase(值) 返回实际删除的元素个数，可以用来判断元素是否存在。

8.4 算法 vs 成员函数：选哪个？

对于 list，应该优先使用成员函数，因为算法不知道自己在操作链表，会低效地移动值而不是修改指针：

// 文件：list_remove_demo.cpp
// 对比 list 的算法删除（低效）和成员函数删除（高效）
#include <list>
#include <algorithm>
int main()
{
    std::list<int> coll;
    for (int i = 1; i <= 6; ++i) {
        coll.push_front(i);
        coll.push_back(i);
    }
    // 低效方式：用算法 remove()（通过移动值实现）
    // 对 list 来说不好，因为 list 的优势是修改链接，而非移动值
    coll.erase(std::remove(coll.begin(), coll.end(), 3), coll.end());
    // 高效方式：用 list 自己的 remove() 成员函数
    // 直接修改链接，真正删除节点，复杂度 O(n)，但常数项更小
    coll.remove(4);
    return 0;
}

https://godbolt.org/z/ohYndzn3x

9. 函数作为算法参数

9.1 普通函数作为参数

// 文件：for_each_func_demo.cpp
// 演示把函数传给 for_each 算法
#include <vector>
#include <algorithm>
#include <iostream>
// 普通函数：打印一个整数
void print(int elem)
{
    std::cout << elem << ' ';
}
int main()
{
    std::vector<int> coll;
    for (int i = 1; i <= 9; ++i) {
        coll.push_back(i);
    }
    // for_each(begin, end, func)：对 [begin, end) 中的每个元素调用 func
    std::for_each(coll.cbegin(), coll.cend(), print);
    std::cout << std::endl;
    // 输出：1 2 3 4 5 6 7 8 9
    return 0;
}

https://godbolt.org/z/jKahxsd4h

9.2 谓词 (Predicates)

谓词是返回布尔值的函数，用于指定搜索条件或排序条件。
一元谓词： 接受一个参数，判断该元素是否满足条件。

// 文件：unary_predicate_demo.cpp
// 演示一元谓词：找第一个质数
#include <list>
#include <algorithm>
#include <iostream>
#include <cstdlib>   // abs()
// 一元谓词：判断一个数是否是质数
bool isPrime(int number)
{
    number = abs(number);  // 忽略负号
    if (number == 0 || number == 1) {
        return false;  // 0 和 1 不是质数
    }
    // 从 number/2 开始向下找因子
    int divisor;
    for (divisor = number / 2; number % divisor != 0; --divisor) {
        ;  // 空循环体，只需要找到 divisor
    }
    return divisor == 1;  // 如果最大因子是 1，则是质数
}
int main()
{
    std::list<int> coll;
    for (int i = 24; i <= 30; ++i) {
        coll.push_back(i);
    }
    // coll: 24 25 26 27 28 29 30
    // find_if：找第一个让谓词返回 true 的元素
    auto pos = std::find_if(coll.cbegin(), coll.cend(), isPrime);
    if (pos != coll.end()) {
        std::cout << *pos << " is first prime found" << std::endl;
        // 输出：29 is first prime found
    }
    return 0;
}

https://godbolt.org/z/nhPnx5a56
二元谓词： 接受两个参数，常用于自定义排序规则。

// 文件：binary_predicate_demo.cpp
// 演示二元谓词：按姓+名排序 Person
#include <algorithm>
#include <deque>
#include <string>
#include <iostream>
class Person {
public:
    std::string firstname() const { return first_; }
    std::string lastname()  const { return last_;  }
    Person(std::string f, std::string l) : first_(f), last_(l) {}
private:
    std::string first_;
    std::string last_;
};
// 二元谓词：比较两个 Person
// 先比较姓，姓相同则比较名
bool personSortCriterion(const Person& p1, const Person& p2)
{
    return p1.lastname() < p2.lastname() ||
           (p1.lastname() == p2.lastname() &&
            p1.firstname() < p2.firstname());
}
int main()
{
    std::deque<Person> coll = {
        {"Alice", "Smith"},
        {"Bob",   "Jones"},
        {"Carol", "Smith"},
        {"Dave",  "Brown"}
    };
    // sort 的第三个参数是二元谓词，定义"谁比谁小"
    std::sort(coll.begin(), coll.end(), personSortCriterion);
    for (const auto& p : coll) {
        std::cout << p.lastname() << ", " << p.firstname() << std::endl;
    }
    // 输出（按姓排序）：
    // Brown, Dave
    // Jones, Bob
    // Smith, Alice
    // Smith, Carol
    return 0;
}

https://godbolt.org/z/hnxvMPYWr

10. Lambda 表达式

10.1 Lambda 是什么

Lambda 表达式（C++11 引入）让你在算法调用处直接内联定义函数行为，不需要单独写一个函数或类。
语法：

[ 捕获列表 ] ( 参数列表 ) { 函数体 }
    |              |           |
    |              |           +-- 函数逻辑
    |              +-- 接受什么参数
    +-- 从外部环境捕获哪些变量
        [=]  按值捕获所有外部变量
        [&]  按引用捕获所有外部变量
        []   不捕获任何外部变量

10.2 Lambda 示例

// 文件：lambda_demo.cpp
// 演示 lambda 的各种用法
#include <algorithm>
#include <deque>
#include <vector>
#include <iostream>
int main()
{
    std::deque<int> coll = { 1, 3, 19, 5, 13, 7, 11, 2, 17 };
    int x = 5;
    int y = 12;
    // --- 用 lambda 作为 find_if 的谓词 ---
    // [=] 表示按值捕获外部变量 x 和 y
    // (int i) 是参数，代表当前被检查的元素
    auto pos = std::find_if(coll.cbegin(), coll.cend(),
                            [=](int i) {
                                return i > x && i < y;  // 找第一个大于 5 且小于 12 的元素
                            });
    if (pos != coll.end()) {
        std::cout << "first elem >5 and <12: " << *pos << std::endl;
        // 输出：first elem >5 and <12: 7
    }
    // --- 用 lambda 变换元素（计算立方）---
    std::vector<double> nums = { 1.0, 2.0, 3.0, 4.0 };
    std::transform(nums.begin(), nums.end(),  // 源范围
                   nums.begin(),              // 目标（原地修改）
                   [](double d) {             // lambda：计算 d 的三次方
                       return d * d * d;
                   });
    for (auto v : nums) {
        std::cout << v << ' ';
    }
    std::cout << std::endl;
    // 输出：1 8 27 64
    return 0;
}

https://godbolt.org/z/b3an371Gx

10.3 Lambda 对比其他方式

假设要找集合中第一个在 $(x, y)$ 范围内的元素，对比三种方式：
方式一：手写循环（繁琐）

// 必须手动写循环和 break
std::vector<int>::iterator pos;
for (pos = coll.begin(); pos != coll.end(); ++pos) {
    if (*pos > x && *pos < y) break;
}

方式二：独立函数（不方便访问 x、y）

// x 和 y 必须通过全局变量或其他方式传入，很不优雅
bool pred(int i) { return i > x && i < y; }
pos = std::find_if(coll.begin(), coll.end(), pred);

方式三：函数对象类（代码量大）

class Pred {
    int x, y;
public:
    Pred(int xx, int yy) : x(xx), y(yy) {}
    bool operator()(int i) const { return i > x && i < y; }
};
pos = std::find_if(coll.begin(), coll.end(), Pred(x, y));

方式四：Lambda（最简洁，推荐）

auto pos = std::find_if(coll.begin(), coll.end(),
                        [=](int i) { return i > x && i < y; });

10.4 Lambda 的限制

Lambda 也有一些局限：

无法持久化内部状态：每次调用 lambda 都是独立的，不能像函数对象那样在多次调用间保持状态。
用于关联容器的排序准则时略显麻烦：需要用 decltype 获取 lambda 的类型。

// Lambda 作为 set 的排序准则（需要 decltype，且必须传给构造函数）
auto cmp = [](const Person& p1, const Person& p2) {
    return p1.lastname() < p2.lastname();
};
std::set<Person, decltype(cmp)> coll(cmp);
// 注意：lambda 没有默认构造函数，所以必须把 cmp 传给 set 的构造函数

11. 函数对象 (Function Objects)

11.1 什么是函数对象

函数对象（也叫仿函数，Functor）是一个重载了 operator() 的类的对象，可以像函数一样调用。

普通函数：  print(42)
函数对象：  PrintInt obj;  obj(42)   // 和调用函数一样！

函数对象的三大优势：

有状态：可以在成员变量中保存状态，普通函数做不到（除非用全局变量）
有独立类型：不同功能的函数对象是不同类型，可以用作模板参数
通常更快：编译器更容易内联优化

11.2 函数对象示例

// 文件：function_object_demo.cpp
// 演示函数对象的定义和使用，以及它的"有状态"优势
#include <list>
#include <algorithm>
#include <iostream>
// 简单的函数对象：打印整数
class PrintInt {
public:
    // operator() 定义"调用行为"
    void operator()(int elem) const {
        std::cout << elem << ' ';
    }
};
// 有状态的函数对象：给每个元素加上指定的值
class AddValue {
private:
    int theValue;  // 状态：要加的值，在构造时初始化
public:
    // 构造函数：初始化要加的值
    explicit AddValue(int v) : theValue(v) {}
    // operator()：被算法调用时执行的操作
    void operator()(int& elem) const {
        elem += theValue;  // 修改元素（引用传参）
    }
};
int main()
{
    std::list<int> coll;
    for (int i = 1; i <= 9; ++i) {
        coll.push_back(i);
    }
    // coll: 1 2 3 4 5 6 7 8 9
    // 用 for_each 调用函数对象 PrintInt
    // PrintInt() 创建一个临时的 PrintInt 对象
    std::for_each(coll.cbegin(), coll.cend(), PrintInt());
    std::cout << std::endl;
    // 输出：1 2 3 4 5 6 7 8 9
    // 用 AddValue(10) 创建一个"加 10"的函数对象
    std::for_each(coll.begin(), coll.end(), AddValue(10));
    std::for_each(coll.cbegin(), coll.cend(), PrintInt());
    std::cout << std::endl;
    // 输出：11 12 13 14 15 16 17 18 19
    // 用 AddValue(coll 的第一个元素) 创建一个"加当前第一个元素"的函数对象
    // *coll.begin() = 11（刚才加过 10）
    std::for_each(coll.begin(), coll.end(), AddValue(*coll.begin()));
    std::for_each(coll.cbegin(), coll.cend(), PrintInt());
    std::cout << std::endl;
    // 输出：22 23 24 25 26 27 28 29 30
    return 0;
}

https://godbolt.org/z/13WjGo3Es

11.3 预定义函数对象

C++ 标准库提供了很多现成的函数对象（在 `<functional>` 中）：

函数对象	等价操作	示例
`less<T>`	`a < b`	默认排序准则
`greater<T>`	`a > b`	降序排序
`equal_to<T>`	`a == b`	相等判断
`negate<T>`	`-a`	取负
`plus<T>`	`a + b`	加法
`multiplies<T>`	`a * b`	乘法
`logical_and<bool>`	`a && b`	逻辑与

// 文件：predefined_functors_demo.cpp
// 演示预定义函数对象的使用
#include <deque>
#include <algorithm>
#include <functional>   // 预定义函数对象头文件
#include <iostream>
#include <set>
int main()
{
    std::deque<int> coll = { 1, 2, 3, 5, 7, 11, 13, 17, 19 };
    // negate<int>() 函数对象：对每个元素取负
    // transform(source_begin, source_end, dest_begin, operation)
    std::transform(coll.cbegin(), coll.cend(),
                   coll.begin(),          // 目标 = 源（原地修改）
                   std::negate<int>());   // 操作：取负
    // coll 变为：-1 -2 -3 -5 -7 -11 -13 -17 -19
    // multiplies<int>() 函数对象：两个源范围对应元素相乘
    // transform(src1_begin, src1_end, src2_begin, dest_begin, operation)
    std::transform(coll.cbegin(), coll.cend(),
                   coll.cbegin(),              // 第二个源（和第一个一样，相当于平方）
                   coll.begin(),               // 目标
                   std::multiplies<int>());    // 操作：相乘
    // coll 变为：1 4 9 25 49 121 169 289 361
    for (auto e : coll) std::cout << e << ' ';
    std::cout << std::endl;
    // 用 greater<int> 作为 set 的排序准则（降序）
    std::set<int, std::greater<int>> descSet = { 3, 1, 4, 1, 5, 9 };
    for (auto e : descSet) std::cout << e << ' ';
    std::cout << std::endl;
    // 输出：9 5 4 3 1（降序，去重）
    return 0;
}

https://godbolt.org/z/fnWYzvfsq

11.4 绑定器 (Binders)

bind() 函数（在 <functional> 中）可以把函数对象的某些参数"绑定"为固定值，生成新的函数对象。
占位符 _1、_2 等表示"第一个/第二个实际调用时的参数"。

// 文件：bind_demo.cpp
// 演示 bind() 的用法
#include <set>
#include <deque>
#include <algorithm>
#include <iterator>
#include <functional>
#include <iostream>
using namespace std::placeholders;  // 引入 _1, _2 等占位符
int main()
{
    // 降序 set（用 greater<int> 排序）
    std::set<int, std::greater<int>> coll1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    // 因为是降序，遍历结果：9 8 7 6 5 4 3 2 1
    std::deque<int> coll2;
    // bind(multiplies<int>(), _1, 10)
    //   = 创建一个函数对象 f，使得 f(x) = x * 10
    //   _1 是占位符，表示实际调用时传入的第一个参数
    std::transform(coll1.cbegin(), coll1.cend(),
                   std::back_inserter(coll2),
                   std::bind(std::multiplies<int>(), _1, 10));
    // coll2: 90 80 70 60 50 40 30 20 10
    // replace_if：把满足条件的元素替换为新值
    // bind(equal_to<int>(), _1, 70) = 创建 f(x)，使得 f(x) = (x == 70)
    std::replace_if(coll2.begin(), coll2.end(),
                    std::bind(std::equal_to<int>(), _1, 70),  // 条件：等于 70
                    42);                                       // 替换为 42
    // coll2: 90 80 42 60 50 40 30 20 10
    // 嵌套 bind：bind(logical_and<bool>(), bind(f1,_1,...), bind(f2,_1,...))
    // 表示：(x >= 50) && (x <= 80)
    coll2.erase(
        std::remove_if(coll2.begin(), coll2.end(),
                       std::bind(std::logical_and<bool>(),
                                 std::bind(std::greater_equal<int>(), _1, 50),
                                 std::bind(std::less_equal<int>(),    _1, 80))),
        coll2.end()
    );
    // 删除 50-80 范围内的元素
    // coll2: 90 42 40 30 20 10
    for (auto e : coll2) std::cout << e << ' ';
    std::cout << std::endl;
    return 0;
}

https://godbolt.org/z/h61cP46Pd

12. 容器元素的要求

12.1 基本要求

放入 STL 容器的元素类型必须满足：

要求	说明
可拷贝或可移动	必须有拷贝构造函数或移动构造函数
可赋值	必须有赋值运算符
可析构	析构函数必须可访问，且不能抛出异常

普通类默认都满足这三点，除非显式禁用了这些操作。

12.2 额外要求（视情况而定）

序列容器的某些操作需要默认构造函数（如 resize(n)）
查找操作需要 operator==
关联容器需要 operator<（或自定义比较函数）
无序容器需要哈希函数和等价判断

12.3 值语义 vs 引用语义

STL 容器默认使用值语义：容器存储的是元素的副本，而非原始对象的引用。

值语义：                         引用语义（用指针实现）：
MyClass obj;                     MyClass obj;
vector<MyClass> v;               vector<MyClass*> v;
v.push_back(obj);                v.push_back(&obj);
// v 存的是 obj 的副本          // v 存的是 obj 的指针（内存地址）
// 修改 obj 不影响 v 中的元素    // 修改 obj 会影响 v 中的"元素"

如果需要引用语义，可以用 shared_ptr 或 std::reference_wrapper：

#include <memory>
#include <vector>
MyClass obj;
std::vector<std::shared_ptr<MyClass>> v;
v.push_back(std::make_shared<MyClass>(obj));
// 多个容器可以共享同一个对象

13. STL 中的错误与异常

13.1 错误处理原则

STL 的设计目标是最高性能，因此几乎不做运行时错误检查（检查会消耗时间）。
如果使用不当，结果是未定义行为——程序可能崩溃，也可能悄悄地给出错误结果。
常见的 STL 使用错误：

// 文件：stl_errors_demo.cpp
// 演示 STL 常见错误（仅供理解，实际运行会出错）
#include <vector>
#include <algorithm>
int main()
{
    std::vector<int> coll1;  // 空容器
    std::vector<int> coll2;  // 空容器
    // 错误 1：对空容器用 ++pos，使 begin() 超出 end()
    // auto pos = coll1.begin();
    // std::reverse(++pos, coll1.end());  // 未定义行为！
    for (int i = 1; i <= 9; ++i) {
        coll1.push_back(i);
    }
    // 错误 2：coll2 是空的，没有空间接收元素，覆盖了不属于它的内存
    // std::copy(coll1.cbegin(), coll1.cend(), coll2.begin());  // 未定义行为！
    // 错误 3：迭代器来自不同容器，范围无效
    // std::copy(coll1.cbegin(), coll2.cend(), coll1.end());  // 未定义行为！
    return 0;
}

使用 STL 时必须保证的前置条件：

条件	说明
迭代器有效	迭代器必须初始化，且未失效
范围有效	begin 和 end 必须属于同一容器，且 begin 不超过 end
目标空间足够	写入操作的目标容器必须有足够空间（或使用插入迭代器）
多范围算法	第二个及后续范围至少和第一个范围一样大

迭代器失效场景：

vector/deque 在插入或删除后，相关迭代器可能失效：
vector v = {1, 2, 3, 4, 5};
auto it = v.begin() + 2;  // 指向 3
v.push_back(6);           // 可能触发重新分配，it 可能失效！
// 此后使用 it 是未定义行为

13.2 异常安全保证

STL 提供以下异常安全保证（从 C++98 开始）：
基本保证： 不泄漏资源，不破坏容器的内部不变量。
强保证（针对特定操作）：

永远不抛异常的操作：
erase()、clear()、pop_back()、pop_front()、swap()

14. 扩展 STL

14.1 集成自定义容器

只要你的类提供 begin()、end() 以及必要的类型定义，STL 算法就可以用于它。
STL 的设计原则：

任何行为像容器的东西就是容器
任何行为像迭代器的东西就是迭代器
这是鸭子类型（Duck Typing）在 C++ 模板中的体现。

14.2 不要从 STL 类型公开继承

STL 类没有虚函数，不支持多态。如果需要扩展容器行为，应该：

// 正确方式：组合或私有继承
class MyContainer {
private:
    std::vector<int> data_;  // 内部使用 vector
public:
    // 提供自定义接口
    void mySpecialInsert(int val) {
        if (val > 0) data_.push_back(val);
    }
    // ...
};

总结：STL 核心思维导图

复杂度速查表

容器	访问	查找	插入（尾）	插入（中）	删除（中）
`array`	$O (1)$	$O (n)$	不支持	不支持	不支持
`vector`	$O (1)$	$O (n)$	$O (1)$ *	$O (n)$	$O (n)$
`deque`	$O (1)$	$O (n)$	$O (1)$	$O (n)$	$O (n)$
`list`	$O (n)$	$O (n)$	$O (1)$	$O (1)$ **	$O (1)$ **
`set/map`	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$
`unordered_*`	$O (1)$ *	$O (1)$ *	$O (1)$ *	$O (1)$ *	$O (1)$ *

* 均摊复杂度
** 已知插入/删除位置时

第七章：STL 容器——从零理解

本章学习路线图

一、STL 容器的三大核心特性

1.1 值语义（Value Semantics）

容器存储的是元素的副本，不是引用。插入时会复制或移动元素。

ASCII 图：值语义 vs 引用语义
值语义（STL 默认）：             引用语义（需手动实现）：
int x = 42;                     int x = 42;
vector<int> v;                  vector<int*> v;
v.push_back(x);  // 复制 42      v.push_back(&x); // 存指针
x = 99;                         x = 99;
// v[0] 仍然是 42                // *v[0] 变成 99 了！

何时需要引用语义？ 对象不可复制、复制太慢、或需要在多个容器中共享同一个对象时，使用 shared_ptr<T> 包装。

1.2 元素有序性

所有容器都保证多次遍历看到的顺序一致（只要没有插入或删除操作）。

1.3 操作不检查边界（默认）

大多数操作不检查越界，越界访问是未定义行为。只有 at() 会抛出异常。

二、所有容器共有的操作

2.1 构造与初始化

// 以 vector 为例，其他容器类似
#include <vector>
#include <list>
#include <string>
#include <iterator>
#include <iostream>
int main() {
    // 1. 默认构造（空容器）
    std::vector<int> v1;
    // 2. 列表初始化（C++11 起）
    std::vector<int> v2 = {1, 2, 3, 5, 7};
    // 3. 用另一个容器的范围初始化（跨类型）
    std::list<int> lst = {10, 20, 30};
    std::vector<float> v3(lst.begin(), lst.end()); // int 自动转 float
    // 4. 移动构造（C++11 起，性能更好）
    std::vector<int> v4 = std::move(v2); // v2 之后状态未定义
    // 5. 从标准输入读取（使用迭代器适配器）
    // std::vector<int> v5{std::istream_iterator<int>(std::cin),
    //                     std::istream_iterator<int>()};
    return 0;
}

2.2 通用操作速查

操作	含义
`c.empty()`	是否为空（比 `size()==0` 可能更快）
`c.size()`	当前元素数量
`c.max_size()`	最多能容纳多少元素
`c1 == c2`	元素相等且顺序相同
`c1 < c2`	字典序比较（无序容器不支持）
`c = c2`	赋值（复制所有元素）
`c = std::move(c2)`	移动赋值（C++11，仅交换指针，快）
`c1.swap(c2)`	交换两个容器内容（常数时间）
`c.begin()` / `c.end()`	返回迭代器
`c.cbegin()` / `c.cend()`	返回只读迭代器（C++11）
`c.clear()`	清空所有元素

2.3 swap() 与移动赋值的区别

ASCII 图：swap 只交换指针（常数时间）
赋值（慢，线性时间）：           swap（快，常数时间）：
v1: [1][2][3]                  v1: [1][2][3]
v2: [4][5]                     v2: [4][5]
v1 = v2  →  复制每个元素         v1.swap(v2)  →  只交换内部指针
v1: [4][5]                     v1: [4][5]
v2: [4][5] (v2 内容不变)        v2: [1][2][3] (v1 原内容)

三、array（固定大小数组）

3.1 基本概念

std::array<T, N> 是对 C 风格数组的包装，大小 N 在编译期固定，不可增删元素。

ASCII 图：array 的内存结构
array<int, 5> a = {11, 22, 33, 0, 0}:
内存（栈上连续）：
[11][22][33][ 0][ 0]
  0    1    2    3    4   ← 索引

3.2 初始化的特殊规则

#include <array>
#include <iostream>
#include <vector>
int main() {
    // 危险：基本类型元素值未定义（不是 0！）
    std::array<int, 4> a1;
    // a1[0] 可能是任意值
    // 安全：空初始化列表，所有元素变为 0
    std::array<int, 4> a2 = {};
    // a2: {0, 0, 0, 0}
    // 部分初始化：剩余元素自动补 0
    std::array<int, 10> a3 = {42};
    // a3: {42, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    // 错误：初始化列表元素数超过数组大小
    // std::array<int, 5> a4 = {1,2,3,4,5,6}; // 编译错误
    // 错误：不能用括号语法初始化（与 vector 不同）
    // std::array<int, 5> a5({1,2,3,4,5}); // 编译错误
    std::vector<int> v5({1,2,3,4,5});     // 这个是 OK 的
    return 0;
}

3.3 元素访问

操作	是否检查边界	越界时
`a[i]`	否	未定义行为
`a.at(i)`	是	抛出 `out_of_range` 异常
`a.front()`	否	空数组时未定义行为
`a.back()`	否	空数组时未定义行为
`a.data()`	-	返回指向第一个元素的原始指针

3.4 完整示例

// array 完整示例
#include <array>
#include <algorithm>    // std::transform, std::accumulate
#include <numeric>      // std::accumulate
#include <functional>   // std::negate
#include <iostream>
#include <cstring>
int main() {
    // 创建一个包含 10 个 int 的数组，前 4 个初始化，其余为 0
    std::array<int, 10> a = {11, 22, 33, 44};
    // 打印所有元素
    for (int x : a) {
        std::cout << x << " ";
    }
    std::cout << "\n";
    // 输出：11 22 33 44 0 0 0 0 0 0
    // 修改最后两个元素
    a.back() = 9999999;          // 修改最后一个
    a[a.size() - 2] = 42;        // 修改倒数第二个（不检查边界）
    for (int x : a) std::cout << x << " ";
    std::cout << "\n";
    // 输出：11 22 33 44 0 0 0 0 42 9999999
    // 求所有元素之和
    int sum = std::accumulate(a.begin(), a.end(), 0);
    std::cout << "sum: " << sum << "\n";
    // 对所有元素取反（transform 就地操作）
    std::transform(
        a.begin(), a.end(),   // 源范围
        a.begin(),            // 目标范围（原地）
        std::negate<int>()    // 操作：取负
    );
    for (int x : a) std::cout << x << " ";
    std::cout << "\n";
    // 输出：-11 -22 -33 -44 0 0 0 0 -42 -9999999
    // 作为 C 风格数组使用（data() 返回原始指针）
    std::array<char, 41> str;
    std::strcpy(str.data(), "hello, world");  // 正确写法
    std::printf("%s\n", str.data());           // 正确写法
    // std::printf("%s\n", str.begin());       // 错误！迭代器不一定是指针
    // Tuple 接口：get<N> 访问特定位置元素
    std::array<std::string, 3> words = {"hello", "world", "cpp"};
    std::cout << std::get<1>(words) << "\n";  // 输出：world
    return 0;
}

https://godbolt.org/z/4oar9dfGW

3.5 swap() 的特殊性

ASCII 图：array 的 swap 与 vector 的 swap 不同
vector::swap()：              array::swap()：
只交换内部指针                 必须逐元素交换（线性复杂度）
迭代器随元素换容器             迭代器仍指向原容器，但元素已换

四、vector（动态数组）

4.1 基本概念

vector 是最常用的容器，内部用动态 C 数组实现，支持随机访问，末尾插入/删除效率高。

ASCII 图：vector 内部结构
vector<int> v（size=5, capacity=8）：
已用空间                    未使用（预留）
[10][20][30][40][50][  ][  ][  ]
  0   1   2   3   4   5   6   7
↑                           ↑
begin()                     capacity=8
                 ↑
                 end()（size=5）

4.2 size 与 capacity 的关系

这是 vector 最重要的概念：

size：当前实际存储的元素数量
capacity：已分配内存能容纳的最大元素数量
当 size == capacity 时再插入，触发重新分配（通常是容量翻倍）
重新分配的代价：
申请新内存
将所有元素移动到新位置
释放旧内存
所有迭代器、指针、引用全部失效！

#include <vector>
#include <string>
#include <iostream>
#include <algorithm>  // std::find, std::swap
#include <iterator>   // std::ostream_iterator
int main() {
    // 创建空 vector，提前预留 5 个位置的空间（避免重新分配）
    std::vector<std::string> sentence;
    sentence.reserve(5);  // 预留内存，不创建元素
    // 追加元素到末尾
    sentence.push_back("Hello,");
    // 一次插入多个（C++11 initializer_list）
    sentence.insert(sentence.end(), {"how", "are", "you", "?"});
    // 打印
    std::copy(sentence.cbegin(), sentence.cend(),
              std::ostream_iterator<std::string>(std::cout, " "));
    std::cout << "\n";
    // 查看技术数据
    std::cout << "max_size(): " << sentence.max_size() << "\n";
    std::cout << "size():     " << sentence.size()     << "\n";
    std::cout << "capacity(): " << sentence.capacity() << "\n";
    // 交换第 2 和第 4 个元素（索引 1 和 3）
    std::swap(sentence[1], sentence[3]);
    // 在 "?" 前插入 "always"
    sentence.insert(
        std::find(sentence.begin(), sentence.end(), "?"),  // 找到 ? 的位置
        "always"
    );
    // 修改最后一个元素
    sentence.back() = "!";
    // 再次打印
    std::copy(sentence.cbegin(), sentence.cend(),
              std::ostream_iterator<std::string>(std::cout, " "));
    std::cout << "\n";
    std::cout << "size():     " << sentence.size()     << "\n";
    std::cout << "capacity(): " << sentence.capacity() << "\n";
    // 删除最后两个元素
    sentence.pop_back();
    sentence.pop_back();
    // 请求收缩容量（C++11，非强制）
    sentence.shrink_to_fit();
    std::cout << "size():     " << sentence.size()     << "\n";
    std::cout << "capacity(): " << sentence.capacity() << "\n";
    return 0;
}

https://godbolt.org/z/ThbzhdYjv

4.3 vector 的插入删除操作

操作	说明	复杂度
`push_back(x)`	末尾追加	均摊 $O (1)$
`pop_back()`	删除末尾（不返回值）	$O (1)$
`insert(pos, x)`	在 pos 前插入	$O (n)$
`erase(pos)`	删除 pos 处元素	$O (n)$
`emplace_back(args...)`	原地构造追加（C++11）	均摊 $O (1)$
`resize(n)`	调整元素数量	$O (n)$
`clear()`	清空（不释放内存）	$O (n)$

重要：删除指定值的元素（erase-remove 惯用法）：

#include <vector>
#include <algorithm>  // std::remove
#include <iostream>
int main() {
    std::vector<int> coll = {1, 3, 5, 3, 7, 3, 9};
    int val = 3;
    // 删除所有值为 val 的元素（erase-remove 组合）
    // remove() 把"不删"的元素移到前面，返回新的逻辑末尾
    // erase() 真正删除从新末尾到原末尾的部分
    coll.erase(
        std::remove(coll.begin(), coll.end(), val),
        coll.end()
    );
    for (int x : coll) std::cout << x << " ";
    std::cout << "\n";
    // 输出：1 5 7 9
    return 0;
}

4.4 迭代器失效规则

ASCII 图：vector 操作导致迭代器失效
情况1：末尾插入，容量足够
[A][B][C][ ][ ]  →  [A][B][C][D][ ]
 ↑                              ↑
pos（仍有效）              新元素
→ 只有 end() 可能失效
情况2：末尾插入，容量不足（触发重分配）
[A][B][C]      →  分配新内存  →  [A][B][C][D]
 ↑                                ↑
pos（已失效！）                新地址
→ 所有迭代器、指针、引用全部失效！
情况3：中间插入
[A][B][C][D]  →  [A][X][B][C][D]
     ↑
    pos（B之后的迭代器全部失效，A 的仍有效）

4.5 vector<bool> 特殊说明

vector<bool> 是特化版本，内部用位存储（每个 bool 占 1 bit），比普通 vector<bool> 节省 8 倍空间。但代价是：

operator[] 返回的不是真正的 bool&，而是代理对象
模板代码中可能出现意外行为
如果需要固定大小的位集合，用 bitset；需要动态位集合，谨慎使用 vector<bool>。

五、deque（双端队列）

5.1 基本概念

deque（发音 “deck”）是两端都可以高效插入删除的容器。

ASCII 图：deque 的内部结构
外部指针数组（控制块）：
[ptr0][ptr1][ptr2][ptr3][ptr4]
  |     |     |     |     |
  ▼     ▼     ▼     ▼     ▼
[块0] [块1] [块2] [块3] [块4]
每个块是固定大小的数组，
首块向左增长，末块向右增长
→ 两端插入删除都是 O(1)
→ 中间插入仍然是 O(n)

5.2 deque vs vector

特性	vector	deque
头部插入/删除	$O (n)$ （需移动所有元素）	$O (1)$
尾部插入/删除	均摊 $O (1)$	均摊 $O (1)$
中间插入/删除	$O (n)$	$O (n)$
随机访问	$O (1)$	$O (1)$ （稍慢，多一次间接）
内存连续性	连续	分块，不连续
容量控制	`reserve()` / `capacity()`	不支持
收缩	`shrink_to_fit()`	`shrink_to_fit()`
迭代器类型	随机访问	随机访问（但类型更复杂）

5.3 deque 特有操作：`push_front` / `pop_front`

#include <deque>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>
int main() {
    std::deque<std::string> coll;
    // 批量赋值（3 个 "string"）
    coll.assign(3, std::string("string"));
    coll.push_back("last string");     // 末尾插入
    coll.push_front("first string");   // 头部插入（vector 没有这个！）
    // 打印
    std::copy(coll.cbegin(), coll.cend(),
              std::ostream_iterator<std::string>(std::cout, "\n"));
    std::cout << "\n";
    // 删除首尾
    coll.pop_front();  // 删除 "first string"
    coll.pop_back();   // 删除 "last string"
    // 修改元素（除第一个外，加前缀 "another "）
    for (unsigned i = 1; i < coll.size(); ++i) {
        coll[i] = "another " + coll[i];
    }
    // 调整大小到 4 个元素（多出的用 "resized string" 填充）
    coll.resize(4, "resized string");
    std::copy(coll.cbegin(), coll.cend(),
              std::ostream_iterator<std::string>(std::cout, "\n"));
    return 0;
}

https://godbolt.org/z/o3vsxqqT8

六、list（双向链表）

6.1 基本概念

list 用双向链表实现，每个节点包含前驱和后继指针。

ASCII 图：list 的内部结构
list<int>:
head ←→ [1] ←→ [2] ←→ [3] ←→ [4] ←→ [5] ←→ tail
（anchor，虚拟节点，不存数据）
插入新节点 99 在 3 之前：
只需修改 [2]→next 和 [3]→prev，不移动其他元素
head ←→ [1] ←→ [2] ←→ [99] ←→ [3] ←→ [4] ←→ [5] ←→ tail

6.2 list 的特点与 vector 的对比

特性	vector	list
随机访问 `v[i]`	$O (1)$	不支持
任意位置插入/删除	$O (n)$	$O (1)$ （到位置后）
查找特定值	$O (n)$	$O (n)$
迭代器失效	可能（插入/删除后）	永不（除被删节点本身）
内存分配	连续块	每个节点独立
额外内存开销	小	每节点多 2 个指针

6.3 list 特有操作

#include <list>
#include <iostream>
#include <algorithm>
#include <iterator>
void printLists(const std::list<int>& l1, const std::list<int>& l2) {
    std::cout << "list1: ";
    std::copy(l1.cbegin(), l1.cend(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\nlist2: ";
    std::copy(l2.cbegin(), l2.cend(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n\n";
}
int main() {
    std::list<int> list1, list2;
    // 填充：list1 = 0 1 2 3 4 5，list2 = 5 4 3 2 1 0
    for (int i = 0; i < 6; ++i) {
        list1.push_back(i);   // 末尾追加
        list2.push_front(i);  // 头部插入
    }
    printLists(list1, list2);
    // splice：把 list1 的全部元素移到 list2 中值为 3 的元素前
    // find() 返回指向 3 的迭代器
    list2.splice(
        std::find(list2.begin(), list2.end(), 3),  // 目标位置
        list1                                        // 源链表
    );
    printLists(list1, list2);
    // list1 变空，list2 的 3 前面插入了原 list1 的所有元素
    // 将 list2 的第一个元素移到末尾
    list2.splice(
        list2.end(),    // 目标：末尾
        list2,          // 源：同一链表
        list2.begin()   // 要移动的元素位置
    );
    printLists(list1, list2);
    // 排序 list2，赋值给 list1，再对 list2 去重相邻重复
    list2.sort();
    list1 = list2;
    list2.unique();  // 删除连续重复元素（要先排序才有意义）
    printLists(list1, list2);
    // 合并两个有序链表
    list1.merge(list2);  // 合并后 list2 变空
    printLists(list1, list2);
    // 删除所有偶数元素（remove_if + lambda）
    list1.remove_if([](int i) {
        return i % 2 == 0;  // 返回 true 的元素被删除
    });
    printLists(list1, list2);
    return 0;
}

https://godbolt.org/z/YdE3jhGrK

6.4 list 特有函数速查

函数	说明
`remove(val)`	删除所有值等于 val 的元素（成员函数版，比算法快）
`remove_if(pred)`	删除所有满足 pred 的元素
`unique()`	删除连续重复元素
`sort()`	排序（list 不支持随机访问，不能用 std::sort）
`merge(list2)`	将有序 list2 合并入当前有序链表
`splice(pos, list2)`	把 list2 全部元素移到 pos 前
`reverse()`	反转元素顺序

七、forward_list（单向链表，C++11）

7.1 与 list 的区别

forward_list 是只能向前遍历的链表，目标是零开销（与手写 C 单链表相比）。

ASCII 图：list vs forward_list
list（双向）：
[1] ←→ [2] ←→ [3] ←→ [4]
（每个节点有 2 个指针）
forward_list（单向）：
[1] → [2] → [3] → [4]
（每个节点只有 1 个指针，更省内存）

7.2 主要限制

特性	list	forward_list
双向遍历	支持	不支持
`size()`	支持	不支持（节省开销）
`back()` / `push_back()`	支持	不支持
反向迭代器	支持	不支持
插入方式	`insert(pos, ...)`	`insert_after(pos, ...)`
删除方式	`erase(pos)`	`erase_after(pos)`

7.3 before_begin() 的作用

由于只能向前，插入/删除时必须持有前驱节点的位置。before_begin() 返回第一个节点之前的虚拟位置：

ASCII 图：before_begin() 的意义
before_begin()  begin()
     ↓             ↓
  [虚拟]  →  [1]  →  [2]  →  [3]
insert_after(before_begin(), 99) 的效果：
  [虚拟]  →  [99]  →  [1]  →  [2]  →  [3]

#include <forward_list>
#include <iostream>
#include <algorithm>
#include <iterator>
int main() {
    std::forward_list<int> fwlist = {1, 2, 3, 4, 5};
    // std::cout<<fwlist.size(); //没有
    // fwlist.push_back(12); //没有
    // 在开头插入多个元素（insert_after + before_begin）
    fwlist.insert_after(
        fwlist.before_begin(),  // 第一个元素前
        {77, 88, 99}            // 插入的值（按序插入）
    );
    // 现在：77 88 99 1 2 3 4 5
    // 查找第一个偶数的前一个位置，在其前面插入 42
    auto posBefore = fwlist.before_begin();
    for (auto pos = fwlist.begin(); pos != fwlist.end(); ++pos, ++posBefore) {
        if (*pos % 2 == 0) {
            break;  // 找到第一个偶数
        }
    }
    fwlist.insert_after(posBefore, 42);
    // 打印
    for (int x : fwlist) std::cout << x << " ";
    std::cout << "\n";
    // 获取大小（forward_list 没有 size()，需要用 distance）
    auto len = std::distance(fwlist.begin(), fwlist.end());
    std::cout << "size: " << len << "\n";
    return 0;
}

https://godbolt.org/z/s6TnMvxrq

八、set 和 multiset（有序集合）

8.1 基本概念

set：自动排序，不允许重复元素
multiset：自动排序，允许重复元素
内部实现：红黑树（平衡二叉搜索树）

ASCII 图：set 的内部红黑树结构
set<int>，插入 {4,2,6,1,3,5,7}：
         4（根）
        / \
       2    6
      / \  / \
     1   3 5   7
查找元素的时间复杂度：O(log n)
1000 个元素 → 平均只需约 10 次比较

8.2 严格弱序（Strict Weak Ordering）

set 的排序准则必须满足以下四条：

反对称性：若 $x < y$ ，则 $y < x$ 为假
传递性：若 $x < y$ 且 $y < z$ ，则 $x < z$
非自反性： $x < x$ 永远为假
等价关系的传递性：若 $\&\& !(b<a)$ 且 $\&\& !(c<b)$ ，则 $\&\& !(c<a)$

注意：<= 不满足这些条件，不能用作排序准则！

8.3 set/multiset 的搜索操作

操作	说明	复杂度
`find(val)`	查找第一个值为 val 的元素	$O(\log n)$
`count(val)`	统计值为 val 的元素数量	$O(\log n + count)$
`lower_bound(val)`	第一个 $\geq$ val 的位置	$O(\log n)$
`upper_bound(val)`	第一个 $>$ val 的位置	$O(\log n)$
`equal_range(val)`	值等于 val 的元素范围（pair）	$O(\log n)$

三个函数都是在已排序的序列里做二分查找，返回的都是迭代器。

准备一个例子

std::set<int> s = {1, 3, 3, 5, 7, 7, 9};
//                  0  1  2  3  4  5  6  （逻辑下标）

lower_bound(val)：第一个 >= val 的位置

auto it = s.lower_bound(3);
// 找第一个 >= 3 的元素
// 1  3  3  5  7  7  9
//    ^
//    这里，值是 3

找到的是"从哪里开始，元素就不比 val 小了"。

upper_bound(val)：第一个 > val 的位置

auto it = s.upper_bound(3);
// 找第一个 > 3 的元素
// 1  3  3  5  7  7  9
//          ^
//          这里，值是 5

找到的是"从哪里开始，元素就比 val 大了"。

两者结合就能圈出所有等于 val 的元素

lower_bound(3) upper_bound(3)
      |        |
      v        v
1  [  3  3  ]  5  7  7  9
      ↑↑↑↑↑
      这段范围内全是 3

equal_range(val)：直接返回这个范围

auto [lo, hi] = s.equal_range(3);
// lo = lower_bound(3)  →  指向第一个 3
// hi = upper_bound(3)  →  指向第一个 5（3 之后）

equal_range 就是把上面两步合并成一次调用，返回一个 pair<iterator, iterator>，表示所有等于 val 的元素的 [lo, hi) 半开区间。

实际用途

// 统计值为 3 的元素个数
auto [lo, hi] = s.equal_range(3);
std::cout << std::distance(lo, hi);  // 输出 2
// 删除所有值为 3 的元素
s.erase(lo, hi);

三者关系一句话

lower_bound = 左边界（包含 val）
upper_bound = 右边界（不包含 val）
equal_range = [lower_bound, upper_bound)

#include <set>
#include <iostream>
int main() {
    std::set<int> c = {1, 2, 4, 5, 6};
    // 注意：3 不在集合里
    // lower_bound(3)：第一个 >= 3 的元素 → 4
    std::cout << "lower_bound(3): " << *c.lower_bound(3) << "\n";  // 4
    // upper_bound(3)：第一个 > 3 的元素 → 4
    std::cout << "upper_bound(3): " << *c.upper_bound(3) << "\n";  // 4
    // lower_bound(5)：第一个 >= 5 的元素 → 5
    std::cout << "lower_bound(5): " << *c.lower_bound(5) << "\n";  // 5
    // upper_bound(5)：第一个 > 5 的元素 → 6
    std::cout << "upper_bound(5): " << *c.upper_bound(5) << "\n";  // 6
    return 0;
}

https://godbolt.org/z/KKccqTzxW

8.4 完整 set 示例：自定义排序、插入、删除

#include <set>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <functional>  // std::greater
int main() {
    // 创建降序 set（通过第二模板参数指定排序准则）
    std::set<int, std::greater<int>> coll1;
    // 插入多个元素（包括重复的 5，但 set 会忽略）
    coll1.insert({4, 3, 5, 1, 6, 2});
    coll1.insert(5);  // 重复，不会插入
    // 打印（降序）
    for (int elem : coll1) std::cout << elem << " ";
    std::cout << "\n";  // 输出：6 5 4 3 2 1
    // 处理 insert() 的返回值（pair<iterator, bool>）
    auto status = coll1.insert(4);
    if (status.second) {
        std::cout << "4 插入成功\n";
    } else {
        std::cout << "4 已存在\n";  // 会输出这个
    }
    // 创建升序 set（不同类型！不能直接赋值）
    std::set<int> coll2(coll1.cbegin(), coll1.cend());
    // 打印（升序）
    std::copy(coll2.cbegin(), coll2.cend(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";  // 输出：1 2 3 4 5 6
    // 删除范围：删除所有小于 3 的元素（即 begin 到 find(3) 之间）
    coll2.erase(coll2.begin(), coll2.find(3));
    // 注意：find(3) 指向 3，但范围是 [begin, find(3))，不包含 3
    // 删除所有值为 5 的元素，返回删除数量
    int num = coll2.erase(5);
    std::cout << num << " 个元素被删除\n";  // 输出：1 个元素被删除
    std::copy(coll2.cbegin(), coll2.cend(),
              std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";  // 输出：3 4 6
    return 0;
}

https://godbolt.org/z/f6G8dqMY6

8.5 运行时自定义排序准则

#include <set>
#include <iostream>
// 可在运行时设置的比较器
class RuntimeCmp {
public:
    enum cmp_mode { normal, reverse };
private:
    cmp_mode mode;
public:
    RuntimeCmp(cmp_mode m = normal) : mode(m) {}
    template <typename T>
    bool operator()(const T& t1, const T& t2) const {
        return mode == normal ? t1 < t2 : t2 < t1;
    }
    bool operator==(const RuntimeCmp& rc) const {
        return mode == rc.mode;
    }
};
using IntSet = std::set<int, RuntimeCmp>;
int main() {
    // 默认升序
    IntSet coll1 = {4, 7, 5, 1, 6, 2};
    for (int x : coll1) std::cout << x << " ";
    std::cout << "\n";  // 1 2 4 5 6 7
    // 创建降序比较器
    RuntimeCmp reverse_order(RuntimeCmp::reverse);
    IntSet coll2(reverse_order);
    coll2 = {4, 7, 5, 1, 6, 2};
    for (int x : coll2) std::cout << x << " ";
    std::cout << "\n";  // 7 6 5 4 2 1
    // 赋值会同时拷贝排序准则！
    coll1 = coll2;
    coll1.insert(3);
    for (int x : coll1) std::cout << x << " ";
    std::cout << "\n";  // 7 6 5 4 3 2 1（降序）
    return 0;
}

https://godbolt.org/z/EnKhTd34c

九、map 和 multimap（键值对映射）

9.1 基本概念

map：键自动排序，键唯一，每个键对应一个值
multimap：键自动排序，键可重复
元素类型是 pair<const Key, Value>（键是 const）

ASCII 图：map 内部结构（键值对红黑树）
map<string, int>:
          "mango"/3
         /         \
    "apple"/5    "orange"/2
    /     \
 "banana"/1  "cherry"/4

9.2 map 作为关联数组（最重要用法）

map 支持 operator[]，可以像数组一样用任意类型的键：

#include <map>
#include <string>
#include <iostream>
#include <iomanip>
int main() {
    std::map<std::string, float> stocks;
    // 像数组一样赋值（如果键不存在，自动创建元素，值默认初始化为 0.0f）
    stocks["BASF"]    = 369.50f;
    stocks["VW"]      = 413.50f;
    stocks["Daimler"] = 819.00f;
    stocks["BMW"]     = 834.00f;
    stocks["Siemens"] = 842.20f;
    // 打印（自动按键（字母序）排序）
    for (const auto& [key, val] : stocks) {  // C++17 结构化绑定
        std::cout << std::left << std::setw(12) << key
                  << val << "\n";
    }
    std::cout << "\n";
    // 所有价格翻倍
    for (auto& [key, val] : stocks) {
        val *= 2;
    }
    // 修改键：先插入新键，再删除旧键
    // （不能直接修改 key，因为 key 是 const）
    stocks["Volkswagen"] = stocks["VW"];
    stocks.erase("VW");
    for (const auto& [key, val] : stocks) {
        std::cout << std::left << std::setw(12) << key << val << "\n";
    }
    return 0;
}

https://godbolt.org/z/Y8aefr875
注意：stocks["typo_key"] 会自动插入一个值为 0 的元素！这是常见的 bug 来源。安全访问用 at()：

// 安全访问（键不存在时抛出 out_of_range）
try {
    float price = stocks.at("BASF");
} catch (const std::out_of_range& e) {
    std::cerr << "键不存在: " << e.what() << "\n";
}

9.3 multimap 用作字典

#include <map>
#include <string>
#include <iostream>
#include <iomanip>
int main() {
    // 创建英德字典（一个英文词可以有多个德文翻译）
    std::multimap<std::string, std::string> dict;
    dict.insert({{"day",     "Tag"},
                 {"strange", "fremd"},
                 {"car",     "Auto"},
                 {"smart",   "elegant"},
                 {"strange", "seltsam"},     // strange 有两个翻译
                 {"smart",   "raffiniert"},
                 {"smart",   "klug"}});
    // 打印所有条目
    std::cout << std::left << std::setw(12) << "english" << "german\n";
    std::cout << std::string(20, '-') << "\n";
    for (const auto& [eng, ger] : dict) {
        std::cout << " " << std::setw(10) << eng << ger << "\n";
    }
    std::cout << "\n";
    // 查找 "smart" 的所有翻译
    std::string word = "smart";
    std::cout << word << ":\n";
    // lower_bound 和 upper_bound 划定等键范围
    for (auto pos = dict.lower_bound(word);
         pos != dict.upper_bound(word);
         ++pos) {
        std::cout << "  " << pos->second << "\n";
    }
    return 0;
}

https://godbolt.org/z/TMxaY6Maa

9.4 遍历时安全删除元素（C++11 起）

#include <map>
#include <string>
#include <iostream>
int main() {
    std::map<std::string, float> coll = {
        {"a", 1.0f}, {"b", 2.0f}, {"c", 3.0f}, {"d", 4.0f}
    };
    float target = 2.0f;
    // C++11 后：erase() 返回下一个迭代器
    for (auto pos = coll.begin(); pos != coll.end(); ) {
        if (pos->second == target) {
            pos = coll.erase(pos);  // erase 返回下一个有效迭代器
        } else {
            ++pos;
        }
    }
    for (const auto& [k, v] : coll) {
        std::cout << k << ": " << v << "\n";
    }
    // 输出：a: 1, c: 3, d: 4
    return 0;
}

https://godbolt.org/z/vnajKG5ba

map 遍历删除元素详解

1. 问题背景：遍历时删除元素为什么危险

对普通容器（如 vector）在遍历中直接删除元素会导致迭代器失效：

for (auto pos = vec.begin(); pos != vec.end(); ++pos) {
    if (*pos == target) {
        vec.erase(pos);  // 危险：erase 后 pos 已失效，++pos 是未定义行为
    }
}

map 的 erase() 不会让其他迭代器失效（只让被删除的那个失效），但如果删除后还对那个失效的迭代器执行 ++，同样是未定义行为。
正确做法是利用 erase() 的返回值。
树的结构（指针连接方式），不是节点本身的内存地址。

红黑树删除的本质

红黑树删除一个节点后，为了保持平衡会做旋转和变色，但这些操作只是改变节点之间的父子指针关系，节点本身还在原来的内存地址上。

删除前：
        d
       / \
      b   e
     / \
    a   c
删除 b 后，树旋转调整：
        d
       / \
      c   e
     /
    a
a、c、d、e 这几个节点的内存地址没有变
只是指针重新连了一下

迭代器存的是什么

map 的迭代器内部存的是指向节点的指针（节点的内存地址）：

// 迭代器内部大致是这样：
struct iterator {
    Node* ptr;  // 指向某个具体节点
};

只要节点没被删除，它的内存地址就不变，指向它的迭代器就永远有效，无论树怎么旋转。

对比 vector 为什么会失效

vector 删除元素后会把后面的元素整体往前移动（或者扩容时整体搬到新内存），元素的内存地址真的变了，所以迭代器失效。

vector 删除中间元素：
删除前：[a][b][c][d]   地址：100 104 108 112
删除 b 后：[a][c][d]   c 从 108 移到了 104，地址变了
                            原来指向 c 的迭代器还记着 108，就失效了

map 的节点散落在堆上各自独立，删除一个不影响其他节点的位置。

一句话总结

旋转改的是节点之间的连接关系，不是节点的内存位置。迭代器记的是地址，地址没变，迭代器就没失效。

2. map 的结构

std::map 内部是红黑树，元素按 key 自动升序排列，每个节点独立存储，删除一个节点不影响其他节点的迭代器。
本例的初始状态：

std::map<std::string, float> coll = {
    {"a", 1.0f}, {"b", 2.0f}, {"c", 3.0f}, {"d", 4.0f}
};

key:   a     b     c     d
value: 1.0   2.0   3.0   4.0

目标：删除所有 value 等于 2.0 的元素（即 key 为 “b” 的那条）。

3. erase() 的返回值

C++11 之前，map::erase() 返回 void，删除后需要手动处理迭代器。
C++11 起，map::erase() 返回被删除元素的下一个有效迭代器：

iterator erase(iterator pos);
// 删除 pos 指向的元素，返回下一个元素的迭代器

这使得遍历删除可以安全地写成一个循环。

4. 代码结构

#include <map>
#include <string>
#include <iostream>
int main() {
    std::map<std::string, float> coll = {
        {"a", 1.0f}, {"b", 2.0f}, {"c", 3.0f}, {"d", 4.0f}
    };
    float target = 2.0f;
    for (auto pos = coll.begin(); pos != coll.end(); ) {
        if (pos->second == target) {
            pos = coll.erase(pos);  // 删除，pos 更新为下一个有效迭代器
        } else {
            ++pos;                  // 不删除，手动前进
        }
    }
    for (const auto& [k, v] : coll) {
        std::cout << k << ": " << v << "\n";
    }
    return 0;
}

https://godbolt.org/z/3M1KP1P4M

5. 循环结构分析

注意循环头：

for (auto pos = coll.begin(); pos != coll.end(); ) {
//                                                ^
//                                         没有 ++pos

自增 ++pos 不在 for 的第三部分，而是放在循环体内部，原因是：

删除时：erase() 已经返回下一个迭代器，不需要再 ++。
不删除时：手动 ++pos。
如果把 ++pos 放在 for 第三部分，删除后会多走一步，跳过紧接在后面的元素。

6. 逐步执行流程

初始状态

pos
 |
 v
a:1.0  b:2.0  c:3.0  d:4.0

第一次循环：pos 指向 a

pos->second == 1.0f  // 不等于 target(2.0f)
++pos                // 手动前进

       pos
        |
        v
a:1.0  b:2.0  c:3.0  d:4.0

第二次循环：pos 指向 b

pos->second == 2.0f  // 等于 target，执行删除
pos = coll.erase(pos)  // 删除 b，pos 更新为下一个元素 c

删除前：a:1.0  b:2.0  c:3.0  d:4.0
                ^
               删除这个
删除后：a:1.0  c:3.0  d:4.0
               ^
              pos 现在在这里（erase 返回的）

第三次循环：pos 指向 c

pos->second == 3.0f  // 不等于 target
++pos                // 手动前进

a:1.0  c:3.0  d:4.0
               ^
              pos

第四次循环：pos 指向 d

pos->second == 4.0f  // 不等于 target
++pos                // 手动前进，pos 到达 end()

循环结束：pos == coll.end()，退出。

7. 最终输出

for (const auto& [k, v] : coll) {
    std::cout << k << ": " << v << "\n";
}

结构化绑定 [k, v] 是 C++17 语法，把 pair<const string, float> 拆成 key 和 value 两个变量。

输出：
a: 1
c: 3
d: 4

8. 为什么不能用范围 for 删除

for (const auto& [k, v] : coll) {
    if (v == target) {
        coll.erase(k);  // 危险：修改正在遍历的容器，行为未定义
    }
}

范围 for 在底层展开后等价于：

auto pos = coll.begin();
auto end = coll.end();
for (; pos != end; ++pos) { ... }

删除元素后 end 可能失效，或者下一次 ++pos 的行为未定义。安全的遍历删除必须用手动的 while 或 for 循环配合 erase() 的返回值。

9. 核心规则总结

情况	做法
遍历 map 时删除元素	pos = coll.erase(pos)，不再手动 ++pos
遍历 map 时不删除元素	手动 ++pos
for 循环第三部分	留空，不写 ++pos，在循环体内控制
范围 for 中删除	不安全，不要使用
erase() 返回值（C++11 起）	被删除元素的下一个有效迭代器

十、无序容器（哈希表，C++11/TR1）

10.1 基本概念

无序容器用哈希表实现，查找/插入/删除的平均复杂度为 $O (1)$ （理想情况），而有序关联容器是 $O(\log n)$ 。

ASCII 图：哈希表内部结构
元素值 → 哈希函数 → 桶(bucket) 索引
                           ↓
桶数组：[桶0][桶1][桶2][桶3][桶4][桶5]...
               ↓
        桶1 → [元素A] → [元素B]（链式处理哈希冲突）

负载因子（load factor） = $\frac{\text{元素数量}}{\text{桶数量}}$
当负载因子超过 max_load_factor（默认 1.0）时，触发重哈希（rehash）：扩大桶数组，重新分配所有元素。

10.2 无序容器 vs 有序容器

特性	有序容器（set/map）	无序容器（unordered_*）
内部结构	红黑树	哈希表
查找复杂度	$O(\log n)$	平均 $O (1)$ ，最坏 $O (n)$
插入复杂度	$O(\log n)$	平均 $O (1)$
元素有序	是（按键排序）	否
支持 `<`, `>`, `<=`, `>=`	是	否
`lower_bound` / `upper_bound`	是	否
需要哈希函数	否	是
内存占用	较小	较大（桶数组）

10.3 自定义哈希函数

对于自定义类型，需要提供哈希函数：

#include <unordered_set>
#include <string>
#include <functional>  // std::hash
#include <iostream>
// 使用 hash_combine 技巧组合多个字段的哈希值
// 来自 Boost 库的经典实现
template <typename T>
inline void hash_combine(std::size_t& seed, const T& val) {
    // 使用魔法数 0x9e3779b9（黄金比例的 32 位近似）
    // 避免不同字段的哈希值简单相加产生碰撞
    seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// 对任意类型列表计算组合哈希
template <typename T>
void hash_val(std::size_t& seed, const T& val) {
    hash_combine(seed, val);
}
template <typename T, typename... Types>
void hash_val(std::size_t& seed, const T& val, const Types&... args) {
    hash_combine(seed, val);
    hash_val(seed, args...);  // 递归处理剩余参数
}
template <typename... Types>
std::size_t hash_val(const Types&... args) {
    std::size_t seed = 0;
    hash_val(seed, args...);
    return seed;
}
// 自定义类型
class Customer {
public:
    std::string fname, lname;
    long no;
    Customer(std::string f, std::string l, long n)
        : fname(f), lname(l), no(n) {}
    friend std::ostream& operator<<(std::ostream& os, const Customer& c) {
        return os << "[" << c.fname << "," << c.lname << "," << c.no << "]";
    }
};
// 自定义哈希函数对象
class CustomerHash {
public:
    std::size_t operator()(const Customer& c) const {
        // 组合三个字段的哈希值
        return hash_val(c.fname, c.lname, c.no);
    }
};
// 自定义等价准则（两个 Customer 当且仅当编号相同时相等）
class CustomerEqual {
public:
    bool operator()(const Customer& c1, const Customer& c2) const {
        return c1.no == c2.no;  // 只比较编号
    }
};
int main() {
    // 使用自定义哈希和等价准则的无序集合
    std::unordered_set<Customer, CustomerHash, CustomerEqual> custset;
    custset.insert(Customer("nico", "josuttis", 42));
    custset.insert(Customer("alice", "smith", 99));
    custset.insert(Customer("bob", "jones", 42));   // 编号 42 已存在，不插入
    for (const auto& c : custset) {
        std::cout << c << "\n";
    }
    return 0;
}

https://godbolt.org/z/Wzbb3vcK6

10.4 使用 Lambda 指定哈希函数

#include <unordered_set>
#include <string>
#include <iostream>
class Customer {
public:
    std::string fname, lname;
    long no;
    Customer(std::string f, std::string l, long n) : fname(f), lname(l), no(n) {}
    std::string firstname() const { return fname; }
    std::string lastname()  const { return lname; }
    long number() const { return no; }
};
// 使用 Boost 风格 hash_combine
template <typename T>
inline void hash_combine(std::size_t& seed, const T& val) {
    seed ^= std::hash<T>()(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
int main() {
    // Lambda 作为哈希函数
    auto hash = [](const Customer& c) -> std::size_t {
        std::size_t seed = 0;
        hash_combine(seed, c.firstname());
        hash_combine(seed, c.lastname());
        hash_combine(seed, c.number());
        return seed;
    };
    // Lambda 作为等价准则
    auto eq = [](const Customer& c1, const Customer& c2) {
        return c1.number() == c2.number();
    };
    // 使用 decltype 获取 Lambda 的类型（Lambda 没有默认构造函数）
    // 必须在构造时传入 Lambda 对象和初始桶数
    std::unordered_set<Customer, decltype(hash), decltype(eq)>
        custset(10, hash, eq);  // 10 = 初始桶数
    custset.insert(Customer("nico", "josuttis", 42));
    return 0;
}

10.5 无序容器的桶接口（调试用）

#include <unordered_set>
#include <iostream>
#include <iomanip>
template <typename T>
void printHashTableState(const T& cont) {
    std::cout << "size:            " << cont.size()           << "\n";
    std::cout << "buckets:         " << cont.bucket_count()   << "\n";
    std::cout << "load factor:     " << cont.load_factor()    << "\n";
    std::cout << "max load factor: " << cont.max_load_factor()<< "\n";
    // 遍历每个桶，打印其中的元素
    std::cout << "data:\n";
    for (std::size_t idx = 0; idx < cont.bucket_count(); ++idx) {
        std::cout << "  b[" << std::setw(2) << idx << "]: ";
        for (auto pos = cont.begin(idx); pos != cont.end(idx); ++pos) {
            std::cout << *pos << " ";
        }
        std::cout << "\n";
    }
    std::cout << "\n";
}
int main() {
    std::unordered_set<int> intset = {1, 2, 3, 5, 7, 11, 13, 17, 19};
    printHashTableState(intset);
    // 插入更多元素（可能触发 rehash）
    intset.insert({-7, 17, 33, 4});
    printHashTableState(intset);
    return 0;
}

https://godbolt.org/z/zsnEGnvaM

size:            9
buckets:         13
load factor:     0.692308
max load factor: 1
data:
  b[ 0]: 13 
  b[ 1]: 1 
  b[ 2]: 2 
  b[ 3]: 3 
  b[ 4]: 17 
  b[ 5]: 5 
  b[ 6]: 19 
  b[ 7]: 7 
  b[ 8]: 
  b[ 9]: 
  b[10]: 
  b[11]: 11 
  b[12]: 
size:            12
buckets:         13
load factor:     0.923077
max load factor: 1
data:
  b[ 0]: 13 
  b[ 1]: 1 
  b[ 2]: 2 
  b[ 3]: 3 
  b[ 4]: 4 17 
  b[ 5]: 5 
  b[ 6]: 19 
  b[ 7]: 33 7 
  b[ 8]: 
  b[ 9]: -7 
  b[10]: 
  b[11]: 11 
  b[12]:

十一、实现引用语义：使用 shared_ptr

当需要多个容器共享同一个对象时，使用 shared_ptr：

#include <set>
#include <deque>
#include <memory>    // std::shared_ptr
#include <algorithm> // std::find_if, std::for_each
#include <string>
#include <iostream>
class Item {
private:
    std::string name;
    float price;
public:
    Item(const std::string& n, float p = 0) : name(n), price(p) {}
    std::string getName()  const { return name; }
    void setName(const std::string& n) { name = n; }
    float getPrice() const { return price; }
    void  setPrice(float p) { price = p; }
};
using ItemPtr = std::shared_ptr<Item>;
template <typename Coll>
void printItems(const std::string& msg, const Coll& coll) {
    std::cout << msg << "\n";
    for (const auto& elem : coll) {
        std::cout << "  " << elem->getName() << ": "
                  << elem->getPrice() << "\n";
    }
}
int main() {
    // 两个容器共享 Item 对象
    std::set<ItemPtr>   allItems;
    std::deque<ItemPtr> bestsellers;
    // 创建畅销书（会同时出现在两个容器里）
    bestsellers = {
        std::make_shared<Item>("Kong Yize", 20.10f),
        std::make_shared<Item>("A Midsummer Night's Dream", 14.99f),
        std::make_shared<Item>("The Maltese Falcon", 9.88f)
    };
    allItems = {
        std::make_shared<Item>("Water", 0.44f),
        std::make_shared<Item>("Pizza", 2.22f)
    };
    // 把畅销书也插入 allItems（共享同一个对象）
    allItems.insert(bestsellers.begin(), bestsellers.end());
    printItems("bestsellers:", bestsellers);
    printItems("all:", allItems);
    std::cout << "\n";
    // 修改畅销书价格（两个容器都能看到变化）
    std::for_each(bestsellers.begin(), bestsellers.end(),
        [](ItemPtr& elem) {
            elem->setPrice(elem->getPrice() * 2);  // 翻倍
        });
    // 把第二本替换为 Pizza
    bestsellers[1] = *std::find_if(allItems.begin(), allItems.end(),
        [](const ItemPtr& elem) {
            return elem->getName() == "Pizza";
        });
    bestsellers[0]->setPrice(44.77f);
    printItems("bestsellers:", bestsellers);
    printItems("all:", allItems);
    // 注意：allItems 中的畅销书价格也已变化（共享对象）
    return 0;
}

十二、如何选择容器？

选择决策树

性能对比总表

容器	随机访问	首尾插入	中间插入	有序	唯一键	查找
array	$O (1)$	不支持	不支持	用户控制	否	$O (n)$
vector	$O (1)$	$O (1)$ 均摊	$O (n)$	用户控制	否	$O (n)$
deque	$O (1)$	$O (1)$ 均摊	$O (n)$	用户控制	否	$O (n)$
list	不支持	$O (1)$	$O (1)$	用户控制	否	$O (n)$
forward_list	不支持	$O (1)$ 仅头	$O (1)$	用户控制	否	$O (n)$
set / multiset	不支持	$O(\log n)$	$O(\log n)$	自动	set唯一	$O(\log n)$
map / multimap	不支持	$O(\log n)$	$O(\log n)$	自动	map唯一	$O(\log n)$
unordered_set	不支持	$O (1)$ 均摊	$O (1)$ 均摊	否	唯一	$O (1)$ 均摊
unordered_map	不支持	$O (1)$ 均摊	$O (1)$ 均摊	否	唯一	$O (1)$ 均摊

实用选择规则（经验法则）

默认用 vector：最简单、随机访问、末尾操作高效
首尾都要快速插入/删除 → deque
中间频繁插入/删除，不需要随机访问 → list
需要按键快速查找（需要有序） → set / map
需要按键极速查找（不在乎顺序） → unordered_set / unordered_map
固定大小数组，需要 STL 接口 → array
需要极省内存的单向遍历链表 → forward_list

排序性能实验对比

用约 35 万字符串，比较 set 和 vector 两种去重排序方案：

// 方案一：用 set（自动排序去重）
#include <set>
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
// 从标准输入读取所有单词，自动排序且去重
std::set<std::string> coll(
    (std::istream_iterator<std::string>(std::cin)),
    std::istream_iterator<std::string>()
);
std::copy(coll.cbegin(), coll.cend(),
          std::ostream_iterator<std::string>(std::cout, "\n"));

// 方案二：用 vector（手动排序后去重）
#include <vector>
#include <iostream>
#include <string>
#include <iterator>
#include <algorithm>
std::vector<std::string> coll(
    (std::istream_iterator<std::string>(std::cin)),
    std::istream_iterator<std::string>()
);
std::sort(coll.begin(), coll.end());
std::unique_copy(coll.cbegin(), coll.cend(),
                 std::ostream_iterator<std::string>(std::cout, "\n"));

实验结果表明：vector 版本在某些场景比 set 版本快 10%~40%，但在另一些机器上慢 50%。说明没有绝对最优方案，应根据实际测试选择。
cat > /mnt/user-data/outputs/cpp_stl_container_members_ch8.md << ‘MARKDOWN_EOF’

第八章：STL 容器成员详解——从零理解

本章导读

本章是 STL 容器的查询手册，系统梳理所有容器提供的类型定义、构造函数、操作函数及策略接口。每个函数都标注了适用容器和复杂度。

一、类型定义（Type Definitions）

每个容器都提供一套标准类型别名，通过这些别名可以写出与容器类型无关的通用代码。

1.1 通用类型定义

ASCII 图：类型定义关系
container<T>
├── value_type        → T（元素类型）
├── reference         → T&（元素引用）
├── const_reference   → const T&（只读引用）
├── pointer           → T*（元素指针）
├── const_pointer     → const T*（只读指针）
├── iterator          → 迭代器类型（类别因容器而异）
├── const_iterator    → 只读迭代器
├── reverse_iterator  → 反向迭代器（部分容器提供）
├── size_type         → 无符号整数（表示大小）
└── difference_type   → 有符号整数（表示距离）

类型名	含义	注意事项
`value_type`	元素类型	set/multiset 中是 const；map 中是 `pair<const Key, T>`
`reference`	元素引用类型	`vector<bool>` 中是特殊代理类
`const_reference`	只读引用	`vector<bool>` 中是 `bool`
`iterator`	迭代器	类别因容器不同（随机/双向/前向）
`const_iterator`	只读迭代器	用 `cbegin()`/`cend()` 获取
`reverse_iterator`	反向迭代器	forward_list、无序容器不提供
`size_type`	无符号大小类型	通常是 `size_t`
`difference_type`	有符号差值类型	迭代器相减的结果类型

1.2 关联容器专有类型

类型名	含义	提供者
`key_type`	键的类型	set/multiset/map/multimap 及无序版本
`mapped_type`	值的类型（键对应的数据）	map/multimap 及无序版本
`key_compare`	排序准则类型	set/multiset/map/multimap
`value_compare`	整体元素比较准则	set/multiset/map/multimap
`hasher`	哈希函数类型	无序容器
`key_equal`	等价判断谓词类型	无序容器
`local_iterator`	桶内迭代器	无序容器（C++11）
`const_local_iterator`	只读桶内迭代器	无序容器（C++11）

1.3 类型定义的实用示例

#include <vector>
#include <map>
#include <string>
#include <iostream>
// 利用类型定义写通用函数
template <typename Container>
void printSize(const Container& c) {
    // 使用容器的 size_type，与具体容器类型无关
    typename Container::size_type n = c.size();
    std::cout << "size = " << n << "\n";
}
int main() {
    // vector 的类型定义示例
    std::vector<int> v = {1, 2, 3};
    // value_type：元素类型
    std::vector<int>::value_type x = 42;  // 等价于 int
    // reference：元素引用
    std::vector<int>::reference ref = v[0];  // 等价于 int&
    ref = 100;  // 修改了 v[0]
    // iterator：迭代器类型
    std::vector<int>::iterator it = v.begin();
    // map 的类型定义示例
    std::map<std::string, double> m = {{"a", 1.0}, {"b", 2.0}};
    // value_type 是 pair<const string, double>
    std::map<std::string, double>::value_type elem = {"c", 3.0};
    m.insert(elem);
    // mapped_type 是值的类型（double）
    std::map<std::string, double>::mapped_type val = m["a"];
    printSize(v);  // size = 3
    printSize(m);  // size = 3
    return 0;
}

二、构造与析构

2.1 构造函数全览

ASCII 图：不同容器的构造函数支持
构造方式                适用容器
────────────────────────────────────────────────
默认构造（空容器）       全部容器
初始化列表构造          全部容器（C++11）
拷贝构造               全部容器
移动构造               全部容器（C++11）
范围构造 [beg,end)      除 array 外所有容器
指定大小 n             vector/deque/list/forward_list
指定大小+默认值 n,val   vector/deque/list/forward_list/string
指定排序准则            set/multiset/map/multimap
指定初始桶数            无序容器

2.2 构造函数详细说明与代码

#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <string>
#include <iostream>
#include <functional>  // std::greater
int main() {
    // ── 默认构造：创建空容器 ──
    std::vector<int>      v1;     // 空 vector
    std::list<double>     l1;     // 空 list
    std::set<std::string> s1;     // 空 set，默认升序排序
    // ── 指定大小构造 ──
    std::vector<int>  v2(5);         // 5 个 int，默认初始化为 0
    std::vector<int>  v3(5, 42);     // 5 个 int，全部初始化为 42
    std::list<double> l2(3, 1.5);    // 3 个 double，全为 1.5
    // ── 初始化列表构造（C++11）──
    std::vector<int>          v4 = {1, 2, 3, 4, 5};
    std::set<int>             s2 = {5, 3, 1, 4, 2};  // 自动排序为 1,2,3,4,5
    std::map<std::string,int> m1 = {{"alice", 1}, {"bob", 2}};
    // ── 范围构造：从另一个容器或数组初始化 ──
    std::list<int>   src = {10, 20, 30, 40};
    // 从 list 的范围初始化 vector（int 可以转为 double）
    std::vector<double> v5(src.begin(), src.end());
    int arr[] = {100, 200, 300};
    std::set<int> s3(std::begin(arr), std::end(arr));  // 从 C 数组初始化
    // ── 拷贝构造 ──
    std::vector<int> v6 = v4;  // 拷贝所有元素
    // ── 移动构造（C++11）：不复制，只转移所有权 ──
    std::vector<int> v7 = std::move(v6);  // v6 之后状态未定义
    // ── 有序容器：指定排序准则 ──
    // 降序 set（通过模板参数）
    std::set<int, std::greater<int>> s4 = {3, 1, 4, 1, 5, 9};
    // 降序 set（通过构造函数参数）
    std::set<int, std::greater<int>> s5(std::greater<int>());
    s5 = {3, 1, 4, 1, 5, 9};
    // ── 无序容器：指定初始桶数和哈希函数 ──
    std::unordered_set<int> us1(10);  // 至少 10 个桶
    // 设置最大负载因子（应在构造后立即设置）
    us1.max_load_factor(0.7f);
    // 打印验证
    std::cout << "v4: ";
    for (int x : v4) std::cout << x << " ";
    std::cout << "\n";
    std::cout << "s2 (sorted): ";
    for (int x : s2) std::cout << x << " ";
    std::cout << "\n";
    std::cout << "s4 (descending): ";
    for (int x : s4) std::cout << x << " ";
    std::cout << "\n";
    return 0;
}

2.3 析构函数

析构函数 ~container() 在对象销毁时自动调用，做三件事：

对每个元素调用析构函数
释放元素占用的内存
释放容器本身占用的内存

ASCII 图：析构顺序
vector<string> v = {"hello", "world"};
// 析构时：
// 1. 调用 v[1]（"world"）的 string 析构函数
// 2. 调用 v[0]（"hello"）的 string 析构函数
// 3. 释放 vector 内部动态数组内存
// 4. 释放 vector 对象自身内存

三、非修改操作

3.1 大小查询操作

函数	返回值	复杂度	适用容器
`empty()`	是否为空（`bool`）	$O (1)$	全部
`size()`	当前元素数量	$O (1)$	除 `forward_list`
`max_size()`	最大可能元素数量	$O (1)$	全部

注意：forward_list 没有 size()，因为单链表计数需要 $O (n)$ ，提供它会误导用户认为是常数时间操作。若需要大小，用 std::distance(fwlist.begin(), fwlist.end())，但它是 $O (n)$ 的。

3.2 比较操作

#include <vector>
#include <set>
#include <iostream>
int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {1, 2, 3};
    std::vector<int> v3 = {1, 2, 4};
    // == ：元素相等且顺序相同
    std::cout << (v1 == v2) << "\n";  // 1（true）
    std::cout << (v1 == v3) << "\n";  // 0（false）
    // < ：字典序比较（逐元素比较）
    // v1 = {1,2,3}，v3 = {1,2,4}：第三个元素 3 < 4
    std::cout << (v1 < v3) << "\n";   // 1（true）
    // 无序容器只支持 == 和 !=（不支持 <、>）
    std::set<int> s1 = {1, 2, 3};
    std::set<int> s2 = {1, 2, 3};
    std::cout << (s1 == s2) << "\n";  // 1（true）
    // std::cout << (s1 < s2) << "\n";  // 无序容器不支持
    return 0;
}

字典序比较规则：

从第一个元素开始逐一比较
第一个不同的位置决定大小关系
如果一个容器是另一个的前缀，则较短的容器更小
$\text{比较复杂度} = O(n)$

3.3 关联容器和无序容器的特殊搜索操作

这些成员函数是对应算法的优化版本，利用容器内部结构实现更低复杂度：

函数	关联容器复杂度	无序容器复杂度	说明
`count(val)`	$O(\log n)$	$O (1)$ 均摊	统计等于 val 的元素数
`find(val)`	$O(\log n)$	$O (1)$ 均摊	查找第一个等于 val 的元素
`lower_bound(val)`	$O(\log n)$	不支持	第一个 $\geq$ val 的位置
`upper_bound(val)`	$O(\log n)$	不支持	第一个 $>$ val 的位置
`equal_range(val)`	$O(\log n)$	$O (1)$ 均摊	val 出现的范围（pair）

性能对比：
$\text{查找 1000 个元素中的某一个：}$
$\text{线性查找} \approx 500 \text{ 次比较（平均）}$
$\text{二叉树查找} \approx \log_2(1000) \approx 10 \text{ 次比较}$
$\text{哈希表查找} \approx 1 \text{ 次比较（理想情况）}$

#include <set>
#include <map>
#include <unordered_map>
#include <string>
#include <iostream>
int main() {
    std::set<int> s = {1, 2, 4, 5, 6};
    // 元素中没有 3
    // lower_bound(3)：第一个 >= 3 的元素 → 迭代器指向 4
    auto lb = s.lower_bound(3);
    std::cout << "lower_bound(3) = " << *lb << "\n";  // 4
    // upper_bound(5)：第一个 > 5 的元素 → 迭代器指向 6
    auto ub = s.upper_bound(5);
    std::cout << "upper_bound(5) = " << *ub << "\n";  // 6
    // equal_range(5)：值为 5 的范围 [5, 6)（6 是下一个）
    auto [first, last] = s.equal_range(5);  // C++17 结构化绑定
    std::cout << "equal_range(5): [" << *first << ", " << *last << ")\n";
    // map 按 key 搜索
    std::map<std::string, int> m = {{"alice", 1}, {"bob", 2}, {"charlie", 3}};
    auto pos = m.find("bob");
    if (pos != m.end()) {
        std::cout << "found: " << pos->first << " = " << pos->second << "\n";
    }
    // count：set 返回 0 或 1，multiset 可能返回 > 1
    std::cout << "count(4) = " << s.count(4) << "\n";  // 1
    std::cout << "count(3) = " << s.count(3) << "\n";  // 0
    return 0;
}

四、赋值操作

4.1 赋值操作速查

操作	语法	说明	适用容器
拷贝赋值	`c = c2`	替换所有元素为 c2 的副本	全部
移动赋值	`c = std::move(c2)`	转移所有权，c2 之后未定义	除 array 外
初始化列表赋值	`c = {1,2,3}`	替换为列表元素（C++11）	除 array 外
`assign(n, val)`	替换为 n 个 val	序列容器
`assign(beg, end)`	替换为范围内元素	序列容器
`assign(initlist)`	替换为列表元素	序列容器（C++11）
`fill(val)`	所有元素替换为 val	仅 array
`swap(c2)`	交换两容器内容	全部

4.2 swap() 的特殊保证

#include <vector>
#include <list>
#include <array>
#include <iostream>
#include <string>
int main() {
    std::vector<int> v1 = {1, 2, 3};
    std::vector<int> v2 = {10, 20, 30, 40};
    // swap 交换内容（常数时间！只交换内部指针）
    v1.swap(v2);
    // 现在 v1 = {10,20,30,40}，v2 = {1,2,3}
    // 迭代器随元素"搬家"（仍指向原来的元素，但现在在另一个容器里）
    auto it = v2.begin();  // 指向 v2 的第一个元素（值为 1）
    v1.swap(v2);           // 再次交换
    // it 现在指向 v1 的第一个元素（值为 1）
    // 全局 swap 函数（等价于成员函数）
    std::swap(v1, v2);
    // array 的 swap 特殊：复杂度是 O(n)（逐元素交换）
    std::array<int, 3> a1 = {1, 2, 3};
    std::array<int, 3> a2 = {4, 5, 6};
    auto ref = a1[0];  // 保存 a1[0] 的副本
    a1.swap(a2);
    // a1 = {4,5,6}，a2 = {1,2,3}
    // 注意：array 的 swap 后迭代器仍指向同一个 array 对象，但元素已改变
    // assign 示例
    std::vector<int> v3 = {1, 2, 3, 4, 5};
    v3.assign(3, 99);  // 替换为 3 个 99
    for (int x : v3) std::cout << x << " ";
    std::cout << "\n";  // 99 99 99
    std::list<int> src = {10, 20, 30};
    v3.assign(src.begin(), src.end());  // 从 list 范围赋值
    for (int x : v3) std::cout << x << " ";
    std::cout << "\n";  // 10 20 30
    return 0;
}

五、元素直接访问

5.1 各容器元素访问方式

函数	边界检查	越界行为	适用容器
`c[idx]`	否	未定义行为	array/vector/deque/string
`c.at(idx)`	是	抛出 `out_of_range`	array/vector/deque/string
`c.front()`	否	空时未定义	array/vector/deque/list/forward_list
`c.back()`	否	空时未定义	array/vector/deque/list/string
`c.data()`	-	返回原始指针	array/vector/string
`m[key]`	否（自动创建）	创建新元素	map/unordered_map
`m.at(key)`	是	抛出 `out_of_range`	map/unordered_map

5.2 map 的 `operator[]` vs `at()` 的关键区别

#include <map>
#include <string>
#include <iostream>
#include <stdexcept>  // std::out_of_range
int main() {
    std::map<std::string, int> m = {{"alice", 1}, {"bob", 2}};
    // operator[]：键不存在时自动创建，默认值初始化
    int v = m["charlie"];     // 创建 "charlie"→0
    std::cout << "charlie: " << v << "\n";     // 0
    std::cout << "size: " << m.size() << "\n"; // 3（多了 charlie）
    // 危险：typo 导致意外插入
    std::cout << m["charliee"] << "\n";  // 又创建了一个错误的键！
    std::cout << "size: " << m.size() << "\n"; // 4
    // at()：键不存在时抛出异常，不会创建新元素
    try {
        int v2 = m.at("dave");  // "dave" 不存在，抛出异常
    } catch (const std::out_of_range& e) {
        std::cout << "键不存在: " << e.what() << "\n";
    }
    std::cout << "size: " << m.size() << "\n"; // 仍然是 4，没有新元素
    // data()：获取原始指针（用于与 C API 交互）
    std::vector<int> vec = {10, 20, 30};
    int* ptr = vec.data();    // 指向第一个元素
    printf("%d %d %d\n", ptr[0], ptr[1], ptr[2]);  // 10 20 30
    return 0;
}

六、迭代器操作

6.1 迭代器类别与容器对应关系

ASCII 图：迭代器类别层次
最强                                              最弱
随机访问 ⊃ 双向 ⊃ 前向 ⊃ 输入/输出
具体容器对应：
- 随机访问：array, vector, deque, string
- 双向：    list, set/multiset, map/multimap（元素/键 const）
- 前向：    forward_list, unordered_*（元素/键 const）

容器	迭代器类别	特殊说明
array	随机访问
vector	随机访问
deque	随机访问
string	随机访问
list	双向
set / multiset	双向	元素是 const
map / multimap	双向	键是 const
forward_list	前向	无反向迭代器
unordered_set / multiset	前向	元素是 const
unordered_map / multimap	前向	键是 const

6.2 迭代器函数速查

函数	C++版本	说明
`begin()` / `end()`	C++98	可读写迭代器
`cbegin()` / `cend()`	C++11	只读迭代器
`rbegin()` / `rend()`	C++98	反向可读写迭代器
`crbegin()` / `crend()`	C++11	反向只读迭代器

注意：forward_list 和无序容器不提供反向迭代器（rbegin/rend）。

6.3 迭代器使用示例

#include <vector>
#include <list>
#include <set>
#include <forward_list>
#include <iostream>
#include <algorithm>
int main() {
    std::vector<int> v = {1, 2, 3, 4, 5};
    // 普通迭代（读写）
    for (auto it = v.begin(); it != v.end(); ++it) {
        *it *= 2;  // 修改元素
    }
    // 只读迭代（cbegin/cend）
    for (auto it = v.cbegin(); it != v.cend(); ++it) {
        std::cout << *it << " ";  // 不能修改
    }
    std::cout << "\n";  // 2 4 6 8 10
    // 反向迭代
    for (auto it = v.rbegin(); it != v.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";  // 10 8 6 4 2
    // set 的迭代器：元素是 const，不能修改
    std::set<int> s = {5, 3, 1, 4, 2};
    for (auto it = s.begin(); it != s.end(); ++it) {
        // *it = 99;  // 编译错误：set 元素是 const
        std::cout << *it << " ";
    }
    std::cout << "\n";  // 1 2 3 4 5（自动排序）
    // forward_list 只有前向迭代器，没有 rbegin
    std::forward_list<int> fl = {1, 2, 3};
    for (auto it = fl.begin(); it != fl.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";
    // range-based for（最简洁，底层调用 begin/end）
    for (const auto& x : v) {
        std::cout << x << " ";
    }
    std::cout << "\n";
    return 0;
}

七、插入与删除

7.1 单元素插入

insert() 返回值的区别：

#include <set>
#include <map>
#include <vector>
#include <iostream>
#include <string>
int main() {
    // set/map insert()：返回 pair<iterator, bool>
    std::set<int> s;
    auto [it1, ok1] = s.insert(42);   // 成功：ok1=true
    auto [it2, ok2] = s.insert(42);   // 失败（重复）：ok2=false
    std::cout << "第一次插入成功: " << ok1 << "\n";  // 1
    std::cout << "第二次插入成功: " << ok2 << "\n";  // 0
    // multiset insert()：总是成功，返回 iterator
    std::multiset<int> ms;
    auto it3 = ms.insert(42);  // 成功，返回迭代器
    auto it4 = ms.insert(42);  // 成功（允许重复）
    // map insert()：用初始化列表插入 pair
    std::map<std::string, int> m;
    auto [it5, ok5] = m.insert({"alice", 1});  // C++11 初始化列表
    std::cout << "map 插入 alice: " << ok5 << "\n";  // 1
    // vector insert()：在指定位置前插入
    std::vector<int> v = {1, 2, 4, 5};
    auto pos = v.begin() + 2;  // 指向元素 4 的位置
    v.insert(pos, 3);           // 在 4 前面插入 3
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 1 2 3 4 5
    // emplace：原地构造，避免不必要的拷贝（C++11）
    std::vector<std::string> vs;
    vs.emplace_back("hello");  // 直接构造，比 push_back("hello") 更高效
    vs.push_back("world");     // 先构造 string，再移动进 vector
    return 0;
}

https://godbolt.org/z/f6qcxPMvh

7.2 多元素插入

#include <vector>
#include <set>
#include <list>
#include <iostream>
int main() {
    // 插入初始化列表（C++11）
    std::vector<int> v = {1, 2, 5};
    v.insert(v.begin() + 2, {3, 4});  // 在 5 前插入 3,4
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 1 2 3 4 5
    // 插入 n 个相同值
    std::vector<int> v2 = {0, 0};
    v2.insert(v2.end(), 3, 99);  // 末尾插入 3 个 99
    for (int x : v2) std::cout << x << " ";
    std::cout << "\n";  // 0 0 99 99 99
    // 从范围插入
    std::list<int> src = {10, 20, 30};
    v2.insert(v2.begin(), src.begin(), src.end());
    for (int x : v2) std::cout << x << " ";
    std::cout << "\n";  // 10 20 30 0 0 99 99 99
    // 关联容器从范围插入
    std::set<int> s;
    int arr[] = {5, 3, 1, 4, 2};
    s.insert(std::begin(arr), std::end(arr));
    for (int x : s) std::cout << x << " ";
    std::cout << "\n";  // 1 2 3 4 5
    return 0;
}

https://godbolt.org/z/46s47xqs1

7.3 删除操作

#include <vector>
#include <set>
#include <map>
#include <list>
#include <iostream>
#include <string>
#include <algorithm>
int main() {
    // ── erase(pos)：删除指定迭代器位置的元素 ──
    std::vector<int> v = {1, 2, 3, 4, 5};
    auto it = v.begin() + 2;  // 指向 3
    auto next = v.erase(it);  // 删除 3，返回下一个元素（4）的迭代器
    std::cout << "after erase(3): ";
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 1 2 4 5
    std::cout << "next element: " << *next << "\n";  // 4
    // ── erase(beg, end)：删除范围 ──
    std::vector<int> v2 = {1, 2, 3, 4, 5};
    v2.erase(v2.begin() + 1, v2.begin() + 4);  // 删除 [2,3,4]
    for (int x : v2) std::cout << x << " ";
    std::cout << "\n";  // 1 5
    // ── 关联容器 erase(val)：按值删除，返回删除数量 ──
    std::set<int> s = {1, 2, 3, 4, 5};
    int num = s.erase(3);  // 删除值为 3 的元素
    std::cout << "deleted " << num << " element(s)\n";  // 1
    // ── map erase(key) ──
    std::map<std::string, int> m = {{"alice", 1}, {"bob", 2}, {"charlie", 3}};
    m.erase("bob");
    for (const auto& [k, v] : m) {
        std::cout << k << ":" << v << " ";
    }
    std::cout << "\n";  // alice:1 charlie:3
    // ── pop_front / pop_back ──
    std::list<int> l = {10, 20, 30};
    l.pop_front();  // 删除第一个
    l.pop_back();   // 删除最后一个
    std::cout << l.front() << "\n";  // 20
    // ── clear()：删除所有元素 ──
    std::vector<int> v3 = {1, 2, 3};
    v3.clear();
    std::cout << "size after clear: " << v3.size() << "\n";  // 0
    // ── 安全地在遍历中删除元素（C++11 风格）──
    std::vector<int> v4 = {1, 2, 3, 4, 5, 6};
    // 删除所有偶数
    for (auto pos = v4.begin(); pos != v4.end(); ) {
        if (*pos % 2 == 0) {
            pos = v4.erase(pos);  // erase 返回下一个迭代器
        } else {
            ++pos;
        }
    }
    for (int x : v4) std::cout << x << " ";
    std::cout << "\n";  // 1 3 5
    return 0;
}

https://godbolt.org/z/nfj5ahrv4

7.4 调整大小（resize）

#include <vector>
#include <string>
#include <iostream>
int main() {
    std::vector<int> v = {1, 2, 3};
    // 扩大：新元素默认初始化为 0
    v.resize(6);
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 1 2 3 0 0 0
    // 扩大：新元素初始化为指定值
    v.resize(8, 99);
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 1 2 3 0 0 0 99 99
    // 缩小：删除末尾元素
    v.resize(3);
    for (int x : v) std::cout << x << " ";
    std::cout << "\n";  // 1 2 3
    return 0;
}

https://godbolt.org/z/f8faEK1hG

八、list 和 forward_list 的特有操作

8.1 链表的优势：O(1) 的任意位置操作

ASCII 图：list 特有操作 splice 的工作原理
原始状态：
list1: [A] ↔ [B] ↔ [C] ↔ [D]
list2: [X] ↔ [Y] ↔ [Z]
list1.splice(list1.begin()+2, list2) 后：
（把 list2 全部移到 list1 的 C 前面）
list1: [A] ↔ [B] ↔ [X] ↔ [Y] ↔ [Z] ↔ [C] ↔ [D]
list2: （空）
只修改了指针，O(1) 时间！元素本身没有移动！

8.2 list 特有操作完整示例

#include <list>
#include <iostream>
#include <algorithm>  // std::find
void print(const std::list<int>& l, const std::string& msg = "") {
    std::cout << msg;
    for (int x : l) std::cout << x << " ";
    std::cout << "\n";
}
int main() {
    std::list<int> l1 = {1, 2, 3, 4, 5};
    std::list<int> l2 = {10, 20, 30};
    // ── remove：删除所有值等于 val 的元素 ──
    l1.remove(3);
    print(l1, "after remove(3): ");  // 1 2 4 5
    // ── remove_if：删除满足条件的元素 ──
    l1.remove_if([](int i) { return i % 2 == 0; });  // 删除所有偶数
    print(l1, "after remove even: ");  // 1 5
    // ── splice：将 l2 全部移到 l1 的第二个元素前 ──
    l1 = {1, 2, 3, 4, 5};
    l2 = {10, 20, 30};
    auto pos = std::next(l1.begin(), 1);  // 指向 2 的位置
    l1.splice(pos, l2);  // l2 全部移到 2 之前
    print(l1, "after splice: ");  // 1 10 20 30 2 3 4 5
    print(l2, "l2 after splice: ");  // （空）
    // ── splice 移动单个元素（同一链表内） ──
    // 将第一个元素移到末尾
    l1 = {1, 2, 3, 4, 5};
    l1.splice(l1.end(), l1, l1.begin());
    print(l1, "after move first to end: ");  // 2 3 4 5 1
    // ── sort：链表自己的排序（list 不能用 std::sort！） ──
    std::list<int> unsorted = {5, 3, 1, 4, 2};
    unsorted.sort();  // 默认升序
    print(unsorted, "sorted: ");  // 1 2 3 4 5
    unsorted.sort(std::greater<int>());  // 降序
    print(unsorted, "sorted descending: ");  // 5 4 3 2 1
    // ── unique：删除连续重复元素（需要先排序） ──
    std::list<int> dup = {1, 1, 2, 3, 3, 3, 4};
    dup.unique();
    print(dup, "after unique: ");  // 1 2 3 4
    // ── merge：合并两个有序链表 ──
    std::list<int> a = {1, 3, 5};
    std::list<int> b = {2, 4, 6};
    a.merge(b);  // b 的元素全部移到 a，并保持有序
    print(a, "after merge: ");  // 1 2 3 4 5 6
    print(b, "b after merge: ");  // （空）
    // ── reverse：反转链表 ──
    std::list<int> r = {1, 2, 3, 4, 5};
    r.reverse();
    print(r, "reversed: ");  // 5 4 3 2 1
    return 0;
}

https://godbolt.org/z/Gn3nfn54n

8.3 forward_list 特有操作

由于是单向链表，所有插入/删除操作都作用在指定位置的后一个元素：

#include <forward_list>
#include <iostream>
#include <algorithm>  // std::find
void print(const std::forward_list<int>& fl, const std::string& msg = "") {
    std::cout << msg;
    for (int x : fl) std::cout << x << " ";
    std::cout << "\n";
}
int main() {
    std::forward_list<int> fl = {1, 2, 3, 4, 5};
    // ── insert_after：在 pos 后面插入 ──
    auto it = fl.begin();  // 指向 1
    fl.insert_after(it, 99);  // 在 1 后面插入 99
    print(fl, "after insert_after(begin, 99): ");  // 1 99 2 3 4 5
    // ── insert_after：在开头前插入（用 before_begin） ──
    fl.insert_after(fl.before_begin(), 0);  // 在第一个元素前插入 0
    print(fl, "after insert at front: ");  // 0 1 99 2 3 4 5
    // ── insert_after：插入多个元素 ──
    fl = {1, 5};
    fl.insert_after(fl.begin(), {2, 3, 4});  // 在 1 后插入 2,3,4
    print(fl, "after insert {2,3,4}: ");  // 1 2 3 4 5
    // ── erase_after：删除 pos 后的元素 ──
    fl = {1, 2, 3, 4, 5};
    fl.erase_after(fl.begin());  // 删除 1 后面的元素（2）
    print(fl, "after erase_after(begin): ");  // 1 3 4 5
    // ── erase_after(beg, end)：删除 (beg, end) 范围内的元素 ──
    // 注意：这是开区间，beg 和 end 本身不删除
    fl = {1, 2, 3, 4, 5};
    auto beg = fl.begin();  // 指向 1
    auto end_it = std::next(fl.begin(), 4);  // 指向 5
    fl.erase_after(beg, end_it);  // 删除 (1, 5) 之间：即 2,3,4
    print(fl, "after erase_after range: ");  // 1 5
    // ── splice_after：移动另一个 forward_list 的元素 ──
    std::forward_list<int> fl2 = {10, 20, 30};
    fl = {1, 2, 3};
    fl.splice_after(fl.before_begin(), fl2);  // 把 fl2 全部移到 fl 开头
    print(fl, "after splice_after: ");  // 10 20 30 1 2 3
    print(fl2, "fl2 after splice: ");   // （空）
    return 0;
}

https://godbolt.org/z/j5xcPqqKq

九、策略接口（容器内部行为控制）

9.1 非修改性策略查询

#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <string>
#include <iostream>
#include <functional>
int main() {
    // ── vector 的容量查询 ──
    std::vector<int> v = {1, 2, 3};
    std::cout << "size:     " << v.size()     << "\n";  // 3（实际元素数）
    std::cout << "capacity: " << v.capacity() << "\n";  // >= 3（预留容量）
    // ── set/map 的排序准则 ──
    std::set<int, std::greater<int>> s = {3, 1, 4, 1, 5};
    auto cmp = s.key_comp();  // 获取比较对象（std::greater<int>）
    std::cout << "cmp(5,3): " << cmp(5, 3) << "\n";  // 1（5 > 3，降序）
    auto vcmp = s.value_comp();  // 对 set，value_comp == key_comp
    std::cout << "vcmp(5,3): " << vcmp(5, 3) << "\n";  // 1
    // ── 无序容器的哈希和等价函数 ──
    std::unordered_map<std::string, int> um = {{"a", 1}, {"b", 2}};
    auto hasher = um.hash_function();  // 获取哈希函数对象
    auto eq = um.key_eq();             // 获取等价判断对象
    std::cout << "hash('a') = " << hasher("a") << "\n";
    std::cout << "eq('a','a') = " << eq("a", "a") << "\n";  // 1
    // ── 无序容器的负载因子 ──
    std::cout << "load_factor:     " << um.load_factor()     << "\n";
    std::cout << "max_load_factor: " << um.max_load_factor() << "\n";  // 默认 1.0
    return 0;
}

https://godbolt.org/z/xof1voEob

9.2 修改性策略函数

#include <vector>
#include <unordered_set>
#include <iostream>
int main() {
    // ── vector::reserve：预留容量，避免重新分配 ──
    std::vector<int> v;
    v.reserve(100);  // 预留 100 个位置的内存
    std::cout << "capacity after reserve(100): " << v.capacity() << "\n";
    // 在 size <= 100 之前，不会发生重新分配
    // reserve 只能增大，不能缩小 vector 的容量
    v.reserve(10);  // 无效果，当前容量已经 >= 100
    std::cout << "capacity after reserve(10): " << v.capacity() << "\n";  // 仍然 >= 100
    // ── shrink_to_fit：请求收缩容量（非强制）──
    v = std::vector<int>(10, 1);  // 10 个元素
    v.push_back(2);  // 触发扩容，capacity 可能是 20+
    v.pop_back();    // size 回到 10，但 capacity 不变
    std::cout << "size: " << v.size() << ", capacity: " << v.capacity() << "\n";
    v.shrink_to_fit();  // 请求收缩（实现可能忽略）
    std::cout << "after shrink_to_fit: " << v.capacity() << "\n";
    // ── 无序容器：rehash 和 reserve ──
    std::unordered_set<int> us = {1, 2, 3, 4, 5};
    std::cout << "buckets: " << us.bucket_count() << "\n";
    // rehash(n)：确保至少 n 个桶
    us.rehash(20);
    std::cout << "after rehash(20): " << us.bucket_count() << "\n";  // >= 20
    // reserve(n)：确保能容纳 n 个元素不触发 rehash
    // 等价于 rehash(ceil(n / max_load_factor))
    us.reserve(50);
    std::cout << "after reserve(50): " << us.bucket_count() << "\n";  // >= 50
    // 设置最大负载因子（影响 rehash 触发时机）
    us.max_load_factor(0.7f);  // 建议 0.7~0.8 之间
    return 0;
}

https://godbolt.org/z/58GdMo3cj

9.3 桶接口（无序容器调试）

#include <unordered_map>
#include <string>
#include <iostream>
#include <iomanip>
int main() {
    std::unordered_map<std::string, int> um = {
        {"alice", 1}, {"bob", 2}, {"charlie", 3},
        {"dave", 4}, {"eve", 5}
    };
    std::cout << "总元素数: " << um.size() << "\n";
    std::cout << "桶的数量: " << um.bucket_count() << "\n";
    std::cout << "最大桶数: " << um.max_bucket_count() << "\n";
    std::cout << "负载因子: " << um.load_factor() << "\n";
    // 查看每个桶的内容
    for (std::size_t i = 0; i < um.bucket_count(); ++i) {
        std::cout << "  桶[" << std::setw(2) << i << "]: ";
        // 用桶迭代器遍历该桶的所有元素
        for (auto it = um.begin(i); it != um.end(i); ++it) {
            std::cout << "[" << it->first << ":" << it->second << "] ";
        }
        std::cout << "\n";
    }
    // 查找特定键所在的桶
    std::cout << "'alice' 在桶 " << um.bucket("alice") << "\n";
    // 查看桶的大小
    std::size_t bucket_idx = um.bucket("alice");
    std::cout << "桶 " << bucket_idx << " 有 "
              << um.bucket_size(bucket_idx) << " 个元素\n";
    return 0;
}

https://godbolt.org/z/TTMnredxn

总元素数: 5
桶的数量: 13
最大桶数: 329406144173384850
负载因子: 0.384615
  桶[ 0]: 
  桶[ 1]: 
  桶[ 2]: [charlie:3] 
  桶[ 3]: [alice:1] 
  桶[ 4]: 
  桶[ 5]: 
  桶[ 6]: 
  桶[ 7]: 
  桶[ 8]: [eve:5] 
  桶[ 9]: 
  桶[10]: [dave:4] 
  桶[11]: [bob:2] 
  桶[12]: 
'alice' 在桶 3
桶 3 有 1 个元素

十、分配器支持

分配器允许自定义容器的内存管理方式（高级特性，日常使用不需要）。

ASCII 图：分配器的作用
container<T, Allocator>
         │         │
         │         └── 控制内存的申请和释放方式
         │               默认：std::allocator<T>（使用 new/delete）
         │               自定义：内存池、共享内存、特殊对齐内存...
         └── 存储元素

#include <vector>
#include <memory>   // std::allocator
#include <iostream>
int main() {
    // 获取容器使用的分配器
    std::vector<int> v = {1, 2, 3};
    auto alloc = v.get_allocator();  // 返回 std::allocator<int>
    // 用分配器手动分配内存（演示，实际很少这样用）
    int* ptr = alloc.allocate(5);   // 分配 5 个 int 的空间
    for (int i = 0; i < 5; ++i) {
        ptr[i] = i * 10;
    }
    for (int i = 0; i < 5; ++i) {
        std::cout << ptr[i] << " ";
    }
    std::cout << "\n";  // 0 10 20 30 40
    alloc.deallocate(ptr, 5);  // 释放内存
    // 传入自定义分配器（实际上使用默认分配器）
    std::allocator<int> my_alloc;
    std::vector<int> v2(my_alloc);  // 使用指定分配器的 vector
    return 0;
}

https://godbolt.org/z/ePYoKMsW8

十一、各操作复杂度速查总表

序列容器

操作	array	vector	deque	list	forward_list
随机访问	$O (1)$	$O (1)$	$O (1)$	$O (n)$	$O (n)$
头部插入	不支持	$O (n)$	$O (1)$	$O (1)$	$O (1)$
尾部插入	不支持	$O(1)^*$	$O (1)$	$O (1)$	$O (n)$
中间插入	不支持	$O (n)$	$O (n)$	$O(1)^{**}$	$O(1)^{**}$
查找	$O (n)$	$O (n)$	$O (n)$	$O (n)$	$O (n)$
size()	$O (1)$	$O (1)$	$O (1)$	$O (1)$	不支持

$^*$ ：均摊 $O (1)$ ，偶发 $O (n)$ （触发重分配时）
$^{**}$ ：到达插入位置后是 $O (1)$ ，但到达该位置需要 $O (n)$

关联容器和无序容器

操作	set/map	multiset/multimap	unordered_set/map	unordered_multi*
查找	$O(\log n)$	$O(\log n)$	$O (1)$ 均摊	$O (1)$ 均摊
插入	$O(\log n)$	$O(\log n)$	$O (1)$ 均摊	$O (1)$ 均摊
删除	$O(\log n)$	$O(\log n)$	$O (1)$ 均摊	$O (1)$ 均摊
lower_bound	$O(\log n)$	$O(\log n)$	不支持	不支持
遍历	$O (n)$	$O (n)$	$O (n)$	$O (n)$

十二、关键设计决策总结

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

Ollama 本地大模型部署与运行深度评测

AtomGit开源社区

OpenClaw实操指南42｜安全边界2：提示词注入与沙箱防护

AtomGit开源社区

LLMLingua：用小型模型“剪枝”大语言模型提示词，让长文本不再昂贵

LLMLingua是一种创新技术，利用小型模型（如GPT-2或LLaMA-7B）对大语言模型的提示词进行"剪枝"压缩。它通过计算每个token的信息熵和困惑度，识别并剔除冗余token，在保持语义完整性的同时实现高达20倍的压缩率。该方法采用预算控制器动态分配压缩率，结合迭代压缩算法处理长距离依赖关系。实际应用中，LLMLingua能显著降低API调用成本、减少延迟，同时避免引入噪声干扰。评估显示

AtomGit开源社区

所有评论(0)

查看更多评论

虾球xz

@TM1695648164

已为社区贡献64条内容

The C++ Standard Library(2012)学习:C++ 标准模板库 (STL)

虾球xz

目录

1. STL 是什么

2. STL 的三大核心组件

2.1 容器 (Container)

2.2 迭代器 (Iterator)

迭代器就像一根"指针"，让你能遍历容器里的每个元素，而不需要关心容器内部的具体结构。 关键操作：

2.3 算法 (Algorithm)

3. 容器 (Containers)

3.1 序列容器详解

vector —— 动态数组

deque —— 双端队列

array —— 固定大小数组

list —— 双向链表

forward_list —— 单向链表

3.2 关联容器详解

3.3 无序容器详解

3.4 容器适配器

容器适配器是对基础容器的封装，提供受限的接口以满足特定需求：

4. 迭代器 (Iterators)

4.1 迭代器是什么

4.2 begin() 和 end()

4.3 为什么用 ++pos 而不是 pos++

4.4 迭代器的分类

5. 算法 (Algorithms)

5.1 算法的基本思想

5.2 算法示例

5.3 范围（Range）的概念

5.4 目标范围必须足够大

6. 迭代器适配器

6.1 插入迭代器 (Insert Iterators)

插入迭代器让算法工作在插入模式而非覆盖模式，自动帮你扩展目标容器。

6.2 流迭代器 (Stream Iterators)

6.3 反向迭代器 (Reverse Iterators)

7. 用户自定义泛型函数

8. 操纵型算法的陷阱

8.1 remove() 并不真正删除元素

8.2 为什么 remove() 不自己调用 erase()

8.3 关联容器和无序容器：用成员函数删除

remove() 与 erase() 详解

1. 算法与容器的设计边界

2. 为什么 remove() 不自己调用 erase()

3. 关联容器和无序容器：为什么不能用 remove()

4. 代码结构

5. 逐步流程

第一步：初始化 set

第二步：打印所有元素

第三步：删除元素

第四步：打印删除后结果

6. set::erase() 的三种重载

7. 与 vector 的对比

8. 核心规则总结

8.4 算法 vs 成员函数：选哪个？

9. 函数作为算法参数

9.1 普通函数作为参数

9.2 谓词 (Predicates)

10. Lambda 表达式

10.1 Lambda 是什么

10.2 Lambda 示例

10.3 Lambda 对比其他方式

10.4 Lambda 的限制

11. 函数对象 (Function Objects)

11.1 什么是函数对象

11.2 函数对象示例

11.3 预定义函数对象

C++ 标准库提供了很多现成的函数对象（在 <functional> 中）：

11.4 绑定器 (Binders)

12. 容器元素的要求

12.1 基本要求

放入 STL 容器的元素类型必须满足：

12.2 额外要求（视情况而定）

12.3 值语义 vs 引用语义

13. STL 中的错误与异常

13.1 错误处理原则

使用 STL 时必须保证的前置条件：

13.2 异常安全保证

14. 扩展 STL

14.1 集成自定义容器

14.2 不要从 STL 类型公开继承

迭代器就像一根"指针"，让你能遍历容器里的每个元素，而不需要关心容器内部的具体结构。
关键操作：

4.3 为什么用 `++pos` 而不是 `pos++`

C++ 标准库提供了很多现成的函数对象（在 `<functional>` 中）：

5.3 deque 特有操作：`push_front` / `pop_front`