C STL 学习笔记C STLStandard Template Library是C标准库的核心封装了常用数据结构与算法凭借“泛型编程”思想实现高复用性让开发者无需重复造轮子专注于核心业务逻辑。本文基于STL底层原理、关键特性与实战场景整理成学习笔记覆盖容器、迭代器、适配器等核心组件。一、STL 核心组件概览STL由五大核心组件构成组件间相互配合实现“数据存储-访问-操作”的完整闭环二、容器详解分类、原理与场景容器是STL的核心按存储逻辑分为顺序容器、关联容器、无序容器三类底层实现决定其性能特性与适用场景。一容器分类与核心特性总览二顺序容器线性存储注重顺序与访问效率顺序容器维护元素的线性序列核心差异体现在内存布局与插入/删除效率详细特性如下1. 各顺序容器对比2. 顺序容器关键问题解析1vector 核心原理连续存储保证内部通过单一内存块存储元素维护三个核心变量T* elements内存起始指针、size当前元素个数、capacity当前内存容量通过指针运算实现随机访问。扩容机制当size capacity空间不足时触发扩容申请原容量1.5~2倍的新内存GCC为2倍VS为1.5倍将旧内存中元素复制/移动到新内存支持移动语义的对象用移动构造否则用拷贝释放旧内存。为什么成倍扩容避免频繁扩容导致的O(n)时间复杂度保证增删操作平均O(1)1.5~2倍兼顾内存利用率3倍及以上易造成内存浪费。2push_back 与 emplace_back 的区别两者均用于在容器尾部添加元素核心差异在于“元素构造方式”示例代码// 自定义类 class Person { public: Person(int age, string name) : age(age), name(name) {} private: int age; string name; }; vectorPerson vec; vec.push_back(Person(20, Tom)); // 先构造临时对象再移动/拷贝 vec.emplace_back(20, Tom); // 直接在vec尾部构造无临时对象3vector 与 array 的核心对比三关联容器有序存储注重查找与排序关联容器基于红黑树实现自平衡二叉搜索树元素按键自动排序查找、插入、删除时间复杂度均为O(logn)核心差异在于存储方式与键的唯一性1. 关联容器对比2. 关联容器关键操作元素查找map/set 提供四种核心查找方法适用于不同场景示例代码map查找mapint, string myMap {{1, one}, {2, two}}; // 1. find方法 auto it myMap.find(1); if (it ! myMap.end()) cout 找到 it-second endl; // 2. count方法 if (myMap.count(2)) cout 找到key2 endl; // 3. lower_bound/upper_bound auto lower myMap.lower_bound(1); auto upper myMap.upper_bound(1); if (lower ! upper) cout 找到 lower-second endl;四无序容器哈希存储注重高效访问无序容器C11引入基于哈希表实现元素无序存储平均查找、插入、删除时间复杂度为O(1)核心特性与关联容器对比1. 无序容器与关联容器核心差异2. 关键注意点哈希容器的 rehash当无序容器的元素个数超过“负载因子”默认1.0时会触发rehash重建哈希表此时所有迭代器失效。避免失效的方法批量插入前调用reserve(n)预分配足够容量减少rehash次数rehash后需重新获取迭代器不可使用旧迭代器。三、迭代器容器的“通用指针”一迭代器的核心作用迭代器提供容器无关的统一元素访问接口无论容器底层是数组、链表还是红黑树都可通过递增、*解引用等操作遍历元素实现“算法与容器解耦”。二迭代器失效高频踩坑点迭代器失效指容器修改后如插入、删除、扩容原有迭代器不再指向有效元素继续使用会导致未定义行为UB。不同容器的失效规则如下1. 各容器迭代器失效规则2. 避免迭代器失效的实战技巧使用 erase 返回值C11起erase(it)返回下一个有效迭代器适用于边遍历边删除// vector安全删除偶数元素 vectorint vec {1,2,3,4}; for (auto it vec.begin(); it ! vec.end(); ) { if (*it % 2 0) it vec.erase(it); // 用返回值更新迭代器 else it; }提前规划容量vector/string 批量插入前调用reserve(n)避免扩容导致全迭代器失效选择稳定迭代器容器频繁插删且需迭代器稳定时优先用list、unordered_map/set避免持有临时容器迭代器局部容器销毁后其迭代器变为“悬垂迭代器”不可使用。四、适配器封装现有组件改变接口适配器Adapters是对现有容器的“包装”改变其接口或功能不直接存储数据依赖底层容器实现关键说明stack/queue 底层默认用deque因其支持双端高效增删且避免vector扩容的开销priority_queue 底层基于vector实现的“大根堆”默认可通过仿函数指定为小根堆// 小根堆 priority_queueint, vectorint, greaterint minHeap;五、容器选择策略按需选型选择容器的核心原则匹配需求与容器性能特性以下是常见场景的最优选择六、实战技巧总结vector 性能优化批量插入前用reserve(n)预分配容量减少扩容次数元素删除安全写法依赖erase返回值更新迭代器避免迭代器失效复杂对象优先用 emplace_back避免临时对象拷贝/移动开销提升效率哈希容器优化通过reserve(n)减少rehash自定义哈希函数降低冲突避免过度依赖 vector中间频繁插删时list效率远高于vectormap 与 unordered_map 选型需有序/范围查询用map需高效查找用unordered_map。总结STL的核心价值在于“泛型、复用、高效”掌握其关键在于理解容器底层实现与性能特性。本文覆盖容器分类、核心原理、迭代器使用、适配器特性与实战技巧建议结合代码练习如容器增删查改、算法结合迭代器使用加深理解。STL的学习无需死记硬背重点在于“按需选型、避坑高效”熟练运用后能大幅提升编码效率与代码质量。
C++ STL 学习笔记
C STL 学习笔记C STLStandard Template Library是C标准库的核心封装了常用数据结构与算法凭借“泛型编程”思想实现高复用性让开发者无需重复造轮子专注于核心业务逻辑。本文基于STL底层原理、关键特性与实战场景整理成学习笔记覆盖容器、迭代器、适配器等核心组件。一、STL 核心组件概览STL由五大核心组件构成组件间相互配合实现“数据存储-访问-操作”的完整闭环二、容器详解分类、原理与场景容器是STL的核心按存储逻辑分为顺序容器、关联容器、无序容器三类底层实现决定其性能特性与适用场景。一容器分类与核心特性总览二顺序容器线性存储注重顺序与访问效率顺序容器维护元素的线性序列核心差异体现在内存布局与插入/删除效率详细特性如下1. 各顺序容器对比2. 顺序容器关键问题解析1vector 核心原理连续存储保证内部通过单一内存块存储元素维护三个核心变量T* elements内存起始指针、size当前元素个数、capacity当前内存容量通过指针运算实现随机访问。扩容机制当size capacity空间不足时触发扩容申请原容量1.5~2倍的新内存GCC为2倍VS为1.5倍将旧内存中元素复制/移动到新内存支持移动语义的对象用移动构造否则用拷贝释放旧内存。为什么成倍扩容避免频繁扩容导致的O(n)时间复杂度保证增删操作平均O(1)1.5~2倍兼顾内存利用率3倍及以上易造成内存浪费。2push_back 与 emplace_back 的区别两者均用于在容器尾部添加元素核心差异在于“元素构造方式”示例代码// 自定义类 class Person { public: Person(int age, string name) : age(age), name(name) {} private: int age; string name; }; vectorPerson vec; vec.push_back(Person(20, Tom)); // 先构造临时对象再移动/拷贝 vec.emplace_back(20, Tom); // 直接在vec尾部构造无临时对象3vector 与 array 的核心对比三关联容器有序存储注重查找与排序关联容器基于红黑树实现自平衡二叉搜索树元素按键自动排序查找、插入、删除时间复杂度均为O(logn)核心差异在于存储方式与键的唯一性1. 关联容器对比2. 关联容器关键操作元素查找map/set 提供四种核心查找方法适用于不同场景示例代码map查找mapint, string myMap {{1, one}, {2, two}}; // 1. find方法 auto it myMap.find(1); if (it ! myMap.end()) cout 找到 it-second endl; // 2. count方法 if (myMap.count(2)) cout 找到key2 endl; // 3. lower_bound/upper_bound auto lower myMap.lower_bound(1); auto upper myMap.upper_bound(1); if (lower ! upper) cout 找到 lower-second endl;四无序容器哈希存储注重高效访问无序容器C11引入基于哈希表实现元素无序存储平均查找、插入、删除时间复杂度为O(1)核心特性与关联容器对比1. 无序容器与关联容器核心差异2. 关键注意点哈希容器的 rehash当无序容器的元素个数超过“负载因子”默认1.0时会触发rehash重建哈希表此时所有迭代器失效。避免失效的方法批量插入前调用reserve(n)预分配足够容量减少rehash次数rehash后需重新获取迭代器不可使用旧迭代器。三、迭代器容器的“通用指针”一迭代器的核心作用迭代器提供容器无关的统一元素访问接口无论容器底层是数组、链表还是红黑树都可通过递增、*解引用等操作遍历元素实现“算法与容器解耦”。二迭代器失效高频踩坑点迭代器失效指容器修改后如插入、删除、扩容原有迭代器不再指向有效元素继续使用会导致未定义行为UB。不同容器的失效规则如下1. 各容器迭代器失效规则2. 避免迭代器失效的实战技巧使用 erase 返回值C11起erase(it)返回下一个有效迭代器适用于边遍历边删除// vector安全删除偶数元素 vectorint vec {1,2,3,4}; for (auto it vec.begin(); it ! vec.end(); ) { if (*it % 2 0) it vec.erase(it); // 用返回值更新迭代器 else it; }提前规划容量vector/string 批量插入前调用reserve(n)避免扩容导致全迭代器失效选择稳定迭代器容器频繁插删且需迭代器稳定时优先用list、unordered_map/set避免持有临时容器迭代器局部容器销毁后其迭代器变为“悬垂迭代器”不可使用。四、适配器封装现有组件改变接口适配器Adapters是对现有容器的“包装”改变其接口或功能不直接存储数据依赖底层容器实现关键说明stack/queue 底层默认用deque因其支持双端高效增删且避免vector扩容的开销priority_queue 底层基于vector实现的“大根堆”默认可通过仿函数指定为小根堆// 小根堆 priority_queueint, vectorint, greaterint minHeap;五、容器选择策略按需选型选择容器的核心原则匹配需求与容器性能特性以下是常见场景的最优选择六、实战技巧总结vector 性能优化批量插入前用reserve(n)预分配容量减少扩容次数元素删除安全写法依赖erase返回值更新迭代器避免迭代器失效复杂对象优先用 emplace_back避免临时对象拷贝/移动开销提升效率哈希容器优化通过reserve(n)减少rehash自定义哈希函数降低冲突避免过度依赖 vector中间频繁插删时list效率远高于vectormap 与 unordered_map 选型需有序/范围查询用map需高效查找用unordered_map。总结STL的核心价值在于“泛型、复用、高效”掌握其关键在于理解容器底层实现与性能特性。本文覆盖容器分类、核心原理、迭代器使用、适配器特性与实战技巧建议结合代码练习如容器增删查改、算法结合迭代器使用加深理解。STL的学习无需死记硬背重点在于“按需选型、避坑高效”熟练运用后能大幅提升编码效率与代码质量。
