STL list与vector核心差异详解

一、上期回顾掌握vector动态数组连续内存、随机访问、自动扩容、size/capacity 区别、常用增删接口。今天学习STL list 双向循环链表和 vector 做对标选型。二、list 底层本质list底层是双向循环链表每一个节点存数据 前驱指针 后继指针内存不连续不支持下标随机访问任意位置插入、删除O(1)效率极高三、list 与 vector 核心差异表格特性vectorlist底层结构连续动态数组双向链表随机访问支持[]下标不支持下标头部 / 中间插入删除O (n) 效率低O (1) 效率高尾部增删O (1) 很快O(1)内存占用紧凑无冗余每个节点带两个指针开销大迭代器可能失效插入不失效仅删除当前迭代器失效选型口诀频繁查询、随机访问 → 用 vector频繁中间 / 头部插入删除、不常查找 → 用 list四、list 常用构造方式#include iostream #include list using namespace std; int main() { // 1. 空链表 listint l1; // 2. 5个默认0 listint l2(5); // 3. 5个值为8 listint l3(5, 8); // 4. 拷贝构造 listint l4(l3); // 5. 区间构造 listint l5(l4.begin(), l4.end()); return 0; }五、list 常用赋值与遍历赋值listint l1 {1,2,3,4}; listint l2; l2 l1; l2.assign(3, 66); l2.assign(l1.begin(), l1.end());遍历方式注意list 不支持下标[]访问只能用迭代器、范围 forlistint l {10,20,30}; // 1. 迭代器遍历 for(listint::iterator it l.begin(); it ! l.end(); it) { cout *it ; } // 2. 范围for遍历 for(auto val : l) { cout val ; }六、list 核心常用接口listint l; // 尾插、头插 l.push_back(10); l.push_front(5); // 尾删、头删 l.pop_back(); l.pop_front(); // 大小、判空、清空 l.size(); l.empty(); l.clear(); // 指定位置插入 l.insert(l.begin(), 99); // 删除 l.erase(l.begin()); // 移除指定元素 l.remove(10); // 反转链表 l.reverse(); // 排序 l.sort();重点remove(值)直接删除所有等于该值的元素vector 没有这个便捷接口sort()list 自带排序不用算法库 sort因为不支持随机访问迭代器七、list 迭代器失效特性插入元素所有迭代器都不失效删除元素仅被删除节点的迭代器失效其他仍有效对比 vector插入删除极易导致大量迭代器失效list 更安全。八、完整综合示例代码#include iostream #include list using namespace std; int main() { listint l; // 头尾插入 l.push_back(1); l.push_back(3); l.push_front(0); l.push_back(5); cout 遍历元素; for(auto val : l) { cout val ; } cout endl; // 反转 l.reverse(); cout 反转后; for(auto val : l) cout val ; cout endl; // 排序 l.sort(); cout 排序后; for(auto val : l) cout val ; return 0; }运行结果遍历元素0 1 3 5 反转后5 3 1 0 排序后0 1 3 5九、今日核心总结list 底层双向循环链表内存不连续不支持下标随机访问只能迭代器 / 范围 for 遍历中间、头部增删效率远高于 vector独有接口remove、reverse、自带sort迭代器不易失效适合频繁插入删除场景业务选型查多用 vector插删多用 list十、课后练习创建 list 存入 5 个数字头插、尾插各加一个数调用 reverse 反转、sort 排序并打印