【C++】手搓 list 容器

这篇具有很好参考价值的文章主要介绍了【C++】手搓 list 容器。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++】手搓 list 容器,从零开始的C++生活,c++,list,windows,算法,开发语言,数据结构,链表
送给大家一句话:

若结局非你所愿,就在尘埃落定前奋力一搏。—— 《夏目友人帐》

1 前言

List是C++标准模板库(STL)中的一个成员,其本质为带头双向循环链表。不同于连续的、紧密排列的数组容器Vector,List容器的内部是由双向链表构成的,使得它在插入和删除操作上,就如同行云流水一般顺畅,不需移动其它元素。

1.1 底层结构

List容器的底层结构,是一个经典的带头双向循环链表。每个节点包含:

  1. 数据
  2. 指向前一个节点的指针
  3. 指向后一个节点的指针。

这种结构赋予了List灵动的特性:它能够轻松地在任意位置增加或移除元素,而这种操作几乎是与容器大小无关的,体现了时间复杂度上的优势。但这种优势的代价是,与数组相比,List在访问元素时的速度会较慢,因为它需要从头开始遍历。这也决定了list的更适合频繁插入的动态数据。
来看STL源码中的节点结构:

template <class T>
struct __list_node {
  typedef void* void_pointer;
  void_pointer next;
  void_pointer prev;
  T data;
};

1.2 使用场景

List最适合的场景是那些需要频繁进行插入和删除操作的场合。
例如,如果你正在管理一个动态变化的列表,如任务调度、人员排队等场景,List的特性将大放异彩。但是如果你的应用场景更多地需要随机访问元素,那么向量(Vector)或者数组可能是更佳的选择。因为List的顺序访问性能相比之下会显得有些力不从心。

  • 所以如果需要频繁随机的访问数据,那么选择vector容器
  • 如果需要频繁插入删除数据,那么选择list容器
  • 排序不要选择list !!!其删除节点的过程就决定了其速度不会太快。

1.3 功能简介

功能简介我们可以参考STL官方库 :list文档介绍

  1. 插入与删除:List的插入和删除操作非常高效,它可以在任意位置快速地添加或移除元素,而不需要像连续内存容器那样进行大量元素的移动。
  2. 多种构造:类都应该包含多种构造函数
  3. 支持迭代器:迭代器是C++重要的特性,我们写的list 也一定要支持迭代器。

2 框架搭建

现在我们开始实现list 容器,首先先要思考一下框架结构:

  1. 首先我们需要一个节点结构体(类似源码中的节点)
  2. 其次我们的list 类要带一个头结点,让我们更方便进行插入删除操作

基本就是这样,现在我们开始手搓

2.1 节点类

// 节点 结构体
template<class T>
struct ListNode
{
	ListNode* _next;
	ListNode* _prev;
	T _data;

	ListNode(T x = T()) :
		_next(nullptr),
		_prev(nullptr),
		_data(x)
	{}
	//ListNode(T x = T()) 
	//{
	//	_next = nullptr;
	//	_prev = nullptr;
	//	_data = x;
	//}	
	~ListNode()
	{
		_next = nullptr;
		_prev = nullptr;
	}
};

这里使用模版来适配更多的情景,然后基本的数据,前后指针都很简单。在编写一个构造函数,==构造函数使用初始化列表,并不是必须使用。析构函数避免野指针出现,将指针赋值为nullptr就可以了。

2.2 list 类

我们先进行简单的框架书写,构造函数需要创建一个头结点,因为我们要创建双向循环链表,所以头尾都要指向头结点本身。 _size赋初值。

template<class T>
class list
{
public:
	//设置适配的节点
	typedef ListNode<T> Node;
	//空初始化
	void empty_init()
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
		_size = 0;
	}
	//构造函数
	list() :
	_head(nullptr)
	{
		empty_init();
	}
private:
	Node* _head;
	size_t _size;
};

接下来我们来逐步完成功能书写,由于我们还没有进行迭代器的书写

2.3 迭代器类

我们思考一下这里能不能使用原生指针来完成迭代器的操作(++ == != --)当然是不能的,因为链表的物理地址并不是连续的,对原生指针的++或–操作是没有意义的,所以我们需要自行编写迭代器类,对原生指针进行封装,来满足我们特殊的++和–操作。

	//这里的模板可以再次升级  先简单写一下
	template<class T>
	class ListIterator 
	{
	public:
		//重命名方便书写
		typedef ListNode<T> Node;
		typedef ListIterator<T> Self;
		Node* _node;
		ListIterator(Node* x ):
			_node(x)
		{}
		//操作符重载 前置++ 与 后置++的区别是参数是否带(int)
		//++t
		Self operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//t++
		Self operator++(int)
		{
			Self tmp(*this);//浅拷贝即可
			_node = _node->_next;
			return tmp;
		}
		//--t
		Self operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		//t--
		Self operator--(int)
		{
			Self tmp(*this);//浅拷贝即可
			_node = _node->_prev;
			return tmp;
		}
		//判断是否相等 比较指针地址是否相同即可
		bool operator!=(const Self& it)
		{
			return _node != it._node;
		}
		//判断是否相等 比较指针地址是否相同即可
		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
		// 解引用操作 *it 返回节点数据的引用 可以进行修改
		T& operator*()
		{
			return  _node->_data;
		}
		//因为指针才能使用-> 所以->要返回地址(指针)		
		T* operator->()//编译器会进行省略->
		{
			return &_node->_data;
		}
	};

这样迭代器类就大致写好了,那么一般我们的迭代器应该还要支持const,不然我们传入一个不可修改的链表(const list l),就会反生报错,那么我们还要书写一份const版的迭代器。如果进行编写,那么是不是会有大部分与刚才我们书写的迭代器重复(++ -- == != 都是一样的),只有operator*()operator->()返回值不一致:

  • 因为是常迭代器,使用场景是对const list<T> l进行操作,那么节点数据不可改变,所以不影响++ -- == != 这些操作,受影响的是operator*()operator->()返回值(该情况下链表本身是只读的,又因为不能将权限进行扩大,所以返回值应该也是只读的(const))。
  • 那这样就发现了不同常迭代器应该为 const T& operator*()const T* operator->() ,所以有没有一种办法可以简单解决呢,当然有了,我们设置一个新模版(带有三个参数),创建的时候就传入对应参数

我们将模版修改为这样,

 //reference 引用  pointer 指针
template<class T , class Ref ,class Ptr>

对应返回值也改变:

 	Ref operator*()
	{
		return  _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}

那么类实例化的时候传入对应参数就好了:

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

这样就实现了迭代器的创建,是不是就非常简洁了呢

3 功能实现

3.1 begin() 与 end()

使用迭代器即可,注意end()是头结点,因为遍历过程中,全部遍历后会回到头结点,所以直接判断是否为头结点就能控制结束位置。

//普通迭代器
typedef ListIterator<T, T&, T*> iterator;
//常迭代器
typedef ListIterator<T, const T&, const T*> const_iterator;

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

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

3.2 插入操作

插入操作我们很熟悉,步骤是创建一个新节点,然后通过改变指针指向来完成插入操作:
来看尾插操作,

void push_back(const T& x = T())
{
	//创建新节点
	Node* node = new Node(x);
	//找尾
	Node* tail = _head->_prev;
	//进行插入
	node->_next = _head;
	node->_prev = tail;
	
	tail->_next = node;
	_head->_prev = node;
	//别忘记大小++
	_size++;
}

任意位置插入,操作思路依然是对前后节点与新节点的指针指向进行操作,来完成插入。

void insert(iterator pos = begin(), T x = T())
{
	//创建新节点
	Node* node = new Node(x);
	//前节点 后节点
	Node* prev = pos._node->_prev;
	Node* next = pos._node;
	//处理新节点
	node->_prev = prev;
	node->_next = next;
	//出现前后节点
	prev->_next = node;
	next->_prev = node;
	//别忘记大小++
	_size++;
}		

头插,直接干脆调用insert就可以了

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

3.3 删除操作

删除操作,同样是使用指针操作,来达到删除的效果。注意要对删除的节点进行释放空间操作(delete),不然会发生内存泄漏!!!

尾删
void pop_back()
{
	Node* tail = _head->_prev;
	Node* prev = tail->_prev;

	prev->_next = _head;
	_head->_prev = prev;

	delete tail;
	_size--;
}
//头删
void pop_front()
{
	Node* head = _head->_next;
	Node* next = head->_next;

	_head->_next = next;
	next->_prev = _head;

	delete head;
	_size--;
}
//任意位置删除
iterator erase(iterator pos)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	prev->_next = next;
	next->_prev = prev;
	delete cur;

	_size--;
	return iterator(next);
}

需要注意的是,任意位置删除因为使用了迭代器,删除后会造成迭代器失效,所以需要更新迭代器,返回被删除节点的下一个节点的迭代器即可。

3.4 拷贝构造

拷贝构造直接将数据一个一个插入到该链表中即可:

list(const list<T>& l)
{
	empty_init();
	iterator it = l.begin();
	while (it != l.end())
	{
		push_back(*it);
		it++;
	}
}

这样十分方便快捷!!!

3.5 析构函数

void clear()
{
	//依次释放
	iterator it = begin();
	while (it != end())
	{
		
		it = erase(it);
	}
}
~list()
{
	clear();
	//需要单独释放头结点空间
	delete _head;
	_head = nullptr;
}

3.6 其他函数

返回大小:

size_t size() const { return _size; }

判断是否为空:

bool empty()
{
	return _size == 0;
}

清空数据:

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

4 总结

本文我们实现了STL库中重要的list 的模拟实现,其中最重要莫过于迭代器的封装类的书写,这是前所未有的操作(对于我来说,我是第一次使用这种结构)。通过list 的模拟实现也帮我们巩固了类与对象的知识,也强化了指针操作的思路。欢迎大家讨论分析。文章来源地址https://www.toymoban.com/news/detail-846832.html

Thanks♪(・ω・)ノ谢谢阅读!!!

下一篇文章见!!!

到了这里,关于【C++】手搓 list 容器的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 从零开始的种田生活-Unity游戏开发

    大家好,这里是暴躁老哥酒九。最近了我们的童年记忆《摩尔庄园》在手机上面复活了,不知道大家有没有沉迷于种菜无法自拔呢(反正我是累了)。 种田才是这个游戏本质吧~ 在《摩尔庄园》中了为我们玩家提供了很多的玩法比如:钓鱼,烹饪,开餐厅,庄园和玩家自身装

    2024年02月02日
    浏览(46)
  • 从零开始的嵌入式Linux生活(一) 背景介绍

    近年来(截至2023年3月),随着各种各样的因素:实体经济、米国制裁、芯片热、智能汽车等, 嵌入式软件开发(Embedded Software)越来越火热,众多的芯片公司、应用方案公司、甚至是代理商公司如雨后春笋般成立; 各大招聘网站上“嵌入式开发”“驱动开发”等岗位也成为

    2023年04月09日
    浏览(44)
  • 从零开始学Docker(二):启动第一个Docker容器

    宿主机环境:RockyLinux 9 这个章节不小心搞成命令学习了,后面在整理成原理吧 我们可以看到,第一个时官方认证构建的nginx  如下,这里我们使用的是简单的pull操作,默认下载的是最新版本 latest  拉取镜像后查看镜像列表  运行该nginx镜像,创建一个具体的容器,然后在这

    2024年02月14日
    浏览(39)
  • 从零开始的知识图谱生活,构建一个百科知识图谱,完成基于Deepdive的知识抽取、基于ES的简单语义搜索、基于 REfO 的简单KBQA

    项目设计集合(人工智能方向):助力新人快速实战掌握技能、自主完成项目设计升级,提升自身的硬实力(不仅限NLP、知识图谱、计算机视觉等领域) :汇总有意义的项目设计集合,助力新人快速实战掌握技能,助力用户更好利用 CSDN 平台,自主完成项目设计升级,提升自

    2024年02月15日
    浏览(56)
  • 从零开始学习 Java:简单易懂的入门指南之Collection集合及list集合(二十一)

    1.1数组和集合的区别 相同点 都是容器,可以存储多个数据 不同点 数组的长度是不可变的,集合的长度是可变的 数组可以存基本数据类型和引用数据类型 集合只能存引用数据类型,如果要存基本数据类型,需要存对应的包装类 1.2集合类体系结构 1.3Collection 集合概述和使用 Collec

    2024年02月10日
    浏览(40)
  • 从零开始配置vim(Windows版)

    事情是这样的,之前linux下vim用习惯了...然后就给自己win下vscode也装了个vim插件,用下来还是感觉不顺手,并且处理太多文本时有明显卡顿,于是乎自己配了下win版的vim。 不过好像也 并不是从零开始 的...初始基础版的.vimrc有copy他们版本,在此基础上进行了各类配置。 先放个

    2024年01月20日
    浏览(38)
  • 从零开始的C++(六)

    1.类和对象补充: 静态成员,有静态成员函数和静态成员变量,特点是不为类的某个对象所有,而是为同类所有对象共有。因为是为同类对象共同拥有,所以计算对象的大小的时忽略静态成员。因为静态成员是放在静态区,对象的作用只是确定类域,所以(类名*)0-静态成员

    2024年02月07日
    浏览(40)
  • 从零开始的C++(十一)

    vector的模拟实现: 1.构造函数: 对象的成员使用了参数列表,防止随机值引发异常。同时,对于传同类型对象的构造函数,复用了传迭代器的构造函数创建临时对象,然后交换this所指对象和临时对象的成员的值,防止浅拷贝,并且利用临时变量销毁原本this对象的成员的内容

    2024年02月07日
    浏览(38)
  • 从零开始的网络安全--Windows系统安全(1)

    1、用户账户概述 用户账户用来记录用户的用户名和口令、隶属的组等信息 每个用户账户包含唯一的登录名和对应的密码 不同的用户身份拥有不同的权限 操作系统根据SID识别不同用户 每个用户拥有唯一安全标识符(SID) 用户权限通过用户的SID来记录 查看命令为:whoami /us

    2024年01月22日
    浏览(47)
  • 从零开始c++精讲:第三篇——内存管理

    为什么要有内存区域的划分呢? 因为不同数据有不同的存储需求,各区域满足不同的需求。 栈(堆栈) :一般存放临时用的,比如非静态局部变量/函数参数/返回值等,栈是向下增长的。 堆 :有动态使用的需求,需要的时候你给我,不需要的时候你释放。也就是出了函数作

    2024年01月21日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包