1. list 的介绍list是 STL 中非常重要的序列式容器之一它可以在常数时间 O(1)内在任意位置进行插入和删除元素。list 的底层结构是带头结点的双向循环链表每个节点包含一个数据域data、一个前驱指针prev和一个后继指针next头结点哨兵节点不保存有效数据它的next指向第一个有效节点prev指向最后一个有效节点空表时哨兵节点的next和prev都指向自己。由于底层是链表list 支持高效的任意位置插入/删除但不支持随机访问访问第 i 个元素的复杂度是 O(N)。2. list 的使用list 接口很多学习时应该先掌握“如何正确使用”再去研究背后的实现原理。下面是 list 中常见的重要接口。2.1 list 的构造接口说明list (size_type n, const value_type val value_type())构造包含 n 个值为 val 的元素的 listlist()构造空的 listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造 list使用示例#includeiostream#includelistusingnamespacestd;intmain(){listintl1;// 空 listlistintl2(4,100);// {100, 100, 100, 100}listintl3(l2);// 拷贝构造listintl4(l2.begin(),l2.end());// 迭代器区间构造listintl5{1,2,3,4,5};// C11 initializer_list 构造return0;}2.2 list 的迭代器此处可以暂时把迭代器理解成一个指针该指针指向 list 中的某个节点。接口说明begin end返回第一个元素的迭代器 最后一个元素下一个位置的迭代器rbegin rend反向迭代器rbegin即end位置rend即begin位置注意begin与end是正向迭代器对迭代器执行迭代器向后移动rbeginend与rendbegin是反向迭代器对迭代器执行迭代器向前移动。使用示例listintl{1,2,3,4,5};// 正向遍历for(autoitl.begin();it!l.end();it)cout*it ;// 反向遍历for(autoitl.rbegin();it!l.rend();it)cout*it ;// 范围 for本质也是 begin()/end()for(autoe:l)coute ;2.3 list capacity接口说明empty检测 list 是否为空是返回 true否则返回 falsesize返回 list 中有效节点的个数2.4 list element access接口说明front返回 list 的第一个节点中值的引用back返回 list 的最后一个节点中值的引用2.5 list modifiers接口说明push_front在 list 首元素前插入值为 val 的元素pop_front删除 list 中第一个元素push_back在 list 尾部插入值为 val 的元素pop_back删除 list 中最后一个元素insert在 list 的 position 位置插入值为 val 的元素erase删除 list 的 position 位置的元素swap交换两个 list 中的元素clear清空 list 中的有效元素2.6 list 的迭代器失效因为 list 的底层结构是带头结点的双向循环链表所以插入操作不会导致 list 的迭代器失效删除操作只会使指向被删除节点的那个迭代器失效其他迭代器不受影响。经典错误示例删除节点后还继续使用已经失效的迭代器。voidTestListIterator1(){intarray[]{1,2,3,4,5,6,7,8,9,0};listintl(array,arraysizeof(array)/sizeof(array[0]));autoitl.begin();while(it!l.end()){// erase() 执行后it 所指向的节点已被删除因此 it 已经失效l.erase(it);it;// 对失效迭代器 未定义行为}}改正方式利用后置先保存旧迭代器、再前进、最后删除旧节点。voidTestListIterator(){intarray[]{1,2,3,4,5,6,7,8,9,0};listintl(array,arraysizeof(array)/sizeof(array[0]));autoitl.begin();while(it!l.end()){l.erase(it);// 等价于 it l.erase(it);}}3. list 的模拟实现要模拟实现 list必须熟悉它的底层结构以及每个接口的含义。3.1 整体结构哨兵节点 双向循环链表下面是本次审查的手写实现的核心结构略有删减行号对应原始List.h#pragmaonce#includeiostream#includeassert.husingnamespacestd;namespacetx_list{templatetypenameTclasslist_Node{friendclasslistT;public:list_Node(constTvalueT()):data(value),next(nullptr),prev(nullptr){}private:T data;// 数据域list_NodeT*next;// 后继指针list_NodeT*prev;// 前驱指针};templatetypenameTclasslist{typedeflist_NodeTNode;public:list(){empty_init();}// 拷贝构造list(constlistTl){empty_init();for(autoe:l)push_back(e);}// initializer_list 构造list(initializer_listTil){empty_init();for(autoe:il)push_back(e);}// 拷贝赋值copy-and-swap 惯用法listToperator(listTlt){swap(lt);return*this;}~list(){clear();delete_head;_headnullptr;}voidempty_init(){_headnewNode(T());// 创建哨兵节点_head-next_head;// 哨兵的 next 指向自己_head-prev_head;// 哨兵的 prev 指向自己_size0;}private:Node*_head;// 哨兵节点size_t _size;};}设计要点哨兵节点头结点不存有效数据让所有插入/删除操作都不需要特判“空表/首尾”情况循环链表_head-next是第一个节点_head-prev是最后一个节点copy-and-swap 赋值operator(listT lt)按值传参先拷贝一份再交换内部指针天然保证异常安全和自赋值安全。3.2 迭代器设计list 的迭代器不是原生指针vector底层是连续空间迭代器可以用原生指针T*但list的节点在内存中不连续/--必须“跳节点”所以list 的迭代器是对节点指针的封装。一个非常巧妙的做法是用Ref和Ptr两个模板参数让同一个模板同时生成iterator和const_iteratortemplateclassT,classRef,classPtrstructlist_iterator{typedeflist_NodeTNode;typedeflist_iteratorT,Ref,PtrSelf;Node*_node;list_iterator(Node*node):_node(node){}Refoperator*(){return_node-_data;}Ptroperator-(){return_node-_data;}Selfoperator(){_node_node-_next;return*this;}Selfoperator--(){_node_node-_prev;return*this;}Selfoperator(int){Selftmp(*this);_node_node-_next;returntmp;}booloperator!(constSelfs)const{return_node!s._node;}booloperator(constSelfs)const{return_nodes._node;}};然后在list里 typedeftypedeflist_iteratorT,T,T*iterator;// 普通迭代器typedeflist_iteratorT,constT,constT*const_iterator;// const 迭代器3.3 关键接口实现insert在 pos 之前插入voidinsert(iterator pos,constTvalue){Node*newNodenewNode(value);Node*curpos._node;Node*prevcur-prev;// 双向链表四步链接prev - newNode - curprev-nextnewNode;newNode-prevprev;newNode-nextcur;cur-prevnewNode;_size;}erase删除 pos 指向的节点voiderase(iterator pos){assert(pos!end());// 不能删除哨兵节点Node*prevpos._node-prev;Node*nextpos._node-next;prev-nextnext;next-prevprev;deletepos._node;_size--;}复用 insert/erase 实现 push/popvoidpush_back(constTvalue){insert(end(),value);}// 在哨兵前插入即尾插voidpush_front(constTx){insert(begin(),x);}// 在首节点前插入voidpop_back(){erase(--end());}// end() 前一个即尾节点4. list 与 vector 的对比vector 与 list 都是 STL 中非常重要的序列式容器由于两者底层结构不同导致其特性及应用场景也不同。维度vectorlist底层结构动态顺序表一段连续空间带头结点的双向循环链表随机访问支持随机访问访问某个元素 O(1)不支持随机访问访问某个元素 O(N)插入和删除任意位置插入/删除效率低需搬移元素 O(N)插入时可能增容开新空间、拷贝元素、释放旧空间任意位置插入/删除效率高不需搬移元素O(1)空间利用率底层连续空间不易造成内存碎片空间利用率高缓存利用率高节点动态开辟小节点易造成内存碎片空间利用率低缓存利用率低迭代器原生指针对原生指针节点指针进行封装迭代器失效插入可能因扩容使所有迭代器失效删除时当前迭代器需重新赋值插入不导致迭代器失效删除只使当前迭代器失效其他不受影响使用场景需要高效存储、支持随机访问、不关心插入删除效率大量插入和删除操作、不关心随机访问5. 总结list 的底层结构是带头结点的双向循环链表因此任意位置插入/删除是 O(1)但不支持随机访问O(N)。list 的迭代器是对节点指针的封装/--实际是沿next/prev指针移动用Ref/Ptr模板参数可以让一套代码同时生成iterator和const_iterator。反向迭代器可以包装正向迭代器实现反向 正向--。list 的迭代器失效规则插入不失效删除只使“被删节点”对应的迭代器失效。删除遍历时要写l.erase(it);。手写 list 的三个高频坑本次审查发现的阻塞级问题erase返回void却写了it erase(it)无法编译 ——erase应返回后继迭代器迭代器访问节点私有成员但忘了声明友元后置--误写为返回Self返回局部对象引用悬垂引用。vector vs list随机访问、连续存储选vector频繁任意位置插入删除选list。参考资料cplusplus.com - listcppreference.com - std::list
1. list 的介绍list是 STL 中非常重要的序列式容器之一它可以在常数时间 O(1)内在任意位置进行插入和删除元素。list 的底层结构是带头结点的双向循环链表每个节点包含一个数据域data、一个前驱指针prev和一个后继指针next头结点哨兵节点不保存有效数据它的next指向第一个有效节点prev指向最后一个有效节点空表时哨兵节点的next和prev都指向自己。由于底层是链表list 支持高效的任意位置插入/删除但不支持随机访问访问第 i 个元素的复杂度是 O(N)。2. list 的使用list 接口很多学习时应该先掌握“如何正确使用”再去研究背后的实现原理。下面是 list 中常见的重要接口。2.1 list 的构造接口说明list (size_type n, const value_type val value_type())构造包含 n 个值为 val 的元素的 listlist()构造空的 listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造 list使用示例#includeiostream#includelistusingnamespacestd;intmain(){listintl1;// 空 listlistintl2(4,100);// {100, 100, 100, 100}listintl3(l2);// 拷贝构造listintl4(l2.begin(),l2.end());// 迭代器区间构造listintl5{1,2,3,4,5};// C11 initializer_list 构造return0;}2.2 list 的迭代器此处可以暂时把迭代器理解成一个指针该指针指向 list 中的某个节点。接口说明begin end返回第一个元素的迭代器 最后一个元素下一个位置的迭代器rbegin rend反向迭代器rbegin即end位置rend即begin位置注意begin与end是正向迭代器对迭代器执行迭代器向后移动rbeginend与rendbegin是反向迭代器对迭代器执行迭代器向前移动。使用示例listintl{1,2,3,4,5};// 正向遍历for(autoitl.begin();it!l.end();it)cout*it ;// 反向遍历for(autoitl.rbegin();it!l.rend();it)cout*it ;// 范围 for本质也是 begin()/end()for(autoe:l)coute ;2.3 list capacity接口说明empty检测 list 是否为空是返回 true否则返回 falsesize返回 list 中有效节点的个数2.4 list element access接口说明front返回 list 的第一个节点中值的引用back返回 list 的最后一个节点中值的引用2.5 list modifiers接口说明push_front在 list 首元素前插入值为 val 的元素pop_front删除 list 中第一个元素push_back在 list 尾部插入值为 val 的元素pop_back删除 list 中最后一个元素insert在 list 的 position 位置插入值为 val 的元素erase删除 list 的 position 位置的元素swap交换两个 list 中的元素clear清空 list 中的有效元素2.6 list 的迭代器失效因为 list 的底层结构是带头结点的双向循环链表所以插入操作不会导致 list 的迭代器失效删除操作只会使指向被删除节点的那个迭代器失效其他迭代器不受影响。经典错误示例删除节点后还继续使用已经失效的迭代器。voidTestListIterator1(){intarray[]{1,2,3,4,5,6,7,8,9,0};listintl(array,arraysizeof(array)/sizeof(array[0]));autoitl.begin();while(it!l.end()){// erase() 执行后it 所指向的节点已被删除因此 it 已经失效l.erase(it);it;// 对失效迭代器 未定义行为}}改正方式利用后置先保存旧迭代器、再前进、最后删除旧节点。voidTestListIterator(){intarray[]{1,2,3,4,5,6,7,8,9,0};listintl(array,arraysizeof(array)/sizeof(array[0]));autoitl.begin();while(it!l.end()){l.erase(it);// 等价于 it l.erase(it);}}3. list 的模拟实现要模拟实现 list必须熟悉它的底层结构以及每个接口的含义。3.1 整体结构哨兵节点 双向循环链表下面是本次审查的手写实现的核心结构略有删减行号对应原始List.h#pragmaonce#includeiostream#includeassert.husingnamespacestd;namespacetx_list{templatetypenameTclasslist_Node{friendclasslistT;public:list_Node(constTvalueT()):data(value),next(nullptr),prev(nullptr){}private:T data;// 数据域list_NodeT*next;// 后继指针list_NodeT*prev;// 前驱指针};templatetypenameTclasslist{typedeflist_NodeTNode;public:list(){empty_init();}// 拷贝构造list(constlistTl){empty_init();for(autoe:l)push_back(e);}// initializer_list 构造list(initializer_listTil){empty_init();for(autoe:il)push_back(e);}// 拷贝赋值copy-and-swap 惯用法listToperator(listTlt){swap(lt);return*this;}~list(){clear();delete_head;_headnullptr;}voidempty_init(){_headnewNode(T());// 创建哨兵节点_head-next_head;// 哨兵的 next 指向自己_head-prev_head;// 哨兵的 prev 指向自己_size0;}private:Node*_head;// 哨兵节点size_t _size;};}设计要点哨兵节点头结点不存有效数据让所有插入/删除操作都不需要特判“空表/首尾”情况循环链表_head-next是第一个节点_head-prev是最后一个节点copy-and-swap 赋值operator(listT lt)按值传参先拷贝一份再交换内部指针天然保证异常安全和自赋值安全。3.2 迭代器设计list 的迭代器不是原生指针vector底层是连续空间迭代器可以用原生指针T*但list的节点在内存中不连续/--必须“跳节点”所以list 的迭代器是对节点指针的封装。一个非常巧妙的做法是用Ref和Ptr两个模板参数让同一个模板同时生成iterator和const_iteratortemplateclassT,classRef,classPtrstructlist_iterator{typedeflist_NodeTNode;typedeflist_iteratorT,Ref,PtrSelf;Node*_node;list_iterator(Node*node):_node(node){}Refoperator*(){return_node-_data;}Ptroperator-(){return_node-_data;}Selfoperator(){_node_node-_next;return*this;}Selfoperator--(){_node_node-_prev;return*this;}Selfoperator(int){Selftmp(*this);_node_node-_next;returntmp;}booloperator!(constSelfs)const{return_node!s._node;}booloperator(constSelfs)const{return_nodes._node;}};然后在list里 typedeftypedeflist_iteratorT,T,T*iterator;// 普通迭代器typedeflist_iteratorT,constT,constT*const_iterator;// const 迭代器3.3 关键接口实现insert在 pos 之前插入voidinsert(iterator pos,constTvalue){Node*newNodenewNode(value);Node*curpos._node;Node*prevcur-prev;// 双向链表四步链接prev - newNode - curprev-nextnewNode;newNode-prevprev;newNode-nextcur;cur-prevnewNode;_size;}erase删除 pos 指向的节点voiderase(iterator pos){assert(pos!end());// 不能删除哨兵节点Node*prevpos._node-prev;Node*nextpos._node-next;prev-nextnext;next-prevprev;deletepos._node;_size--;}复用 insert/erase 实现 push/popvoidpush_back(constTvalue){insert(end(),value);}// 在哨兵前插入即尾插voidpush_front(constTx){insert(begin(),x);}// 在首节点前插入voidpop_back(){erase(--end());}// end() 前一个即尾节点4. list 与 vector 的对比vector 与 list 都是 STL 中非常重要的序列式容器由于两者底层结构不同导致其特性及应用场景也不同。维度vectorlist底层结构动态顺序表一段连续空间带头结点的双向循环链表随机访问支持随机访问访问某个元素 O(1)不支持随机访问访问某个元素 O(N)插入和删除任意位置插入/删除效率低需搬移元素 O(N)插入时可能增容开新空间、拷贝元素、释放旧空间任意位置插入/删除效率高不需搬移元素O(1)空间利用率底层连续空间不易造成内存碎片空间利用率高缓存利用率高节点动态开辟小节点易造成内存碎片空间利用率低缓存利用率低迭代器原生指针对原生指针节点指针进行封装迭代器失效插入可能因扩容使所有迭代器失效删除时当前迭代器需重新赋值插入不导致迭代器失效删除只使当前迭代器失效其他不受影响使用场景需要高效存储、支持随机访问、不关心插入删除效率大量插入和删除操作、不关心随机访问5. 总结list 的底层结构是带头结点的双向循环链表因此任意位置插入/删除是 O(1)但不支持随机访问O(N)。list 的迭代器是对节点指针的封装/--实际是沿next/prev指针移动用Ref/Ptr模板参数可以让一套代码同时生成iterator和const_iterator。反向迭代器可以包装正向迭代器实现反向 正向--。list 的迭代器失效规则插入不失效删除只使“被删节点”对应的迭代器失效。删除遍历时要写l.erase(it);。手写 list 的三个高频坑本次审查发现的阻塞级问题erase返回void却写了it erase(it)无法编译 ——erase应返回后继迭代器迭代器访问节点私有成员但忘了声明友元后置--误写为返回Self返回局部对象引用悬垂引用。vector vs list随机访问、连续存储选vector频繁任意位置插入删除选list。参考资料cplusplus.com - listcppreference.com - std::list
