文章目录引入一、先看节点和遍历边界1.1 一个数据节点两个方向1.2 空链表并不是没有任何节点二、节点指针为什么需要包装2.1 原始指针的操作与我们要的操作不同2.2 先忽略 const理解最小实现骨架三、逐个拆解运算符重载3.1 operator*返回引用才能修改真实元素3.2 operator-让箭头指向元素而不是节点3.3 前置 改变自身返回自身引用3.4 后置 保存旧副本再改变自身3.5 -- 同理但移动条件不同3.6 比较的是位置不是元素数值四、通过三个模板参数生成两种迭代器4.1 为什么只用 T 不够4.2 在 list 中填入两组类型4.3 为什么不能简单换成 list_iterator const T 4.4 begin / end 的 const 重载把类型连接到容器五、const 的三个位置含义各不相同六、节点操作和资源管理6.1 insert保存前驱再接上四条连接6.2 erase先保存后继再删除当前节点6.3 拷贝构造与赋值重载七、小结续接上篇list 的使用把节点、位置和操作联系起来的综合叙述上代码仓库《list测试与模拟实现》引入在学习了解过前面的容器后构造、析构、深拷贝和交换这些基础操作已经基本熟练不必再次深入。对于list与之前容器的最大不同之处就是其迭代器的实现同一个节点指针被包装成类对象后怎样获得*it、it-成员、it这些表达式的含义怎样复用移动逻辑却让不同迭代器获得不同访问权限一、先看节点和遍历边界1.1 一个数据节点两个方向templateclassTstructlist_Node{T _data;list_NodeT*_next;list_NodeT*_prev;list_Node(constTxT()):_data(x),_next(nullptr),_prev(nullptr){}};list_Nodeint的_data是 元素数据两个连接指向相同类型的节点。构造全新的节点时先保存元素再将连接初始化为空只有插入链表后连接才代表真正的前后关系。1.2 空链表并不是没有任何节点_head指向哨兵。空链表时_head-_next _head、_head-_prev _head元素数量为 0。非空时哨兵next指向首数据节点prev指向尾数据节点。因此begin包装的是_head-_nextend包装_head空链表中二者相等。哨兵节点的存在让尾插能复用insert(end(),x)但end 只是边界不允许读取哨兵的_data。二、节点指针为什么需要包装2.1 原始指针的操作与我们要的操作不同假设Node* p指向保存 10 的节点表达式原始 Node 指针希望迭代器提供的含义*p/*it整个节点对象元素 10 的引用p/it指针算术试图前进一个Node沿当前节点的next找到后继p-.../it-...访问节点成员访问元素对象的成员相等比较比较地址比较是否表示同一个节点位置节点各自分配不构成供p做数组遍历的连续Node数组。双向链表节点内存并不是连续的因此对原始的节点指针直接既不能表达“沿链接前进”也不能拿计算出的地址当作后继节点访问。所以需要一个类把节点指针存进去再给操作定义合理的含义。这就是迭代器包装。迭代器不拥有节点不在析构时释放节点vector 迭代器就是原生指针内存连续直接指针算术即可。list 迭代器类封装包装节点指针重载operator内部执行_node _node-_next。2.2 先忽略 const理解最小实现骨架templateclassTstructsimple_iterator{list_NodeT*_node;simple_iterator(list_NodeT*p):_node(p){}Toperator*()const{return_node-_data;}simple_iteratoroperator(){_node_node-_next;return*this;}};it是迭代器对象it._node是它记录的地址。复制it通常只是复制这个地址所以auto another it得到独立的迭代器对象但两者最初指向同一元素。随后another改变another的地址成员不改变it也不复制链表。三、逐个拆解运算符重载以下代码中的Self表示当前这一种迭代器类型Ref表示解引用返回类型Ptr表示箭头返回类型。3.1 operator*返回引用才能修改真实元素Refoperator*(){return_node-_data;}普通迭代器的Ref表示的是T。表达式*it调用it.operator*()返回节点里那个T对象的引用。因此*it 8能够改变真实元素.如果返回T得到的是元素副本不能提供正常的可写迭代器语义而且对复杂的类还可能发生一些不必要的复制。3.2 operator-让箭头指向元素而不是节点Ptroperator-(){return_node-_data;}当元素是简单的一个类 A有成员变量int _a1此时希望写的是it-_a1而不是暴露_node-_data._a1。返回_node-_data得到元素指针编译器对箭头重载继续应用箭头访问最终将会通过这个真实指针来访问成员。真实过程等价于//it 指向有效 A 元素。it-_a1;it.operator-()-_a1;(*it)._a1;3.3 前置 改变自身返回自身引用//前置Selfoperator(){_node_node-_next;return*this;}it调用无额外参数的operator。第一句沿链接改变it保存的地址第二句返回it自身的引用所以结果代表的是新位置。这里容易混淆的是*it与*this*itit是类对象调用重载operator*得到元素引用。*thisthis是指向当前迭代器对象的真实指针使用内置解引用得到的是迭代器对象本身。所以return *this不会递归调用元素解引用也不返回节点数据。正好匹配上了Self。3.4 后置 保存旧副本再改变自身//后置Selfoperator(int){Selftmp(*this);_node_node-_next;returntmp;}it调用带int占位参数的版本。这个int只用于让编译器区分前置与后置没有其它特殊含义。假设it指向 10next是 20执行auto old it;Self old *this复制迭代器把“指向 10”的地址保存到另一个对象。修改it的地址使it指向 20。按值返回old使表达式结果仍表示原来的 10。3.5 – 同理但移动条件不同//前置--Selfoperator--(){_node_node-_prev;return*this;}//后置--Selfoperator--(int){Selftmp(*this);_node_node-_prev;returntmp;}前置--返回自身引用后置--返回旧副本。都沿prev移动。非空链表的end有最后一个元素作前驱所以可以先复制end再--begin没有接口意义上的前驱所以不能--begin。写法相应成员调用改变 it 吗返回什么itit.operator()是沿next改变后的it自身引用itit.operator(0)是沿next修改前的独立副本--itit.operator--()是沿prev改变后的it自身引用it--it.operator--(0)是沿prev修改前的独立副本3.6 比较的是位置不是元素数值booloperator!(constSelfs)const{return_node!s._node;}booloperator(constSelfs)const{return_nodes._node;}两个节点都保存 5元素值相等但迭代器不相等。若错误地比较_data重复元素的存在就会破坏遍历。不要随意比较来自不同容器的迭代器。公开的接口只保证其规定比较域内的行为。四、通过三个模板参数生成两种迭代器4.1 为什么只用 T 不够如果iterator始终返回T通过const容器仍能修改元素违背只读访问要求。若始终返回const T普通容器也失去可写迭代器。初始做法是可以复制两份类一份返回可写类型一份返回只读类型但其中、--、比较的代码完全一样造成了大量的代码冗余而且如果后续需要修改的话还要改两遍。下面则通过三个模板参数的配合实现了两种迭代器的返回templateclassT,classRef,classPtrstructlist_iterator{typedeflist_NodeTNode;typedeflist_iteratorT,Ref,PtrSelf;//...T决定节点内的元素类型Ref决定operator*返回什么Ptr决定operator-返回什么。链表的移动沿Node的链接进行不依赖Ref与Ptr因此两种可以共用。4.2 在 list 中填入两组类型templateclassTclasslist{public:typedeflist_NodeTNode;typedeflist_iteratorT,T,T*iterator;typedeflist_iteratorT,constT,constT*const_iterator;//...这是代码实现的核心下面暂时把T代为int参数或成员普通迭代器只读迭代器完整类型list_iteratorint,int,int*list_iteratorint,const int,const int*TintintRefintconst intPtrint*const int*Nodelist_Nodeintlist_Nodeint_nodelist_Nodeint*list_Nodeint*解引用可修改元素的引用只读元素引用/--修改迭代器的位置同样可以修改迭代器的位置4.3 为什么不能简单换成 list_iterator const T 如果把const放到节点的 T 上Node就会变成list_Nodeconst int它和list_Nodeint是两种不同节点类型。我们要的不是把节点结构换掉而是让同一批节点得到不同的元素访问接口。T 不变Ref 与 Ptr 加const正好表达这个需求。4.4 begin / end 的 const 重载把类型连接到容器iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}const_iteratorbegin()const{returnconst_iterator(_head-_next);}const_iteratorend()const{returnconst_iterator(_head);}非const容器调用非const begin得到iteratorconst容器只能调用const begin得到const_iterator。两者都包装同一个位置只是返回类型不同。五、const 的三个位置含义各不相同写法能移动迭代器吗能通过它修改元素吗iterator it能能const_iterator cit能不能const iterator fixed不能能const const_iterator fixed_cit不能不能第三行最容易误解const iterator只是一个不能改变地址成员的迭代器对象相当于关注“位置固定”它的Ref仍然是T因此正常解引用仍能写元素。const_iterator的类型则改变了Ref与Ptr相当于关注“访问只读”。可以类比指针普通const_iterator的接口权限近似const T*而const iterator则近似与T* const。六、节点操作和资源管理6.1 insert保存前驱再接上四条连接//指定位置前插入数据iteratorinsert(iterator pos,constTx){Node*curpos._node;Node*newNodenewNode(x);cur-_prev-_nextnewNode;newNode-_prevcur-_prev;newNode-_nextcur;cur-_prevnewNode;_size;returnnewNode;}insert(end(), x)是尾插insert(begin(), x)是头插。空链表时prev和cur都是哨兵仍使用同一套步骤。6.2 erase先保存后继再删除当前节点//删除指定位置数据iteratorerase(iterator pos){assert(pos!end());Node*prevpos._node-_prev;Node*nextpos._node-_next;prev-_nextnext;next-_prevprev;deletepos._node;--_size;returnnext;}删除以后不能再读取cur-next所以提前保存next。assert则防止误删end6.3 拷贝构造与赋值重载//初始化头节点voidempty_init(){_headnewNode();_head-_prev_head;_head-_next_head;_size0;}//构造函数list(){empty_init();}//拷贝构造list(constlistTlt){empty_init();for(autoe:lt){push_back(e);}}//拷贝交换voidswap(listTlt){std::swap(_head,lt._head);std::swap(_size,lt._size);}listoperator(listTlt){swap(lt);return*this;}这里的赋值重载种按值参数other是副本不是源对象的引用。交换后本对象取得复制内容other取得本对象旧节点函数结束时清理旧节点。自赋值也先复制再交换不会提前清空源。(与之前的string和vector一样)七、小结理解这份实现时可以一直沿着同一个问题往下问这个表达式修改的是迭代器的位置、节点的连接还是节点中的元素分清这三层再把返回类型与模板参数对应起来list的迭代器就不再是一组难记的符号。对照资料list 总览与接口splice节点转移、重载版本与时间复杂度merge有序归并前提、源容器清空规则unique / remove / sortlist 专属成员函数迭代器、引用失效规则与常见陷阱