抚州城乡建设厅网站网站开发工程师资格证

当前位置： 首页 > news >正文

抚州城乡建设厅网站,网站开发工程师资格证,东海建设局网站,化妆品做备案的网站目录 前言 总代码 ListNode类框架的建立 (成员与模板) list类的框架 普通构造 与 empty_init#xff08;适合不同类型构造函数的小函数#xff09; list的迭代器 引子 operator、operator–#xff08;前置与后置#xff09; operator 与 operator! operator* 与 …目录 前言 总代码 ListNode类框架的建立 (成员与模板) list类的框架 普通构造 与 empty_init适合不同类型构造函数的小函数 list的迭代器 引子 operator、operator–前置与后置 operator 与 operator! operator* 与 operator- operator* operator- 普通迭代器 与 const迭代器的实现 begin、endconst 与 非const insert 插入 erase 删除 push_back、pop_back、push_front、pop_front(头删尾删、头插尾插) 拷贝构造 析构函数 赋值重载 initializer_list 构造 结语 前言 相比于vector和stringlist这个迭代器可就开始上强度了 其主要的强度在于vector和string都是开辟的一段连续的空间所以这两个的迭代器用原生指针就可以实现 但是list不一样list的空间是分散的只有通过每个节点里的next指针才能找到下一个节点还有就是实现const迭代器于普通迭代器两个版本的时候需要在模板参数上动点手脚这也是一个相对晦涩的地方 如果有友友想看一下list全部函数的用法的话可以到C较为官方的网站上去查阅如下 https://legacy.cplusplus.com/reference/list/list/?kwlist 总代码 如果有友友只是复习需要只想看完整代码的话可以直接点下面的gitee链接 当然对于看完了整篇文章的友友也可以照着这里的代码敲一篇进一步理解喔…()ノ gitee - list - blog - 2024-08-07 ListNode类框架的建立 (成员与模板) 首先库里的类是一个带头双向循环链表我们今天的底层实现将会紧跟着库里的实现走 所以我们的成员为 两个指针一个指向下一个节点_next一个指向上一个节点_prev一个数据表示节点内的数据 而为了实现这个链表什么类型的值都可以存进去所以我们需要写一个类模板表示那个数据类型 代码如下 templateclass T struct ListNode {ListNode(const T x):_next(nullptr),_prev(nullptr),_data(x){}ListNodeT _next;ListNodeT* _prev;T _data; }; list类的框架 我们list类里面仅需要一个参数就是一个指向头节点的指针 由于库里的类是一个带头双向循环链表所以我们这个指针是需要指向哨兵位的这个在构造函数部分再解决 另外我们还可以给ListNode类型加一个typedef将其改成Node方便我们后续的操作 代码如下 templateclass T class list {typedef ListNodeT Node;private:Node* _head; }; 普通构造 与 empty_init适合不同类型构造函数的小函数 这个函数的作用就是——new一个哨兵位因为我们后续会有很多种构造比如普通的构造拷贝构造initializer_list构造这些构造之前都需要创建哨兵位而这些代码又都是重复的代码所以就写一个小函数来放这一部分代码 代码如下 // 初始化函数创建哨兵位void empty_init() {_head new Node(0);_head-_next _head;_head-_prev _head; } 由于我们上面实现了一个empty_init小函数作用是创建哨兵位所以我们这个普通的构造直接使用这个小函数即可代码如下 list() {empty_init(); } list的迭代器 引子 我们之前的vector和string都是一段连续空间所以原生指针就可以作为其迭代器直接typedef一下即可 string: typedef char* iterator;verctor: typedef T* iterator; 我们对其原生指针就能找到下一个–亦然 但是我们今天的list并不是连续的空间所以我们可以这么玩儿搞一个类类里面重载operator和operator–实现下一个和上一个然后还有operatoroperator-等等其成员只需要一个节点即可 同时我们这里的节点指向的空间都是浅拷贝的因为我要的就是指向同一块空间这样我才能修改到如果是另外开空间的话就成大坑了 如下 templateclass T struct ListIterator {typedef ListNodeT Node;typedef ListIteratorT Self;Node _node;ListIterator(Node* node):_node(node){} }; 我们会看到上面还typedef了一个Self这是因为我们后续的和–都需要返回一个iterator类型为了方便所以我们就多写一个typedef operator、operator–前置与后置 我们operator的主要逻辑就是让_node指向下一个所以我们只需要让_node做出改变再将一个iterator类型返回即可*thisoperator–依然 //前置与–Self operator() {_node _node-_next;return *this; }Self operator–() {_node _node-_prev;return *this; } 注意我们这里需要的是返回一整个iterator类型所以是先处理_node的位置再返回*this而不是直接返回_node-_next这样子的话返回的类型不匹配迭代器在外面接受的时候发现类型不匹配就报错了 你可以想象一下这个iterator是一个整体要我们遍历到下一个的时候我们是将这个整体里面的_node改变了让其指向下一个之后再返回这个整体的 同样的 前置的版本与后置的版本唯一的区别就在于参数那个地方加一个int没有实际意义之后编译器就会知道你这个是后置的这也算是祖师爷为这块打的一个补丁吧记住就好 代码如下 //后置与–Self operator(int) {Self tmp(*this);_node _node-_next;return tmp; }Self operator–(int) {Self tmp(this);_node _node-_prev;return tmp; } operator 与 operator! 这块的代码相对简单就不做讲解了代码如下 bool operator!(const Self it) {return _node !it._node; }bool operator(const Self it) {return _node it._node; } operator 与 operator- operator* 我们的operator要的就是直接返回这个链表节点里面对应的值所以我们直接返回_node里面的_data就是了如下 T operator() {return _node-_data; } operator- 而operator-相对来说会更为的晦涩难懂 我们在外面使用iterator的时候是直接 it-_data 来取到数据的按理来说我们在实现的内部也应该返回一个引用 但是其实编译器在这里做了一个隐藏你看到的 it-_data 其实被隐藏了一个 - it-_data; it.operator-()-_data; 如上我们可以看到编译器在这里确实是为了美观藏了一个 -所以我们在返回的时候应该返回一个指针类型的数据也就是 _node-_data 的指针 综上代码如下 T* operator-() {return _node-_data; } 注意这里的 -优先级高于所以取到的是_data的地址 普通迭代器 与 const迭代器的实现 我们的const与非const其实也就是operator与operator-需要改写成const而已 至于其他的函数比如operatoroperator–operatoroperator!这些都不会影响因为const迭代器要的只是指向的内容不修改而已、–只是指向下一个节点而已要加const的只是取出数据的那两个函数重载 但是这里有两个我们难道再写一个类吗太冗余了 那传一个const T过去吗不行类型不匹配ListNode那个类的 T 不是const 这里最好的方法就是模板那里再加两个参数 T operator() {return _node-_data; }T* operator-() {return _node-_data; } 我们可以看到这里就只有两个函数需要用const修饰而唯一需要改的就只有返回值所以我们直接加两个参数 一个用来代替TRef一个用来代替TPtr 如下 templateclass T, class Ref, class Ptr struct ListIterator {typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;Ref operator(){return _node-_data;}Ptr operator-(){return _node-_data;}//。。。。。。其他重载函数}; 这样子的话我们在typedef迭代器的时候就可以分别控制了如下 typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator; begin、endconst 与 非const 我们的begin和end都需要返回一个迭代器类型的引用 而begin指向的是头节点end指向的是尾节点的下一个节点也就是哨兵位 所以我们可以直接使用匿名对象构造一个节点后返回如下 iterator begin() {return iterator(_head-_next); }iterator end() {return iterator(_head); }const_iterator begin()const {return const_iterator(_head-_next); }const_iterator end()const {return const_iterator(_head); } insert 插入 这里虽然插入并没有迭代器失效但是库里面还是写了返回值所以我们写的版本也写一个返回值吧 插入的参数是两个 迭代器代表位置待插入的数据 而我们只需要new一个新节点然后将该节点的前后关系链接起来即可图示如下 代码如下 //insert没有迭代器失效 iterator insert(iterator pos, const T x) {Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);newnode-_next cur;newnode-_prev prev;prev-_next newnode;cur-_prev newnode;return iterator(newnode); } erase 删除 需要注意的是删除这里是有迭代器失效的因为删除之后这个节点就没了而我们的迭代器还指向那块被销毁的空间所以需要返回值在外面接收的时候就能接收到删除位置的下一个位置的迭代器这样子就能处理好迭代器失效的问题了 图示如下假设此时我要删除的是3节点 代码如下 //erase有迭代器失效 iterator erase(iterator pos) {assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return iterator(next); } push_back、pop_back、push_front、pop_front(头删尾删、头插尾插) 这里的插入和删除我们都可以复用 insert 和 erase 的逻辑 头删就是删除begin位置的节点 尾删就是删除哨兵位的上一个节点 头插就是在begin位置的前面插入新节点 尾插就是在哨兵位位置的前面插入新节点 代码如下 void push_back(const T x) {insert(end(), x); }void pop_back() {erase(–end()); }void push_front(const T x) {insert(begin(), x); }void pop_front(const T x) {erase(begin()); } 拷贝构造 我们的拷贝构造主要分为以下两个步骤 new出哨兵位上文中我们提到了empty_init可以直接使用该函数将参数传过来的list一个一个push_back 代码如下 //拷贝构造 list(const listT lt) {empty_init();for (auto e : lt){push_back(e);} }void empty_init() {_head new Node(0);_head-_next _head;_head-_prev _head; } 析构函数 这里的析构我们可以直接选择复用上文实现的erase 上文中提到由于删除了之后迭代器指向的节点被删除会发生迭代器失效所以返回的是下一个节点的迭代器 我们这里可以直接使用迭代器访问每遍历到一个就删除一个然后再拿迭代器接收就行了也不用走因为返回的就是下一个 删除完所有节点之后我们还需要手动将哨兵位删除最后再将_head指针置为空即可 代码如下 ~list() {auto it begin();while (it ! end()){it erase(it);}delete _head;_head nullptr; } 赋值重载 我们来思考这样一个问题我们的整个链表其实都只是由一个指向哨兵位的指针维护的如果已经有一个不要的对象了我们要获得这个对象的空间的话我们只需要将两个对象的指针交换即可 同理我们在这里可以让参数传一个list过来但是我们不加这样编译器就会自动调用拷贝构造拷贝一份函数结束后调用其析构销毁 而我们要快速获得这块空间的话我们只需要将两个对象的指针交换这样其实就间接地完成了空间的交换也就完成了赋值重载 代码如下 listT operator(listT lt) {swap(_head, lt._head);return *this; } initializer_list 构造 initializer_list其实是一个类这个类里面也有空间存着我们要的数据 我们需要先使用empty_list这个上文中提到的函数将哨兵位创造出来 void empty_init() {_head new Node(0);_head-_next _head;_head-_prev _head; } 然后就只需要使用范围for将里面的数据一个一个提取出来再依次push_back即可 代码如下 list(initializer_listT il) {empty_init();for (auto e : il){push_back(e);} } 结语 到这里我们的list底层实现相关内容就结束啦(▽) 如果觉得对你有帮助的话希望可以多多支持喔(〃︶)人(︶〃)我们下一篇博客再见