C++ STL 基础讲解

• 值语义：容器存储的是对象的副本
• RAII 原则：自动管理内存，离开作用域自动释放
• 异常安全：保证基本异常安全

关键点 3：接口统一
所有容器都提供类似的接口：

• size()：元素个数
• empty()：是否为空
• begin()/end()：迭代器
• clear()：清空

2. 算法（Algorithms）—— 操作的'说明书'

算法是操作数据的通用方法，就像一本说明书，告诉你如何对数据进行排序、查找、复制、删除等操作。

2.1 算法特点

关键特点 1：通用性
算法不关心具体容器类型，只通过迭代器操作数据：

// 同样的 sort 算法，可以对 vector、deque、array 等排序
sort(vector.begin(), vector.end());
sort(deque.begin(), deque.end());

关键特点 2：函数模板
算法都是函数模板，可以处理各种数据类型：

sort(int_vector.begin(), int_vector.end()); // 排序 int
sort(string_vector.begin(), string_vector.end()); // 排序 string

关键特点 3：迭代器依赖
算法通过迭代器访问容器元素，不直接操作容器本身。

2.2 算法分类

常用算法类别：

1. 排序算法
   • sort：快速排序
   • stable_sort：稳定排序（相等元素保持原顺序）
   • partial_sort：部分排序
2. 查找算法
   • find：线性查找
   • binary_search：二分查找（要求已排序）
   • lower_bound/upper_bound：边界查找
3. 修改算法
   • copy：复制
   • fill：填充
   • replace：替换
   • remove：删除（实际是移动，需要配合 erase）
4. 数值算法
   • accumulate：累加
   • inner_product：内积
   • adjacent_difference：相邻差
5. 集合算法
   • set_union：并集
   • set_intersection：交集
   • set_difference：差集

重要概念：算法复杂度

sort() // O(n log n) - 快排
find() // O(n) - 线性查找
binary_search() // O(log n) - 二分查找

3. 迭代器（Iterators）—— 访问的'指针'

迭代器是连接容器和算法的桥梁，它像是一个智能指针，知道如何在容器中移动并访问元素。

3.1 迭代器的作用

桥梁作用：

text
容器（数据存储） ←→ 迭代器（访问接口） ←→ 算法（操作逻辑）

关键能力：

1. 遍历：逐个访问容器元素
2. 访问：读写容器元素
3. 连接：让算法可以操作不同容器

3.2 迭代器分类（五种）

理解层次：从简单到复杂

1. 输入迭代器（Input Iterator）
   • 只能读，不能写
   • 只能向前移动（单次）
   • 像一次性读取器
   • 例子：从键盘读取数据
2. 输出迭代器（Output Iterator）
   • 只能写，不能读
   • 只能向前移动
   • 像打印机
   • 例子：向屏幕输出
3. 前向迭代器（Forward Iterator）
   • 可以读写
   • 只能向前移动
   • 可以多次遍历
   • 例子：单向链表
4. 双向迭代器（Bidirectional Iterator）
   • 可以向前向后移动
   • 可以读写
   • 例子：双向链表、红黑树
5. 随机访问迭代器（Random Access Iterator）
   • 可以任意跳跃访问
   • 支持所有指针运算
   • 例子：数组、vector、deque

3.3 迭代器失效问题

**重要警告：**某些操作会使迭代器失效！

vector 的典型问题：

vector<int> v = {1, 2, 3};
auto it = v.begin() + 1; // 指向 2
v.push_back(4); // 可能导致重新分配内存
// 此时 it 失效！不能再使用

不同容器的失效规则：

• vector：插入/删除可能导致所有迭代器失效
• deque：中间插入/删除会使所有迭代器失效
• list/set/map：只影响被删除元素的迭代器

4. 仿函数（Functors）—— 行为的'函数对象'

仿函数是行为像函数的对象，它实际上是一个重载了 () 运算符的类对象。

4.1 为什么需要仿函数？

传统函数指针的局限性：

1. 无法携带状态
2. 无法内联优化
3. 类型不安全

仿函数的优势：

1. 可以保存状态
2. 编译器可以内联优化
3. 是对象，有类型信息

4.2 仿函数的使用

简单示例：

// 定义一个仿函数类
struct AddValue {
    int value;
    AddValue(int v) : value(v) {}
    // 重载 () 运算符
    int operator()(int x) const {
        return x + value;
    }
};

// 使用
AddValue add5(5);
int result = add5(10); // 调用 add5.operator()(10)，返回 15

4.3 STL 中的预定义仿函数

算术运算：

• plus<T>：加法
• minus<T>：减法
• multiplies<T>：乘法
• divides<T>：除法
• modulus<T>：取模
• negate<T>：取负

比较运算：

• equal_to<T>：等于
• not_equal_to<T>：不等于
• greater<T>：大于
• less<T>：小于
• greater_equal<T>：大于等于
• less_equal<T>：小于等于

逻辑运算：

• logical_and<T>：与
• logical_or<T>：或
• logical_not<T>：非

使用示例：

// 使用 greater 进行降序排序
sort(v.begin(), v.end(), greater<int>());

4.4 现代替代品：Lambda 表达式

C++11 引入 lambda 表达式，很多情况下替代仿函数：

// 传统仿函数
struct Compare {
    bool operator()(int a, int b) {
        return a > b;
    }
};
sort(v.begin(), v.end(), Compare());

// Lambda 表达式（更简洁）
sort(v.begin(), v.end(), [](int a, int b) {
    return a > b;
});

5. 适配器（Adapters）—— 接口的'转换器'

适配器是接口转换器，它修改现有组件的接口，使其适应新的需求。

5.1 三种适配器

1. 容器适配器

• 基于现有容器提供新接口
• 三种主要类型：
  • stack：基于 deque/vector/list，提供栈接口
  • queue：基于 deque/list，提供队列接口
  • priority_queue：基于 vector，提供优先队列接口

示例：stack 的实现原理

// stack 内部包含一个 deque
template<typename T, typename Container = deque<T>>
class stack {
private:
    Container c; // 底层容器
public:
    void push(const T& value) {
        c.push_back(value);
    }
    void pop() {
        c.pop_back();
    }
    T& top() {
        return c.back();
    }
    // ... 其他操作
};

2. 迭代器适配器

• 修改迭代器的行为
• 主要类型：
  • reverse_iterator：反向迭代器
  • insert_iterator：插入迭代器
  • stream_iterator：流迭代器

示例：反向迭代器

vector<int> v = {1, 2, 3};
// 反向遍历
for (auto rit = v.rbegin(); rit != v.rend(); ++rit) {
    cout << *rit << " "; // 输出：3 2 1
}

3. 函数适配器

• 修改函数对象的行为
• 在 C++11 后，很多被 bind/lambda 替代
• 主要类型：
  • binder1st/binder2nd：绑定参数（C++11 前）
  • not1/not2：逻辑取反

示例：bind 适配器（C++11）

// 绑定函数的第二个参数
auto add = [](int a, int b) {
    return a + b;
};
auto add5 = std::bind(add, std::placeholders::_1, 5);
cout << add5(10); // 输出 15

三、五大组件如何协同工作

工作流程示例：排序一个 vector

// 1. 容器：创建数据存储
vector<int> numbers = {5, 2, 8, 1, 9};

// 2. 迭代器：提供访问接口
auto begin = numbers.begin(); // 获取起始位置
auto end = numbers.end();     // 获取结束位置

// 3. 算法：执行排序操作
// 内部使用迭代器访问元素
sort(begin, end);

// 可选：使用仿函数改变排序行为
sort(begin, end, greater<int>()); // 降序排序

// 4. 适配器：改变访问方式
// 反向输出
copy(numbers.rbegin(), numbers.rend(), ostream_iterator<int>(cout, " "));

整个过程的数据流：

text
数据 → 存入容器 → 迭代器访问 → 算法处理 → 结果输出

组件间的松耦合设计

关键设计思想：

1. 容器和算法分离：算法通过迭代器操作容器，不依赖具体容器类型
2. 迭代器作为粘合剂：统一了不同容器的访问方式
3. 仿函数提供策略：允许自定义操作行为
4. 适配器扩展功能：不改动原有代码，增加新功能

四、总结：五大组件的关系比喻

完整比喻：图书馆系统

1. 容器 = 书架、储物柜（各种存储设施）
   • vector：一排可以扩展的书架
   • list：用链条连接的书格
   • map：按书名排序的目录柜
   • set：不允许重复的珍本书架
2. 算法 = 图书管理方法
   • sort：按某种规则整理书籍
   • find：查找特定书籍
   • copy：复印书籍
   • remove：下架旧书
3. 迭代器 = 图书管理员的手/扫码枪
   • 可以指向特定位置
   • 可以移动到相邻位置
   • 可以读取书籍信息
   • 连接书架（容器）和管理方法（算法）
4. 仿函数 = 智能工具/规则
   • 按作者排序的规则
   • 按出版日期筛选的条件
   • 自动贴标签的机器
5. 适配器 = 转换接口
   • 把普通书架变成只能从顶部取书的'栈式书架'
   • 把书架变成只能从一端取书的'队列式书架'
   • 反向阅读器（从后向前读）

整个系统工作流程：
管理员（算法）使用扫码枪（迭代器）按照特定规则（仿函数）在书架（容器）上操作，通过特殊设备（适配器）满足特殊需求。