C++list模拟实现

C++list模拟实现

  • list接口总结
  • 结点类的模拟实现
  • 迭代器的模拟实现
    • 迭代器模板参数
    • 迭代器类中的构造函数
    • 迭代器类中的运算符重载
      • operator++和operator - -
      • operator!= 和operator==
      • operator*
      • operator->
      • 总览
  • list 类
      • 构造函数
      • 拷贝构造函数
      • 赋值运算符重载operator=
      • clear()
      • 析构函数
    • 迭代器相关函数
      • begin和end
  • 与容器修改有关函数
      • insert 插入
      • erase 删除
      • push_back()尾插
      • pop_back 尾删
      • push_front 头插
      • pop_front 头删
      • size

list接口总结

namespace bite
{
    // List的节点类
    template<class T>
    struct ListNode
    {
        ListNode(const T& val = T());
        ListNode<T>* _pre;
        ListNode<T>* _next;
        T _date;
    };

    //List的迭代器类
    template<class T, class Ref, class Ptr>
    class Listiterator
    {
        typedef ListNode<T>* Node;
        typedef Listiterator<T, Ref, Ptr> Self;
    public:
        Listiterator(Node* Node);
        Ref operator*();
        Ptr operator->();
        Self& operator++();d
        Self operator++(int);
        Self& operator--();
        Self& operator--(int);
        bool operator!=(const Self& l);
        bool operator==(const Self& l);
    private:
        Node _node;
    };

    //list类
    template<class T>
    class list
    {
        typedef ListNode<T> Node;
    public:
        typedef Listiterator<T, T&, T*> iterator;
        typedef Listiterator<T, const T&, const T&> const_iterator;
    public:
        ///
        // List的构造
        void init();
        list();
        list(const list<T>& val)
        list<T>& operator==(list<T> val)
        ~list();
        ///
        // List Iterator
        iterator begin();
        iterator end();
        const_iterator begin();
        const_iterator end();

        ///
        // List Capacity
        size_t size()const;
        bool empty()const;

        
        // List Modify
        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()); }
        // 在pos位置前插入值为val的节点
        iterator insert(iterator pos, const T& val);
        // 删除pos位置的节点,返回该节点的下一个位置
        iterator erase(iterator pos);
        void clear();
        void swap(list<T>& lt);
    private:
        Node* _head;
        size_t _size;
    };
};

结点类的模拟实现

STL中的list为带头双向循环链表。
如图:
在这里插入图片描述
所以我们要实现list链表之前还要实现结点类。 结点中要存储前一个结点的地址和后一个结点的地址、还有数据。因此我们只需要设定成员变量和构造函数就行。

template <class T>  //设定模板结点中的数据类型可以是不同的
struct ListNode
{
	typedef ListNode<T> Node;
	ListNode(const T& val = T())//构造函数
		:_prev(nullptr)
		,_next(nullptr)
		,_date(val)
	{}
	Node* _prev;//前驱指针
	Node* _next;//后驱指针
	T _date;//数据

};

迭代器的模拟实现

我们在string和vector中迭代器模拟都是直接给定模板指针。但是到了list中我们就需要实现一个迭代器类型。why?
这是因为我们在string和vector中数据的存储都是存放在一块连续的空间。我们可以同过指针进行对数据的增删查改。
在这里插入图片描述
list并不是存放一块连续的空间,而是通过结点存放下一个结点的地址一个一个连结起来的。 所以我们不能通过指针来实现链表的增删查改。
迭代器是一种用于遍历集合或容器中元素的接口,它可以隔离对容器的访问方式和底层实现,从而实现解耦。迭代器可以依次访问容器中的每一个元素,而无需了解容器的内部细节。
既然我们的指针不能满足迭代器的行为,那我们就将指针封装成类,使其能够满足迭代器的需要。

迭代器模板参数

迭代器我们给处三个模板参数。

 template<class T, class Ref, class Ptr>

实现两个迭代器,一个iterator 和另一个 const_iterator。

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

从这里我们可以看出,Ref 代表的是引用类型和指针类型。

迭代器类中的构造函数

我们迭代器的底层就是对指针进行的封装,因此成员变量就一个就是结点指针。

Listiterator(Node* node)
	:_node(node)
{}

迭代器类中的运算符重载

operator++和operator - -

list的迭代器没必要实现operator+,只需要实现自增和和自减
自增:

//前置++
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;
}

operator!= 和operator==

实现两个迭代器之间的比较。

bool operator!=(const self& val)
{
	return _node != val._node;
}

bool operator==(const self& val)
{
	return _node == val._node;
}

operator*

当我们使用解引用操作符,想要得到的是这个地址所指向的数据。所以我们operator* 返回该地址所指向的数据就行。

Ref operator*()
{
	return _node->_date;
}

operator->

我们在使用list时,如果list内结点存储的数据不是内置类型,而是自定义类型,例如Date日期类。我们访问Date类中的成员,就需要用到operator->。
例如:

struct A //自定义类型
{
	A(int x=0 ,int y =0)
		:_aa1(x)
		,_aa2(y)
	{}
	int _aa1;
	int _aa2;
};
void test()
{
	A aa1(0,0);
	list<A> lt;
	lt.push_back(aa1);
	lt.push_back(A(1, 1));
	lt.push_back({ 2,2 });
	lt.push_back({3,3});

	list<A>::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << it->_aa1 << " " << it->_aa2 << endl;;
		it++;
	}
}

operator->只需要返回结点数据的地址就行。

Ptr operator->()
{
	return &_node->_date;
}

这里有人就可能发现,这种方式访问自定义类型成员需要用到两个->。
在这里插入图片描述

在这里插入图片描述

这里其实是忽略了一个->,两个->第一个运算符重载的调用是指向A* ,另一个是原生指针的调用。为了让代码有良好的可读性,编译器做了特殊处理,忽略了一个->。

总览

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

	Ref operator*()
	{
		return _node->_date;
	}

	Ptr operator->()
	{
		return &_node->_date;
	}

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

	bool operator!=(const self& val)
	{
		return _node != val._node;
	}

	bool operator==(const self& val)
	{
		return _node == val._node;
	}

};

list 类

构造函数

list是一个双向带头循环链表,list初始化需要设置一个哨兵位,并使其的前驱指针和后驱指针都指向自己。

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

	_size = 0;
}
list()
{
	init();
}

拷贝构造函数

list的拷贝构造就是根据所给的对象,拷贝处一个新的对象。拷贝构造函数我们先给一个头结点使其前驱指针和后驱指针都指向自己,然后再遍历对象,让对象中的结点一个一个尾插入到新的list中去。

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

赋值运算符重载operator=

我们这里直接使用现代写法。利用传入的参数通过编译器自动调用list构造函数构造出一个list对象,
再使用swap使其与原来的容器进行交换。

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

clear()

clear函数只需要将链表中的结点和数据清理即可,给一个迭代器使其指向头结点,然后遍历链表将结点一个一个删除,除了哨兵位以外。

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

析构函数

析构函数首先我们先将list容器中的数据清除,让后在释放哨兵位和让_size归零。

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

迭代器相关函数

begin和end

在这里我们需要清楚的是begin为哨兵位的下一个结点,而end就是哨兵位。

iterator begin()
{
	return _head->_next;
}

iterator end()
{
	return _head;
}

还有const begin 和end

const_iterator begin() const
{
	return _head->_next;
}

const_iterator end() const 
{
	return _head;
}

与容器修改有关函数

insert 插入

insert函数作用是在pos位置插入一个新的结点。
如图:
在这里插入图片描述
我们要在pos位置插入一个新的结点(newnode)就得让新结点前驱指针指向pos结点前一个结点(prev),让prev的后驱指针指向newnode。newnode后驱指针指向pos结点,pos前驱指针指向newnode。

void insert(iterator pos , const T& val)
{
	Node* newnode = new Node(val);
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	
	newnode->_next = cur;
	cur->_prev = newnode;
	newnode->_prev = prev;
	prev->_next = newnode;

	_size++;

}

erase 删除

erase就是删除pos位置的结点。
如图:
在这里插入图片描述

iterator erase(iterator pos)
{
	assert(pos != _head);
	Node* del = pos._node;
	Node* prev = del->_prev;
	Node* next = del->_next;
	
	prev->_next = next;
	next->_prev = prev;

	delete del;
	--_size;

	return iterator(next);
}

注意: erase还要注意迭代器失效的问题因此我们的返回值指向的是下一个结点。

push_back()尾插

双向带头循环链表的尾插比较容易理解。新建一个结点使其的前驱指针指向尾结点,尾结点的后驱结点指向新的结点。新结点的后驱指针指向哨兵位,哨兵位的前驱指针指向新结点,再++_size。
在这里插入图片描述

void push_back(const T& val)
{
	Node* newnode = new Node(val);
	Node* tail = _head->_prev;

	newnode->_prev = tail;
	tail->_next = newnode;

	newnode->_next = _head;
	_head->_prev = newnode;
	_size++;
}

还可以复用insert函数,是push_back函数变得简单。

 void push_back(const T& val) 
 { 
    insert(end(), val); 
 }   

pop_back 尾删

我们这里直接复用erase函数。

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

push_front 头插

头插也是复用insert函数。

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

pop_front 头删

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

size

返回结点个数。

size_t size()
{
	return _size;
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

高精度定时器中 single-shot 计数模式不工作

1. 问题提出 客户使用 STM32G474 的高精度定时器&#xff0c;基于 CubeMX 进行外设配置与代码生成&#xff0c;将某个子定时器的计数方式设置为 retriggerable single shot 方式&#xff0c;发现该子定时器无 PWM 输出&#xff0c;在调试模式下发现该子定时器的计数器一直为 0…

2024MathorCup(妈妈杯) C题完整思路+数据集+完整代码+高质量成品论文

C题物流网络分中心货量预测及人员排班 &#xff08;完整的资料数据集代码在文末&#xff09; 电商物流网络在订单履约中由多个环节组成&#xff0c;其中&#xff0c;分拣中心作为网络的中 间环节&#xff0c;需要将包裹按照不同流向进行分拣并发往下一个场地&#xff0c;最终使…

「每日跟读」英语常用句型公式 第10篇

「每日跟读」英语常用句型公式 第10篇 1. It goes without saying that __ 毋庸置疑的是 ______ It goes without saying that hard work pays off(毋庸置疑的是&#xff0c;努力工作会有回报) It goes without saying that health is the most important wealth(毋庸置疑的…

C++第十五弹---string基本介绍(一)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】 目录 1、什么是STL 2、STL的版本 3、STL的六大组件 4、STL的重要性 5、如何学习STL 6、STL的缺陷 7、为什么学习string类 7.1、C语言中的字符串…

节省30%成本,宝马使用 NVIDIA Omniverse 构造的数字孪生虚拟汽车工厂,实现降本增效

在数字化转型过程中&#xff0c;汽车制造商宝马集团将工业 AI 的力量运用到整个生产网络&#xff0c;与NVIDIA Omniverse平台共同构建并运行工业元宇宙应用。 宝马集团董事Milan Nedeljković在GTC主题演讲会中&#xff0c;与NVIDIA创始人兼首席执行官黄仁勋共同展示了Omniver…

YOLOv8打印模型结构配置信息并查看网络模型详细参数:参数量、计算量(GFLOPS)

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…

LeetCode-1143. 最长公共子序列【字符串 动态规划】

LeetCode-1143. 最长公共子序列【字符串 动态规划】 题目描述&#xff1a;解题思路一&#xff1a;动规五部曲解题思路二&#xff1a;1维DP解题思路三&#xff1a;0 题目描述&#xff1a; 给定两个字符串 text1 和 text2&#xff0c;返回这两个字符串的最长 公共子序列 的长度。…

TSINGSEE青犀AI智能分析网关V4吸烟/抽烟检测算法介绍及应用

抽烟检测AI算法是一种基于计算机视觉和深度学习技术的先进工具&#xff0c;旨在准确识别并监测个体是否抽烟。该算法通过训练大量图像数据&#xff0c;使模型能够识别出抽烟行为的关键特征&#xff0c;如烟雾、手部动作和口部形态等。 在原理上&#xff0c;抽烟检测AI算法主要…

【目标检测数据集】城市街道垃圾堆相关数据集

一、GarbageOverflow&#xff1a;城市街道垃圾堆数据集 该垃圾堆数据集是通过爬虫从网上进行爬取得到的&#xff0c;一共包含1188张图片&#xff0c;有2个类别&#xff0c;分别为[overflow, No Overflow]&#xff0c;两个标签的数量分别为1734个标签和414个标签。部分数据集及…

中国历年GDP统计-探数API统计

数据介绍 时间维度&#xff1a;1978年-2021年 单位&#xff1a;亿元 该数据来源于国家统计局发布的中国统计年鉴2021&#xff0c;为按当年价格计算的中国历年GDP以及人均GDP。 数据说明&#xff1a; 数据来源于国家统计局。

【更新】全国省级-新质生产力数据集(2010-2022年)

01、数据简介 新质生产力&#xff0c;又称为新型生产力&#xff0c;是指在现代科技和经济社会发展的推动下&#xff0c;由新的生产要素、生产方式、生产关系等构成的具有新质特点的生产力。这种生产力突破了传统生产力的局限&#xff0c;具有更高的效率和创造力&#xff0c;是…

题目 2694: 蓝桥杯2022年第十三届决赛真题-最大数字【暴力解法】

最大数字 原题链接 &#x1f970;提交结果 思路 对于每一位&#xff0c;我我们都要尽力到达 9 所以我们去遍历每一位, 如果是 9 直接跳过这一位 如果可以上调到 9 我们将这一位上调到 9 &#xff0c;并且在a 中减去对应的次数 同样的&#xff0c;如果可以下调到 9&#xff0c;我…

黄金基金和黄金有什么区别?

黄金基金本质上是一种投资工具&#xff0c;它通过间接投资黄金或与其紧密相关的金融衍生品来反映黄金市场的表现。不同于直接持有实物黄金&#xff0c;投资者购买黄金基金并不涉及实体黄金的保管问题&#xff0c;而是将资金交由专业的基金管理人管理&#xff0c;由他们代表投资…

Input DropDown 拼接成 select组件(基于antd和react)

前言&#xff1a;为什么不直接用select&#xff0c;还要舍近求远搞inputdropdown这种缝合怪&#xff0c;是因为antd的select不支持选中项再编辑&#xff0c;效果如图 比如&#xff1a;选中的lucy文案变成了placeholder不能再编辑了 封装此组件虽然比较简单&#xff0c;但还是有…

一文读懂Partisia Blockchain,被严重低估的隐私区块链生态

在今年 3 月&#xff0c;隐私公链 Partisia Blockchain 迎来了重要的进展&#xff0c;该生态通证 $MPC 上线了交易所&#xff0c;目前 $MPC 通证可以在 Kucoin、Gate、BitMart、Bitfinex、Bitture 等平台交易&#xff0c;并将在不久后上线 MEXC 平台。 在上个月上线市场至今&am…

中颖51芯片学习4. 可编程计数器阵列PCA0

中颖51芯片学习4. 可编程计数器阵列PCA0 一、PCA介绍1. PCA简介2. SH79F9476的PCA0特性3. PCA0 功能4. 时钟5. PCA0原理框图6. 工作方式 二、PCA0寄存器1. PCA0标志寄存器2. PCA使能寄存器3. PCA0方式寄存器4. P0CPMn PCA捕捉/比较寄存器5. P0FORCE强制输出控制寄存器6. PCA0计…

期货量化交易软件:MQL5 中的范畴论 (第 15 部分)函子与图论

概述 在上一篇文章中&#xff0c;我们目睹了前期文章中涵盖的概念&#xff08;如线性序&#xff09;如何视作范畴&#xff0c;以及为什么它们的“态射”在与其它范畴相关时即构成函子。在本文中&#xff0c;我们赫兹量化软件将阐述来自前期文章中的概括&#xff0c;即通过查看…

三方库移植之NAPI开发[2]C/C++与JS的数据类型转

通过NAPI框架进行C/C与JS数据类型的转换 OpenHarmony NAPI将ECMAScript标准中定义的Boolean、Null、Undefined、Number、BigInt、String、Symbol和Object八种数据类型&#xff0c;以及函数对应的Function类型&#xff0c;统一封装成napi_value类型&#xff0c;下文中表述为JS类…

基于LNMP部署wordpress

目录 一.环境准备 二.配置源并安装 三.配置Nginx 四.配置数据库 五.上传源码并替换 六.打开浏览器&#xff0c;输入虚拟机ip访问安装部署 七.扩展增加主题 一.环境准备 centos7虚拟机 关闭防火墙和seliunx stop firewalld #关闭防火墙 setenforce 0 …

隐身打击云函数CDN对抗 | 应急响应

0x00 简介 在攻防演练中&#xff0c;使用云函数来隐藏 C&C 的 ip 地址已经成为了一种“标配” 在应急处置过程中&#xff0c;我们经常遇到 netstat -pantu | grep ip 无法找到安全设备关于红队外联的告警的情况 由于 C&C 的 ip 地址是一直变化的&#xff0c;所以常…