C++ list容器的实现及讲解

所需要的基础知识

对C++类的基本了解 默认构造函数 操作符重载 this指针 引用 模板等知识具有一定的了解，阅读该文章会很轻松。

链表节点

	template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x), _next(nullptr)//只需要将链表的节点初始化为空 在链表对象中重新进行节点的设置, _prev(nullptr){}};

template<class T> 是类模板 取决于链表存的数据类型 因为链表可以存许多类型的数据类型 那么只要显示传类型 就可以反复去复用 类模板 但是该写的代码编译器会帮你写 就是每个类型都会有一份代码  

默认构造函数 对链表成员进行初始化 运用了初始化列表 在花括号中只能进行赋值 不是初始化

链表list中的成员及函数 

插入 

从插入函数的实现就可以看出 该链表是双向循环链表

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

插入和C语言中链表的插入没有区别 创建一个新节点 先对新结点进行操作 再对要插入的位置进行操作一面将插入的位置丢失 无法将双向循环链表连接上

返回值是新节点的位置 防止你再再此处插入 方便插入

下面的头插尾插都是对插入接口的赋用  

		void push_back(const T& x){insert(--end(), x);}void push_front(const T& x){insert(begin(), x);}

链表的遍历靠的就是迭代器 所以传迭代器就知道了链表的节点位置 依次可以插入 如果你要任意位置插入 那就要计算 迭代器的位置 进行传入  

删除

		iterator earse(iterator pos){node* cur = pos.node;node* next = cur->_next;node* prev = cur->_prev;delete cur;next->_prev = prev;prev->_next = next;--_size;return iterator(next);}

删除也是和之前讲过的C语言部分链表一样 删除操作要返回下一个位置的迭代器 

返回值这样设计 就可以自动向后遍历删除

头删尾删 就是对删除链表的复用

		void pop_back(){earse(--end());}void pop_front(){earse(begin());}

链表中的迭代器调用接口

		iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}  const_reverse_iterator rend()const{return const_reverse_iterator(begin());}

 迭代器再外面就是这样调用的 只需调用list函数中的正向和反向迭代器接口 就可以进行正反向遍历

清除函数clear()

		void clear(){iterator it = begin();while (it != end()){it = earse(it);//it++;//因为earse()返回的是该节点下一个节点 所以不用在进行++}}

 clear()就是复用earse()函数 只保留头节点_head

析构函数

		~list(){clear();_size = 0;delete _head;_head = nullptr;}

 编译器自己写的析构函数对自定义类型不进行析构 链表节点就是自定义类型 所以需要自己写析构函数 进行数据的释放 

赋值操作符重载“=”

		void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> x){swap(x);return *this;}

 operator=(参数) 参数是进行传值传参 传值传参就是原数据的拷贝 出了该函数这个拷贝参数x会自行销毁 会调用自己的构造函数 既然x和原数据类型值是一样的 所以就可以进行交换

swap(x)->this->swap(x) 在list函数内部除了static修饰的函数没有this指针其他函数都有this指针 你可以在函数内部进行显示调用 但是函数参数不能出现

如：A=B A的地址就是this B就是x; 

链表中的类型及函数讲解

     

  • 正向迭代器

    typedef的类型简化

        typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> self;

        由于原始类型过于繁杂 所以进行类型简化 

迭代器函数介绍：

        默认构造函数

        list_iterator(Node* x):node(x){}

        因为迭代器中存的是 链表的节点 是自定义类型 需要调用对应的默认初始化函数 

        正向迭代器的功能就是将链表正向遍历一遍 

        既然是遍历肯定要将链表中的数据打印出来那就需要对应的函数去获取

        操作符重载：

        “*”->operator*()

		Ref operator*(){return node->_data;}

        "->"operator->()

        Ptr operator->(){return &node->_data;}

     

迭代器中存的是链表的节点 然而用迭代器是这么用的

        list<T>::iterator it = begin()获取迭代器的首 it就是指针 所以你想获取链表节点中的数据就需要重载“*和->" *it的功能就是获取该节点的数据 只是迭代器中对其进行了重载实现 所以你可以这样使用 ”->"道理也是一样 都是迭代器进行了重载实现 功能就是通过指针进行迭代器中共有函数和成员的直接获取 淡然*it也是可以就需要叫“.”操作符进行公有成员和函数的获取

        这两个返回值的类型是不一样的 “*”既然是数据 那么就可以引用返回 只要你不销毁程序不结束没有出作用域 就可以进行传引用返回 “->"返回的就是指针类型就是T* 他的返回值前面有个&取地址符 然而”*“和”->"两者遇到一起就抵消了 就剩下node->_data也就是你想要的节点数据 我就是这样理解操作符“->"的重载实现原理的

          "前置++，--，后置++，--"

		self& operator++(){node = node->_next;return *this;}self& operator--(){node = node->_prev;return *this;}self operator++(int){self tmp(*this);node = node->_next;return tmp;}self operator--(int){self tmp(*this);node = node->_prev;return tmp;}

        前置与后置操作的区别就是前置不需要数据类型进行占位 构成操作符重载

        那么返回值类型就是迭代器的类型 返回值根据前置和后置的功能有所不同

        前置：先++/--在用 也就迭代器要返回下一个位置 由于下一个位置是存在的你不销毁或者程序不结束 那么该位置始终是有效的 所以可以返回引用 &

        后置：先用再++/-- 也就是要返回当前的值还要进行++/-- 那就要储存当前的值 不然进行完++/--找起来有点麻烦 可以找因为list的结构是双向循环链表可以向前查找 返回++/--的前一个节点就行

拷贝当前数据出了作用域该数据会销毁 那么就不能进行引用& 返回 只能传值拷贝返回

        “比较操作符!=,==”因为不需要大于或小于 比较对象是指针

		bool operator==(const self& x){return node == x.node;}bool operator!=(const self& x){return node != x.node;}

既然是地址的比较就应该返回 bool类型的值 （true/false） 

反向迭代器

由上图可以看出 反向迭代器是对正向迭代器的赋用 而且反向迭代器中成员存的是正向迭代器_it

反向迭代器的默认构造函数

		reverse_iterator(iterator it):_it(it){}

 用正向迭代器对其进行初始化

操作符重载——>"*和->"

		Ref operator*(){iterator tmp = _it;return *(--tmp);}Ptr operator->(){iterator tmp = _it;return &(operator*());}

观察上图的反向迭代器的首部 再要获取节点的前一个位置 所以要先保存当前节点 再对当前进行前移 依次达到目的 

“->"返回的就是指针类型就是T* 他的返回值前面有个&取地址符 然而”*“和”->"两者遇到一起就抵消了 就剩下node->_data也就是你想要的节点数据 我就是这样理解操作符“->"的重载实现原理的

所以返回的既然是数据 那么就可以复用 之前实现的“operator*()”, 

Ref -> T& Ptr -> T* T就是模板参数 取决于外面链表中存的是什么类型的参数

操作符->前置“++/--”和后置"++/--"

		self& operator++(){--_it;return *this;}self& operator--(){++_it;return *this;}self operator++(int){self tmp(*this);--_it;return *this;}self operator--(int){self tmp(*this);++_it;return *this;}

 前置++/-- 和后置++/-- 都是对链表节点进行操作 然而迭代器中存的是链表节点 在外界对迭代器进行操作 为了使类型可以对上 所以返回self 就是反向迭代器的简化类型

反向迭代器的运用

前置++/-- 和后置++/--原理是一样的 先++再用 先用再++ 在正向迭代器中讲过 所以不再重复

迭代器判断是否相等

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

 

链表list对象的实现

#pragma once#include<iostream>
#include<string>
#include<vector>
using namespace std;namespace DZ
{template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T()):_data(x), _next(nullptr)//只需要将链表的节点初始化为空 在链表对象中重新进行节点的设置, _prev(nullptr){}};template<class T, class Ref, class Ptr>class list_iterator{public:typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> self;list_iterator(Node* x):node(x){}self& operator++(){node = node->_next;return *this;}self& operator--(){node = node->_prev;return *this;}self operator++(int){self tmp(*this);node = node->_next;return tmp;}self operator--(int){self tmp(*this);node = node->_prev;return tmp;}bool operator==(const self& x){return node == x.node;}bool operator!=(const self& x){return node != x.node;}Ref operator*(){return node->_data;}Ptr operator->(){return &node->_data;}Node* node;};template<class iterator,class Ref,class Ptr>class reverse_iterator{public:iterator _it;typedef reverse_iterator<iterator, Ref, Ptr> self;reverse_iterator(iterator it):_it(it){}Ref operator*(){iterator tmp = _it;return *(--tmp);}Ptr operator->(){iterator tmp = _it;return &(operator*());}self& operator++(){--_it;return *this;}self& operator--(){++_it;return *this;}self operator++(int){self tmp(*this);--_it;return *this;}self operator--(int){self tmp(*this);++_it;return *this;}bool operator!=(const self& s){return _it != s._it;}};template<class T>class list{public:typedef list_node<T> node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;typedef reverse_iterator<iterator, T&, T*> reverse_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rbegin()const{return const_reverse_iterator(end());}const_reverse_iterator rend()const{return const_reverse_iterator(begin());}void empty_inti(){_head = new node;_head->_next = _head;_head->_prev = _head;}//it1(it2)list(const list<T>& x){empty_inti();for (auto& e : x){push_back(e);}}list(){empty_inti();_size = 0;}void push_back(const T& x){insert(--end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){earse(--end());}void pop_front(){earse(begin());}//list<T>& operator=(const list<T>& x)//{//	if (this != &x)//	{//		clear();//		for (auto& e : x)//		{//			push_back(e);//		}//	}//	return *this;//}//void swap(list<T>& x)//{//	std::swap(_size, x._size);//	std::swap(_head, x._head);//}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> x){swap(x);return *this;}~list(){clear();_size = 0;delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = earse(it);//it++;//因为earse()返回的是该节点下一个节点 所以不用在进行++}}iterator insert(iterator pos, const T& x){node* cur = pos.node;node* newnode = new node(x);newnode->_next = cur->_next;newnode->_prev = cur;cur->_next->_prev = newnode;cur->_next = newnode;++_size;return newnode;}iterator earse(iterator pos){node* cur = pos.node;node* next = cur->_next;node* prev = cur->_prev;delete cur;next->_prev = prev;prev->_next = next;--_size;return iterator(next);}size_t size(){return _size;}private:size_t _size;node* _head;};void test_list1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);// 封装屏蔽底层差异和实现细节// 提供统一的访问修改遍历方式list<int>::iterator it = lt.begin();while (it != lt.end()){*it += 20;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;/*set<int> s;s.insert(1);s.insert(3);s.insert(2);s.insert(4);set<int>::iterator sit = s.begin();while (sit != s.end()){cout << *sit << " ";++sit;}cout << endl;*/}void test_list2(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int> lt1(lt);for (auto e : lt){cout << e << " ";}cout << endl;for (auto e : lt1){cout << e << " ";}cout << endl;list<int> lt2;lt2.push_back(10);lt2.push_back(200);lt2.push_back(30);lt2.push_back(40);lt2.push_back(50);lt1 = lt2;for (auto e : lt1){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;}struct AA{AA(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;};void test_list3(){list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));list<AA>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1<<" "<<(*it)._a2 << endl;cout << it->_a1 << " " << it->_a2 << endl;cout << it.operator->()->_a1 << " " << it.operator->()->_a1 << endl;++it;}cout << endl;int* p = new int;*p = 1;AA* ptr = new AA;ptr->_a1 = 1;}template<typename Container>void print_container(const Container& con){typename Container::const_iterator it = con.begin();while (it != con.end()){cout << *it << " ";++it;}cout << endl;}void test_list4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);//print_list(lt);print_container(lt);list<string> lt1;lt1.push_back("1111111111111");lt1.push_back("1111111111111");lt1.push_back("1111111111111");lt1.push_back("1111111111111");lt1.push_back("1111111111111");//print_list(lt1);print_container(lt1);vector<string> v;v.push_back("222222222222222222222");v.push_back("222222222222222222222");v.push_back("222222222222222222222");v.push_back("222222222222222222222");//print_list(v);print_container(v);}void test_list5(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::reverse_iterator it = lt.rbegin();while (it != lt.rend()){cout << *it << " ";++it;}}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/140695.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

顺序表的实现和练习

顺序表的实现和练习

杂谈&#xff1a; 有些数据结构&#xff08;C语言实现&#xff09;的教材/教程中会使用C中引用的语法&#xff0c;引用确实在形式上比指针简洁&#xff0c;这样做无非是为了避免后续对二级指针的使用。 我认为既然使用C语言实现数据结构&#xff0c;那么指针就不应该是门槛。…
阅读更多...
关于地址存放的例题

关于地址存放的例题

unsigned int a 0x1234; unsigned char b *(unsigned char*)&a; 上面代码大端存储和小端存储的值分别是多少&#xff1f; 大端存储的是把高位地址存放在低位地址处&#xff0c;低位存放到高位。小端是高位存放在高位&#xff0c;低位在低位。因为a是整型&#xff0c;所…
阅读更多...
Kafka的消息存储机制

Kafka的消息存储机制

前面咱们简单讲了K啊开发入门相关的概念、架构、特点以及安装启动。 今天咱们来说一下它的消息存储机制。 前言&#xff1a; Kafka通过将消息持久化到磁盘上的日志文件来实现高吞吐量的消息传递。 这种存储机制使得Kafka能够处理大量的消息&#xff0c;并保证消息的可靠性。 1…
阅读更多...
vue重修003

vue重修003

文章目录 版权声明day03一、今日目标1.生命周期2.综合案例-小黑记账清单3.工程化开发入门4.综合案例-小兔仙首页 二、Vue生命周期三、Vue生命周期钩子四、生命周期钩子小案例1.在created中发送数据2.在mounted中获取焦点 五、案例-小黑记账清单1.需求图示&#xff1a;2.需求分析…
阅读更多...
ChatGPT批量写作文章软件

ChatGPT批量写作文章软件

什么是ChatGPT批量写作文章。简单来说&#xff0c;它是一种使用ChatGPT技术的方法&#xff0c;可以帮助您批量生成各种类型的文章和内容。无论您是需要新闻报道、博客文章、产品描述、社交媒体帖子还是其他类型的内容&#xff0c;ChatGPT都能满足您的需求。它可以在极短的时间内…
阅读更多...
探索 GO 项目依赖包管理与Go Module常规操作

探索 GO 项目依赖包管理与Go Module常规操作

探索 GO 项目依赖包管理与Go Module常规操作 文章目录 探索 GO 项目依赖包管理与Go Module常规操作一.Go 构建模式的演变1.1 GOPATH &#xff08;初版&#xff09;1.1.1 go get 1.2 vendor 机制&#xff08;中版&#xff09;1.3 Go Module&#xff08;最新版&#xff09; 二.创…
阅读更多...
C语言 cortex-A7核UART总线实验

C语言 cortex-A7核UART总线实验

一、C 1&#xff09;uart4.h #ifndef __UART4_H__ #define __UART4_H__ #include "stm32mp1xx_rcc.h" #include "stm32mp1xx_gpio.h" #include "stm32mp1xx_uart.h&quo…
阅读更多...
4k、VR与万兆光网

4k、VR与万兆光网

“全光万兆”对VR意义重大。 pico4的分辨率 PICO 4 的单眼分辨率是 2160 2160&#xff0c;整体分辨率高达 4320 2160。这是一款高性能的 VR 一体机&#xff0c;采用了 2.56 英寸的 Fast-LCD 屏幕&#xff0c;最高可实现 90Hz 刷新率&#xff0c;还有 1200 PPI 和 20.6 PPD 的…
阅读更多...
基于海康Ehome/ISUP接入到LiveNVR实现海康摄像头、录像机视频统一汇聚，做到物联网无插件直播回放和控制

基于海康Ehome/ISUP接入到LiveNVR实现海康摄像头、录像机视频统一汇聚，做到物联网无插件直播回放和控制

LiveNVR支持海康NVR摄像头通EHOME接入ISUP接入LiveNVR分发视频流或是转GB28181 1、海康 ISUP 接入配置2、海康设备接入2.1、海康EHOME接入配置示例2.2、海康ISUP接入配置示例 3、通道配置3.1、直播流接入类型 海康ISUP3.2、海康 ISUP 设备ID3.3、启用保存3.4、接入成功 4、相关…
阅读更多...
Mac磁盘空间满了怎么办？Mac如何清理磁盘空间

Mac磁盘空间满了怎么办？Mac如何清理磁盘空间

你是不是发现你的Mac电脑存储越来越满&#xff0c;甚至操作系统本身就占了100多G的空间&#xff1f;这不仅影响了电脑的性能&#xff0c;而且也让你无法存储更多的重要文件和软件。别担心&#xff0c;今天这篇文章将告诉你如何清除多余的文件&#xff0c;让你的Mac重获新生。 一…
阅读更多...
Nginx的location作用

Nginx的location作用

location Nginx 的 locaiton 作⽤是根据⽤户请求的 URI 不同&#xff0c;来执行不同的应用。针对用户请求的网站URL 进行匹配&#xff0c;匹配成功后进行对应的操作。 location [ | ~| ~* | ^~ ] url {#指定对应的动作 } 正则表达式解释 匹配符 匹配规则 优先级 精确匹配 1…
阅读更多...
数据结构——二叉树层序遍历

数据结构——二叉树层序遍历

链式二叉树的建立 前言一、层序遍历的概念和实现二、判断二叉树是否是完全二叉树总结 前言 来喽来喽~ 二叉树的层序遍历来喽~ 层序遍历那是相当有趣滴&#xff01; 我的朋友&#xff0c;请不要迷惘&#xff0c;你要记住&#xff0c;你终有鲲鹏一日&#xff01; 加油吧&#xf…
阅读更多...
详解MySQL存储引擎

详解MySQL存储引擎

前言： 📕作者简介：热爱编程的小七，致力于C、Java、Python等多编程语言，热爱编程和长板的运动少年！ 📘相关专栏Java基础语法，JavaEE初阶，数据库，数据结构和算法系列等，大家有兴趣的可以看一看。 😇😇😇有兴趣的话关注博主一起学习，一起进步吧！ 一、MySQL存…
阅读更多...
修改vscode底部栏背景和字体颜色

修改vscode底部栏背景和字体颜色

修改vscode底部栏背景和字体颜色 如图&#xff1a; 首先打开齿轮&#xff0c;打开设置搜索workbench.colorCustomizations,然后点击编辑setting.json修改setting.json内内容 "workbench.colorCustomizations": {"statusBar.foreground": "#FFFFFF…
阅读更多...
5G通信与蜂窝模组之间的关系

5G通信与蜂窝模组之间的关系

5G通信是第五代移动通信技术的简称&#xff0c;它代表了一种新一代的无线通信技术标准。5G通信的主要目标是提供更高的数据传输速度、更低的延迟、更大的网络容量以及更可靠的连接&#xff0c;以支持各种新兴应用和服务&#xff0c;包括高清视频流、虚拟现实、物联网&#xff0…
阅读更多...
安全生产一张图 安全生产三维地理信息平台

安全生产一张图 安全生产三维地理信息平台

一、 建设目标 易图讯科技是一家专业从事大数据、移动互联网、物联网、三维GIS、AI系统研发&#xff0c;开发了三维电子沙盘、AI三维电子沙盘、WEB三维地球、移动端三维地球、数字武装三维电子沙盘、智慧动员三维电子沙盘、智慧公安三维电子沙盘、智慧安监三维电子沙盘、森林防…
阅读更多...
【动手学深度学习-Pytorch版】序列到序列的学习（包含NLP常用的Mask技巧）

【动手学深度学习-Pytorch版】序列到序列的学习（包含NLP常用的Mask技巧）

序言 这一节是对于“编码器-解码器”模型的实际应用&#xff0c;编码器和解码器架构可以使用长度可变的序列作为输入&#xff0c;并将其转换为固定形状的隐状态&#xff08;编码器实现&#xff09;。本小节将使用“fra-eng”数据集&#xff08;这也是《动手学习深度学习-Pytor…
阅读更多...
linux 安装 wordpress

linux 安装 wordpress

文章目录 linux 安装 wordpress1. wordpress 简介2. wordpress功能和特点3. 部署要求4. 环境搭建4.1 部署 nginx4.1.1 新增配置文件 4.2 部署 PHP74.2.1 查看当前版本4.2.2 YUM 安装 PHP74.2.3 查看 PHP 版本4.2.4 启动PHP-FPM4.2.5 修改配置文件4.2.6 重启服务 4.3 部署 mysql…
阅读更多...
IDEA下使用Spring MVC

IDEA下使用Spring MVC

<?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM/4.0.0 http://ma…
阅读更多...
【Git】轻松学会 Git：深入理解 Git 的基本操作

【Git】轻松学会 Git：深入理解 Git 的基本操作

文章目录 前言一、创建 Git 本地仓库1.1 什么是仓库1.2 创建本地仓库1.3 .git 目录结构 二、配置 Git三、认识 Git 的工作区、暂存区和版本库3.1 什么是 Git 的工作区、暂存区和版本库3.2 工作区、暂存区和版本库之间的关系 四、添加文件4.1 添加文件到暂存区和版本库中的命令4…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023