Lesson10---list

Lesson10—list

第10章 c++的list的使用和实现


文章目录

  • Lesson10---list
  • 前言
  • 一、list的初始化
  • 二、list的遍历
    • 1.迭代器
    • 2.范围for
  • 三、list常用的内置函数
    • 1.sort(慎用)
    • 2.unique
    • 3.reverse
    • 4.merge
    • 5.splice
  • 四、模拟实现
    • 1.基本框架
    • 2.构造函数
    • 3.push_back
    • 4. 遍历
    • 5.const迭代器
    • 6.代码
    • 7.const迭代器改进
    • 8.insert
    • 9.erase
    • 10. pop_back
    • 11. push_front
    • 12.pop_front
    • 13.clear
    • 14.析构函数
    • 15.拷贝构造
    • 16.赋值
    • 17.initializer
  • 五.完整代码
  • 总结


前言

这篇博客写了怎么使用list和怎么实现


list和前面的string 和vector 的有很多重复的就不过多赘述

一、list的初始化

vector的底层是数组,list的底层是结构体,所以list不能用下标的方式去访问,因为这样会让效率变的特别低

可以直接用花括号去初始化这样就不要一个个尾插,vector和list都可以
在这里插入图片描述

二、list的遍历

1.迭代器

在这里插入图片描述
vector的底层是数组,在内存上是连续的但是链表不是,但这里链表依旧可以使用迭代器来遍历,非常的强大

既然可以用迭代器去访问一个在内存上不连续的list那能不能给这个链表用sort排序呢?
答案是不能,因为这样排序效率特别低,如果想要去排序链表,list提供了sort函数
在这里插入图片描述

2.范围for

在这里插入图片描述


有很多和vector重复了就不重复写了感兴趣的可以看我的vector篇

三、list常用的内置函数

1.sort(慎用)

在这里插入图片描述
在这里插入图片描述
默认是升序加上仿函数是降序

list的排序底层用的不是快排用的是归并排序,如果数据很多又要排序就不要用list用vector
在这里插入图片描述
list排序时间是vector的三倍左右,而且特别稳定基本都是三倍左右,虽然归并排序和快排都是nlogn但是list排序还是罗逊vector

甚至把list里面的数据拷贝给vector让vector用快排排序,把排序好的数据在拷贝回来这样会都比list的sort的归并排序快简直拉跨

在这里插入图片描述
在这里插入图片描述

2.unique

unique的作用是去重但数据必须是排序以后或者连续的
在这里插入图片描述
不排序或者不连续就会这样去不干净
在这里插入图片描述

3.reverse

逆置这个链表,比较简单
在这里插入图片描述

4.merge

合并链表,这里必须是要有序的
在这里插入图片描述
在这里插入图片描述

5.splice

这个函数差不多就是剪切的意思,第一个参数要迭代器,第二个参数是链表

从迭代器的位置插入一整个链表
在这里插入图片描述
还可以这样用
在这里插入图片描述

四、模拟实现

模板不建议声明和定义分开会有各种问题,建议直接把定义写在.h文件里面

1.基本框架

#pragma once
#include<iostream>
using namespace std;
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prve;T _data;
};template<class T>
class my_list
{
public:typedef ListNode<T> Node;
private:Node* _head;
};

先把基本的框架写好来

2.构造函数

在这里插入图片描述

3.push_back

在这里插入图片描述
这里可以画个草图理解,要尾插就要先找尾巴

void push_back(const T& x)
{Node* newnode = new Node(x);Node* tail = _head->_prve;tail->_next = newnode;newnode->_prve = tail;newnode->_next = _head;_head->_prve = newnode;
}

在这里插入图片描述
运行以后会这个错误

在这里插入图片描述
编译器给的是这个错误,这是因为,new Node 会去调用 node默认构造函数但是这里没有写
在这里插入图片描述

在这里插入图片描述

struct ListNode
{ListNode<T>* _next;ListNode<T>* _prve;T _data;ListNode(const T& data = T()):_next(nullptr),_prve(nullptr),_data(data){}
};

在这里插入图片描述

4. 遍历

链表在逻辑上是连在一起的但是它在物理上就不一定是连续的了是所用它不能想vector一样的用++去遍历vector底层是数组
这里我采用迭代器的方式去遍历,因为指针++需要像数组那样在物理上连续才可以所以这里采用封装然后运算符重载去实现

class ListIterator
{
public:typedef ListNode<T> Node;typedef ListIterator<T> self;Node* _node;ListIterator(Node* node):_node(node){}self& operator++( ){_node = _node->_next;return *this;}T& operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}
};

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
这样就可以遍历了,也支持范围for
在这里插入图片描述

5.const迭代器

如果有人这样去访问迭代器就会把回来的值改变不安全,有时候还会在不经意间改变原来的值
在这里插入图片描述
在这里插入图片描述
这里还需要重载一个const迭代器,只能去访问但是不能修改里面的值

template<class T>
class ListConstIterator{
public:typedef ListNode<T> Node;typedef ListConstIterator<T> self;ListConstIterator(Node* node):_node(node){}Node* _node;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prve;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prve;return tmp;}const T& operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}bool operator ==(const self& it){return _node == it._node;}
};

这里只需要复制一份原来的迭代器改下名字就行,然后重载一下
在这里插入图片描述
然后加上const就可以了然后再去my_list里面加上就行
在这里插入图片描述
加上const迭代器的begin和end
在这里插入图片描述
在这里插入图片描述
这里就不让改了

6.代码

#pragma once
#include<iostream>
using namespace std;
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prve;T _data;ListNode(const T& data = T()):_next(nullptr),_prve(nullptr),_data(data){}
};
template<class T>
class ListIterator{
public:typedef ListNode<T> Node;typedef ListIterator<T> self;ListIterator(Node* node):_node(node){}Node* _node;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prve;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prve;return tmp;}T& operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}bool operator ==(const self& it){return _node == it._node;}
};
template<class T>
class ListConstIterator{
public:typedef ListNode<T> Node;typedef ListConstIterator<T> self;ListConstIterator(Node* node):_node(node){}Node* _node;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prve;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prve;return tmp;}const T& operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}bool operator ==(const self& it){return _node == it._node;}
};template<class T>
class my_list
{
public:typedef ListNode<T> Node;typedef ListIterator<T> iterator;typedef ListConstIterator<T> const_iterator;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);}my_list(){_head = new Node;_head->_next = _head;_head->_prve = _head;}void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prve;tail->_next = newnode;newnode->_prve = tail;newnode->_next = _head;_head->_prve = newnode;}private:Node* _head;
};

7.const迭代器改进

上面const迭代器有一个问题,就是只要解引用那一点点不一样甚至只是返回值加了const代码就边长了那么多这里还可以在优化一下

#pragma once
#include<iostream>
using namespace std;
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prve;T _data;ListNode(const T& data = T()):_next(nullptr), _prve(nullptr), _data(data){}
};
template<class T,class Ref>
class ListIterator{
public:typedef ListNode<T> Node;typedef ListIterator<T,Ref> self;ListIterator(Node* node):_node(node){}Node* _node;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prve;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prve;return tmp;}Ref operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}bool operator ==(const self& it){return _node == it._node;}
};
//template<class T>
//class ListConstIterator
//
//{
//public:
//
//	typedef ListNode<T> Node;
//	typedef ListConstIterator<T> self;
//	ListConstIterator(Node* node)
//		:_node(node)
//	{
//
//	}
//	Node* _node;
//	self& operator++()
//	{
//		_node = _node->_next;
//		return *this;
//	}
//	self& operator--()
//	{
//		_node = _node->_prve;
//		return *this;
//	}
//	self operator++(int)
//	{
//		self tmp(*this);
//		_node = _node->_next;
//		return tmp;
//	}
//	self operator--(int)
//	{
//		self tmp(*this);
//		_node = _node->_prve;
//		return tmp;
//	}
//	const T& operator*()
//	{
//		return _node->_data;
//	}
//	bool operator !=(const self& it)
//	{
//		return _node != it._node;
//	}
//	bool operator ==(const self& it)
//	{
//		return _node == it._node;
//	}
//};template<class T>
class my_list
{
public:typedef ListNode<T> Node;typedef ListIterator<T,T&> iterator;typedef ListIterator<T,const T&> const_iterator;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);}my_list(){_head = new Node;_head->_next = _head;_head->_prve = _head;}void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prve;tail->_next = newnode;newnode->_prve = tail;newnode->_next = _head;_head->_prve = newnode;}private:Node* _head;
};

8.insert

可以画个草图方便理解
在这里插入图片描述

iterator insert(iterator pos ,const T& x)
{Node* newnode = new Node(x);Node* cur = pos._node;newnode->_prve = cur->_prve;cur->_prve->_next = newnode;newnode->_next = cur;cur->_prve = newnode;return iterator(newnode);
}

9.erase

iterator erase(iterator pos)
{Node* cur = pos._node;Node* prve = cur->_prve;Node* next = cur->_next;prve->_next = next;next->_prve = prve;delete cur;return iterator(next);
}

10. pop_back

void pop_back()
{erase(--end());
}

11. push_front

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

12.pop_front

void pop_front()
{erase(begin());
}

13.clear

void clear()
{auto it = begin();while (it !=end()){it=erase(it);}
}

14.析构函数

~my_list()
{clear();delete _head;_head = nullptr;
}

15.拷贝构造

my_list(const my_list<T>& lt)
{_head = new Node;_head->_next = _head;_head->_prve = _head;for (const auto& e : lt){push_back(e);}
}

16.赋值

my_list<T>& operator = (my_list<T> lt)
{swap(lt._head, _head);return *this;
}

17.initializer

my_list(initializer_list<T> il)
{_head = new Node;_head->_next = _head;_head->_prve = _head;for (auto e : il){push_back(e);}
}

五.完整代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prve;T _data;ListNode(const T& data = T()):_next(nullptr), _prve(nullptr), _data(data){}
};
template<class T, class Ref>
class ListIterator{
public:typedef ListNode<T> Node;typedef ListIterator<T, Ref> self;ListIterator(Node* node):_node(node){}Node* _node;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prve;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prve;return tmp;}Ref operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}bool operator ==(const self& it){return _node == it._node;}
};
//template<class T>
//class ListConstIterator
//
//{
//public:
//
//	typedef ListNode<T> Node;
//	typedef ListConstIterator<T> self;
//	ListConstIterator(Node* node)
//		:_node(node)
//	{
//
//	}
//	Node* _node;
//	self& operator++()
//	{
//		_node = _node->_next;
//		return *this;
//	}
//	self& operator--()
//	{
//		_node = _node->_prve;
//		return *this;
//	}
//	self operator++(int)
//	{
//		self tmp(*this);
//		_node = _node->_next;
//		return tmp;
//	}
//	self operator--(int)
//	{
//		self tmp(*this);
//		_node = _node->_prve;
//		return tmp;
//	}
//	const T& operator*()
//	{
//		return _node->_data;
//	}
//	bool operator !=(const self& it)
//	{
//		return _node != it._node;
//	}
//	bool operator ==(const self& it)
//	{
//		return _node == it._node;
//	}
//};template<class T>
class my_list
{
public:typedef ListNode<T> Node;typedef ListIterator<T, T&> iterator;typedef ListIterator<T, const T&> const_iterator;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);}void empty(){_head = new Node;_head->_next = _head;_head->_prve = _head;}my_list(){empty();}//lt2(lt1)my_list(initializer_list<T> il){empty();for (auto e : il){push_back(e);}}my_list(const my_list<T>& lt){empty();for (const auto& e : lt){push_back(e);}}~my_list(){clear();delete _head;_head = nullptr;}//lt3 = lt1my_list<T>& operator = (my_list<T> lt){swap(lt._head, _head);return *this;}void push_back(const T& x){/*Node* newnode = new Node(x);Node* tail = _head->_prve;tail->_next = newnode;newnode->_prve = tail;newnode->_next = _head;_head->_prve = newnode;*/insert(end(), x);}iterator insert(iterator pos ,const T& x){Node* newnode = new Node(x);Node* cur = pos._node;newnode->_prve = cur->_prve;cur->_prve->_next = newnode;newnode->_next = cur;cur->_prve = newnode;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prve = cur->_prve;Node* next = cur->_next;prve->_next = next;next->_prve = prve;delete cur;return iterator(next);}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void clear(){auto it = begin();while (it !=end()){it=erase(it);}}
private:Node* _head;
};

总结

例如:以上就是要讲的内容,本文仅仅简单介绍了list的使用和简单的模拟实现

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

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

相关文章

PON架构(全光网络)

目前组网架构 世界上有一种最快的速度又是光&#xff0c;以前传统以太网络规划满足不了现在的需求。 有线网 无线网 全光网络方案 场景 全光网络分类 以太全光网络 PON&#xff08;Pas-sive-Optical Network 无源光网络&#xff09; 再典型的中大型高校网络中 推荐万兆入…

Java项目-基于springboot框架的原创歌曲分享系统项目实战(附源码+文档)

作者&#xff1a;计算机学长阿伟 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、ElementUI等&#xff0c;“文末源码”。 开发运行环境 开发语言&#xff1a;Java数据库&#xff1a;MySQL技术&#xff1a;SpringBoot、Vue、Mybaits Plus、ELementUI工具&#xff1a;IDEA/…

【功能安全】系统架构设计

目录 01 系统架构介绍 02 投票逻辑架构介绍 03 SIS架构 04 ADS域控制器架构设计 01 系统架构介绍 法规GBT 34590 Part4 part10定义的软件要求、设计和测试子阶段之间的关系&#xff08;其中的3-7个人建议翻译为初始架构设计更合理 &#xff09; 系统架构的作用&#xf…

工具:Typora自定义高效率主题

1 分享主题 工欲善其事必先利其器。分享一个文档编辑器主题。 1.1 特点 &#xff08;1&#xff09;大纲放在右侧、目录放在左侧&#xff0c;互不干扰 &#xff08;2&#xff09;标题颜色特殊处理 1.2 使用方式 打开Typora --> 文件 --> 偏好设置 --> 外观 -->…

给已经写好的裸机程序移植freeRTOS操作系统

接了公司一个项目&#xff0c;这是一个采用Dante模块把I2S数据通过网络交换机转发的音频控制器。包含两个串口配置。一开始以为使用裸机即可满足项目要求&#xff0c;实际上如果只有一个串口确实能满足要求了&#xff0c;现在发现Dante模块也需要串口通讯&#xff0c;2个串口同…

《Windows PE》6.4.2 远程注入DLL

实验四十七&#xff1a;远程注入DLL 写一个窗口程序&#xff0c;将一个dll通过远程注入的方法&#xff0c;注入到第三章的示例程序PEHeader.exe中&#xff0c;支持32位和64位PE。 ●dll.c /*------------------------------------------------------------------------FileNam…

记一次js泄露pass获取核心业务

文章目录 一、漏洞原因二、漏洞成果三、漏洞利用过程1.js泄露口令信息2、进入系统后台,管理数据库权限(22个)3、执行命令获取服务器权限4、通过添加扫描脚本,获取存活的内网信息四、免责声明一、漏洞原因 系统存在js泄露口令信息,获取系统超级管理员权限。系统为核心数据研…

ZYNQ AXI_GPIO_INT

REVIEW 软核AXI_GPIO之前已经简单学习过&#xff1a; AXI_GPIO_axi-gpio-CSDN博客 PS侧中断也简单调试过&#xff1a; ZYNQ PS_GPIO中断-CSDN博客 1. 今日摸鱼任务 简单实现AXI_GPIO中断&#xff1a; ps_key控制pl_led闪烁(MIO中断) pl_key控制ps_led闪烁(AXI_GPIO中断) …

js(深浅拷贝,节流防抖,this指向,改变this指向的方法)

一、深浅拷贝 1.基本数据类型和引用数据类型的区别&#xff1a; 1. 基本数据类型的变量存储的是值 引用数据类型的变量存储的是地址值 2. 基本数据类型的变量存储的值在栈内存 引用数据类型的变量存储的值在堆内存 3. 基本数据类型的变量存储的是值和值之间相互不影响 引用数据…

矩阵基础知识

矩阵定义 矩阵的定义 1.矩阵是由一组数按照矩形排列而成的数表。矩阵通常用大写字母表示&#xff0c;例如 AA、BB 等。矩阵中的每个数称为矩阵的元素或元。 一个 mn的矩阵 AA 可以表示为&#xff1a; 其中 aij表示矩阵 A中第i行第j列的元素。 矩阵的维度 1.矩阵的维度由它…

【多线程和高并发】多线程和高并发提纲

文章目录 多线程(多线程问题的)三大源头两个主要问题两大解决方案 高并发问题解决方案 对多线程和高并发相关问题整理了一个简单的提纲。 通过这个提纲&#xff0c;足够引出对并发编程中大部分问题的讨论~ 多线程 (多线程问题的)三大源头 线程并发执行带来的原子性问题。这是…

去梯之言:招聘行业运作的秘密——之找到一份工作

一、前言 招聘行业是一个水很深的行当。不过&#xff0c;尽管它很复杂&#xff0c;了解该行业的工作方式还是很重要的&#xff0c;这样你就可以在这片波涛汹涌的水域中平安航行&#xff0c;获得自己心仪的软件开发职位。反过来&#xff0c;如果你对这个波谲云诡的行业一无所知&…

接口测试(四)jmeter——文件上传

一、文件上传&#xff08;注&#xff1a;示例仅供参考模仿&#xff09; 1. 添加【HTTP信息头管理器】&#xff0c;配置【HTTP信息头管理器】如下&#xff1a; 2. 添加【HTTP请求默认值】&#xff0c;配置【HTTP请求默认值】如下&#xff1a; 3. 添加【HTTP请求】&#xff0…

window7虚拟机VMware与主机共享文件

文件管理器》计算机网络右键》属性》高级共享设置——全部启用 新建文件夹》右键》属性》共享》选择可以共享的用户——我这里选的是所有用户 点击高级共享》权限》保存设置——设置文件权限 文件管理器》计算机网络》右键》属性》————查看虚拟机计算机名称 主机访问 主机…

GIS常见前端开发框架

#1024程序员节&#xff5c;征文# 伴随GIS的发展&#xff0c;陆续出现了众多开源地图框架&#xff0c;这些地图框架与众多行业应用融合&#xff0c;极大地拓展了GIS的生命力&#xff0c;这里介绍几个常见的GIS前端开发框架&#xff0c;排名不分先后。 1.Leaflet https://leafl…

android 微信分享报:签名不对,请检查签名是否与开发平台签名一致的解决

1、微信分享会检查签名与开发平台的签名是否一致&#xff1a; 基本信息 | 微信开放文档 官方文档 下载签名工具&#xff0c;并且&#xff0c;将包名输入&#xff0c;然后点击生成&#xff0c;得到这个一串字符串。 2、到开发平台中&#xff1a;微信开放平台 登录&#xff0c;…

Vue2、Element中实现Enter模拟Tab,实现切换下一个框的效果

目录 &#x1f4c3;前序 &#x1f449;开发历程 &#x1f4bb;实际代码 &#x1f4fd;实现效果图 前序 在几乎所有的浏览器中&#xff0c;都具备通过 Tab 键来切换焦点的功能。然而&#xff0c;有些用户提出了强烈要求&#xff0c;希望能够增加通过 Enter 键…

批量合并PDF 文件的 5 大解决方案

PDF 可以将一个、两个、三个甚至更多的记录封装在一起&#xff0c;以显示完整的信息和用于逻辑和交互式结构化的不同元素。由于 PDF 可以提出多层结构&#xff0c;因此当用户知道如何最大化这种格式时&#xff0c;将所有文件组织到其中非常有效。正如许多经验丰富的用户和 PDF …

selenium案例——爬取哔哩哔哩排行榜

案例需求&#xff1a; 1.使用selenium自动化爬虫爬取哔哩哔哩排行榜中舞蹈类的数据&#xff08;包括视频标题、up主、播放量和评论量&#xff09; 2.利用bs4进行数据解析和提取 3.将爬取的数据保存在本地json文件中 4.保存在excel文件中 分析&#xff1a; 1.请求url地址&…

03 springboot-国际化

Spring Boot 提供了很好的国际化支持&#xff0c;可以轻松地实现中英文国际化。 项目创建&#xff0c;及其springboot系列相关知识点详见&#xff1a;springboot系列 springboot系列&#xff0c;最近持续更新中&#xff0c;如需要请关注 如果你觉得我分享的内容或者我的努力对…