list~模拟实现

目录

list的介绍及使用

list的底层结构

节点类的实现

list的实现

构造函数

拷贝构造

方法一：方法二：

 析构函数

赋值重载

insert  /  erase

push_/pop_(尾插/尾删/头插/头删)

begin和end（在已建立迭代器的基础上）

迭代器实现

迭代器类模板参数说明

list包含在头文件

 部分摘自— list模拟实现

list的介绍及使用

list的介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素。ps—>2
3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问，比如：要访问list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间 开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)

list的底层结构

ps—>2

list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向 其前一个元素和后一个元素

节点类的实现

但我们要去实现list，就首先需要定义实现好一个结点类。

而一个结点需要存储：

需要存储的数据、前驱节点、后继节点的地址。

这里用struct定义这个节点类不用class，因为很多地方都要用到和访问这个节点类，成员变量就都共有。

这里也不需要专门单独写一个析构函数，因为这个节点类并没有对应的资源需要清理；

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

list的实现

链表其实就是用一个指向头节点的指针管理起来的，所以，我们可以定义一个list类，它的成员变量是一个指向头节点的指针，因为，list的底层是一个带头双向循环链表，所以这里的指针，应该指向，带有哨兵位的头节点。

template<class T>
class list
{
public:/*typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;list(){_head = new Node();_head->_prev = _head;_head->_next = _head;}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}*/private:Node* _head;
};

构造函数

ist是一个带头双向循环链表，在构造一个list对象时，首先要申请一个头结点，并让其前驱指针和后继指针都指向自己。

list()
{_head = new node; //申请头结点_head->_next = _head; //头结点的后继指针指向自己_head->_prev = _head; //头结点的前驱指针指向自己
}

拷贝构造

拷贝构造有两种方式：        ①用一个list构造方法二        ②迭代器区间

为了方便起见，我们可以先封装手撕一个empty（）函数，去申请头节点，生成一个空链表，在构造和拷贝构造的时候，可以更加方便地调用。

void empty()
{_head = new Node;_head->_prev = _head;_head->_next = _head;
}

方法一：

已经申请一个头结点，并让其前驱指针和后继指针都指向自己，然后将所给容器当中的数据，通过遍历的方式一个个尾插到新构造的容器后面即可。

list(const list<T>& lt)
{empty();for (const auto& e : lt){push_back(e);}
}

方法二：

我们先实现一个使用迭代器区间构造的函数。

template <class Iterator>
list(Iterator first, Iterator last)
{empty;//不加会出问题while (first != last){push_back(*first);++first;}
}

然后，我们先创建一个临时对象让他利用被拷贝对象的迭代器构造出来，然后再交换，被利用完后的临时对象会在栈帧结束后被清除。

我们先实现swap函数，很简单，交换头节点的指针就可以。

void swap(list<T>& tmp)
{std::swap(_head, tmp._head);
}

list(const list<T>& lt)
{empty();list<T> tmp(lt.begin(), lt.end());swap(tmp);
}

 析构函数

我们可以调用clear函数清理容器当中的数据，然后将头结点释放，最后将头指针置空即可

void clear()//将头结点释放
{iterator it = begin();while (it != end()){//it = erase(it);erase(it++);}
}

~list()
{clear();//将头结点释放delete _head;//最后将头指针置空即可_head = nullptr;
}

赋值重载

通过编译器自动调用list的拷贝构造函数构造出来一个list对象，然后调用swap函数将原容器与该list对象进行交换即可。

list<T>& operator=(list<T> tmp)
{swap(tmp);return *this;
}

insert  /  erase

insert函数的作用时在指定迭代器的位置之前插入一个数据。

iterator insert(iterator pos, const T& x)
{Node* node = pos._node;//记录当前节点Node* prev = node->_prev;//记录前驱节点Node* newnode = new Node(x);//记录要插入节点newnode->_prev = prev;newnode->_next = node;prev->_next = newnode;node->_prev = newnode;return iterator(newnode);
}

erase函数用来删除指定迭代器位置的数据。

iterator erase(iterator pos)
{assert(pos != end());//防止删除头节点Node* del = pos._node;//记录要删除节点Node* prev = del->_prev;//记录前驱节点Node* next = del->_next;//记录后续节点prev->_next = next;next->_prev = prev;return iterator(next);//返回所给迭代器pos的下一个迭代器，防止迭代器失效
}

push_/pop_(尾插/尾删/头插/头删)


void push_back(const T& val) 
{ insert(end(), val); 
}void pop_back() 
{ erase(--end()); 
}void push_front(const T& val) 
{ insert(begin(), val); 
}void pop_front() 
{ erase(begin()); 
}

begin和end（在已建立迭代器的基础上）

begin函数返回的是第一个有效数据的迭代器，end函数返回的是最后一个有效数据的下一个位置的迭代器。

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

迭代器实现

对于list来说，它的数据不是连续存储的而是通过一个一个节点通过指针连接到一起的，所以，_head++，并不能到下一个数据的位置，但是可以通过_head = _head->_next实现，所以这里我们可以使用节点的指针单独封装一个类，通过运算符重载模拟指针的行为。

（vector迭代器可以使用原生指针来实现，因为vector的空间时连续的，可以直接支持运算符++的重载，_start时指向第一个数据的指针，_start++就指向下一个位置了。）

迭代器类模板参数说明

template<class T, class Ref, class Ptr>

 在list的模拟实现当中，我们typedef了两个迭代器类型，普通迭代器和const迭代器

typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;

所以，迭代器类的模板参数列表当中的Ref和Ptr分别代表的是解引用类型和指针类型。

当我们使用普通迭代器时，编译器就会实例化出一个普通迭代器对象；当我们使用const迭代器时，编译器就会实例化出一个const迭代器对象。

template <class T,class Ref,class Ptr>
struct ListIterator
{typedef ListNode<T> Node;Node* _node;typedef ListIterator<T,Ref,Ptr> self;ListIterator(Node* node):_node(node){}self& operator++(){_node = _node->_next;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}bool operator!=(const self& node){return _node != node._node;}bool operator==(const self& node){return _node == node._node;}Ptr operator->(){return &_node->_data;}
};


struct Pos{int _row;int _col;Pos(int row = 0, int col = 0):_row(row),_col(col){}};void test_list2(){list<Pos> lt1;lt1.push_back(Pos(100, 100));lt1.push_back(Pos(200, 200));lt1.push_back(Pos(300, 300));list<Pos>::iterator it = lt1.begin();while (it != lt1.end()){//cout << (*it)._row << ":" << (*it)._col << endl;// 为了可读性，省略了一个->cout << it->_row << ":" << it->_col << endl;//cout << it->->_row << ":" << it->->_col << endl;cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;++it;}cout << endl;}

list包含在头文件

因为list类是一种模板，不建议list内部内容函数声明定义分开来写，所以都包含在同一个文件当中

#pragma once
#include<assert.h>namespace bit
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _data;ListNode(const T& data = T()):_next(nullptr),_prev(nullptr),_data(data){}};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;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;}Ref operator*(){return _node->_data;}Ptr 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//{//	typedef ListNode<T> Node;//	typedef ListConstIterator<T> Self;//	Node* _node;//public://	ListConstIterator(Node* node)//		:_node(node)//	{}//	// ++it;//	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;//	}//	//*it//	const T& operator*()//	{//		return _node->_data;//	}//	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 list{typedef ListNode<T> Node;public:// 不符合迭代器的行为，无法遍历//typedef Node* iterator;//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(){//iterator it(_head->_next);//return it;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);}list(){_head = new Node();_head->_next = _head;_head->_prev = _head;}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);}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}// 没有iterator失效iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;// prev  newnode  curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}// erase 后 pos失效了，pos指向节点被释放了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);}private:Node* _head;};void Func(const list<int>& lt){// const iterator const 迭代器不能普通迭代器前面加const修饰// const 迭代器目标本身可以修改，指向的内容不能修改 类似const T* p list<int>::const_iterator it = lt.begin();while (it != lt.end()){// 指向的内容不能修改//*it += 10;cout << *it << " ";++it;}cout << endl;}void test_list1(){list<int> lt1;// 按需实例化（不调用就不实例化这个成员函数）lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);Func(lt1);//ListIterator<int> it = lt1.begin();list<int>::iterator it = lt1.begin();while (it != lt1.end()){*it += 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt1){cout << e << " ";}cout << endl;}struct Pos{int _row;int _col;Pos(int row = 0, int col = 0):_row(row),_col(col){}};void test_list2(){list<Pos> lt1;lt1.push_back(Pos(100, 100));lt1.push_back(Pos(200, 200));lt1.push_back(Pos(300, 300));list<Pos>::iterator it = lt1.begin();while (it != lt1.end()){//cout << (*it)._row << ":" << (*it)._col << endl;// 为了可读性，省略了一个->cout << it->_row << ":" << it->_col << endl;//cout << it->->_row << ":" << it->->_col << endl;cout << it.operator->()->_row << ":" << it.operator->()->_col << endl;++it;}cout << endl;}void test_list4(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.push_back(5);Func(lt1);lt1.push_front(10);lt1.push_front(20);lt1.push_front(30);Func(lt1);lt1.pop_front();lt1.pop_front();Func(lt1);lt1.pop_back();lt1.pop_back();Func(lt1);lt1.pop_back();lt1.pop_back();lt1.pop_back();lt1.pop_back();//lt1.pop_back();Func(lt1);}
}

 部分摘自— list模拟实现

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

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

相关文章

React@16.x（17）Portals

React@16.x（17）Portals

目录 1&#xff0c;使用2&#xff0c;事件冒泡 一句话总结&#xff1a;和 Vue3 的 Teleport 一个效果。 1&#xff0c;使用 import React, { PureComponent } from "react"; import ReactDOM from "react-dom";// 返回一个 React 元素&#xff08;ReactNo…
阅读更多...
基于Cortex的MCU设计

基于Cortex的MCU设计

基于Cortex的MCU设计 今日更新的存货文档&#xff0c;发现日更文章还是很花时间的。保证一周更新三篇文章就行啦&#xff0c;本篇文章的内容起始主要取自于《Cortex-M3 权威指南》和知网下载的论文。写的不详细&#xff0c;想进一步了解的就去看这篇文档或网上找别的资料&#…
阅读更多...
爬虫利器Frida RPC入门——夜神模拟器环境篇

爬虫利器Frida RPC入门——夜神模拟器环境篇

Frida是一款轻量级HOOK框架&#xff0c;可用于多平台上&#xff0c;例如android、windows、ios等。 frida分为两部分&#xff0c;服务端运行在目标机上&#xff0c;通过注入进程的方式来实现劫持应用函数&#xff0c;另一部分运行在系统机器上。frida上层接口支持js、python、…
阅读更多...
香橙派 AIpro开发体验：使用YOLOV8对USB摄像头画面进行目标检测

香橙派 AIpro开发体验：使用YOLOV8对USB摄像头画面进行目标检测

香橙派 AIpro开发体验&#xff1a;使用YOLOV8对USB摄像头画面进行目标检测 前言一、香橙派AIpro硬件准备二、连接香橙派AIpro1. 通过网线连接路由器和香橙派AIpro2. 通过wifi连接香橙派AIpro3. 使用vscode 通过ssh连接香橙派AIpro 三、USB摄像头测试1. 配置ipynb远程开发环境1.…
阅读更多...
C语言：（动态内存管理）

C语言：（动态内存管理）

目录 动态内存有什么用呢 malloc函数 开辟失败示范 free函数 calloc函数 realloc函数 当然realooc也可以开辟空间 常⻅的动态内存的错误 对NULL指针的解引⽤操作 对动态内存开辟的空间越界访问 对⾮动态开辟内存使⽤free释放 使⽤free释放⼀块动态开辟内存的⼀部分 …
阅读更多...
Mac逆向Electron应用

Mac逆向Electron应用

工具库 解压asar文件 第一步 找到应用文件夹位置 打开活动监视器&#xff1a; 搜索相关应用 用命令行打开刚才复制的路径即可 open Applications/XXX.app/Contents/Resources/app第二步 解压打包文件 解压asar文件
阅读更多...
[深度学习]yolov10+deepsort+pyqt5实现目标追踪

[深度学习]yolov10+deepsort+pyqt5实现目标追踪

YOLOv10DeepSORTPyQt5实现目标追踪系统 在现代智能监控系统中&#xff0c;目标追踪技术扮演着至关重要的角色。结合YOLOv10&#xff08;一种先进的实时目标检测算法&#xff09;与DeepSORT&#xff08;一种多目标追踪算法&#xff09;&#xff0c;并通过PyQt5构建用户界面&…
阅读更多...
StretchSense：将手部动作无缝集成到Xsens全身动捕系统中

StretchSense：将手部动作无缝集成到Xsens全身动捕系统中

在动画制作中逼真的手部动作可以大幅提升角色的情感表现能力&#xff0c;这将使观众更加轻易的走进角色&#xff0c;感受角色的情感变化并更加快速的了解角色的性格特点。如性格外向的角色将拥有更加复杂的手部动作表达。因此有效加强角色的手部动画真实度有助于吸引更多的观众…
阅读更多...
element table表格行列合并span-method，根据数据动态行列合并

element table表格行列合并span-method，根据数据动态行列合并

表格行列合并需要用到 table的方法 span-method 根据数据来进行动态的行列合并&#xff0c;实例如下&#xff1a; <el-table:data"tableData":span-method"objectSpanMethod" style"width: 100%"><el-table-columnprop"key"l…
阅读更多...
PCIe的链路状态

PCIe的链路状态

目录 概述 链路训练的目的 两个概念 下面介绍LTSSM状态机 概述 PCie链路的初始化过程较为复杂&#xff0c;Pcie总线进行链路训练时&#xff0c;将初始化Pcie设备的物理层&#xff0c;发送接收模块和相关的链路状态信息&#xff0c;当链路训练成功结束后&#xff0c;PCIe链…
阅读更多...
xcode开发swift允许发送http请求设置

xcode开发swift允许发送http请求设置

Xcode 现在新建项目默认只支持HTTPS请求&#xff0c;认为HTTP请求不安全&#xff0c;所以不支持。但是开发环境一般都是http模式&#xff0c;所以需要单独配置才可以访问。 需要到项目的设置里面&#xff0c;点击info&#xff0c;如果没有App Transport Security Setting这一项…
阅读更多...
c# - - - winform 右下角气球提示通知

c# - - - winform 右下角气球提示通知

c# - - - winform 右下角气球提示通知 winform 右下角气球提示通知 1.1 winform 右下角气球提示通知 在工具箱中点击 NotifyIcon 控件&#xff0c;拖动到 Form1 窗体上添加这个控件。 在“提示”按钮的点击事件中写气球提示通知内容。 public partial class Form1 : Form {…
阅读更多...
民国漫画杂志《时代漫画》第29期.PDF

民国漫画杂志《时代漫画》第29期.PDF

时代漫画29.PDF: https://url03.ctfile.com/f/1779803-1248635405-bf3c87?p9586 (访问密码: 9586) 《时代漫画》的杂志在1934年诞生了&#xff0c;截止1937年6月战争来临被迫停刊共发行了39期。 ps: 资源来源网络!
阅读更多...
《探索Stable Diffusion：AI绘画的创意之路与实战秘籍》

《探索Stable Diffusion：AI绘画的创意之路与实战秘籍》

《Stable Diffusion AI 绘画从提示词到模型出图》介绍了 Stable Diffusion AI 绘画工具及其使用技巧。书中内容分为两部分&#xff1a;“基础操作篇”&#xff0c;讲解了 SD 文生图、图生图、提示词、模型、ControlNet 插件等核心技术的应用&#xff0c;帮助读者快速从新手成长…
阅读更多...
算法思想总结：哈希表

算法思想总结：哈希表

一、哈希表剖析 1、哈希表底层&#xff1a;通过对C的学习&#xff0c;我们知道STL中哈希表底层是用的链地址法封装的开散列。 2、哈希表作用&#xff1a;存储数据的容器&#xff0c;插入、删除、搜索的时间复杂度都是O&#xff08;1&#xff09;&#xff0c;无序。 3、什么时…
阅读更多...
YOLOv10训练教程—用YOLOv10训练自己的数据集

YOLOv10训练教程—用YOLOv10训练自己的数据集

文章目录 YOLOv10简介亮点模型介绍 下载源码环境配置准备数据集训练模型&#xff1a;命令行py文件 验证模型推理参考文献 ✨✨✨✨立志真正解决大家问题&#xff0c;只写精品博客文章&#xff0c;感谢关注&#xff0c;共同进步✨✨✨✨ YOLOv9还没捂热乎&#xff0c;YOLOv10就推…
阅读更多...
【传知代码】探索视觉与语言模型的可扩展性（论文复现）

【传知代码】探索视觉与语言模型的可扩展性（论文复现）

前言&#xff1a;在数字化时代的浪潮中&#xff0c;我们见证了人工智能&#xff08;AI&#xff09;技术的飞速发展&#xff0c;其中视觉与语言模型作为两大核心领域&#xff0c;正以前所未有的速度改变着我们的生活和工作方式。从图像识别到自然语言处理&#xff0c;从虚拟现实…
阅读更多...
防雷接地测试方法及注意事项

防雷接地测试方法及注意事项

一、防雷接地的测试方法 检测避雷针、高层建筑物等设施的接地电阻&#xff0c;接雷后能否顺畅导入大地。 1、你先找到防雷接地网的接地引线或等电位联接箱。 2、用接地电阻测测试仪测接地电阻。 &#xff08;有两根测试桩0.4M的要插入泥土&#xff0c;一根距测试点20米&…
阅读更多...
抽屉式备忘录（共25041字）

抽屉式备忘录（共25041字）

Sing Me to Sleep <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>与妖为邻的备忘录</title&g…
阅读更多...
什么是Swagger UI ，swagger ui 的authorization怎么获取？

什么是Swagger UI ，swagger ui 的authorization怎么获取？

什么是Swagger UI Swagger UI 是一个用于可视化和交互式地展示API文档的工具。它是Swagger&#xff08;现称为OpenAPI&#xff09;生态系统的一部分&#xff0c;旨在帮助开发者和API用户更好地理解、测试和调试API。 主要功能和作用 1. API文档自动生成&#xff1a; Swagge…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发