目录
前言：为什么需要list
二、基础认知：list的底层与初始化
2.1什么是list
2.2头文件与命名空间
2.3初始化方式
三、迭代器误区
四、核心操作：增删查改
4.1元素添加：push_back/push_front/insert
4.2元素删除：pop_back/pop_front/erase/clear
五、常用操作
六、进阶玩法：list的特殊成员函数
6.1排序：list::sort vs 算法库sort
6.2去重：unique函数的使用前提
6.3合并与反转：merge/reverse
前言：为什么需要list
我们常用的vector基于动态数组实现，其优势是支持随机访问，通过[]或at()能快速定位元素。但它的短板也十分突出：当在数组中间或头部插入/删除元素时，需要移动后续所有元素，时间复杂度为O(n)；且扩容时可能需要重新分配内存并拷贝数据，存在性能开销和内存浪费。
list的底层是双向循环链表，每个元素（节点）包含数据和两个指针（分别指向前和后节点），节点间通过指针连接，无需连续内存空间。这种结构使其在头尾插入/删除和中间插入/删除场景下，仅需修改指针指向，时间复杂度均为O(1)（找到目标位置后），完美解决了vector的痛点。
所以当你需要进行大量“频繁插入删除”操作，且对随机访问需求较低时，list是比vector更优的选择。
二、基础认知：list的底层与初始化
2.1什么是list
list是双向循环链表结构，有两个特点
每个节点包含prev（前指针）、data（数据）、next（后指针）
尾节点的next指针指向头节点，头节点的prev指针指向尾节点，形成闭环，便于首尾操作
关于双向链表如果不了解可以去看我的这篇博客帮助理解。（链接：数据结构2：单链表-CSDN博客）
2.2头文件与命名空间
#include <iostream> #include <list> using namespace std; //也可以使用std::list明确命名空间2.3初始化方式
list的初始化方式灵活，可根据实际需求选择
void test1() { list<int> lt1; list<int> lt2 = { 1, 2, 3, 4, 5 }; // 等价于list<int> lst2{1,2,3,4,5}; vector<int> v = { 6, 7, 8 }; list<int> lt3(v.begin(), v.end()); // 从vec的开头到结尾构造lst3 list<int> lt4(5, 10); // 5个元素，每个元素值为10 print(lt1); print(lt2); print(lt3); print(lt4); }我们这里为了方便验证，根据之前学习string和vector的经验写了一个打印函数
void print(list<int>& lt) { for (auto n : lt) { cout << n << ' '; } cout << endl; }验证结果：
三、迭代器误区
list中有的迭代器和string或vector中的区别不大，但需要注意的是list中不支持[ ]随机访问/at随机访问，而且list中的迭代器不能直接+n，必须要一个一个从开头遍历到想要的地方。
因为list是链表结构，没有连续的内存地址，无法通过“基地址+偏移量”的方式快速定位元素。简单来说就是list在物理空间上的位置，也就是说它里面前后节点的位置在物理上不连续。
void test2() { list<int> lt = { 1, 2, 3, 4, 5 }; //auto it = lt.begin() + 3;//err auto it = lt.begin(); int k = 3; while (k--) { ++it; } list<int> lt2(it, lt.end()); print(lt); print(lt2); }验证结果：
四、核心操作：增删查改
4.1元素添加：push_back/push_front/insert
void test3() { list<int> lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); lt1.push_back(5); print(lt1); lt1.push_front(0); print(lt1); //加一个 auto it = lt1.begin(); int k = 3; while (k--) { ++it; } lt1.insert(it, 3); print(lt1); //加多个一样的 auto it1 = lt1.begin(); int i = 3; while (i--) { ++it1; } lt1.insert(it1, 2, 3); print(lt1); //加个迭代器区间的 list<int> lt2 = { 1,2,3,4,5 }; lt1.insert(lt1.end(), lt2.begin(), lt2.end()); print(lt1); }验证结果：
4.2元素删除：pop_back/pop_front/erase/clear
删除操作的核心注意点是迭代器失效问题——list的erase会删除指定节点并返回下一个有效的迭代器，若直接使用失效的迭代器会导致程序崩溃。
void test4() { list<int> lt = { 0, 20, 20, 20, 1, 10, 2, 3, 4, 100, 200 }; print(lt); lt.pop_back(); print(lt); lt.pop_front(); print(lt); //删除单个元素：用erase返回值更新迭代器 auto it = lt.begin(); int i = 3; while (i--) { ++it; } it = lt.erase(it); // 删除后，it指向后续的10（避免失效） print(lt); //删除迭代器范围的元素（左闭右开） auto it1 = lt.begin(); auto it2 = lt.begin(); int j = 3; while (j--) { ++it1; } int k = 6; while (k--) { ++it2; } auto it_start = it1; auto it_end = it2; lt.erase(it_start, it_end); print(lt); lt.clear(); print(lt); }验证结果：
五、常用操作
按值删除：remove（删除所有等于val的元素）
按条件删除：remove_if（删除满足条件的元素）
void test5() { list<int> lt = { 0,1,2,3,4,5 }; print(lt); lt.remove(2); // 删除所有值为2的元素 print(lt); lt.remove_if([](int val) { return val % 2 == 1; });//删除所有奇数 print(lt); }验证结果：
size/empty/resize用于管理list的状态
void test6() { list<int> lt = { 1,2,3,4,5 }; print(lt); cout << lt.size() << endl; lt.resize(7, 6); print(lt); lt.resize(2); print(lt); cout << "lt空吗？" << (lt.empty() ? "是" : "否") << endl; }验证结果：
六、进阶玩法：list的特殊成员函数
list提供了一些专属的成员函数，这些函数基于链表特性优化，性能优于STL通用算法，是进阶使用的核心技巧。
6.1排序：list::sort vs 算法库sort
STL算法库的sort函数要求迭代器支持随机访问，而list的迭代器是双向迭代器，因此无法直接使用algorithm中的sort，必须使用list自带的sort成员函数。list::sort基于双向链表优化，采用归并排序思想，时间复杂度O(nlogn)。
void test7() { list<int> lt = { 3, 1, 4, 1, 5, 9 }; // 1. 正确用法：list自带的sort成员函数 lt.sort(); // 默认升序排序 print(lt); // 2. 自定义降序排序（用lambda表达式） lt.sort([](int a, int b) { return a > b; }); print(lt); // 3. 错误示范：无法使用算法库的sort // sort(lt.begin(), lt.end()); // 编译报错：迭代器类型不匹配 }验证结果：
6.2去重：unique函数的使用前提
list::unique用于删除相邻的重复元素，因此使用前必须先排序（确保重复元素相邻），否则无法彻底去重。
void test8() { list<int> lt = { 3, 1, 4, 1, 5, 9 }; lt.sort(); print(lt); lt.unique(); print(lt); }验证结果：
6.3合并与反转：merge/reverse
merge用于合并两个已排序的list，合并后原list会被清空；reverse用于反转list的元素顺序，时间复杂度O(n)。
void test9() { list<int> lt1 = { 1, 3, 5 }; print(lt1); list<int> lt2 = { 2, 4, 6 }; print(lt2); lt1.merge(lt2); // 合并lt2到lt1（lst2需已排序） print(lt1); print(lt2); lt1.reverse(); print(lt1); }验证结果：
