17网站一起做网批,网站服务器租用价格多少钱一年,wordpress模版标签,公司注册地址可以是住宅文章目录 list定义结点类#xff08;list_node#xff09;为什么封装迭代器为类 #xff1f;库里面模板多参数的由来 #xff1f;为什么普通迭代器不能隐式类型转换成const迭代器#xff1f;迭代器位置指向及其返回值和整体代码 list list 和前面学习的 string 和 vector … 文章目录 list定义结点类list_node为什么封装迭代器为类 库里面模板多参数的由来 为什么普通迭代器不能隐式类型转换成const迭代器迭代器位置指向及其返回值和整体代码 list list 和前面学习的 string 和 vector 稍有差别list 存储空间是不连续的不支持随机访问。list是一个双向带头循环链表成员变量只有一个结点Node类型的指针 。在 C 语言部分结点是个结构体而在 C 中已经升级成为了类可以实现自己的各种默认成员函数。这无疑成为了我们实现的难点。因为 list也是个类其成员函数是 Node 类的指针而且我们还要用模板来实现 定义结点类list_node 这里注意用 struct 定义结点(Node)类因为 list 类要频繁使用 Node 类友元太麻烦下方迭代器类也是用 struct 定义方便 list 频繁使用。我们定义的时候随便把构造函数写一下用 T() 空类型作缺省值T 如果是内置类型 int就会用 0 初始化。类名不用 Node因为库里别的容器也会用到结点类且实现方式不一样这里区分一下
库里定义的 自己实现的 为什么封装迭代器为类 在 sting 和 vector 里面迭代器可以实现成原生指针解引用变得到了 val 值。而现在 list的存储空间不连续迭代器是到下一个结点位置我们中间解引用得到的是一个结点而我们现在需要的是解引用能到得结点里面的 val 值。对此我们不得不将迭代器封装成为一个类通过重载 operator 和 operator* 来实现迭代器的功能。 迭代器的成员变量只有一个就是 Node 类型的指针 由于我们迭代器类需要结点类型的指针于是我们 typedef 重命名一下 list_node 为 Node
库里面模板多参数的由来 首先迭代器的类名不能直接是 iterator别的容器也有迭代器这里定义成 _list_iterator 。我们一开始是这么定义普通对象的 iterator 那么思考我们如何定义 const 迭代器 typedef _list_iterator iterator; 假如我们向下面这样定义 const 迭代器第一眼看好像没什么问题但仔细一想迭代器的成员变量是一个 Node 指针这么定义是结点不能移动指向下一个位置反而结点指向的内容可以被修改。我们需要的是 operator* 解引用后结点的 val 不能被修改但是结点可以依然可以移动指向下一个位置 typedef const _list_iterator const_iterator; 倘若我们像下面这样多定义一个 const 迭代器类然后除了返回值不一样其它照抄 _list_iterator 类来写的话又会造成代码冗余 template struct _list_const_iterator { …… } typedef const _list_const_iterator const_iterator; 对此我们多加一个模板参数T 对于普通对象用实例化为普通迭代器const 对象就实例化为 const 迭代器这样就解决了 operator* 函数返回值的问题而库里面又重载了 operator- 函数返回值是 T*有分普通和 const 对象因此我们再增加一个模板参数 T*。在这里注意一下operator- 返回的是指针假设我们有 list 迭代器 it且 T 类型为一个结构体。当我们要用迭代器访问结构体内的成员我们就要这样写it--(结构体内的成员)第一个箭头调用 operator-第二个指向结构体内的成员。但是编译器要求可读性会优化为 it-(结构体内的成员) typedef _list_iteratorT,T iterator; typedef _list_iteratorT,const T const_iterator; //普通迭代器 typedef _list_iteratorT,T,T* iterator; //const迭代器 typedef _list_iteratorT,const T,const T* const_iterator 为什么普通迭代器不能隐式类型转换成const迭代器 首先确保自己知道了 list 的大致实现原理。那么当我们自己实现一个 iterator 时如果不加以注意可能会发生如下情况我们明明没有对权限进行放大为什么编译器还会报错呢 这是因为在泛型编程中如果我们没有专门定义一个拷贝构造函数那么默认的会以自己的类型为基准去考虑参数类型。不要用 int 可以隐式转化成 const int 的思维去考虑类模板。虽然 iterator和const_iterator 在底层调用的都是同一个类模板但是在实例化的时候编译器会认为这是两个不同的类型所以这里原因很清楚了当我们定义一个const_iterator时其默认拷贝构造的参数也是const_iterator。 所以这里原因很清楚了当我们定义一个 const_iterator 时其默认拷贝构造的参数也是 const_iterator。因此编译器才会报错说 iteratorint, int, int* 无法转化为 iteratorint, const int, const int* 。 解决方式也很简单我们只需要在list_iterator 类中定义一个构造函数即可参数为普通对象的迭代器类型这样无论被拷贝对象时const迭代器还是普通迭代器都能调用这个函数而且迭代器我们只需要完成浅拷贝因为我们就是要指向同一块空间
看看库里的
迭代器位置指向及其返回值和整体代码 稍微注意一下begin() 指向的是 _head 的下一个结点而 end() 指向的是 _head 结点。增删查改中由于 erase 函数删除结点会导致迭代器失效因此需要更新返回新的迭代器新的迭代器指向删除结点的下一个。 insert 函数的话也和 erase 函数保持一致返回迭代器不过返回的是新插入的结点 #pragma once
#include iostream
#include assert.hnamespace Me
{//定义结点templateclass Tstruct list_node{//定义为公有让迭代器访问list_nodeT* _prev;list_nodeT* _next;T _val;//升级成为了类有自己的构造函数list_node(const T val T()): _prev(nullptr),_next(nullptr), _val(val){}};//封装迭代器,定义为公有让list访问templateclass T,class Ref,class Ptrstruct _list_iterator{typedef list_nodeT Node;typedef _list_iteratorT, T, T* iterator;typedef _list_iteratorT, const T, const T* const_iterator;typedef _list_iteratorT, Ref, Ptr self;Node* _node;//升级成为了类有自己的构造函数_list_iterator(Node* nodenullptr):_node(node){}_list_iterator(const iteratorx):_node(x._node){}Ref operator*() const{return _node-_val;}self operator(){_node _node-_next;return *this;}self operator(int){//这里不用单独写拷贝构造浅拷贝就行按需求来分析self tmp(*this);_node _node-_next;return tmp;}self operator--() {_node _node-_prev;return *this;}self operator--(int) {//这里不用单独写拷贝构造浅拷贝就行按需求来分析_list_iteratorT tmp(*this);_node _node-_prev;return tmp;}Ptr operator-(){return _node-_val;}bool operator!(const self it) const{return _node ! it._node;}bool operator(const self it) const{return _node it._node;}};//定义链表templateclass Tclass list//定义链表{typedef list_nodeT Node;public://普通迭代器typedef _list_iteratorT,T,T* iterator;//const迭代器typedef _list_iteratorT,const T,const T* const_iterator;//typedef const _list_iteratorT const_iterator;// 这样设计const迭代器是不行的因为const迭代器期望指向内容不能修改// 这样设计是迭代器本身不能修改iterator begin(){//return _head-_next;return iterator(_head-_next);}iterator end(){//左闭又开 _head不存储有效数据//return iterator(_head);return _head;}const_iterator begin() const{//return _head-_next;return const_iterator(_head-_next);}const_iterator end() const{//左闭又开 _head不存储有效数据//return iterator(_head);return _head;}//哨兵卫头结点初始化void empty_init(){_head new Node;_head-_prev _head;_head-_next _head;}list(){empty_init();}list(listT lt){empty_init();//迭代拷贝for (auto e : lt){push_back(e);}}void swap(listT lt){std::swap(_head, lt._head);}//拷贝构造后交换listT operator(listT lt){swap(lt);return *this;}//清理部分void clear(){iterator it begin();while (it ! end()){it erase(it);}}~list(){clear();delete _head;_head nullptr;}void push_front(const T x){insert(begin(), x);}void push_back(const T x){//Node* newnode new Node(x);//Node* tail _head-_prev;//tail-_next newnode;//newnode-_prev tail;//newnode-_next _head;//_head-_prev newnode;insert(end(), x);}void pop_front(){erase(begin());}void pop_back(){//assert(_head ! _head-_next);//Node* tail _head-_prev;//Node* tailP tail-_prev;//tailP-_next _head;//_head-_prev tailP;//delete tail;erase(--end());}iterator insert(iterator pos, const T x){//调用结点的拷贝构造函数Node* newnode new Node(x);//找插入的前一个结点Node* prev pos._node-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next pos._node;pos._node-_prev newnode;return newnode;}iterator erase(iterator pos){assert(pos._node ! _head);assert(_head ! _head-_next);Node* prev pos._node-_prev;Node* next pos._node-_next;prev-_next next;next-_prev prev;delete pos._node;pos._node nullptr;return next;}size_t size(){size_t sz 0;for (auto e : *this){sz;}return sz;}void print(){iterator it begin();while (it ! end()){cout *it ;it;}cout endl;}private:Node* _head;//带哨兵我的头节点};
}
