C++ STL list 超详细解析：从接口使用到模拟实现

C STL list 超详细解析从接口使用到模拟实现本文全面讲解 C STL 中list容器包含基础介绍、常用接口、迭代器失效、模拟实现、与 vector 对比附可直接运行的完整代码适合学习与面试复习。一、list 基础介绍list是 C STL 中的序列式容器底层实现为带头结点的双向循环链表核心特点不支持随机访问不能用[]访问任意位置插入/删除效率极高 O(1)插入不会导致迭代器失效删除仅失效被删节点迭代器二、list 常用接口使用1. list 构造函数构造函数功能list()构造空 listlist(n, val)构造含 n 个 val 的 listlist(const list x)拷贝构造list(first, last)用迭代器区间构造代码示例#includeiostream#includelistusingnamespacestd;voidtest_construct(){// 空构造listintl1;// n个vallistintl2(5,10);// 拷贝构造listintl3(l2);// 迭代器区间构造intarr[]{1,2,3,4,5};listintl4(arr,arrsizeof(arr)/sizeof(arr[0]));}2. 迭代器iteratorlist迭代器是双向迭代器只支持/--不支持n/-n。接口功能begin()/end()正向迭代器rbegin()/rend()反向迭代器代码示例voidtest_iterator(){listintl{1,2,3,4,5};// 正向遍历cout正向;for(autoitl.begin();it!l.end();it){cout*it ;}coutendl;// 反向遍历cout反向;for(autoitl.rbegin();it!l.rend();it){cout*it ;}coutendl;}3. 容量与元素访问接口功能empty()是否为空size()元素个数front()首元素引用back()尾元素引用代码示例voidtest_capacity(){listintl{1,2,3};coutempty: boolalphal.empty()endl;coutsize: l.size()endl;coutfront: l.front()endl;coutback: l.back()endl;}4. 插入与删除核心接口功能push_back(val)尾插pop_back()尾删push_front(val)头插pop_front()头删insert(pos, val)在 pos 前插入erase(pos)删除 pos 位置swap(list)交换两个 listclear()清空代码示例voidtest_modify(){listintl;// 尾插l.push_back(1);l.push_back(2);// 头插l.push_front(0);// insertautoitl.begin();it;l.insert(it,10);// 在 0 后插入 10// eraseitl.begin();l.erase(it);// 遍历for(autox:l)coutx ;coutendl;l.clear();}三、list 迭代器失效问题高频面试核心结论插入不会导致任何迭代器失效删除只有被删除节点的迭代器失效其他不受影响错误写法voidTestListIterator1(){intarr[]{1,2,3,4,5};listintl(arr,arr5);autoitl.begin();while(it!l.end()){l.erase(it);// it 已失效it;// 非法访问}}正确写法voidTestListIterator(){intarr[]{1,2,3,4,5};listintl(arr,arr5);autoitl.begin();while(it!l.end()){// 后置先传值删除再自增l.erase(it);// 或 it l.erase(it);}}四、list 模拟实现精简完整版1. 节点结构templateclassTstructListNode{T _data;ListNode*_prev;ListNode*_next;ListNode(constTvalT()):_data(val),_prev(nullptr),_next(nullptr){}};2. 正向迭代器封装templateclassT,classRef,classPtrstructListIterator{typedefListNodeTNode;typedefListIteratorT,Ref,PtrSelf;Node*_node;ListIterator(Node*node):_node(node){}// 解引用Refoperator*(){return_node-_data;}Ptroperator-(){return_node-_data;}// Selfoperator(){_node_node-_next;return*this;}Selfoperator(int){Selftemp(*this);_node_node-_next;returntemp;}// --Selfoperator--(){_node_node-_prev;return*this;}Selfoperator--(int){Selftemp(*this);_node_node-_prev;returntemp;}booloperator!(constSelfs)const{return_node!s._node;}booloperator(constSelfs)const{return_nodes._node;}};3. 反向迭代器适配器templateclassIteratorclassReverseIterator{public:Iterator _it;typedefReverseIteratorIteratorSelf;ReverseIterator(Iterator it):_it(it){}autooperator*(){Iterator temp_it;--temp;return*temp;}Selfoperator(){--_it;return*this;}Selfoperator--(){_it;return*this;}booloperator!(constSelfs)const{return_it!s._it;}};4. list 主体实现templateclassTclasslist{typedefListNodeTNode;public:// 迭代器类型typedefListIteratorT,T,T*iterator;typedefListIteratorT,constT,constT*const_iterator;typedefReverseIteratoriteratorreverse_iterator;// 构造空表list(){_headnewNode;_head-_next_head;_head-_prev_head;}// 迭代器iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}reverse_iteratorrbegin(){returnreverse_iterator(end());}reverse_iteratorrend(){returnreverse_iterator(begin());}// 尾插voidpush_back(constTval){Node*newnodenewNode(val);Node*tail_head-_prev;tail-_nextnewnode;newnode-_prevtail;newnode-_next_head;_head-_prevnewnode;}// eraseiteratorerase(iterator pos){Node*curpos._node;Node*prevcur-_prev;Node*nextcur-_next;prev-_nextnext;next-_prevprev;deletecur;returniterator(next);}// 其他接口insert、clear、swap、拷贝构造、析构...private:Node*_head;};五、list 与 vector 核心对比面试必背对比项vectorlist底层结构连续动态数组双向循环链表随机访问支持 O(1)不支持 O(N)插入删除需挪动元素 O(N)不需挪动 O(1)空间利用率高、连续、缓存友好低、易产生碎片迭代器原生指针封装节点指针迭代器失效插入/删除易失效插入不失效删除仅当前失效适用场景频繁访问、少插入频繁插入/删除、不随机访问六、总结list是双向循环链表插入删除极快不支持随机访问。迭代器是双向迭代器删除时注意失效问题。模拟实现核心节点结构 迭代器封装。与vector互补根据场景选择。