侯捷C++课程学习笔记：STL相关（六）

侯捷C++课程学习笔记：STL相关（六）

一、STL设计哲学

1. 六大核心组件

• ​容器：数据存储的泛型结构（序列式/关联式）

• ​算法：与数据结构解耦的操作集合（非成员函数模板）

• ​迭代器：统一访问容器的抽象指针（五类迭代器）
  

• ​函数对象：重载operator()的可调用对象（谓词/运算符）

• ​适配器：接口转换工具（容器/迭代器/函数适配器）

• ​分配器：内存管理的策略类（隐藏于容器默认参数）

2. 泛型编程精髓

• ​正交分解：算法与容器通过迭代器解耦合
• ​概念约束：模板类型需满足特定接口要求（C++20概念前身）
• ​零成本抽象：通过模板实例化达成运行时零额外开销

二、容器深度解析

1. 序列容器特性

• ​vector：动态数组（随机访问O(1)，尾部操作分摊O(1)）
• ​deque：分块连续存储（双端队列，中间插入O(n)）
• ​list：双向链表（稳定迭代器，节点操作O(1)）
• ​forward_list：单向链表（极简内存布局，无size()方法）

2. 关联容器实现

• ​红黑树系：set/map/multiset/multimap（平衡二叉搜索树）
• ​哈希表系：unordered_系列（开链法解决哈希冲突）
• ​自定义排序：通过函数对象指定元素比较规则

3. 容器选择策略

• ​访问模式：随机访问需求决定使用vector或list
• ​内存敏感度：连续存储容器更易触发缓存预取
• ​迭代器失效：插入/删除操作对不同容器的影响差异

三、迭代器机制

1. 迭代器类别

• ​输入/输出：单次遍历流式数据（如istream_iterator）
• ​前向：单向多趟遍历（如哈希容器迭代器）
• ​双向：支持–操作（list/rb_tree迭代器）
• ​随机访问：支持算术运算（vector/string迭代器）

2. 失效规则

• ​vector：容量变化导致全部失效，插入导致后方失效
• ​deque：首尾插入部分失效，中间插入全部失效
• ​关联容器：仅被删除元素迭代器失效
• ​unordered容器：rehash操作导致全表失效

四、算法与函数对象

1. 算法分类

• ​非修改型：find/count/accumulate（保持原容器）
• ​修改型：copy/transform/replace（直接修改元素）
• ​排序相关：sort/partial_sort/nth_element
• ​数值运算：inner_product/adjacent_difference

2. 函数对象进化

• ​传统仿函数：重载operator()的struct
• ​lambda表达式：C++11引入的匿名函数对象
• ​绑定器：bind/placeholder机制实现参数绑定
• ​函数包装器：function模板统一可调用对象类型

五、内存管理机制

1. 分配器设计

• ​接口规范：allocate/deallocate方法遵循STL协议
• ​rebind机制：支持同一分配器服务不同容器类型
• ​内存池优化：自定义分配器减少碎片化开销

2. 容器内存策略

• ​vector扩容：2倍/1.5倍几何增长策略选择
• ​string优化：短字符串存储在栈内存（SSO优化）
• ​node-based容器：每个元素独立分配内存节点

六、STL扩展应用

1. C++11/17新特性

• ​移动语义支持：emplace系列方法避免临时对象构造
• ​结构化绑定：简化pair/tuple的成员访问
• ​并行算法：C++17引入执行策略参数（par/seq等）

2. 适配器组合

• ​容器适配器：stack/queue/priority_queue
• ​迭代器适配器：reverse/insert/stream迭代器
• ​函数适配器：not1/bind2nd组合谓词逻辑

七、STL设计陷阱

1. 常见误用场景

• ​无效迭代器：在循环中错误删除元素
• ​类型不匹配：auto推导隐藏的代理迭代器问题
• ​性能误区：在vector头部频繁插入数据
• ​内存泄漏：指针容器未手动释放元素

2. 模板元编程影响

• ​编译膨胀：过度模板实例化导致代码体积激增
• ​调试困难：模板错误信息可读性差（C++20概念改善）
• ​跨DLL风险：不同模块实例化相同模板可能引发问题

八、现代C++对STL的影响

1. 语义增强

• ​移动迭代器：move_iterator实现元素所有权转移
• ​范围访问：C++11引入的全局begin()/end()函数
• ​透明运算符：允许异构查找（set<void*>特性）

2. 新容器演进

• ​array：替代传统C风格数组
• ​unordered系列：提供更优平均时间复杂度
• ​forward_list：极致优化的单向链表实现

3. 并发安全

• ​原子操作支持：atomic与容器的组合使用
• ​线程安全层级：STL容器仅保证读操作的并发安全
• ​锁机制整合：结合mutex实现容器细粒度锁定