迭代器与模板的结合——stl的list

Ciallo(∠・ω )⌒☆C语言专栏C语言博客_CSDN数据结构专栏数据结构博客_CSDNC专栏C博客_CSDNPython专栏Python博客_CSDN作者仓库代码仓库_gitee文章目录一、引言二、list 的介绍与使用2.1 list 的底层结构2.2 list 的构造2.3 list 的迭代器2.4 list 的容量与元素访问2.5 list 的增删查改2.6 list 的迭代器失效三、list 的模拟实现3.1 节点的定义3.2 迭代器的设计——把一个指针封装成一个类为什么不能直接用指针- 是最容易懵的const 的迭代器还得再写一份给自己起个别名 self既然只差三处交给模板合并普通迭代器怎么转成 const 迭代器begin() 的两种返回写法3.3 list 框架与哨兵位3.4 insert 与 erase3.5 拷贝构造、赋值重载、析构四、迭代器的分类五、list 的反向迭代器六、list 与 vector 的对比七、总结一、引言上一篇我们模拟实现了 vector它底层是一段连续空间随机访问很高效但任意位置插入删除需要搬移元素效率不高。C 语言阶段的链表虽然能很好地解决插入删除的问题但接口太少、用起来麻烦而 STL 的list正是基于链表封装出来、接口完善的容器。这一篇我们就来探究 list 的实现思路——它是怎么把「带头结点的双向循环链表」这个底层结构包装成一个个好用接口的。二、list 的介绍与使用2.1 list 的底层结构list底层是带头结点的双向循环链表。「带头结点」指链表的第一个节点是哨兵位不存有效数据只为统一头插、尾插、中间插的边界处理「循环」指头尾相接。这样无论头插、尾插、还是中间插定位和串接逻辑都完全一致不用单独为「在头结点前插入」写特判。2.2 list 的构造listintl1;// 空 listlistintl2(10,1);// 10 个值为 1 的元素listintl3(l2);// 拷贝构造listintl4(l2.begin(),l2.end());// 迭代器区间构造2.3 list 的迭代器可以把 list 的迭代器先理解成「一个指向节点的指针」。正向迭代器begin/end执行向后移动反向迭代器rbegin/rend执行向前移动因为它内部其实就是正向迭代器的--。listintlt;for(autoe:lt){coute ;}2.4 list 的容量与元素访问empty判断是否为空size返回有效节点个数front/back返回首尾节点值的引用。2.5 list 的增删查改push_back/pop_back、push_front/pop_front、insert/erase、swap、clear都是常用接口。这里额外提一下emplace_backC11 引入和push_back都能尾插区别是emplace_back会直接把构造参数传进去、就地构造省掉一次临时对象拷贝对构造复杂的自定义类型效率更高。structA{int_a1,_a2;A(inta11,inta21):_a1(a1),_a2(a2){}};listAlt;Aaa(1,1);lt.push_back(aa);// 需要临时对象lt.push_back(A(2,2));// 需要临时对象lt.emplace_back(3,3);// 直接传构造参数就地构造2.6 list 的迭代器失效vector 因为扩容会让迭代器全部失效但 list 底层是节点插入节点不会改变已有节点的地址所以插入元素不会导致迭代器失效。真正会失效的只有删除被删的那个节点对应的迭代器失效了其他迭代器不受影响。// 错误写法erase 之后 it 指向的节点已被删除it 失效while(it!l.end()){l.erase(it);it;}// 正确写法接收 erase 返回值 / 先自增再删除itl.erase(it);// 返回被删节点的下一个// 或 l.erase(it);三、list 的模拟实现list的部分实现还是比较简单的我们学了模板所以迭代器我们需要细嗦3.1 节点的定义双向循环链表每个节点要存三个东西数据、前驱指针、后继指针。templateclassTstructlist_Node{list_Node(constT dateT()){_datedate;_next_prevnullptr;}T _date;list_NodeT*_next;list_NodeT*_prev;};3.2 迭代器的设计——把一个指针封装成一个类为什么不能直接用指针vector 的迭代器就是裸指针T*因为数据连续存放it就是指针加 1天然成立。但 list 的数据是一个个节点、彼此不连续it根本不知道往哪儿走——它要跳到_next节点。所以 list 的迭代器不能是裸指针必须把它写成一个类让、--、*、-这些操作符在我们定义的行为下工作。-是最容易懵的先写出一个「正常」的迭代器operator*简单返回当前节点的数据引用可operator-却让我卡了很久。当时我盯着-想它明明和*一样是「取当前节点的东西」为什么operator*返回T而operator-却要返回T*地址关键就在于-在 C 里是个特殊的操作符。你写it-data编译器并不是直接调用operator-拿到 data而是把它拆解成it-data (it.operator-())-data也就是说operator-()返回的是一个指针然后编译器拿着这个指针再对它做一次-。所以要想让it-data拿到节点的数据operator-必须返回「数据的地址」这样it-data (it.operator-())-data (_node-_data)-data // 即 (*it).data这下就通了。-的重载不是「直接返回数据」而是「返回数据的地址交给编译器再解引用一次」。这就是它和*最大的不同。templateclassTstructlist_iterator{typedeflist_NodeTNode;Node*_node;list_iterator(Node*node):_node(node){}Toperator*(){return_node-_date;}T*operator-(){return(_node-_date);}list_iteratorToperator(){_node_node-_next;return*this;}list_iteratorToperator--(){_node_node-_prev;return*this;}booloperator!(constlist_iteratorTs)const{return_node!s._node;}booloperator(constlist_iteratorTs)const{return_nodes._node;}};const 的迭代器还得再写一份const listint这种对象只允许读所以要一个operator*返回const T、operator-返回const T*的迭代器。于是我又复制了一份改成 const。两个类摆在一起你会发现除了三处类型其余全是重复的。templateclassTstructlist_const_iterator{typedeflist_NodeTNode;constNode*_node;list_const_iterator(constNode*node):_node(node){}constToperator*(){return_node-_date;}constT*operator-(){return(_node-_date);}list_const_iteratorToperator(){_node_node-_next;return*this;}list_const_iteratorToperator--(){_node_node-_prev;return*this;}booloperator!(constlist_const_iteratorTs)const{return_node!s._node;}booloperator(constlist_const_iteratorTs)const{return_nodes._node;}};给自己起个别名self写到这份上我发现自己每次都要写一长串list_iteratorT尤其返回值、参数、比较到处都是。一旦后面模板参数变多写全名更容易写错。于是我就用typedef给「自己」起个别名self这样operator返回self、operator!参数写const self简洁多了。typedeflist_iteratorTself;既然只差三处交给模板合并普通和 const 两个类就差三处指针是Node*还是const Node*、operator*返回T还是const T、operator-返回T*还是const T*。既然「会变的就这几处」那就把它们抽成模板参数Ref和Ptr用templateclass T, class Ref, class Ptr把两个类合并成一个。Ref管operator*返回什么、Ptr管operator-返回什么。普通迭代器实例化成list_iteratorT, T, T*const 迭代器实例化成list_iteratorT, const T, const T*。templateclassT,classRef,classPtrstructlist_iterator{typedeflist_NodeTNode;typedeflist_iteratorT,Ref,Ptrself;Node*_node;list_iterator(Node*node):_node(node){}Refoperator*(){return_node-_date;}Ptroperator-(){return_node-_date;}selfoperator(){_node_node-_next;return*this;}selfoperator--(){_node_node-_prev;return*this;}selfoperator(int){self tmp*this;_node_node-_next;returntmp;}selfoperator--(int){self tmp*this;_node_node-_prev;returntmp;}booloperator!(constselfs)const{return_node!s._node;}booloperator(constselfs)const{return_nodes._node;}};list类里就只要两句typedef了typedeflist_iteratorT,T,T*iterator;typedeflist_iteratorT,constT,constT*const_iterator;一个巧思这里const不是靠const Node*这种「指针本身只读」来体现的而是通过返回值——Ref是const T、Ptr是const T*。这样拿到的是「只读」的引用/指针能改对象的操作自然被拦住了。普通迭代器怎么转成 const 迭代器平时我们常写const listint的begin()返回const_iterator。那想用一个已有的普通iterator去初始化const_iterator能不能转能。权限只能缩小普通→const不能放大const→普通这才安全。所以给迭代器加一个「模板构造函数」用普通迭代器构造 const 迭代器只把_node拷过来。templateclassRef2,classPtr2list_iterator(constlist_iteratorT,Ref2,Ptr2lt):_node(lt._node){}你会发现一个模板参数T的类里还能再嵌套一个「函数模板」这种「类模板的成员函数依旧是模板」的写法和 vector 里用「迭代器区间构造」是一个道理模板参数可以层层叠加。begin()的两种返回写法写begin()的时候会发现返回_head-_next这个Node*其实可以有两种写法都能过编译但背后逻辑值得想一想。iteratorbegin(){returniterator(_head-_next);// 方式一先构造一个临时迭代器对象再返回}iteratorbegin(){return_head-_next;// 方式二直接用 Node* 隐式类型转换返回}方式一是「显式构造临时对象再返回」写得很明确方式二是靠迭代器的构造函数做隐式类型转换更简洁。两者结果一样方式二更常用。const版本同理const_iteratorbegin()const{return_head-_next;}3.3 list 框架与哨兵位list持有两个成员_head哨兵位和_size节点数。初始化时先empty_init把哨兵位弄成自循环的空链表。voidempty_init(){_headnewNode;_head-_next_head;_head-_prev_head;_size0;}一个值得记住的点end()返回的正是哨兵位_head。这样begin到end遍历正好覆盖所有有效节点一次而且「插入到end()就是尾插」逻辑统一头插尾插中间插全是一样的代码。3.4 insert 与 erase中间的插入删除是双向链表的常规操作思路和 C 语言链表一致插入时新建节点把当前节点和它的前驱串起来删除时先接好前后两段再delete掉当前节点。这里只强调一点——插入返回新节点的迭代器删除返回被删节点的下一个迭代器。iteratorinsert(iterator pos,constTx){Node*pcurpos._node;Node*prevpcur-_prev;Node*newnodenewNode(x);newnode-_nextpcur;newnode-_prevprev;pcur-_prevnewnode;prev-_nextnewnode;_size;returnnewnode;}iteratorerase(iterator pos){assert(pos!end());Node*pcurpos._node-_next;Node*prevpos._node-_prev;pcur-_prevprev;prev-_nextpcur;deletepos._node;--_size;returnpcur;}有了insert/erasepush_back、push_front、pop_back、pop_front、clear都能直接复用很简洁。voidpush_back(constTx){insert(end(),x);}voidpush_front(constTx){insert(begin(),x);}voidpop_back(){erase(--end());}voidpop_front(){erase(begin());}voidclear(){autoitbegin();while(it!end()){iterase(it);}}3.5 拷贝构造、赋值重载、析构拷贝构造复用尾插一件件搬进来即可。赋值重载用「现代写法」参数不引用传进来的是临时对象交换后临时对象出作用域自动销毁。list(constlistTlt){empty_init();for(autoe:lt){push_back(e);}}listToperator(listTlt){swap(lt);return*this;}voidswap(listTlt){std::swap(_head,lt._head);std::swap(_size,lt._size);}~list(){clear();delete_head;_headnullptr;}四、迭代器的分类写到这里我想专门把迭代器的类型展开聊一聊。因为基础阶段容易把它当成「一个统一的指针」可实际上迭代器是有强弱之分、有层级关系的而且有些接受迭代器的库函数并不支持所有迭代器不了解这一点很容易用错。迭代器按能力分为以下几类从弱到强Input Iterator 输入迭代器 只读只能向前单遍扫描比如 istream_iterator Output Iterator 输出迭代器 只写只能向前单遍扫描比如 ostream_iterator Forward Iterator 前向迭代器 可读可写只能向前可多遍扫描比如 forward_list Bidirectional Iterator 双向迭代器 可读可写既能也能--比如 list、set、map Random Access Iterator 随机访问迭代器 可读可写支持/--/n/-n/下标比如 vector、deque、string Contiguous Iterator 连续迭代器 在随机访问基础上保证内存连续比如 vector、stringC17 起它们之间有明显的继承关系能力越强能覆盖的操作越多越往下越能当作上面一层的类型使用。可以用一张图来表示Contiguous Iterator | Random Access Iterator | Bidirectional Iterator | Forward Iterator / \ Input Iterator Output Iterator也就是说Contiguous 属于 Random AccessRandom Access 属于 BidirectionalBidirectional 属于 Forward。而 list 的迭代器是Bidirectional Iterator不是 Random Access。这点很关键。标准库的std::sort需要随机访问迭代器因为它要能直接跳位置做分区所以std::sort(lt.begin(), lt.end())对 list 是编译不过的。list 只能用自己的成员函数lt.sort()来排序。反过来std::reverse、std::find这些只要求双向或前向的算法list 就能直接用。判断一个算法能不能用关键看它的迭代器「要求等级」是否 ≤ 你容器迭代器的「等级」。list 是双向迭代器凡是要随机访问迭代器的算法它都用不了只能用自己类里提供的成员版本。这也是前面为什么 vector 能直接std::sort而 list 得lt.sort()的根本原因。五、list 的反向迭代器反向迭代器没必要重写一遍。它的就是正向迭代器的----就是正向迭代器的所以反向迭代器内部持有一个正向迭代器把接口包装一下就行。于是我们写出这样一个类模板参数Iterator就是正向迭代器templateclassIteratorclassReverseListIterator{public:typedeftypenameIterator::Ref Ref;typedeftypenameIterator::Ptr Ptr;typedefReverseListIteratorIteratorSelf;...};有个细节要注意operator*要解引用「当前的前一个位置」得先拷贝一份再前移不能改动自身的_it。Refoperator*(){Iteratortemp(_it);--temp;return*temp;}还有typename这个关键字它是用来告诉编译器Ref是Iterator类里的类型而不是静态成员变量——因为模板还没实例化编译器分不清Iterator::Ref到底是类型还是变量typename就是帮它排雷的。这一点和前面 vector 打印函数里typename vectorT::const_iterator it是一个道理。正因为 vector 和 list 都能复用这个模板所以通常会把反向迭代器抽成一个通用的reverse_iterator。六、list 与 vector 的对比vector 和 list 都是 STL 重要的序列式容器但底层结构不同特性也不同整理成表对比项vectorlist底层结构动态顺序表一段连续空间带头结点的双向循环链表随机访问支持访问某元素 O(1)不支持访问某元素 O(N)插入和删除任意位置插入删除效率低要搬移元素O(N)插入可能扩容更慢任意位置插入删除效率高不用搬移O(1)空间利用率连续空间不易碎片缓存利用率高节点动态开辟小节点易碎片缓存利用率低迭代器原生态指针对节点指针进行封装迭代器失效插入可能扩容使全部失效删除当前迭代器要重新赋值插入不失效删除只使被删节点迭代器失效使用场景需要高效存储、支持随机访问、不关心插删效率大量插入删除、不关心随机访问一个实际体感list 节点分散、缓存命中率低所以即便插入删除是 O(1)真实跑起来未必比 vector 快。测试里把上百万个随机数分别用list.sort()和「拷贝到 vector 排序再拷回」比较往往是 vector 那条路更快这就是缓存的威力。所以选容器时要看核心操作是「随机访问」还是「大量插入删除」。七、总结list 的核心是带头结点的双向循环链表它把「节点如何串联、迭代器如何封装」隐藏起来暴露出一套统一好用的接口。这一篇我们重点看了模拟实现尤其是迭代器怎么把裸指针封装成类、普通/const 迭代器怎么用一个类模板合并、以及迭代器分类和 const 权限转换。比起 vector它牺牲了随机访问和缓存效率换来了任意位置插入删除的高效。而且通过迭代器一步步写过来的过程也更能体会到把裸指针封装成类、再用模板合并这层设计思想的巧妙。