list 的实现

ops/2024/10/30 8:46:40/

在这里插入图片描述
上图的下述代码实现:

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;
}

顺序表可以用原生指针代替迭代器的指针,但链表不可以,链表的指针++并不能够保证找到下一个节点的位置。因此需要把当前节点封装起来作为迭代器,在迭代器类中重载++函数,使其++也可以找到下一个结点的位置。

下述代码为list的迭代器代码,对于拷贝构造使用浅拷贝就可以,因为只需要让另一个指针指向当前节点的资源,而链表不可以浅拷贝。对于析构函数,迭代器不能去析构资源。因为资源是在链表中的,迭代器只是访问。

对于迭代器而言,需要完成 *it,重载 ++ 和 – 函数,还有迭代器的比较节点是否相等函数。
在这里插入图片描述

const迭代器为什么是const_iterator而不是const iterator?
const迭代器是迭代器指向的内容不能修改而不是迭代器本身不能修改,而const iterator是iterator不能修改,因此不满足需求。
const迭代器相当于要模拟的不是 T* const 而是 const T*
list中写了一个模板类,编译器底层生成了两个类。
在这里插入图片描述

const类型的迭代器只有operator*和operator->的返回值和普通迭代器的返回值不同,返回值不同就可以用模板。
对于下述代码自定义类型A而言,如果想用迭代器->读取A的内容,就需要在迭代器中重载->,也就是定义的模板 Ptr 函数。

template <class T , class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T> Node; typedef ListIterator<T, Ref, Ptr> Self;Node* _node; //内置类型浅拷贝就可以了ListIterator(Node* node):_node(node){}//*it 可读可写,得引用返回。//T& operator*()Ref operator*(){return _node->_data;}// it->//T* operator->()Ptr operator->(){//node里的data进行取地址,返回一个T类型的指针指向data的地址,//如果存放的是A类型数据,data就是一个A类型指针就可以访问a1和a2return &_node->_data; }Self& operator++() //前置++ 返回++以后的值{_node = _node->_next;return *this;}Self operator++(int){//让tmp指针指向NOde*的资源就行了 浅拷贝够用。Self tmp(*this); _node = _node->_next;return tmp;}Self& operator--() //前置-- 返回--以后的值{_node = _node->_prev;return *this;}Self operator--(int){//让tmp指针指向NOde*的资源就行了 浅拷贝够用。Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}
};

只有list才知道链表的开始和结束,因此得用list把封装的iterator连接起来。
完整的list代码:

namespace ggg
{// 节点类型定义template<class T>struct ListNode //节点的数据需要公开 用struct{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& x = T()):_next(nullptr), _prev(nullptr), _data(x){}};// 封装节点迭代器完成的工作 普通迭代器和const迭代器使用模板复用template <class T , class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node; typedef ListIterator<T, Ref, Ptr> Self;Node* _node; //内置类型浅拷贝就可以了ListIterator(Node* node):_node(node){}//*it 可读可写,得引用返回。//T& operator*()Ref operator*(){return _node->_data;}// it->//T* operator->()Ptr operator->(){//node里的data进行取地址,返回一个T类型的指针指向data的地址,//如果存放的是A类型数据,data就是一个A类型指针就可以访问a1和a2return &_node->_data; }Self& operator++() //前置++ 返回++以后的值{_node = _node->_next;return *this;}Self operator++(int){//让tmp指针指向NOde*的资源就行了 浅拷贝够用。Self tmp(*this); _node = _node->_next;return tmp;}Self& operator--() //前置-- 返回--以后的值{_node = _node->_prev;return *this;}Self operator--(int){//让tmp指针指向NOde*的资源就行了 浅拷贝够用。Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};/// 链表的类template<class T>class list{typedef ListNode<T> Node;public://typedef ListIterator<T> iterator;//typedef ListConstIterator<T> const_iterator;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;iterator begin(){//return iterator(_head->_next); 匿名对象iterator it(_head->_next);return it;}//链表的结尾是最后一个节点的下一个位置,也就是哨兵位iterator end() {return iterator(_head);}//类比:相当于要模拟的不是 T* const 而是 const T*const_iterator begin() const{const_iterator it(_head->_next);return it;}const_iterator end() const{return const_iterator(_head);}///void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}void clear(){iterator it = begin();while (it != end()) // !=end() 就不会清除掉head节点{it = erase(it);}}list() //构造{empty_init();}//lt1(lt)list(const list<T>& lt) //拷贝构造{empty_init();for (auto& e : lt){push_back(e);}}list<T>& operator=(list<T> lt) //赋值{std::swap(_head, lt._head);std::swap(_size, lt._size);return *this;}~list() //析构{clear();delete _head;_head = nullptr;}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); //在end前面插入就是尾插}void push_front(const T& x){insert(begin(), x);}//尾删,删掉end()(哨兵位head)的下一个,也就是最后一个有数据的位置,--就是求上一个位置prevvoid pop_back() {erase(--end());}void pop_front() //头删,begin()就是头{erase(begin());}void insert(iterator pos, const T& val){Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}size_t size() const{return _size;}bool empty(){return _size == 0;}private:Node* _head;size_t _size;};/struct A{int _a1;int _a2;A(int a1 = 0, int a2 = 0):_a1(a1),_a2(a2){}};}

http://www.ppmy.cn/ops/129533.html

相关文章

自动化部署-02-jenkins部署微服务

文章目录 前言一、配置SSH-KEY1.1 操作jenkins所在服务器1.2 操作github1.3 验证 二、服务器安装git三、jenkins页面安装maven四、页面配置自动化任务4.1 新建任务4.2 选择4.3 配置参数4.4 配置脚本 五、执行任务5.1 点击执行按钮5.2 填写参数5.3 查看日志 六、查看服务器文件七…

面对复杂的软件需求:5大关键策略!

面对软件需求来源和场景的复杂性&#xff0c;有效地管理和处理需求资料是确保项目成功的关键&#xff0c;能够提高需求理解的准确性&#xff0c;增强团队协作和沟通&#xff0c;降低项目风险&#xff0c;提高开发效率。反之&#xff0c;项目可能面临需求理解不准确、团队沟通不…

【优选算法篇】前缀之序,后缀之章:于数列深处邂逅算法的光与影

文章目录 C 前缀和详解&#xff1a;基础题解与思维分析前言第一章&#xff1a;前缀和基础应用1.1 一维前缀和模板题解法&#xff08;前缀和&#xff09;图解分析C代码实现易错点提示代码解读题目解析总结 1.2 二维前缀和模板题解法&#xff08;二维前缀和&#xff09;图解分析C…

FFmpeg 深度教程音视频处理的终极工具

1. 引言 什么是 FFmpeg&#xff1f; FFmpeg 是一个开源的跨平台多媒体处理工具&#xff0c;广泛应用于音视频的录制、转换、流式传输以及编辑等多个领域。它由 FFmpeg 项目团队开发和维护&#xff0c;支持几乎所有主流的音视频格式和编解码器。FFmpeg 包含了一系列强大的命令…

Redis-README官方入门文档

文章目录 Redis是什么&#xff1f;什么是Redis社区版&#xff1f;构建Redis修复依赖项或缓存构建选项的构建问题修复构建32位二进制文件的问题分配器单调时钟详细构建运行Redis运行支持TLS的Redis玩转Redis安装Redis代码贡献Redis商标Redis内部结构源代码布局server.hserver.cc…

rtp协议:rtcp包发送和接收规则和报告!

RTCP Packet Send and Receive Rules&#xff1a; 发送和接收 RTCP 包的规则在此列出。允许在多播环境或多点单播环境中运行的实现必须满足第 6.2 节中的要求。这样的实现可以使用本节定义的算法来满足这些要求&#xff0c;或者可以使用其他算法&#xff0c;只要其性能等同或更…

C++:多态(原理篇)

文章目录 前言一、常见笔试题&#xff08;问题引入&#xff09;二、虚函数表感性认识三、再谈笔试题四、父类指针或引用与赋值1. 父类的指针或引用2. 子类给父类赋值 五、子类自己的虚函数在哪里&#xff1f;1. 对于单继承2. 对于多继承1&#xff09;Derive对象的大小2&#xf…

模拟 DDoS 攻击与防御实验

模拟 DDoS 攻击与防御实验可以帮助理解攻击原理和防御策略。在进行这种实验时&#xff0c;必须确保在受控、合法的环境中进行&#xff0c;避免对真实网络造成损害。以下是具体步骤&#xff1a; 环境要求 硬件&#xff1a;至少两台计算机&#xff08;或虚拟机&#xff09;&…