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

list 的实现

news 来源：原创 2024/7/2 14:56:14

目录

list

结点类

结点类的构造函数

list的尾插尾删

list的头插头删

迭代器

++运算符重载

--运算符重载

==和!= 运算符重载

* 和 -> 运算符重载

 list 的insert

list的erase

list

list实际上是一个带头双向循环链表,要实现list,则首先需要实现一个结点类,而一个结点需要存储的信息为:数据、前驱指针、后继指针

而对于该结点类的成员函数来说,我们只需实现一个构造函数即可,因为该结点类只需要根据数据来构造一个结点即可,而结点的释放则由list的析构函数来完成,

结点类

结点类的基本结构：

	template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _date;ListNode(const T& pos = T()){_next = nullptr;_prev = nullptr;_date = pos;}};

这里用struct 的原因是因为ListNode 的 每个成员变量都会被频繁调用。

用struct则不需要封装了。

结点类的构造函数

构造函数直接根据所给数据构造一个结点即可,构造出来的结点的数据域存储的就是所给数据,而前驱指针和后继指针均初始化为空指针即可

		ListNode(const T& pos = T()){_next = nullptr;_prev = nullptr;_date = pos;}

list的尾插尾删

	template<class T>class list{public:typedef ListNode<T> node;	list():_head(new node){_head->_next = _head;_head->_prev = _head;}void push_back(const T& x){node* head = _head;node* tail = _head->_prev;node* p = new node(x);tail->_next = p;p->_prev = tail;p->_next = head;head->_prev = p;}void pop_back(){assert(_head != _head->_next);node* head = _head;node* tail = head->_prev;node* newtail = tail->_prev;newtail->_next = head;head->_prev = newtail;delete[] tail;}private:node* _head;};

list的头插头删

	template<class T>class list{public:	typedef ListNode<T> node;list():_head(new node){_head->_next = _head;_head->_prev = _head;}void push_front(const T& x){node* newnode = new node(x);node* head = _head;node* tail = _head->_next;head->_next = newnode;newnode->_prev = head;newnode->_next = tail;tail->_prev = newnode;}void pop_front(){assert(_head != _head->_next);node* head = _head;node* tail = _head->_next;head->_next = tail->_next;tail->_next->_prev = head;delete[]tail;}private:node* _head;};

迭代器

迭代器有两种实现方式,具体应根据容器底层数据结构实现：

  1. 原生态指针,比如：vector和string ->物理空间是连续的，因为string和vector对象都将其数据存储在了一块连续的内存空间,我们通过指针进行自增、自减以及解引用等操作,就可以对相应位置的数据进行一系列操作,因此string和vector当中的迭代器就是原生指针。
  2. .将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下方法：

指针可以解引用,迭代器的类中必须重载operator*()
指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()
指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)
至于operator--()/operator--(int) 是否需要重载,根据具体的结构来抉择,双向链表可
以向前 移动,所以需要重载,如果是forward_list就不需要重载–
迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()
但是对于list来说,其各个结点在内存当中的位置是随机的,并不是连续的,我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作,

总结：list的迭代器 实际上就是对结点指针进行了封装,对其各种运算符进行了重载,使得结点指针的各种行为看起来和普通指针一样,（例如,对结点指针自增就能指向下一个结点 p = p->next）

	template<class T1, class T2>struct Reverse_iterator{typedef Reverse_iterator<T1, T2> self;typedef ListNode<T1> node;node* _it;Reverse_iterator(node* pos)；self& operator++()；self operator++(int)；self& operator--()；self operator--(int)；T2& operator*()；T2* operator->()；bool operator!=(const self& pos)；bool operator==(const self& pos)；}；

迭代器模板参数说明：

构造函数
迭代器类实际上就是对结点指针进行了封装

其成员变量就是结点指针,所以其构造函数直接根据所给结点指针构造一个迭代器对象即可,

		Reverse_iterator(node* pos){_it = pos;}

拷贝构造,operator,析构函数我们都不需要写,因为成员变量是内置类型(指针), 用编译器默认生成的就可以。

++运算符重载

		self& operator++()//前置{_it =_it->_prev;return *this;}self operator++(int)//后置{self tmp(_it);_it = _it->_prev;return tmp;}

前置++原本的作用是将数据自增,然后返回自增后的数据,

而对于结点迭代器的前置++:应该先让结点指针指向后一个结点.然后再返回“自增”后的结点迭代器即可

后置++,先拷贝构造当前迭代器结点, 然后让当前迭代器结点的指针自增指向下一个结点,最后返回“自增”前的结点迭代器即可,

--运算符重载

		self& operator--()//前置{_it = _it->_next;return *this;}self operator--(int)//后置{self tmp(_it);_it = _it->_next;return tmp;}

前置- -：当前迭代器结点中的指针指向前一个结点,然后再返回“自减”后的结点迭代器即可,

后置--：拷贝构造当前迭代器对象 -> 当前迭代器结点中的指针自减指向前一个结点 ->返回自减前的迭代器。

==和!= 运算符重载

		bool operator!=(const self& pos){return _it != pos._it;}bool operator==(const self& pos){return _it == pos._it;}

这里注意形参别写错就好了。

* 和 -> 运算符重载

使用解引用操作符时,是想得到该指针指向的数据内容

因此,我们直接返回当前结点指针所指结点的数据即可,这里需要使用引用返回,因为解引用后可能需要对数据进行修改,

		T2& operator*(){return _it->_date;}

->返回当前迭代器结点的指针所指结点的数据的地址

		T2* operator->(){return &_it->_date;}

使用场景：

 list 的insert

insert函数可以在所给迭代器pos之前插入一个新结点,

1.先根据所给迭代器pos得到该位置处的结点指针

2.然后通过该指针找到前一个位置的结点指针last

根据所给数据x构造一个新结点

		iterator insert(iterator pos,const T& x){node* newnode = new node(x);node* next = pos._node;node* last = next->_prev;last->_next = newnode;newnode->_prev = last;newnode->_next = next;next->_prev = newnode;return iterator(newnode);}

list的erase

erase函数可以删除所给迭代器位置的结点,

注意**:pos不可以是哨兵位的迭代器,即不能删除哨兵位 pos迭代器结点中的指针不能为空**

1.根据所给迭代器得到该位置处的结点指针self

2.通过self指针找到前一个位置的结点指针last,以及后一个位置的结点指针next

3.紧接着释放cur结点,最后prev和next结点进行链接

		iterator erase(iterator pos){assert(pos._node);assert(_head != _head->_next);node* self = pos._node;node* next = self->_next;node* last = self->_prev;last->_next = next;next->_prev = last;delete[] self;return iterator(next);}

关于insert 和 erase 迭代器失效的问题：

insert不会导致迭代器失效,因为pos迭代器中的节点指针仍然指向原来的节点。

问:erase之后, pos迭代器是否失效：
一定失效,因为此时pos迭代器中的节点指针指向的节点已经被释放了,该指针相当于是野指针。

 最后所有代码如下：
 

namespace bit
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _date;ListNode(const T& pos = T()){_next = nullptr;_prev = nullptr;_date = pos;}};template<class T1,class T2 = T1>struct ListIterator{typedef ListIterator<T1,T2> iterator;typedef ListNode<T1> node;node* _node;ListIterator(node* pos){_node = pos;}T2& operator*(){return _node->_date;}iterator& operator++(){_node = _node->_next;return *this;}		iterator operator++(int){iterator tmp(_node);_node = _node->_next;return tmp;}iterator& operator--(){_node = _node->_prev;return *this;}iterator operator--(int){iterator tmp(_node);_node = _node->_prev;return tmp;}T2* operator->(){return &_node->_date;}bool operator!=(const iterator& pos){return _node != pos._node;}bool operator==(const iterator& pos){return _node == pos._node;}};template<class T1, class T2>struct Reverse_iterator{typedef Reverse_iterator<T1, T2> self;typedef ListNode<T1> node;node* _it;Reverse_iterator(node* pos){_it = pos;}self& operator++(){_it =_it->_prev;return *this;}self operator++(int){self tmp(_it);_it = _it->_prev;return tmp;}self& operator--(){_it = _it->_next;return *this;}self operator--(int){self tmp(_it);_it = _it->_next;return tmp;}T2& operator*(){return _it->_date;}T2* operator->(){return &_it->_date;}bool operator!=(const self& pos){return _it != pos._it;}bool operator==(const self& pos){return _it == pos._it;}};template<class T>class list{public:typedef Reverse_iterator<T, T> reverse_iterator;typedef Reverse_iterator<T, const T> const_reverse_iterator;typedef ListNode<T> node;typedef ListIterator<T> iterator;typedef ListIterator<T,const T> const_iterator;list():_head(new node){_head->_next = _head;_head->_prev = _head;}list(const list& pos){_head = new node;_head->_next = _head;_head->_prev = _head;for (auto e : pos){push_back(e);}}list(initializer_list<T> il){_head = new node;_head->_next = _head;_head->_prev = _head;for (auto e : il){push_back(e);}}void push_back(const T& x){node* head = _head;node* tail = _head->_prev;node* p = new node(x);tail->_next = p;p->_prev = tail;p->_next = head;head->_prev = p;}void pop_back(){assert(_head != _head->_next);node* head = _head;node* tail = head->_prev;node* newtail = tail->_prev;newtail->_next = head;head->_prev = newtail;delete[] tail;}reverse_iterator rbegin(){return reverse_iterator(_head->_prev);}reverse_iterator rend(){return reverse_iterator(_head);}const_reverse_iterator crbegin()const{return const_reverse_iterator(_head->_prev);}const_reverse_iterator crend()const{return const_reverse_iterator(_head);}iterator begin(){return iterator(_head->_next);}const_iterator begin()const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}void push_front(const T& x){node* newnode = new node(x);node* head = _head;node* tail = _head->_next;head->_next = newnode;newnode->_prev = head;newnode->_next = tail;tail->_prev = newnode;}void pop_front(){assert(_head != _head->_next);node* head = _head;node* tail = _head->_next;head->_next = tail->_next;tail->_next->_prev = head;delete[]tail;}iterator insert(iterator pos,const T& x){node* newnode = new node(x);node* next = pos._node;node* last = next->_prev;last->_next = newnode;newnode->_prev = last;newnode->_next = next;next->_prev = newnode;return iterator(newnode);}iterator erase(iterator pos){assert(pos._node);assert(_head != _head->_next);node* self = pos._node;node* next = self->_next;node* last = self->_prev;last->_next = next;next->_prev = last;delete[] self;return iterator(next);}~list(){iterator it1 = begin();while (it1 != end()){it1 = erase(it1);}delete _head;_head = nullptr;}private:node* _head;};

相关文章：

  • Kubernetes (K8s) 普及指南
  • golang开发 gorilla websocket的使用
  • Python代码：二十五、有序的列表
  • 英伟达A100算力卡性能及应用
  • 基于Spring前后端分离版本的论坛系统-自动化测试
  • spring管理bean
  • 数据标准的制定落地
  • 使用Python爬取华为市场游戏类APP应用
  • Redis用GEO实现附近的人功能
  • 网络流量处理及分析工具
  • Redis 中的 Zset 数据结构详解
  • C++系列——————类和对象（上）
  • 固定翼飞机（固定翼飞行器）种类丰富 国家政策推动行业发展速度加快
  • 基于FreeRTOS+STM32CubeMX+LCD1602+MCP6S28的8通道模拟可编程增益放大器Proteus仿真
  • 什么是AVIEXP提前发货通知?
  • 4. 路由到控制器 - Laravel从零开始教程
  • angular2开源库收集
  • HTTP 简介
  • Java 9 被无情抛弃，Java 8 直接升级到 Java 10！！
  • JavaScript 事件——“事件类型”中“HTML5事件”的注意要点
  • mongodb--安装和初步使用教程
  • MYSQL如何对数据进行自动化升级--以如果某数据表存在并且某字段不存在时则执行更新操作为例...
  • mysql外键的使用
  • Spark学习笔记之相关记录
  • SQLServer之创建显式事务
  • Web标准制定过程
  • 基于Android乐音识别(2)
  • 设计模式 开闭原则
  • 1.Ext JS 建立web开发工程
  • PostgreSQL之连接数修改
  • Spring第一个helloWorld
  • ​Base64转换成图片,android studio build乱码,找不到okio.ByteString接腾讯人脸识别
  • # C++之functional库用法整理
  • #QT（TCP网络编程-服务端）
  • (14)Hive调优——合并小文件
  • (delphi11最新学习资料) Object Pascal 学习笔记---第14章泛型第2节（泛型类的类构造函数）
  • （Matalb时序预测）WOA-BP鲸鱼算法优化BP神经网络的多维时序回归预测
  • （八）Flask之app.route装饰器函数的参数
  • （附源码）springboot电竞专题网站 毕业设计 641314
  • （算法二）滑动窗口
  • （转）树状数组
  • ****三次握手和四次挥手
  • .htaccess 强制https 单独排除某个目录
  • .net core使用EPPlus设置Excel的页眉和页脚
  • @SentinelResource详解
  • []error LNK2001: unresolved external symbol _m
  • [120_移动开发Android]008_android开发之Pull操作xml文件
  • [20150321]索引空块的问题.txt
  • [AIGC] SQL中的数据添加和操作：数据类型介绍
  • [AIGC] 使用Curl进行网络请求的常见用法
  • ［Android Studio 权威教程］断点调试和高级调试
  • [APUE]进程关系(下)
  • [bug总结]: Feign调用GET请求找不到请求体实体类
  • [BZOJ 3282] Tree 【LCT】
  • [BZOJ 4598][Sdoi2016]模式字符串