C++——list模拟实现

news/2025/2/23 6:46:17

目录

前言

一、list的结构

二、默认成员函数

构造函数

析构函数

clear

拷贝构造

赋值重载

swap

三、容量相关

empty

size

四、数据访问

front/back

五、普通迭代器

begin/end

六、const迭代器

begin/end

七、插入数据

insert

push_back

push_front

八、删除数据

erase

pop_back

pop_front

九、代码

总结

前言

我们之前讲解了string和vector的模拟实现，它们都是类似于顺序表的结构，string的底层是一个指针，一个元素的数量，一个空间总容量，而vector的底层是三个指针，这是它们结构上不一样的地方，但是实现的方法和原理还是大差不差的，那本篇我们来谈谈list，list的迭代器和之前的容器是不一样的，而且是一个双向带头循环链表，任意位置的插入删除效率都是O(1)，那我们开始正题

一、list的结构

list的结构是一个一个的节点，所以我们在定义的时候就要去定义一个节点

template<class T>
struct list_node
{
	list_node<T>* _prev;
	list_node<T>* _next;
	T _val;
};

_prev指向前一个节点

_next指向下一个节点

_val表示节点中存储的值

list_node这个类可以写成class，然后放成公有，也可以直接定义成struct的，因为这个类中的成员在list这个类中会用到，所以像这种节点类就直接放成公有就好

template<class T>
class list
{
	typedef list_node<T> Node;
private:
	Node* _head;
	size_t _size;
};

对于list这个类，我们需要先把list_node这个类给typedef，否则一直用他太长了，而且要带上模版参数，要注意的是，typedef也会受到访问限定符的限制，所以在外面是看不到Node的，然后我们用这个Node来定义一个头结点，也就是指向头节点的指针_head，然后还有一个成员函数是_size，_size是用来返回链表内的数据个数的，如果没有_size的话就只能遍历求一遍，这样增加一个成员变量代价反而小了

二、默认成员函数

构造函数

构造函数要来初始化成员变量，所以就需要先去给_head去new一个节点，然后它的前驱和后继都指向自己，_size初始化成0就好了，因为头节点不存储有效数据，所以也就不算做元素个数了

list()
{
	_head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    _size = 0;
}

对于Node这个类在new的时候会去调用它的构造函数，所以我们要给Node类补上一个构造，用匿名对象做这里的缺省参数

template<class T>
struct list_node
{
	list_node<T>* _prev;
	list_node<T>* _next;
	T _val;

	list_node(const T& val = T())
		:_prev(nullptr)
		, _next(nullptr)
		, _val(val)
	{}
};

析构函数

析构函数需要把所有的节点都释放了，因为所有节点都是new出来的，那就先来实现一个clear函数

clear

clear是要清空除头节点外链表中所有的节点，就要从头节点的下一个节点开始，去删除每一个节点，但是删除了当前节点就会找不到下一个节点，所以要先保存一下下一个节点

void clear()
{
	Node* cur = _head->_next;
	while (cur != _head)
	{
		Node* next = cur->_next;
		delete cur;
		cur = next;
	}
}

cur表示的是当前节点，next记录下一个节点的位置，循环判断的条件就是不等于头结点就继续删，删到最后一个节点，那它的next就是头结点了，也就证明删完了，循环结束

那在析构函数中就先去调用clear先把后面链接的节点全部删掉，然后再把头节点删掉并置空就好了

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

拷贝构造

这里就不能再去用memcpy或者赋值来写了，因为list在物理上并不是连续的空间，不可以用下标来访问，所以采用的方法是遍历有数据的这个容器，然后依次尾插进被拷贝的容器中

//l2(l1)
list(const list<T>& l)
{
	_head = new Node;
    _head->_next = _head;
    _head->_prev = _head;
    _size = 0;

	for (auto e : l)
	{
		push_back(e);
	}
}

然后这里的l2在插入数据前一定要去初始化，要把头节点new出来再把前后都指向自己，否则在访问时会出问题，这里用的是范围for，那就需要支持迭代器才可以，并且push_back也还没有实现，所以暂时这个拷贝构造是不能跑的，大家可以等下面的实现完再回来看

赋值重载

赋值就写一个现代写法去调用拷贝构造就可以，这个我们很详细的说过了，在这里就不再多赘述了

swap

void swap(list<T>& l)
{
	std::swap(_head, l._head);
	std::swap(_size, l._size);
}
//l2 = l1
list<T>& operator=(list<T> l)
{
	swap(l);
	
	return *this;
}

三、容量相关

empty

判空的逻辑是判断头节点的前驱和后继是不是指向自己，且元素个数是否为0

bool empty() const
{
	return _head->_next == _head
		&& _head->_prev == _head
		&& _size == 0;
}

size

size函数只需要返回_size的值就可以

size_t size() const
{
	return _size;
}

四、数据访问

front/back

front就是返回第一个节点里存储的值，back返回最后一个节点里的值，一定要注意是第一个存储有效数据的节点，所以是头结点的下一个节点，而不是头节点中存储的值

front和back各自分别有两个版本，一个普通版本，一个const版本，跟我们之前讲的一样，普通对象优先调用普通版本，如果没有普通版本再去调用const版本，const对象只能调用const版本

T& front()
{
	return _head->_next->_val;
}

const T& front() const
{
	return _head->_next->_val;
}

T& back()
{
	return _head->_prev->_val;
}

const T& back() const
{
	return _head->_prev->_val;
}

五、普通迭代器

我们在最开始的时候说过，list的迭代器与前面的有些不一样，我们就来看看list的迭代器有哪些不一样，可以说list最重要的部分就是迭代器，大家先来看可不可以这么写我们的迭代器呢？

typedef Node* iterator

答案显而易见，肯定是不可以的，因为迭代器我们解引用是要拿到数据，但是现在解引用拿到的是一个节点，而且++要向下一个位置走，--要向前一个位置走，现在这个迭代器++走到哪去谁能知道呢？所以我们要用运算符重载来控制这里的逻辑，也就要再封装一个迭代器的类来控制

template<class T>
struct __list_iterator
{
	typedef list_node<T> Node;
	Node* _node;
};

在外面需要去访问这个类中的成员函数，所以我们把这个迭代器类定义成struct的，里面有一个节点的指针_node，我们先来实现下*和->，*就是返回数据的引用，->是返回数据的地址

T& operator*()
{
	return _node->_val;
}

T* operator->()
{
	return &(_node->_val);
}

然后是++和--，++就是向下一个节点走，--就是向前一个节点走，而++和--呢又分为前置和后置，我们先实现前置，前置的话就是_node走完返回迭代器的本身，那这个迭代器类的名字太长了，我们也同样来typedef一下

typedef __list_iterator<T> Self;

这个typedef就和Node的typedef放在一起就行 

Self& operator++()
{
	_node = _node->_next;

	return *this;
}    

Self& operator--()
{
	_node = _node->_prev;

	return *this;
}

前置++返回的是迭代器走完的结果，所以就可以用引用返回

后置是返回++或者--之前的值，那就需要先保存一份才可以，然后返回保存的这一份，区分前置和后置，就是给后置加上一个int类型的参数

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& s)
{
	return _node != s._node;
}

bool operator==(const Self& s)
{
	return _node == s._node;
}

begin/end

begin就是返回头节点的下一个位置，因为迭代器是左闭右开，所以end应该返回的是最后一个有效数据的下一个位置，也就是头节点_head

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

iterator end()
{
	return _head;
}

那在list这个类中需要用到iterator，我们就把这个类给嵌到list这个类里，这个要放成公有的，外面要用迭代器

public:
    typedef __list_iterator<T> iterator;

而且还要给迭代器类实现一个构造函数，用节点指针去构造迭代器，现在的begin和end是隐式类型转换，构造加拷贝构造，拷贝构造我们不需要实现，迭代器去浅拷贝就可以了，也可以返回匿名对象或者是先构造出来对象再返回这个对象，这三种都可以，我们这种是最简单的，直接隐式类型的转换

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

我们再结合迭代器的使用来看

int main()
{
	hx::list<int> l;

	hx::list<int>::iterator it = l.begin();
	while (it != l.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

    return 0;
}

需要什么我们就写什么就可以了，迭代器也就是需要这几个函数，不需要实现其他功能了，那我们的普通迭代器就实现好了

六、const迭代器

下面我们来看一下const迭代器，有了刚才的封装，那const迭代器可不可以直接套上一个const呢？

typedef __list_iterator<T> iterator;
typedef const __list_iterator<T> const_iterator;

这样写也是不行的，因为这样写就是修饰迭代器本身不能修改了，那迭代器本身都不能修改了还怎么++/--呢？所以const迭代器也是需要我们自己去封装一个自定义类型来控制，那我们就照葫芦画瓢来实现一个

template<class T>
struct __list_const_iterator
{
	typedef __list_const_iterator<T> Self;
	typedef list_node<T> Node;
	Node* _node;

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

	const T& operator*()
	{
		return _node->_val;
	}

	const T* operator->()
	{
		return &(_node->_val);
	}

	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& s)
	{
		return _node != s._node;
	}

	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};

那大家有没有发现，普通迭代器和const迭代器不一样的地方就在于*和->的返回值，其他的地方全都一样，那这样设计就太冗余了，我们有没有办法可以就用一个类来控制一下*和->的返回值呢？其实很好办，只需要增加模版参数就可以

template<class T, class Ref, class Ptr>
struct __list_iterator
{
	typedef __list_iterator<T, Ref, Ptr> Self;
	typedef list_node<T> Node;
	Node* _node;

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

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

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

	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& s)
	{
		return _node != s._node;
	}

	bool operator==(const Self& s)
	{
		return _node == s._node;
	}
};

Ref是引用，也就是operator*的返回值，Ptr是指针，也就是operator->的返回值，然后不要忘记在typedef Self的时候把这两个模版参数给加上，然后在list类中我们把后面的两个模版参数写死就可以了

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

begin/end

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

const_iterator end() const
{
	return _head;
}

begin和end还是一样的实现逻辑，返回值变一样，再设计成const成员函数就可以

那迭代器部分我们就说到这里，因为这里可能会比较复杂，三个类互相缠绕，所以在文章的最后会把所有的代码给贴出来，如果大家对这里还有不太懂的地方可以去参考

七、插入数据

insert

insert是在某个迭代器插入一个val，那就是把这个迭代器里存的节点指针定义出来，然后找到前一个，再新创建一个节点，把他们之间互相链接起来就行了，最后返回新插入的这个节点的迭代器

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

	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;
	++_size;

	return newnode;
}

push_back

push_back是尾插，直接去复用insert，给一个迭代器位置

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

 end就是头结点，那在头节点的前面插入也就是尾插

push_front

push_back是头插，直接去复用insert，给一个迭代器位置

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

begin就是头结点的下一个位置，在begin之前插入，也就是在头结点和第一个节点之间插入，就是头插

八、删除数据

erase

erase是要删除某个迭代器位置，那也是把迭代器里存的节点指针定义出来，然后找到前后节点，把前后节点互相连起来就好了，最后再删除，然后要返回删除的这个位置的下一个节点的迭代器

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

pop_back

pop_back是尾删，直接去复用erase，给一个迭代器位置

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

end是头节点的位置，那--end就是头结点的前一个，也就是最后一个节点

pop_front

pop_front是头删，直接去复用erase，给一个迭代器位置

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

begin是头结点的下一个位置，也就是第一个存放有效数据的节点

九、代码

namespace hx
{
	template<class T>
	struct list_node
	{
		list_node<T>* _prev;
		list_node<T>* _next;
		T _val;

		list_node(const T& val = T())
			:_prev(nullptr)
			, _next(nullptr)
			, _val(val)
		{}
	};

	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef __list_iterator<T, Ref, Ptr> Self;
		typedef list_node<T> Node;
		Node* _node;

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

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

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

		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& s)
		{
			return _node != s._node;
		}

		bool operator==(const Self& s)
		{
			return _node == s._node;
		}
	};

	
	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		typedef __list_iterator<T, T&, T*> iterator;
		typedef __list_iterator<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;
		}

		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		//l2(l1)
		list(const list<T>& l)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;

			for (auto e : l)
			{
				push_back(e);
			}
		}

		//l2 = l1
		list<T>& operator=(list<T> l)
		{
			swap(l);
			
			return *this;
		}

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

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

		bool empty() const
		{
			return _head->_next == _head
				&& _head->_prev == _head
				&& _size == 0;
		}

		size_t size() const
		{
			return _size;
		}

		void clear()
		{
			Node* cur = _head->_next;
			while (cur != _head)
			{
				Node* next = cur->_next;
				delete cur;
				cur = next;
			}
		}

		T& front()
		{
			return _head->_next->_val;
		}

		const T& front() const
		{
			return _head->_next->_val;
		}

		T& back()
		{
			return _head->_prev->_val;
		}

		const T& back() const
		{
			return _head->_prev->_val;
		}

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

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			++_size;

			return newnode;
		}

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

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

	private:
		Node* _head;
		size_t _size;
	};
}

总结

本篇文章我们讲了list，以及关于迭代器部分，list的迭代器类型是一个自定义类型，跟以前不太一样，但是这种方式在以前也还是很常见的，比如map/set，unordered map/unordered set，还是要这么用，迭代器部分都要去这样封装，大家还是要习惯这种方式，那本篇文章就到这里啦，如果觉得下篇写的不错的小伙伴，可以给小编一个一键三连表示支持，感谢大家！！！


http://www.niftyadmin.cn/n/5863140.html

相关文章

A097基于SpringBoot实现的社区博客管理系统

A097基于SpringBoot实现的社区博客管理系统

系统介绍 基于SpringBootVue实现的社区博客管理系统设计了超级管理员、系统观察者、用户三种角色&#xff0c;超级管理员可对用户授权&#xff0c;具体实现的功能如下 • 文章采用了比较火的Markdown编辑器。 • 系统集成了邮件发送功能。 • 系统可以自定义友情链接。…
阅读更多...
无人机避障——Mid360+Fast-lio感知建图+Ego-planner运动规划（胎教级教程）

无人机避障——Mid360+Fast-lio感知建图+Ego-planner运动规划（胎教级教程）

电脑配置&#xff1a;Xavier-nx、ubuntu 18.04、ros melodic 激光雷达&#xff1a;Livox_Mid-360 结果展示&#xff1a;左边Mid360Fast-lio感知建图&#xff0c;右边Ego-planner运动规划 1、读取雷达数据并显示 无人机避障——感知篇&#xff08;采用Livox-Mid360激光雷达获…
阅读更多...
普通人怎样用好Deepseek?

普通人怎样用好Deepseek?

第一章&#xff1a;准备篇&#xff08;30分钟上手&#xff09; DeepSeek 是一款功能强大的数据处理和分析工具&#xff0c;广泛应用于数据挖掘、机器学习、商业智能等领域。 本文将通过图文结合的方式&#xff0c;详细介绍 DeepSeek 的安装、配置、基本使用、高级功能以及实用…
阅读更多...
LLaMA-Factory|微调大语言模型初探索(3)，qlora微调deepseek记录

LLaMA-Factory|微调大语言模型初探索(3)，qlora微调deepseek记录

前言 上篇文章记录了使用lora微调llama-1b，微调成功，但是微调llama-8b显存爆炸，这次尝试使用qlora来尝试微调参数体量更大的大语言模型，看看64G显存的极限在哪里。 1.Why QLora? QLoRA 在模型加载阶段通过 4-bit 量化大幅减少了模型权重的显存占用。QLoRA 通过 反量化到 …
阅读更多...
XiaoMi Mi5(gemini) 刷入Ubuntu Touch 16.04——安卓手机刷入Linux

XiaoMi Mi5(gemini) 刷入Ubuntu Touch 16.04——安卓手机刷入Linux

最近在研究个人用的小服务器&#xff0c;期间也搞了一台某讯的盒子&#xff0c;s905的芯片&#xff0c;28G&#xff0c;刷入了Armbian&#xff0c;在自己本地当linux服务器用用挺方便的&#xff0c;但总感觉性能不太够。 然后灵机一动&#xff0c;手上还有几台旧的安卓手机&am…
阅读更多...
2025年华为手机解锁BL的方法

2025年华为手机解锁BL的方法

注&#xff1a;本文是我用老机型测试的&#xff0c;新机型可能不适用 背景 华为官方已经在2018年关闭了申请BL解锁码的通道&#xff0c;所以华为手机已经无法通过官方获取解锁码。最近翻出了一部家里的老手机华为畅玩5X&#xff0c;想着能不能刷个系统玩玩&#xff0c;但是卡…
阅读更多...
请求go构建缓存，go clean -cache

请求go构建缓存，go clean -cache

go clean -cache go 构建时会产生很多缓存&#xff0c; 一般是目录&#xff1a;/Users/xxx/Library/Caches/go-build 此目录README&#xff1a; This directory holds cached build artifacts from the Go build system. Run "go clean -cache" if the directory …
阅读更多...
DeepSeek写贪吃蛇手机小游戏

DeepSeek写贪吃蛇手机小游戏

DeepSeek写贪吃蛇手机小游戏 提问 根据提的要求&#xff0c;让DeepSeek整理的需求&#xff0c;进行提问&#xff0c;内容如下&#xff1a; 请生成一个包含以下功能的可运行移动端贪吃蛇H5文件&#xff1a; 要求 蛇和食物红点要清晰&#xff0c;不超过屏幕外 下方有暂停和重新…
阅读更多...
最新文章

Copyright @ 2022~2023