引言在C编程中标准模板库是不可或缺的核心组成部分。无论你是参加算法竞赛、开发大型项目还是准备技术面试STL都能极大地提升你的开发效率。STL发展历程中的几个重要版本版本开发者/应用场景特点HP版本惠普公司原始开发是STL的原始实现后被纳入C标准SGI版本Linux系统常用实现开源实现被GCC编译器采用PJ版本Visual Studio配套实现Windows平台主流实现今天我们重点讲解的是在实际开发中最常用的容器——vector和list以及配套的迭代器、算法等核心组件。第一部分STL的核心组成一、STL的四大组件组件作用举例容器存储数据的数据结构vector、list、map、set迭代器统一访问容器元素的接口begin()、end()算法通用的数据处理函数sort、find、copy仿函数行为类似函数的对象greater、less二、迭代器Iterator迭代器是面向对象化的指针支持解引用、移动等操作是连接容器与算法的桥梁。#include iostream #include vector using namespace std; int main() { vectorint arr {1, 2, 3, 4, 5}; // 迭代器的基本使用 vectorint::iterator it arr.begin(); cout 第一个元素: *it endl; // 遍历所有元素 for (it arr.begin(); it ! arr.end(); it) { cout *it ; } cout endl; return 0; }三、算法Algorithm算法库提供了大量常用操作直接调用即可无需重复造轮子。分类算法函数功能排序sort()排序查找find()查找元素拷贝copy()复制元素删除remove()删除元素统计count()计数#include iostream #include vector #include algorithm using namespace std; int main() { vectorint arr {5, 2, 8, 1, 9, 3}; // 排序默认升序 sort(arr.begin(), arr.end()); // 结果1 2 3 5 8 9 // 降序排序 sort(arr.begin(), arr.end(), greaterint()); // 结果9 8 5 3 2 1 return 0; }第二部分vector容器详解一、vector的底层结构vector是动态数组在内存中开辟连续空间存储元素。其底层由三个关键指针管理指针含义start堆空间首地址finish最后一个元素的后继地址决定sizeend_of_storage空间容量末尾地址决定capacity重要概念size()实际存储的元素个数capacity()预分配的空间大小size capacity二、vector的扩容机制当空间不足时vector会自动扩容通常按2倍或1.5倍增长。#include iostream #include vector using namespace std; int main() { vectorint arr; cout 初始: size arr.size() , capacity arr.capacity() endl; for (int i 0; i 10; i) { arr.push_back(i); cout push_back( i ): size arr.size() , capacity arr.capacity() endl; } return 0; }扩容过程的影响存储对象时扩容需要逐个迁移对象并调用拷贝构造函数性能开销大存储指针时仅需迁移指针地址性能更优但需注意内存释放问题三、vector的初始化方式#include iostream #include vector using namespace std; int main() { // 1. 默认构造 vectorint v1; // 2. 指定大小 vectorint v2(10); // 10个元素值为0 vectorint v3(10, 5); // 10个元素值都为5 // 3. 列表初始化C11 vectorint v4 {1, 2, 3, 4, 5}; vectorint v5{1, 2, 3, 4, 5}; // 4. 拷贝构造 vectorint v6(v4); // 5. 迭代器范围构造 vectorint v7(v4.begin(), v4.end()); return 0; }四、vector的元素访问方式访问方式语法边界检查效率下标运算符arr[i]❌ 无检查最高at()方法arr.at(i)✅ 抛出异常较高front()arr.front()空容器未定义高back()arr.back()空容器未定义高data()arr.data()返回底层数组指针高#include iostream #include vector #include stdexcept using namespace std; int main() { vectorint arr {10, 20, 30, 40, 50}; // 下标访问无边界检查 cout arr[0] endl; // 10 // arr[10] 100; // 越界未定义行为 // at()方法有边界检查 try { cout arr.at(2) endl; // 30 cout arr.at(10) endl; // 抛出out_of_range异常 } catch (const out_of_range e) { cout 越界: e.what() endl; } // 首尾元素 cout 第一个元素: arr.front() endl; // 10 cout 最后一个元素: arr.back() endl; // 50 return 0; }五、vector的遍历方式#include iostream #include vector using namespace std; int main() { vectorint arr {1, 2, 3, 4, 5}; // 方式1下标遍历 cout 下标遍历: ; for (size_t i 0; i arr.size(); i) { cout arr[i] ; } cout endl; // 方式2迭代器遍历 cout 迭代器遍历: ; for (vectorint::iterator it arr.begin(); it ! arr.end(); it) { cout *it ; } cout endl; // 方式3范围for循环C11 cout 范围for值传递: ; for (auto x : arr) { // 拷贝每个元素 cout x ; } cout endl; // 方式4范围for引用传递避免拷贝 cout 范围for引用传递: ; for (const auto x : arr) { // 只读不拷贝 cout x ; } cout endl; // 修改元素需要引用 for (auto x : arr) { x * 2; } return 0; }效率对比值传递for (auto x : arr)每次迭代都会拷贝元素效率低引用传递for (auto x : arr)不拷贝效率高const引用for (const auto x : arr)只读场景效率高且语义明确六、vector的容量管理#include iostream #include vector using namespace std; int main() { vectorint arr; // 预分配容量避免频繁扩容 arr.reserve(100); cout reserve后: capacity arr.capacity() endl; // 添加元素 for (int i 0; i 50; i) { arr.push_back(i); } cout size arr.size() , capacity arr.capacity() endl; // 释放多余内存 arr.shrink_to_fit(); cout shrink_to_fit后: capacity arr.capacity() endl; return 0; }方法作用说明reserve(n)预分配容量避免频繁扩容不改变sizeshrink_to_fit()释放多余内存将capacity缩小到sizeclear()清空元素size变为0capacity不变七、vector的插入与删除#include iostream #include vector using namespace std; int main() { vectorint arr {1, 2, 3, 4, 5}; // 尾部操作高效O(1) arr.push_back(6); // 尾部插入 arr.pop_back(); // 尾部删除 // 中间操作低效O(n) arr.insert(arr.begin() 2, 100); // 在位置2插入100 arr.erase(arr.begin() 3); // 删除位置3的元素 // 遍历 for (int x : arr) { cout x ; } cout endl; return 0; }复杂度总结操作时间复杂度说明push_back()/pop_back()O(1)尾部操作高效insert()/erase()中间O(n)需要移动元素低效第三部分迭代器详解一、迭代器的基本使用#include iostream #include vector using namespace std; int main() { vectorint arr {10, 20, 30, 40, 50}; // 正向迭代器 cout 正向遍历: ; for (vectorint::iterator it arr.begin(); it ! arr.end(); it) { cout *it ; } cout endl; // 只读迭代器 cout 只读遍历: ; for (vectorint::const_iterator it arr.cbegin(); it ! arr.cend(); it) { cout *it ; // *it 100; // 错误const_iterator不能修改 } cout endl; // 反向迭代器 cout 反向遍历: ; for (vectorint::reverse_iterator it arr.rbegin(); it ! arr.rend(); it) { cout *it ; } cout endl; return 0; }二、迭代器类型总结迭代器类型获取方式可读可写方向iteratorbegin()/end()✅✅正向const_iteratorcbegin()/cend()✅❌正向reverse_iteratorrbegin()/rend()✅✅反向三、迭代器失效问题#include iostream #include vector using namespace std; int main() { vectorint arr {1, 2, 3, 4, 5}; // 获取迭代器 auto it arr.begin() 2; // 指向元素3 cout *it *it endl; // 插入操作可能导致迭代器失效 arr.insert(arr.begin(), 0); // 头部插入可能导致所有迭代器失效 // 危险it可能已经失效 // cout *it *it endl; // 重新获取迭代器 it arr.begin() 3; cout 重新获取后: *it *it endl; return 0; }迭代器失效场景插入元素导致扩容时所有迭代器失效删除元素后被删除位置之后的迭代器失效第四部分list容器详解一、list的底层结构list是双向链表节点在内存中不连续通过指针连接。// list节点的简化结构 templatetypename T struct ListNode { T data; // 数据域 ListNode* prev; // 前驱指针 ListNode* next; // 后继指针 }; // 带哨兵节点的双向链表 // head指向头节点哨兵size记录元素个数list内存布局逻辑结构 ┌──────┐ ┌──────┐ ┌──────┐ ┌──────┐ │ 节点1 │◄──►│ 节点2 │◄──►│ 节点3 │◄──►│ 节点4 │ │ data │ │ data │ │ data │ │ data │ └──────┘ └──────┘ └──────┘ └──────┘ ↑ ↑ └──────────────┐ ┌──────────────────┘ ▼ ▼ ┌──────────┐ │ 哨兵节点 │ └──────────┘二、list的基本操作#include iostream #include list using namespace std; int main() { // 初始化 listint lst {1, 2, 3, 4, 5}; // 插入操作高效O(1) lst.push_back(6); // 尾部插入 lst.push_front(0); // 头部插入 // 删除操作高效O(1) lst.pop_back(); // 尾部删除 lst.pop_front(); // 头部删除 // 访问只能访问首尾 cout 第一个元素: lst.front() endl; cout 最后一个元素: lst.back() endl; // ❌ list不支持下标访问 // cout lst[2] endl; // 错误 // 遍历使用迭代器或范围for cout 遍历: ; for (int x : lst) { cout x ; } cout endl; return 0; }三、list vs vector特性vectorlist底层结构动态数组连续内存双向链表非连续随机访问✅ O(1)❌ O(n)中间插入/删除❌ O(n)✅ O(1)尾部插入/删除✅ O(1)扩容时O(n)✅ O(1)内存占用较少无指针开销较大前后指针适用场景频繁访问、尾部操作频繁中间插入删除四、list的特殊操作#include iostream #include list #include algorithm using namespace std; int main() { listint lst {5, 2, 8, 1, 3, 2, 5, 2}; // list专属排序不能用标准库的sort lst.sort(); // 升序排序 // lst.sort(greaterint()); // 降序排序 // 去重必须先排序 lst.unique(); // 删除相邻重复元素 // 删除指定值的所有元素 lst.remove(2); // 删除所有值为2的元素 // 合并两个有序list listint lst2 {10, 20, 30}; lst.merge(lst2); // lst2被清空元素合并到lst // 反转 lst.reverse(); for (int x : lst) { cout x ; } cout endl; return 0; }第五部分关联容器set/map一、set容器集合set中的元素唯一且自动排序底层基于红黑树实现。#include iostream #include set using namespace std; int main() { vectorint arr {5, 2, 8, 1, 5, 2, 9, 3}; // 使用set去重 setint s; for (int x : arr) { s.insert(x); } cout 去重后: ; for (int x : s) { cout x ; } cout endl; // 输出1 2 3 5 8 9自动排序 // 查找元素 if (s.find(5) ! s.end()) { cout 5存在 endl; } return 0; }二、map容器映射map存储键值对键唯一且自动排序。#include iostream #include map using namespace std; int main() { vectorint arr {1, 2, 3, 2, 1, 3, 4, 2, 1}; // 统计每个元素出现的次数 mapint, int freq; for (int x : arr) { freq[x]; // 使用[]操作符 } // 遍历map for (const auto kv : freq) { cout kv.first 出现 kv.second 次 endl; } return 0; }三、unordered_set/unordered_map无序版本底层基于哈希表实现查找更快O(1)但不保证顺序。容器底层结构有序性查找复杂度set/map红黑树有序O(log n)unordered_set/unordered_map哈希表无序O(1) 平均#include iostream #include unordered_set using namespace std; int main() { unordered_setint us {5, 2, 8, 1, 9}; // 顺序不确定 for (int x : us) { cout x ; } cout endl; return 0; }总结一、容器特性对比容器底层随机访问中间插入/删除适用场景vector动态数组✅ O(1)❌ O(n)频繁访问、尾部操作list双向链表❌ O(n)✅ O(1)频繁中间插入删除deque双端队列✅ O(1)两端O(1)双端操作set/map红黑树❌插入/查找O(log n)有序唯一集合unordered_set/unordered_map哈希表❌插入/查找O(1)快速查找、去重二、迭代器类型迭代器获取方式支持操作iteratorbegin()/end()读写const_iteratorcbegin()/cend()只读reverse_iteratorrbegin()/rend()反向遍历三、vector常用操作速查操作方法复杂度尾部插入push_back()O(1)尾部删除pop_back()O(1)中间插入insert()O(n)中间删除erase()O(n)访问元素[]/at()O(1)大小size()O(1)容量capacity()O(1)预分配reserve()O(n)四、list常用操作速查操作方法复杂度头部插入push_front()O(1)头部删除pop_front()O(1)尾部插入push_back()O(1)尾部删除pop_back()O(1)排序sort()O(n log n)去重unique()O(n)合并merge()O(n)STL是C标准库的核心掌握STL能够极大地提升开发效率。STL使用三步法掌握基本使用方法熟练运用各类容器和算法理解源码实现并实现功能扩展学习建议优先级vectorlistmapunordered_map迭代器遍历时注意引用传递避免拷贝使用reserve()预分配容量避免频繁扩容优先使用emplace_back()替代push_back()减少拷贝根据场景选择合适的关联容器有序选map无序选unordered_map