前言这篇笔记是我的实践记录从节点、迭代器到容器接口一步步还原list的核心逻辑把 “用容器” 变成 “懂容器”。一、list的介绍list是 STL 中支持在任意位置高效常数时间插入、删除的双向迭代序列式容器底层基于带头双向链表实现 —— 每个元素存于独立节点通过指针连接前后元素它和forward_list类似但后者是单链表、仅支持前向迭代和array、vector、deque相比list的插入删除效率更优但缺点是不支持随机访问访问第 n 个元素需线性遍历且每个节点的指针会占用额外空间对存储小元素的大list影响较明显。二、list的常用接口及其使用2.1 构造函数构造函数 (constructor)接口说明list (size_type n, const value_type val value_type())构造的 list 中包含 n 个值为 val 的元素list()构造空的 listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用迭代器区间构造 list2.2 增删查改函数声明接口说明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 中的有效元素//尾插l1.push_back(0);l1.push_back(1);l1.push_back(2);for(autov:l1){coutv ;}coutendl;//头插l1.push_front(-1);for(autov:l1){coutv ;}coutendl;//头删l1.pop_front();for(autov:l1){coutv ;}coutendl;//在pos处插入//先来一个迭代器后面我们具体讲listint::iterator it1l1.begin();//it就可以在开始的下一个位置插入l1.insert(it1,999);for(autov:l1){coutv ;}coutendl;l1.erase(--it1);for(autov:l1){coutv ;}coutendl;for(autov:l2){coutv;}coutendl;l1.swap(l2);for(autov:l1){coutv ;}coutendl;for(autov:l2){coutv ;}coutendl;l1.clear();for(autov:l1){coutv ;}coutendl;swap接口为了避免因使用std::swap交换效率低下需要拷贝list重载了swap这个重载的底层是交换两个链表的指针。list没有重载find需要调用std::find。2.3list特殊接口除了上述 STL 容器基本都有的一般接口外list还提供一些独有的特殊操作接口如下函数声明接口说明splice将 list1 中的元素转移到 list2 中remove移除 list 中的指定元素unique链表去重merge合并两个链表sort链表排序reverse链表逆置2.3.1 splice 接口有两种使用方式从一个list剪切到另外一个list的一个位置前面coutl1:;for(autov:l1){coutv;}coutendl;coutl2:;for(autov:l2){coutv;}coutendl;l1.splice(l1.begin(),l2);coutl1:;for(autov:l1){coutv;}coutendl;coutl2:;for(autov:l2){coutv;}coutendl;从自身的某个位置开始剪切到自身的某个位置前面。// splice( 插入位置, 源链表, 源区间起点, 源区间终点 )lt.splice(pos,source,first,last);2.3.2 remove 接口通过元素的值来移除元素。for(autov:l2){coutv;}coutendl;l2.remove(6);for(autov:l2){coutv;}coutendl;2.3.3 unique 接口去重要求链表有序原因是底层是默认相同的数据被放在一起。for(autov:l2){coutv;}coutendl;l2.unique();for(autov:l2){coutv;}coutendl;2.3.4 merge 接口合并链表需要两个链表有序底层有点类似于归并排序的逻辑双指针遍历两个链表找小插入再返回拷贝。被合并的list会变空。listintl1;listintl2;l1.push_back(1);l1.push_back(3);l1.push_back(5);l1.push_back(7);l2.push_back(0);l2.push_back(2);l2.push_back(4);l2.push_back(6);l2.push_back(8);coutl1:;for(autov:l1){cout v;}coutendl;coutl2:;for(autov:l2){cout v;}coutendl;l1.merge(l2);coutl1:;for(autov:l1){cout v;}coutendl;coutl2:;for(autov:l2){cout v;}coutendl;2.3.5 sort 接口链表排序只能使用list提供的sort接口而不能使用 algorithm 提供的sort接口因为链表物理地址不连续迭代器为双向迭代器不支持 - 操作而算法库中的sort函数需要支持 - 的随机迭代器listintl1;listintl2;l1.push_back(1);l1.push_back(3);l1.push_back(5);l1.push_back(7);l1.push_back(0);l1.push_back(2);l1.push_back(4);l1.push_back(6);l1.push_back(8);coutl1:;for(autov:l1){cout v;}coutendl;l1.sort();coutl1:;for(autov:l1){cout v;}coutendl;2.3.6 reversecoutl1:;for(autov:l1){cout v;}coutendl;l1.reverse();coutl1:;for(autov:l1){cout v;}coutendl;2.3.7 总结1、链表排序只能使用list提供的sort接口而不能使用 algorithm 提供的sort接口因为链表物理地址不连续迭代器为双向迭代器不支持 - 操作而算法库中的sort函数需要支持 - 的随机迭代器2、链表去重之前必须保证链表有序否则去重不完全3、两个有序链表合并之后仍然保存有序最后虽然list提供了这些具有特殊功能的接口它们也确实有一定的作用但是实际上这些特殊接口使用频率非常低包括sort接口链表排序的效率太低。2.4list排序的性能分析虽然链表排序只能使用list提供的sort接口而不能使用 algorithm 提供的sort接口但是其使用频率仍然非常低这是由于链表排序的效率太低了我们可以通过对比两组测试数据来直观地感受链表排序的效率。测试一vector排序与list排序性能对比srand((size_t)time(0));constintN1000000;//100万个数据vectorintv;v.reserve(N);listintlt;for(inti0;iN;i){autoerand();v.push_back(e);lt.push_back(e);}//vector sortintbegin1clock();sort(v.begin(),v.end());intend1clock();//list sortintbegin2clock();lt.sort();intend2clock();printf(vector sort:%d\n,end1-begin1);printf(list sort:%d\n,end2-begin2);测试二list直接进行排序与将数据拷贝到vector中使用vector排序后再将数据拷回list中性能对比srand(time(0));constintN1000000;//100万个数据listintlt1;listintlt2;for(inti0;iN;i){autoerand();lt1.push_back(e);lt2.push_back(e);}//list sort -- lt1intbegin1clock();lt1.sort();intend1clock();// 将数据拷贝到vector中排序排完以后再拷贝回来 -- lt2intbegin2clock();vectorintv;v.reserve(N);for(autoe:lt2)//拷贝{v.push_back(e);}sort(v.begin(),v.end());//排序lt2.assign(v.begin(),v.end());//拷贝intend2clock();printf(list1 sort:%d\n,end1-begin1);printf(list2 sort:%d\n,end2-begin2);可以看到list sort的效率远低于vector sort甚至于说直接使用list sort的效率都不如先将数据拷贝到vector中然后使用vector sort排序之后再将数据拷贝回list中快至此我们也能明白为什么list sort接口使用得非常少了。注在工程中在 release 版本下测试软件或算法性能得到的结果要比在 debug 版本下得到的结果具有参考意义。三、list迭代器3.1 迭代器类别迭代器类别–-Input只读✓✗✗✗Output只写✓✗✗✗Forward单向✓✗✗✗Bidirectional双向✓✓✗✗Random Access随机✓✓✓✓迭代器有很多种类如上我们全部列举出来了。vector的迭代器是随机迭代器支持 –- 多种操作。和vector和string不同由于结构非连续问题list的迭代器并非一个原生指针。所以list作为一个双向链表是一个双向迭代器。也就是说list的迭代器不支持 和 - 操作。由于是双向迭代器所以list不能采用vector的方式来直接在中间插入数据。迭代的类型会限制接口的访问以下我们讲两个例子。首先是标准库的sort由于sort的底层需要operator[]大量访问数据所以只支持随机迭代器。我们看看sort的底层代码如你所见使用了 - 操作符自然不支持。reversereverse的底层有使用 – 操作所以只能支持双向迭代器。但是这里又要讲一个直接支持和间接支持的问题直接支持如下reverse直接支持双向迭代器。间接支持随机迭代器可以用 --所以reverse也支持随机迭代器的使用。实际上可以理解为一种包含的关系双向是一种特殊的单向。随机是一种特殊的双向/单向。这也可被认为是一种继承 —— 子类是一种特殊的父类。没有对应的直接类型但是可以传递其以上任意父类3.2list迭代器失效问题和vector不同list进行insert操作后并不会产生迭代器失效问题因为list插入的新节点是动态开辟的同时由于list每个节点的物理地址是不相关的所以插入的新节点并不会影响原来其他节点的地址但是list在erase之后会发生迭代器失效因为list删除节点会直接将该节点释放掉此时我们再访问该节点就会造成越界访问。3.3list迭代器源码分析list的迭代器底层不是原生指针而是一个封装指针。原因是结构不连续无法通过 C/C 内置的指针算术进行操作。这个封装指针的解引用、operator、operator!等等操作都需修改。此外迭代器需要构造函数因为在调用的时候不能再以一个指针的形态来简单调用了得构造一个迭代器才能使用。迭代器本身就是一个封装指针所以不需要拷贝构造浅拷贝够用//节点定义templateclassTstruct__list_node{typedefvoid*void_pointer;void_pointer next;void_pointer prev;T data;};//迭代器定义typedef__list_iteratorT,T,T*iterator;typedef__list_iteratorT,constT,constT*const_iterator;//迭代器类templateclassT,classRef,classPtrstruct__list_iterator{typedef__list_iteratorT,Ref,Ptrself;typedef__list_nodeT*link_type;//节点的指针link_type node;//类成员变量__list_iterator(link_type x):node(x){}//将节点指针构造为类对象//... 使用运算符重载支持迭代器的各种行为selfoperator(){...}selfoperator--(){...}Refoperator*()const{...}};如上我们为迭代器专门设计了一个__list_iterator类然后在类内配合运算符重载、模板等操作使得迭代器支持指针的各种行为至于这里为什么__list_iterator会有三个模板参数我们会在后面模拟实现中具体解释当前我们只需要理解其第一个模板参数T即可。
前言这篇笔记是我的实践记录从节点、迭代器到容器接口一步步还原list的核心逻辑把 “用容器” 变成 “懂容器”。一、list的介绍list是 STL 中支持在任意位置高效常数时间插入、删除的双向迭代序列式容器底层基于带头双向链表实现 —— 每个元素存于独立节点通过指针连接前后元素它和forward_list类似但后者是单链表、仅支持前向迭代和array、vector、deque相比list的插入删除效率更优但缺点是不支持随机访问访问第 n 个元素需线性遍历且每个节点的指针会占用额外空间对存储小元素的大list影响较明显。二、list的常用接口及其使用2.1 构造函数构造函数 (constructor)接口说明list (size_type n, const value_type val value_type())构造的 list 中包含 n 个值为 val 的元素list()构造空的 listlist (const list x)拷贝构造函数list (InputIterator first, InputIterator last)用迭代器区间构造 list2.2 增删查改函数声明接口说明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 中的有效元素//尾插l1.push_back(0);l1.push_back(1);l1.push_back(2);for(autov:l1){coutv ;}coutendl;//头插l1.push_front(-1);for(autov:l1){coutv ;}coutendl;//头删l1.pop_front();for(autov:l1){coutv ;}coutendl;//在pos处插入//先来一个迭代器后面我们具体讲listint::iterator it1l1.begin();//it就可以在开始的下一个位置插入l1.insert(it1,999);for(autov:l1){coutv ;}coutendl;l1.erase(--it1);for(autov:l1){coutv ;}coutendl;for(autov:l2){coutv;}coutendl;l1.swap(l2);for(autov:l1){coutv ;}coutendl;for(autov:l2){coutv ;}coutendl;l1.clear();for(autov:l1){coutv ;}coutendl;swap接口为了避免因使用std::swap交换效率低下需要拷贝list重载了swap这个重载的底层是交换两个链表的指针。list没有重载find需要调用std::find。2.3list特殊接口除了上述 STL 容器基本都有的一般接口外list还提供一些独有的特殊操作接口如下函数声明接口说明splice将 list1 中的元素转移到 list2 中remove移除 list 中的指定元素unique链表去重merge合并两个链表sort链表排序reverse链表逆置2.3.1 splice 接口有两种使用方式从一个list剪切到另外一个list的一个位置前面coutl1:;for(autov:l1){coutv;}coutendl;coutl2:;for(autov:l2){coutv;}coutendl;l1.splice(l1.begin(),l2);coutl1:;for(autov:l1){coutv;}coutendl;coutl2:;for(autov:l2){coutv;}coutendl;从自身的某个位置开始剪切到自身的某个位置前面。// splice( 插入位置, 源链表, 源区间起点, 源区间终点 )lt.splice(pos,source,first,last);2.3.2 remove 接口通过元素的值来移除元素。for(autov:l2){coutv;}coutendl;l2.remove(6);for(autov:l2){coutv;}coutendl;2.3.3 unique 接口去重要求链表有序原因是底层是默认相同的数据被放在一起。for(autov:l2){coutv;}coutendl;l2.unique();for(autov:l2){coutv;}coutendl;2.3.4 merge 接口合并链表需要两个链表有序底层有点类似于归并排序的逻辑双指针遍历两个链表找小插入再返回拷贝。被合并的list会变空。listintl1;listintl2;l1.push_back(1);l1.push_back(3);l1.push_back(5);l1.push_back(7);l2.push_back(0);l2.push_back(2);l2.push_back(4);l2.push_back(6);l2.push_back(8);coutl1:;for(autov:l1){cout v;}coutendl;coutl2:;for(autov:l2){cout v;}coutendl;l1.merge(l2);coutl1:;for(autov:l1){cout v;}coutendl;coutl2:;for(autov:l2){cout v;}coutendl;2.3.5 sort 接口链表排序只能使用list提供的sort接口而不能使用 algorithm 提供的sort接口因为链表物理地址不连续迭代器为双向迭代器不支持 - 操作而算法库中的sort函数需要支持 - 的随机迭代器listintl1;listintl2;l1.push_back(1);l1.push_back(3);l1.push_back(5);l1.push_back(7);l1.push_back(0);l1.push_back(2);l1.push_back(4);l1.push_back(6);l1.push_back(8);coutl1:;for(autov:l1){cout v;}coutendl;l1.sort();coutl1:;for(autov:l1){cout v;}coutendl;2.3.6 reversecoutl1:;for(autov:l1){cout v;}coutendl;l1.reverse();coutl1:;for(autov:l1){cout v;}coutendl;2.3.7 总结1、链表排序只能使用list提供的sort接口而不能使用 algorithm 提供的sort接口因为链表物理地址不连续迭代器为双向迭代器不支持 - 操作而算法库中的sort函数需要支持 - 的随机迭代器2、链表去重之前必须保证链表有序否则去重不完全3、两个有序链表合并之后仍然保存有序最后虽然list提供了这些具有特殊功能的接口它们也确实有一定的作用但是实际上这些特殊接口使用频率非常低包括sort接口链表排序的效率太低。2.4list排序的性能分析虽然链表排序只能使用list提供的sort接口而不能使用 algorithm 提供的sort接口但是其使用频率仍然非常低这是由于链表排序的效率太低了我们可以通过对比两组测试数据来直观地感受链表排序的效率。测试一vector排序与list排序性能对比srand((size_t)time(0));constintN1000000;//100万个数据vectorintv;v.reserve(N);listintlt;for(inti0;iN;i){autoerand();v.push_back(e);lt.push_back(e);}//vector sortintbegin1clock();sort(v.begin(),v.end());intend1clock();//list sortintbegin2clock();lt.sort();intend2clock();printf(vector sort:%d\n,end1-begin1);printf(list sort:%d\n,end2-begin2);测试二list直接进行排序与将数据拷贝到vector中使用vector排序后再将数据拷回list中性能对比srand(time(0));constintN1000000;//100万个数据listintlt1;listintlt2;for(inti0;iN;i){autoerand();lt1.push_back(e);lt2.push_back(e);}//list sort -- lt1intbegin1clock();lt1.sort();intend1clock();// 将数据拷贝到vector中排序排完以后再拷贝回来 -- lt2intbegin2clock();vectorintv;v.reserve(N);for(autoe:lt2)//拷贝{v.push_back(e);}sort(v.begin(),v.end());//排序lt2.assign(v.begin(),v.end());//拷贝intend2clock();printf(list1 sort:%d\n,end1-begin1);printf(list2 sort:%d\n,end2-begin2);可以看到list sort的效率远低于vector sort甚至于说直接使用list sort的效率都不如先将数据拷贝到vector中然后使用vector sort排序之后再将数据拷贝回list中快至此我们也能明白为什么list sort接口使用得非常少了。注在工程中在 release 版本下测试软件或算法性能得到的结果要比在 debug 版本下得到的结果具有参考意义。三、list迭代器3.1 迭代器类别迭代器类别–-Input只读✓✗✗✗Output只写✓✗✗✗Forward单向✓✗✗✗Bidirectional双向✓✓✗✗Random Access随机✓✓✓✓迭代器有很多种类如上我们全部列举出来了。vector的迭代器是随机迭代器支持 –- 多种操作。和vector和string不同由于结构非连续问题list的迭代器并非一个原生指针。所以list作为一个双向链表是一个双向迭代器。也就是说list的迭代器不支持 和 - 操作。由于是双向迭代器所以list不能采用vector的方式来直接在中间插入数据。迭代的类型会限制接口的访问以下我们讲两个例子。首先是标准库的sort由于sort的底层需要operator[]大量访问数据所以只支持随机迭代器。我们看看sort的底层代码如你所见使用了 - 操作符自然不支持。reversereverse的底层有使用 – 操作所以只能支持双向迭代器。但是这里又要讲一个直接支持和间接支持的问题直接支持如下reverse直接支持双向迭代器。间接支持随机迭代器可以用 --所以reverse也支持随机迭代器的使用。实际上可以理解为一种包含的关系双向是一种特殊的单向。随机是一种特殊的双向/单向。这也可被认为是一种继承 —— 子类是一种特殊的父类。没有对应的直接类型但是可以传递其以上任意父类3.2list迭代器失效问题和vector不同list进行insert操作后并不会产生迭代器失效问题因为list插入的新节点是动态开辟的同时由于list每个节点的物理地址是不相关的所以插入的新节点并不会影响原来其他节点的地址但是list在erase之后会发生迭代器失效因为list删除节点会直接将该节点释放掉此时我们再访问该节点就会造成越界访问。3.3list迭代器源码分析list的迭代器底层不是原生指针而是一个封装指针。原因是结构不连续无法通过 C/C 内置的指针算术进行操作。这个封装指针的解引用、operator、operator!等等操作都需修改。此外迭代器需要构造函数因为在调用的时候不能再以一个指针的形态来简单调用了得构造一个迭代器才能使用。迭代器本身就是一个封装指针所以不需要拷贝构造浅拷贝够用//节点定义templateclassTstruct__list_node{typedefvoid*void_pointer;void_pointer next;void_pointer prev;T data;};//迭代器定义typedef__list_iteratorT,T,T*iterator;typedef__list_iteratorT,constT,constT*const_iterator;//迭代器类templateclassT,classRef,classPtrstruct__list_iterator{typedef__list_iteratorT,Ref,Ptrself;typedef__list_nodeT*link_type;//节点的指针link_type node;//类成员变量__list_iterator(link_type x):node(x){}//将节点指针构造为类对象//... 使用运算符重载支持迭代器的各种行为selfoperator(){...}selfoperator--(){...}Refoperator*()const{...}};如上我们为迭代器专门设计了一个__list_iterator类然后在类内配合运算符重载、模板等操作使得迭代器支持指针的各种行为至于这里为什么__list_iterator会有三个模板参数我们会在后面模拟实现中具体解释当前我们只需要理解其第一个模板参数T即可。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
