作为 C 初学者在接触 STL 容器时最容易混淆的就是vector和list—— 明明都是存数据的容器为啥用法和场景差这么多这篇文章就像你的 “list 专属学习笔记”用新手能看懂的语言把 list 的底层逻辑、核心用法、避技巧讲透。 目录新手友好版1.【唠唠基础】list 是个啥和 vector 差在哪2.【核心技能】list 的 “常用招式”构造 / 迭代器 / 增删改查3.【踩坑预警】迭代器失效新手最容易栽的坑4.【动手实操】新手也能看懂的 list 模拟实现5.【终极对比】list vs vector啥时候用谁6.【复习小结】核心知识点一键回顾1. 【唠唠基础】list 是个啥和 vector 差在哪对于刚学 C 的同学来说先不用死记 “双向循环链表” 这种专业术语咱们先打个比方vector就像你手里的一排连续座位每个座位紧挨着想找第 5 个座位直接走过去就行随机访问但如果要在中间加个座位就得把后面的人全挪开插入效率低list就像一串手拉手的小朋友每个小朋友都记着前面和后面是谁想在中间加个小朋友只需要让前后的小朋友换个牵手对象就行插入效率高但想找第 5 个小朋友得从第一个开始数不支持随机访问。1.1 list 的官方定义简化版list 是 STL 里的序列式容器底层是「带头结点的双向循环链表」核心特点✅ 优点任意位置插入 / 删除元素超快只改指针不用搬移数据插入元素不会让迭代器失效❌ 缺点不能直接访问第 n 个元素比如list[5]会报错每个节点要存额外的指针占内存1.2 新手必懂的基础对比先记结论在 C 标准库中std::list 和 std::vector 对于插入操作时的迭代器失效行为不同根源在于它们的底层存储结构vector内部使用连续内存类似动态数组。插入元素时若容量不足则重新分配整块内存并将所有元素移动/拷贝到新空间此时所有迭代器、引用、指针都会失效即使容量充足插入点之后的所有元素也会向后移动导致指向插入点之后元素的迭代器失效。list内部使用双向链表。插入新元素只需创建新节点并调整相邻节点的前后指针原有节点的内存地址不变因此所有指向已存在元素的迭代器、引用、指针均保持有效仅指向被插入元素自身的迭代器是新产生的但不会影响已有的。2. 【核心技能】list 的 “常用招式”构造 / 迭代器 / 增删改查新手学 list先掌握 “最常用的接口” 就行不用记所有函数以下是高频使用的核心操作。2.1 第一步创建 list构造函数就像买新本子先选 “空本子”“有 n 页的本子” 还是 “抄别人的本子”list 有 4 种常用创建方式#includeiostream#includelist// 新手必记用list必须加这个头文件usingnamespacestd;intmain(){// 招式1创建空list最常用listintl1;// 招式2创建有5个元素每个元素都是10的listlistintl2(5,10);// 招式3拷贝别人的list复制l2listintl3(l2);// 招式4用数组初始化list新手也常用intarr[]{1,2,3,4,5};listintl4(arr,arr5);// 打印l4看看效果新手小技巧用迭代器遍历for(autoitl4.begin();it!l4.end();it){cout*it ;// 输出1 2 3 4 5}return0;}2.2 第二步遍历 list迭代器的用法新手容易懵 “迭代器到底是个啥”—— 你可以把它理解成 “指向 list 节点的小手”能帮你一个个摸遍 list 里的元素。list 支持两种迭代器新手先掌握正向迭代器就行intmain(){listintl{10,20,30,40,50};// 正向迭代器从第一个元素走到最后一个cout正向遍历;for(listint::iterator itl.begin();it!l.end();it){cout*it ;// 输出10 20 30 40 50}// 反向迭代器新手了解即可从最后一个走到第一个cout\n反向遍历;for(listint::reverse_iterator itl.rbegin();it!l.rend();it){cout*it ;// 输出50 40 30 20 10}return0;} 小提醒begin()是 “第一个元素的小手”end()是 “最后一个元素的下一个位置”不是最后一个元素反向迭代器的其实是往 “前” 走和正向相反不用死记用的时候试一次就懂了。2.3 第三步查容量、取元素高频操作list 的容量接口很简单只有 2 个元素访问也只有 2 个因为不能随机访问intmain(){listintl{1,2,3};// 1. 查容量empty是否为空、size元素个数if(l.empty()){coutlist是空的;}else{coutlist有l.size()个元素\n;// 输出3}// 2. 取元素front第一个、back最后一个cout第一个元素l.front()endl;// 输出1cout最后一个元素l.back()endl;// 输出3// 新手小技巧front/back返回的是引用能直接修改元素l.front()100;cout修改后第一个元素l.front()endl;// 输出100return0;}2.4 第四步增删改查list 的核心优势这是 list 最牛的地方 —— 任意位置增删都超快新手先掌握这些高频接口intmain(){listintl{1,2,3};// 1. 首尾增删最简单l.push_front(0);// 头部加0 → {0,1,2,3}l.push_back(4);// 尾部加4 → {0,1,2,3,4}l.pop_front();// 删头部 → {1,2,3,4}l.pop_back();// 删尾部 → {1,2,3}// 2. 任意位置插入新手重点// 先找到要插入的位置比如第二个元素autoitl.begin();it;// 从第一个元素走到第二个元素的位置l.insert(it,99);// 在第二个位置插99 → {1,99,2,3}// 3. 任意位置删除itl.begin();it;// 指向99的位置l.erase(it);// 删除99 → {1,2,3}// 4. 清空list// l.clear(); // 清空后list为空size0// 遍历看看最终结果for(autonum:l){// 新手简化写法范围for循环coutnum ;// 输出1 2 3}return0;} 小提醒范围 for 循环for (auto num : l)是 C11 的特性底层还是迭代器新手用这个遍历更简单插入 / 删除时先找迭代器位置再调用接口别直接写数字比如l.insert(2, 99)会报错因为 list 不支持随机访问。3. 【踩坑预警】迭代器失效新手最容易栽的坑这是新手学 list 最容易出错的地方先搞懂 “迭代器失效” 的本质迭代器指向的节点被删了这个 “小手” 就抓空了再用就会崩溃。intmain(){listintl{1,2,3,4};autoitl.begin();while(it!l.end()){l.erase(it);// 删完it指向的节点it就失效了it;// 报错失效的迭代器不能}return0;}3.2 正确写法必记有两种写法推荐第一种简单好记// 写法1erase(it) → 先把it传给erase再让it自增此时it还没失效intmain(){listintl{1,2,3,4};autoitl.begin();while(it!l.end()){l.erase(it);// 安全}coutl.size();// 输出0return0;}// 写法2it l.erase(it) → erase返回下一个有效迭代器intmain(){listintl{1,2,3,4};autoitl.begin();while(it!l.end()){itl.erase(it);// 接收返回值it指向新的有效位置}return0;}3.3 必记的迭代器失效规则4. 【动手实操】新手也能看懂的 list 模拟实现学完用法新手可以简单了解 list 的底层实现不用全写看懂核心逻辑就行能帮你更好理解为啥 list 这么用。4.1 第一步定义节点结构小朋友的 “牵手信息”每个节点要存 “自己的数据”“前面的人”“后面的人”// 模板类支持存任意类型int/string等templateclassTstructListNode{// 节点构造函数新手T()是默认值比如int就是0ListNode(constTvalT()):_val(val),_prev(nullptr),_next(nullptr){}T _val;// 自己的数据ListNode*_prev;// 前面的节点ListNode*_next;// 后面的节点};4.2 第二步封装迭代器新手的 “小手”因为 list 的节点不是连续内存不能直接用指针所以要封装迭代器重载/–/*这些操作templateclassT,classRef,classPtrstructListIterator{typedefListNodeTNode;Node*_node;// 指向节点的指针// 构造给迭代器绑定一个节点ListIterator(Node*node):_node(node){}// 解引用拿到节点里的数据新手Ref是引用能修改Refoperator*(){return_node-_val;}// 迭代器往后走ListIteratoroperator(){_node_node-_next;// 指向后面的节点return*this;}// 迭代器往前⾛--ListIteratoroperator--(){_node_node-_prev;// 指向前面的节点return*this;}// 判断两个迭代器是否相等booloperator!(constListIteratorit){return_node!it._node;}};4.3 第三步list 主体类管理整个链表核心是 “头结点”不存数据只用来统一操作封装构造、迭代器、增删等接口templateclassTclassList{typedefListNodeTNode;public:// 迭代器类型定义新手简化写法typedefListIteratorT,T,T*iterator;// 构造空list创建头结点自己指向自己双向循环List(){_headnewNode();_head-_prev_head;_head-_next_head;}// 迭代器接口返回头结点后面的第一个节点iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}// 尾是头结点// 尾部插入新手简化版voidpush_back(constTval){Node*tail_head-_prev;// 找到最后一个节点Node*new_nodenewNode(val);// 新建节点// 改指针尾节点→新节点→头结点tail-_nextnew_node;new_node-_prevtail;new_node-_next_head;_head-_prevnew_node;}private:Node*_head;// 头结点};4.4 新手测试模拟实现的 listintmain(){Listintl;l.push_back(1);l.push_back(2);l.push_back(3);// 遍历和STL的list用法一样for(autoitl.begin();it!l.end();it){cout*it ;// 输出1 2 3}return0;} 小总结模拟实现不用写全只要知道 “list 是节点拼起来的迭代器是封装的指针”就能理解为啥 list 不能随机访问、增删快。5. 【终极对比】list vs vector啥时候用谁新手最纠结 “该用 list 还是 vector”记住这几个场景就行不用死记原理// 场景1查成绩要随机访问→ 用vectorvectorintscores{90,85,95,88};cout第3个同学的成绩scores[2]endl;// 直接访问// 场景2排队买票频繁有人插队/离开→ 用listliststringqueue;queue.push_back(小明);queue.push_back(小红);autoitqueue.begin();queue.insert(it,小刚);// 小刚插队到第一个6. 【复习小结】核心知识点一键回顾总结1.list 底层是双向循环链表核心优势是任意位置 O (1) 增删核心短板是不支持随机访问2.迭代器失效是新手最大坑list 删除后只有被删节点的迭代器失效推荐用l.erase(it)3.选容器的核心原则查得多用 vector增删多用 list4.模拟实现不用全写记住“节点存数据 前后指针迭代器封装指针” 就行5.新手用 list 的高频接口push_back/push_front/insert/erase/begin/end。
C++10(list)
作为 C 初学者在接触 STL 容器时最容易混淆的就是vector和list—— 明明都是存数据的容器为啥用法和场景差这么多这篇文章就像你的 “list 专属学习笔记”用新手能看懂的语言把 list 的底层逻辑、核心用法、避技巧讲透。 目录新手友好版1.【唠唠基础】list 是个啥和 vector 差在哪2.【核心技能】list 的 “常用招式”构造 / 迭代器 / 增删改查3.【踩坑预警】迭代器失效新手最容易栽的坑4.【动手实操】新手也能看懂的 list 模拟实现5.【终极对比】list vs vector啥时候用谁6.【复习小结】核心知识点一键回顾1. 【唠唠基础】list 是个啥和 vector 差在哪对于刚学 C 的同学来说先不用死记 “双向循环链表” 这种专业术语咱们先打个比方vector就像你手里的一排连续座位每个座位紧挨着想找第 5 个座位直接走过去就行随机访问但如果要在中间加个座位就得把后面的人全挪开插入效率低list就像一串手拉手的小朋友每个小朋友都记着前面和后面是谁想在中间加个小朋友只需要让前后的小朋友换个牵手对象就行插入效率高但想找第 5 个小朋友得从第一个开始数不支持随机访问。1.1 list 的官方定义简化版list 是 STL 里的序列式容器底层是「带头结点的双向循环链表」核心特点✅ 优点任意位置插入 / 删除元素超快只改指针不用搬移数据插入元素不会让迭代器失效❌ 缺点不能直接访问第 n 个元素比如list[5]会报错每个节点要存额外的指针占内存1.2 新手必懂的基础对比先记结论在 C 标准库中std::list 和 std::vector 对于插入操作时的迭代器失效行为不同根源在于它们的底层存储结构vector内部使用连续内存类似动态数组。插入元素时若容量不足则重新分配整块内存并将所有元素移动/拷贝到新空间此时所有迭代器、引用、指针都会失效即使容量充足插入点之后的所有元素也会向后移动导致指向插入点之后元素的迭代器失效。list内部使用双向链表。插入新元素只需创建新节点并调整相邻节点的前后指针原有节点的内存地址不变因此所有指向已存在元素的迭代器、引用、指针均保持有效仅指向被插入元素自身的迭代器是新产生的但不会影响已有的。2. 【核心技能】list 的 “常用招式”构造 / 迭代器 / 增删改查新手学 list先掌握 “最常用的接口” 就行不用记所有函数以下是高频使用的核心操作。2.1 第一步创建 list构造函数就像买新本子先选 “空本子”“有 n 页的本子” 还是 “抄别人的本子”list 有 4 种常用创建方式#includeiostream#includelist// 新手必记用list必须加这个头文件usingnamespacestd;intmain(){// 招式1创建空list最常用listintl1;// 招式2创建有5个元素每个元素都是10的listlistintl2(5,10);// 招式3拷贝别人的list复制l2listintl3(l2);// 招式4用数组初始化list新手也常用intarr[]{1,2,3,4,5};listintl4(arr,arr5);// 打印l4看看效果新手小技巧用迭代器遍历for(autoitl4.begin();it!l4.end();it){cout*it ;// 输出1 2 3 4 5}return0;}2.2 第二步遍历 list迭代器的用法新手容易懵 “迭代器到底是个啥”—— 你可以把它理解成 “指向 list 节点的小手”能帮你一个个摸遍 list 里的元素。list 支持两种迭代器新手先掌握正向迭代器就行intmain(){listintl{10,20,30,40,50};// 正向迭代器从第一个元素走到最后一个cout正向遍历;for(listint::iterator itl.begin();it!l.end();it){cout*it ;// 输出10 20 30 40 50}// 反向迭代器新手了解即可从最后一个走到第一个cout\n反向遍历;for(listint::reverse_iterator itl.rbegin();it!l.rend();it){cout*it ;// 输出50 40 30 20 10}return0;} 小提醒begin()是 “第一个元素的小手”end()是 “最后一个元素的下一个位置”不是最后一个元素反向迭代器的其实是往 “前” 走和正向相反不用死记用的时候试一次就懂了。2.3 第三步查容量、取元素高频操作list 的容量接口很简单只有 2 个元素访问也只有 2 个因为不能随机访问intmain(){listintl{1,2,3};// 1. 查容量empty是否为空、size元素个数if(l.empty()){coutlist是空的;}else{coutlist有l.size()个元素\n;// 输出3}// 2. 取元素front第一个、back最后一个cout第一个元素l.front()endl;// 输出1cout最后一个元素l.back()endl;// 输出3// 新手小技巧front/back返回的是引用能直接修改元素l.front()100;cout修改后第一个元素l.front()endl;// 输出100return0;}2.4 第四步增删改查list 的核心优势这是 list 最牛的地方 —— 任意位置增删都超快新手先掌握这些高频接口intmain(){listintl{1,2,3};// 1. 首尾增删最简单l.push_front(0);// 头部加0 → {0,1,2,3}l.push_back(4);// 尾部加4 → {0,1,2,3,4}l.pop_front();// 删头部 → {1,2,3,4}l.pop_back();// 删尾部 → {1,2,3}// 2. 任意位置插入新手重点// 先找到要插入的位置比如第二个元素autoitl.begin();it;// 从第一个元素走到第二个元素的位置l.insert(it,99);// 在第二个位置插99 → {1,99,2,3}// 3. 任意位置删除itl.begin();it;// 指向99的位置l.erase(it);// 删除99 → {1,2,3}// 4. 清空list// l.clear(); // 清空后list为空size0// 遍历看看最终结果for(autonum:l){// 新手简化写法范围for循环coutnum ;// 输出1 2 3}return0;} 小提醒范围 for 循环for (auto num : l)是 C11 的特性底层还是迭代器新手用这个遍历更简单插入 / 删除时先找迭代器位置再调用接口别直接写数字比如l.insert(2, 99)会报错因为 list 不支持随机访问。3. 【踩坑预警】迭代器失效新手最容易栽的坑这是新手学 list 最容易出错的地方先搞懂 “迭代器失效” 的本质迭代器指向的节点被删了这个 “小手” 就抓空了再用就会崩溃。intmain(){listintl{1,2,3,4};autoitl.begin();while(it!l.end()){l.erase(it);// 删完it指向的节点it就失效了it;// 报错失效的迭代器不能}return0;}3.2 正确写法必记有两种写法推荐第一种简单好记// 写法1erase(it) → 先把it传给erase再让it自增此时it还没失效intmain(){listintl{1,2,3,4};autoitl.begin();while(it!l.end()){l.erase(it);// 安全}coutl.size();// 输出0return0;}// 写法2it l.erase(it) → erase返回下一个有效迭代器intmain(){listintl{1,2,3,4};autoitl.begin();while(it!l.end()){itl.erase(it);// 接收返回值it指向新的有效位置}return0;}3.3 必记的迭代器失效规则4. 【动手实操】新手也能看懂的 list 模拟实现学完用法新手可以简单了解 list 的底层实现不用全写看懂核心逻辑就行能帮你更好理解为啥 list 这么用。4.1 第一步定义节点结构小朋友的 “牵手信息”每个节点要存 “自己的数据”“前面的人”“后面的人”// 模板类支持存任意类型int/string等templateclassTstructListNode{// 节点构造函数新手T()是默认值比如int就是0ListNode(constTvalT()):_val(val),_prev(nullptr),_next(nullptr){}T _val;// 自己的数据ListNode*_prev;// 前面的节点ListNode*_next;// 后面的节点};4.2 第二步封装迭代器新手的 “小手”因为 list 的节点不是连续内存不能直接用指针所以要封装迭代器重载/–/*这些操作templateclassT,classRef,classPtrstructListIterator{typedefListNodeTNode;Node*_node;// 指向节点的指针// 构造给迭代器绑定一个节点ListIterator(Node*node):_node(node){}// 解引用拿到节点里的数据新手Ref是引用能修改Refoperator*(){return_node-_val;}// 迭代器往后走ListIteratoroperator(){_node_node-_next;// 指向后面的节点return*this;}// 迭代器往前⾛--ListIteratoroperator--(){_node_node-_prev;// 指向前面的节点return*this;}// 判断两个迭代器是否相等booloperator!(constListIteratorit){return_node!it._node;}};4.3 第三步list 主体类管理整个链表核心是 “头结点”不存数据只用来统一操作封装构造、迭代器、增删等接口templateclassTclassList{typedefListNodeTNode;public:// 迭代器类型定义新手简化写法typedefListIteratorT,T,T*iterator;// 构造空list创建头结点自己指向自己双向循环List(){_headnewNode();_head-_prev_head;_head-_next_head;}// 迭代器接口返回头结点后面的第一个节点iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}// 尾是头结点// 尾部插入新手简化版voidpush_back(constTval){Node*tail_head-_prev;// 找到最后一个节点Node*new_nodenewNode(val);// 新建节点// 改指针尾节点→新节点→头结点tail-_nextnew_node;new_node-_prevtail;new_node-_next_head;_head-_prevnew_node;}private:Node*_head;// 头结点};4.4 新手测试模拟实现的 listintmain(){Listintl;l.push_back(1);l.push_back(2);l.push_back(3);// 遍历和STL的list用法一样for(autoitl.begin();it!l.end();it){cout*it ;// 输出1 2 3}return0;} 小总结模拟实现不用写全只要知道 “list 是节点拼起来的迭代器是封装的指针”就能理解为啥 list 不能随机访问、增删快。5. 【终极对比】list vs vector啥时候用谁新手最纠结 “该用 list 还是 vector”记住这几个场景就行不用死记原理// 场景1查成绩要随机访问→ 用vectorvectorintscores{90,85,95,88};cout第3个同学的成绩scores[2]endl;// 直接访问// 场景2排队买票频繁有人插队/离开→ 用listliststringqueue;queue.push_back(小明);queue.push_back(小红);autoitqueue.begin();queue.insert(it,小刚);// 小刚插队到第一个6. 【复习小结】核心知识点一键回顾总结1.list 底层是双向循环链表核心优势是任意位置 O (1) 增删核心短板是不支持随机访问2.迭代器失效是新手最大坑list 删除后只有被删节点的迭代器失效推荐用l.erase(it)3.选容器的核心原则查得多用 vector增删多用 list4.模拟实现不用全写记住“节点存数据 前后指针迭代器封装指针” 就行5.新手用 list 的高频接口push_back/push_front/insert/erase/begin/end。
