一. list 是什么先搞懂底层结构list的本质是双向循环链表且带有一个哨兵位头结点(不存储有效数据)结构如下在这里插入图片描述双向每个字节包含前驱指针 (prev) 和后继指针 (next) 支持向前向后遍历循环尾节点的 next 指向头结点头结点的 prev 指向尾结点形成闭环哨兵位头结点避免插入/删除时判断是否为空”是否为头结点“的麻烦简化代码逻辑。这种结构决定了 list 的核心特性任意位置插入/删除效率高O(1)但不支持随机访问(访问元素需要遍历O(N))。头文件包含代码语言javascriptAI代码解释#define _CRT_SECURE_NO_WARNINGS 1 #includeiostream #includelist #includealgorithm using namespace std;参考文档list - C Reference二. list核心接口使用从构造到修改list的接口丰富但重点掌握构造迭代器容量元素访问修改’五大类即可满足日常开发需求以下结合代码示例讲解。2.1 构造函数初始化一个listlist提供4种常用构造方式覆盖空容器n个相同元素拷贝区间初始化场景构造函数接口说明代码示例list()构造空 listlistint l1;空链表仅含头结点list(size_type n, const T val T())构造含 n 个 val 的 listlistint l2(5, 3);元素3,3,3,3,3list(const list x)拷贝构造listint l3(l2);l3 是 l2 的副本list(InputIterator first, InputIterator last)用 [first, last) 区间构造int arr[] {1,2,3}; listint l4(arr, arr3);元素1,2,3代码演示代码语言javascriptAI代码解释void test_list1() { //展示其中两个其实使用起来跟前面的vector差不多 listint lt1;//无参构造 listint lt2 {1,2,3,4,5}; listint::iterator it2 lt2.begin(); while (it2 ! lt2.end()) { cout *it2 ; it2; } cout endl; for (auto e : lt2) { cout e ; } cout endl; } int main() { test_list1(); }在这里插入图片描述2.2 迭代器遍历list的 “指针”list的迭代器本质是 “结点指针的封装”支持正向和反向遍历核心接口如下(当然也可以使用范围for)函数声明接口说明特点begin() / end()正向迭代器begin() 指向 list 第一个有效元素end() 指向头结点尾后位置对迭代器执行 操作迭代器向后移动用于正向遍历所有有效元素rbegin() / rend()反向迭代器rbegin() 指向 list 最后一个有效元素rend() 指向头结点反向尾后位置对迭代器执行 操作迭代器向前移动用于反向遍历所有有效元素迭代器知识补充在这里插入图片描述在这里插入图片描述2.3 容量与元素访问判断空、查大小、取首尾list不支持随机访问没有operator[]和at()仅提供 “判断空、获取大小、取首尾元素” 的接口函数声明接口说明代码示例基于 l4 {1,2,3,4}empty()检测 list 是否为空空则返回 true非空返回 falsel4.empty();返回 false因 l4 含 4 个有效元素size()返回 list 中有效元素的个数单位为无符号整数size_typel4.size();返回 4对应 l4 中的元素 1、2、3、4front()返回 list 第一个有效元素的引用支持读写操作可直接修改元素值l4.front() 10;修改后 l4 变为 {10,2,3,4}back()返回 list 最后一个有效元素的引用支持读写操作可直接修改元素值l4.back() 40;修改后 l4 变为 {10,2,3,40}注意front()和back()仅在list非空时使用若为空会触发未定义行为建议先empty()判断。2.4 元素修改插入删除清空list的核心优势在修改操作,任意位置插入/删除仅需调整指针效率极高常用接口如下函数声明接口说明代码示例基于 l4 {10,2,3,40}push_front(const T val)在 list 头部第一个个有效元素之前插入值为 val 的元素l4.push_front(0);插入后 l4 变为 {0,10,2,3,40}pop_front()删除 list 的第一个个有效元素l4.pop_front();删除后 l4 变回 {10,2,3,40}push_back(const T val)在 list 尾部最后一个有效元素之后插入值为 val 的元素l4.push_back(50);插入后 l4 变为 {10,2,3,40,50}pop_back()删除 list 的最后一个有效元素l4.pop_back();删除后 l4 变回 {10,2,3,40}insert(iterator pos, const T val)在迭代器 pos 指向的位置之前插入值为 val 的元素返回指向新插入元素的迭代器auto it l4.begin(); it; l4.insert(it, 15);it 初始指向 2插入后 l4 变为 {10,15,2,3,40}erase(iterator pos)删除迭代器 pos 指向的元素返回指向被删除元素下一个元素的迭代器it l4.begin(); it; l4.erase(it);it 指向 15删除后 l4 变回 {10,2,3,40}clear()清空 list 中所有有效元素仅保留头结点清空后 size() 为 0l4.clear();清空后 l4 无有效元素l4.size() 返回 02.5 常用算法与操作find、sort、unique、reverselist提供多个实用成员函数和适配的通用算法用于处理查找、排序、去重、反转等场景具体如下函数类型函数声明 / 调用方式接口说明代码示例基于 listint l {3,1,4,1,5,9}注意事项算法函数需包含 algorithmfind(iterator first, iterator last, const T val)在 [first, last) 区间查找值为 val 的元素返回首个匹配元素的迭代器若未找到返回 last#include algorithm auto it find(l.begin(), l.end(), 4); // it 指向元素 4值为4的位置1. 属于 STL 通用算法非 list 成员函数2. 时间复杂度 O(N)需遍历查找成员函数sort()对 list 元素进行升序排序默认按 比较l.sort(); // 排序后 l {1,1,3,4,5,9}1. list 不支持随机访问不能用 STL 通用 sort 算法需用自身成员函数2. 底层通常为归并排序时间复杂度 O(N log N)成员函数unique()移除连续重复的元素只保留第一个返回指向最后一个有效元素后位置的迭代器l.sort(); // 先排序使重复元素连续{1,1,3,4,5,9} l.unique(); // 去重后 l {1,3,4,5,9}1. 仅移除“连续重复”元素需先 sort() 使相同元素相邻才能完全去重2. 时间复杂度 O(N)成员函数reverse()反转 list 中所有元素的顺序l.reverse(); // 原 l{3,1,4,1,5,9} → 反转后 {9,5,1,4,1,3}仅调整节点指针方向时间复杂度 O(N)效率极高代码演示代码语言javascriptAI代码解释void test_list2() { listint lt1;//无参构造 listint lt2 { 1,2,3,4,5 }; auto pos find(lt2.begin(),lt2.end(),3); if (pos ! lt2.end()) { lt2.insert(pos, 30);//pos没有失效因为没有扩容 lt2.erase(pos);//pos失效了 //cout *pos endl; } for (auto e : lt2) { cout e ; } cout endl; } void test_list3() { listint lt2 { 1,2,4,3,5 }; //sort(lt2.begin(), lt2.end());//不支持 lt2.sort(); for (auto e : lt2) { cout e ; } cout endl; } void test_list4() { listint lt3 { 1,2,2,3,3,2,3,4,5 }; for (auto e : lt3) { cout e ; } cout endl; lt3.sort(); lt3.unique();//去重 for (auto e : lt3) { cout e ; } cout endl; } int main() { //test_list1(); test_list2 (); test_list3(); test_list4(); }在这里插入图片描述三. list迭代器失效只在删除时发生前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。迭代器失效是使用list时的核心注意点但其失效规则比vector简单得多插入时list 插入仅需调整指针不会移动现有节点因此所有迭代器都不会失效删除时仅指向 “被删除节点” 的迭代器失效其他迭代器指向未删除节点不受影响。