【C++】list的模拟实现【完整理解版】

目录

一、list的概念引入

1、vector与list的对比

 2、关于struct和class的使用

3、list的迭代器失效问题 

 二、list的模拟实现

1、list三个基本函数类

2、list的结点类的实现

3、list的迭代器类的实现 

3.1 基本框架

3.2构造函数 

3.3 operator*

3.4 operator->

3.5 operator前置++和--与后置++和-- 

3.5 operator==与operator!=

4、list类的实现

 4.1 基本框架

4.2 构造函数 

4.2 begin()和end()

4.3 拷贝构造

4.4  clear

4.5 operator=

4.6  析构函数

 4.7 insert

4.8 push_back 和 push_front

4.9 erase

4.10 pop_back 和 pop_front

三、完整源代码：

list.h:

 test.cpp:

一、list的概念引入

1、vector与list的对比

 两者的区别十分类似于顺序表和链表的区别

STL中的list底层其实就是带哨兵位循环双向链表而已

 2、关于struct和class的使用

C++中的struct和class的唯一区别在于默认访问限定符（即你不写public、private这种访问限定符）不同，struct默认为公有（public），而class默认为私有（private），一般情况，成员部分私有，部分共有，就用class，所有成员都开放或共有，就用struct

所以下文写的节点和迭代器类都用struct是因为，struct中的成员函数默认为公有了，也不用写public了，但是你用class就要写个public

3、list的迭代器失效问题 

 list本质：带头双向循环链表 

支持操作接口的角度分迭代器的类型：单向（forward_list）、双向（list）、随机（vector）

从使用场景的角度分迭代器的类型：（正向迭代器，反向迭代器）+const迭代器

 迭代器失效本质是内存空间的问题，失效原因：

1、增容完还指向旧空间

2、节点已经被释放（list里面）

list的erase迭代器失效

注意：删除不会报错，迭代器失效也不会报错，是删除以后迭代器失效了，是去访问失效的迭代器才会报错

插入知识点（库里面的find实现，可不看）

​

 二、list的模拟实现

1、list三个基本函数类

list本质是一个带头双向循环链表：

模拟实现list，要实现下列三个类：

①、模拟实现结点类
②、模拟实现迭代器的类
③、模拟list主要功能的类
list的类的模拟实现其基本功能（增删等操作）要建立在迭代器类和结点类均已实现好的情况下才得以完成。

2、list的结点类的实现

因为list的本质为带头双向循环链表，所以其每个结点都要确保有下列成员：

1. 前驱指针
2. 后继指针
3. data值存放数据

而结点类的内部只需要实现一个构造函数即可。

//1、结点类
template<class T>
struct __list_node//前面加__是命名习惯,一般这么写表示是给别人用的
{
	//前驱指针和后驱指针
	__list_node* _next;//C++中可不写struct，直接用名定义，但注意这里还要加类型
	__list_node* _prev;
	T _data;//存节点的值
 
	//构造函数
	__list_node(const T& val = T())//给一个缺省值T()
		:_next(nullptr)
		, _prev(nullptr)
		, _data(val)
	{}
};

①、为什么是__list_node？

首先，C++中用struct定义时可不加struct，重点是这里用了一个类模板，类模板的类名不是真正的类型且类模板不支持自动推类型，即__list_node不是真正的类型，定义变量时__list_node这种才是真正的类型，也就是用类模板定义变量时必须 指定对应的类型 。 注：结构体模板或类模板在定义时可以不加 ，但 使用时必须加 。

3、list的迭代器类的实现 

因为list其本质是带头双向循环链表，而链表的物理空间是不连续的，是通过结点的指针顺次链接，我们不能像先前的string和vector一样直接解引用去访问其数据，结点的指针解引用还是结点，结点指针++还是结点指针，而string和vector的物理空间是连续的，所以这俩不需要实现迭代器类，可以直接使用。

为了能让list像vector一样解引用后访问对应节点中的值，++访问到下一个数据，我们需要单独写一个迭代器类的接口实现，在其内部进行封装补齐相应的功能，而这就要借助运算符重载来完成。 

注：迭代器封装后是想模拟指针的行为 

3.1 基本框架

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

①、迭代器类模板为什么要三个参数？

若只有普通迭代器的话，一个class T参数就够了，但因为有const迭代器原因，需要加两个参数，两个参数名Ref（reference:引用）和Ptr（pointer:指针），名字怎么起都行，但这种有意义的名字是很推荐的，即这两个参数一个让你传引用，一个让你传指针，具体等下文讲到const迭代器再说

②、迭代器类到底是什么？

迭代器类就一个节点的指针变量_node，但是因为我们要运算符重载等一系列操作，不得不把list的迭代器写成类，完成那些操作，list的迭代器才能正确的++到下一位置，解引用访问节点的值

③、节点指针和迭代器的区别？

​

3.2构造函数 

	//迭代器的构造函数只需要一个指针构造
	__list_iterator (Node* node)
		:_node(node)
	{ }

3.3 operator*

//*it（调用的是函数，返回节点中的值）
	Ref operator*()
	{//出了作用域还在，引用返回
		return _node->_data;
	}

①、 返回值为什么是Ref？

Ref是模板参数，因为迭代器类的模板参数Ref传入的要么是T&要么是const T&，就是为了const迭代器和普通迭代器的同时实现，底层就是这么实现的，意义就是一个只读，一个可读可写 

注：比如之前讲的vector的迭代器，*it（假设it是迭代器变量）就是拿到对应的值，那么list的迭代器也要同理，解引用迭代器就是为了访问对应位置的值，那么list只要通过迭代器返回对应节点的值就好了（*it，我们是就想要对应的值）

3.4 operator->

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

①、为什么需要operator->？

本质因为自定义类型需要，那需从list存的类型是个自定义类型说起，以Date类型为例

​

 若list存了个自定义类型的Date类，程序错误，因为我们并没有重载Date类的operator<<，若是内置类型的话才可以正常输出，那写一个operator<<重载吗？不，因为你无法确定要用哪些类，也不能每个类都写operator<<，那怎么办？我们访问Date类本质是想访问它内置类型（int）的_year、_month和_day吧，那我们不妨写个专属于自定义类型的operator->（因为内置类型只需要*it就可以直接输出了，但自定义类型不可以直接输出），利用operator->直接访问类的成员变量，而内置类型可以直接输出

故从根源上解决问题： 在迭代器中实现个operator->：

（Ptr是迭代器的模板参数，我们用来作为T*或const T*的）

​

3.5 operator前置++和--与后置++和-- 

//++it;（迭代器++本质就是指针往后移，加完后还应是个迭代器）
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	//it++;
	Self operator++(int)//加参数以便于区分前置++
	{
		Self tmp(*this);//拷贝构造tmp
		_node = _node->_next;//直接让自己指向下一个结点即可实现++
		return tmp;//注意返回tmp，才是后置++
	}
	//--it;
	Self& operator--()
	{
		_node = _node->_prev;//让_node指向上一个结点即可实现--
		return *this;
	}
	//it--;
	Self operator--(int)//记得传缺省值以区分前置--
	{
		Self tmp(*this);//拷贝构造tmp
		_node = _node->_prev;
		return tmp;
	}

①、迭代器++对于list是什么意思？

迭代器++的意思就是想让其指向下一个节点，--正好相反，为了区分前置和后置++（--），我们会用函数重载，也就是多一个“没用的”参数：int，这个参数没什么用，只是为了区分++与--

3.5 operator==与operator!=

 
	//it != end() 
	bool operator!=(const Self& it)
	{
		//迭代器是否相等只要判断对应节点地址是否相等即可
		return _node != it._node;
	}
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}

①、两个迭代器怎么比较的？

迭代器中就一个成员变量_node，节点指针，只要比较当前的节点指针是否相同即可，这个操作在判断迭代器是否走到头有用（比如 it != s.end()）

问题：迭代器的拷贝构造和赋值和析构函数需我们自己实现吗？

 答：不需要

因为迭代器存的就是一个节点指针，而节点是属于链表list的，那么它的释放应由list来实现，那么迭代器的析构也无需我们自己写了。且拷贝构造和赋值就是节点指针的拷贝和赋值，即使指向同一节点了，迭代器也不会析构，而list的析构到时候只会释放这个节点一次，不存在什么问题，即我们无需深拷贝，使用系统提供的浅拷贝即可。

4、list类的实现

 在结点类和迭代器类都实现的前提下，就可实现list主要功能：增删等操作的实现

 4.1 基本框架

//3、链表类
template<class T>
class list
{
	typedef __list_node Node;
public:
	typedef __list_iterator iterator;
	typedef __list_iteratorconst T&,const T*> const_iterator;
 
private:
	Node* _head;//头结点
}

①、const_iterator(const迭代器的介绍)

我们知道const_iterator在begin()和end()中的返回值是需要用到的，其主要作用就是当迭代器只读时使用， 因为普通迭代器和const迭代器的实现区别仅仅在于内部成员函数的返回值不同，难道重写一遍吗？不用，我们模板参数多两个就好了，一个是引用class Ref（T&或const T&），一个是指针class Ptr（T*或const T*），当Ref时const T&就是const迭代器的调用，当Ref时T& 时就是普通迭代器的调用，这就利用模板实现了两个迭代器的同时实现

4.2 构造函数 

//带头双向循环链表的构造函数
list()
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
}

解释：我们开辟一个头结点，然后使其处于一个对应的初始状态即可

4.2 begin()和end()

iterator begin()
{
	//第一个位置应该是头结点的下一个节点
	return iterator(_head->_next);//用匿名对象构造iterator类型的
}
iterator end()
{
	//最后一个数据的下一个位置应该是第一个节点，即头结点
	return iterator(_head);
}
 
const_iterator begin()const
{
	return const_iterator(_head->_next);
}
const_iterator end()const
{
	return const_iterator(_head);
}

①、关于匿名构造的理解

比如 iterator(_head->_next); iterator是个类模板类型（它被typedef过的），那不应该实例化一个对象再构造吗？这里没有用是因为这里是匿名对象的构造，这里这么用比较方便

4.3 拷贝构造

//拷贝构造：传统写法
list(const list& lt)
{
	_head = new Node;//开辟一样的头结点
	_head->_next = _head;
	_head->_prev = _head;
	//1、用迭代器遍历
	/*const_iterator it = lt.begin();
	while (it != lt.end())
	{
		push_back(*it);
		++it;
	}*/
 
	//2、范围for遍历
	//遍历lt1，把lt1的元素push_back到lt2里头
	for (auto e : lt)
	{
		push_back(e);//自动开辟新空间，完成深拷贝
	}
}

 解释：list的拷贝构造跟vector不同，它的拷贝是拷贝一个个节点（因为不连续的物理空间）， 那么我们可以用迭代器拿到list的一个个节点【上面是传统写法】

现代写法：

template<class InputIterator> 
list(InputIterator first, InputIterator last) {
	_pHead = new Node();
	_pHead->_next = _pHead;
	_pHead->_prev = _pHead;
 
	while (first != last) {
		push_back(*first);
		first++;
	}
}
/* 拷贝构造（现代写法）：L2(L1) */
list(const list& L) {
    _pHead = new Node();
	_pHead->_next = _pHead;
	_pHead->_prev = _pHead;
 
	list tmp(L.begin(), L.end());
	swap(_pHead, tmp._pHead);  // 交换两个结点的指针
}

①、为什么有的拷贝构造需初始化，operator=不需要？

以string的模拟实现为例

这里为什么s2要初始化？

是因为string的模拟实现有交换操作，而list的传统写法无需交换，开辟一个头结点即可

因为s2是要被拷贝构造出来的，没被拷贝构造前还没存在，然后s2要跟tmp交换，如果也就是tmp得到s2的数据，如果s2之前没初始化，析构销毁就出问题了，因为没初始化是随机值

但是赋值不一样，赋值是两个对象都存在，不存在随机值问题，所以不用一上来就初始化

4.4  clear

void clear()
{//clear不删除头结点，因为万一删除了头结点你还想插入数据怎么办
	iterator it = begin();
	while (it != end())
	{
        //法一、通过返回值针对迭代器失效问题
		it = erase(it);
        //法二、直接++针对迭代器失效问题
        //erase(it++);   //这里一定不能写为erase(it); it++;这样迭代器已经失效了，不能++
	}
}

①、 it = erase(it)什么意思?

防止迭代器失效，因为erase返回的是被删除位置的下一位置，比如删除pos位置的，pos位置被删除后，这个位置的迭代器就失效了，那就无法通过++找到后面的位置了，所以我们通过erase返回值来更新一下迭代器位置，即更新到被删除位置的下一位置

4.5 operator=

        
	//赋值运算符重载（传统写法）
	//lt1 = lt3
	//list& operator=(const list& lt)
	//{
	//	if (this != <)
	//	{
	//		clear();//先释放lt1
	//		for (auto e : lt)
	//			push_back(e);
	//	}
	//	return *this;
	//}
 
	//赋值运算符重载（现代写法）
	//lt1 = lt3
	list& operator=(list lt)//套用传值传参去拷贝构造完成深拷贝
	{
		swap(_head,lt._head);//交换两个list的头结点即可
		//lt出了作用域，析构函数销毁lt1原来的链表，一举两得
		//swap(lt);
		return *this;
	}

注：传统写法要先把被赋值的对象先释放，然后利用push_bak尾插，push_back在下文说明

4.6  析构函数

 
	//析构函数
	~list()
	{
		clear();//删除除头结点以外的节点
		delete _head;//删去哨兵位头结点
		_head = nullptr;
	}

 4.7 insert

//insert，插入pos位置之前
iterator insert(iterator pos, const T& x)
{
	Node* newnode = new Node(x);//创建新的结点
	Node* cur = pos._node; //迭代器pos处的结点指针
	Node* prev = cur->_prev;
	//prev newnode cur
	//链接prev和newnode
	prev->_next = newnode;
	newnode->_prev = prev;
	//链接newnode和cur
	newnode->_next = cur;
	cur->_prev = newnode;
	//返回新插入元素的迭代器位置
	return iterator(newnode);
}

①、返回参数为什么是iterator？

本质是为了防止迭代器失效问题

注：insert指的是插入到指定位置的前面

4.8 push_back 和 push_front

//尾插
void push_back(const T& x)
{
	Node* tail = _head->_prev;//找尾
	Node* newnode = new Node(x);//创建一个新的结点
	//_head  tail  newnode
	//使tail和newnode构成循环
	tail->_next = newnode;
	newnode->_prev = tail;
	//使newnode和头结点_head构成循环
	newnode->_next = _head;
	_head->_prev = newnode;
 
}
//头插
void push_front(const T& x)
{
	insert(begin(), x);
}

4.9 erase

//erase
iterator erase(iterator pos)
{
	assert(pos != end());
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
	//prev cur next
	//链接prev和next
	prev->_next = next;
	next->_prev = prev;
	//delete删去结点,因为每一个节点都是动态开辟出来的
	delete cur;
	//返回被删除元素后一个元素的迭代器位置
	//return next;
	return iterator(next);
}

①、 返回值问题

erase的返回值，返回的是被删除位置的下一位置，库里面这么规定的，本质是因为删除元素一定会导致此位置的迭代器失效，故返回被删除位置的下一次位置可以更新迭代器

4.10 pop_back 和 pop_front

//尾删
void pop_back()
{
	erase(--end());
	//erase(iterator(_head->prev));//构造个匿名对象
}
//头删
void pop_front()
{
	erase(begin());
}

最后， list的排序意义不大，因为实际生活中我们都是对数组等排序

三、完整源代码：

list.h:

#pragma once
 
namespace mz
{
	//1、结点类
	template<class T>
	struct __list_node//前面加__是命名习惯,一般这么写表示是给别人用的
	{
		//前驱指针和后驱指针
		__list_node* _next;//C++中可不写struct，直接用名定义，但注意这里还要加类型
		__list_node* _prev;
		T _data;//存节点的值
 
		//构造函数
		__list_node(const T& val = T())//给一个缺省值T()
			:_next(nullptr)
			, _prev(nullptr)
			, _data(val)
		{}
	};
 
	//2、迭代器类
 
	//__list_iterator              -> iterator
	//__list_iterator  -> const_iterator
	template<class T,class Ref,class Ptr>
	struct __list_iterator
	{
		typedef __list_node Node;
		typedef __list_iterator Self;
		Node* _node;
 
		//迭代器的构造函数只需要一个指针构造
		__list_iterator (Node* node)
			:_node(node)
		{ }
 
		//*it（调用的是函数，返回节点中的值）
		Ref operator*()
		{//出了作用域还在，引用返回
			return _node->_data;
		}
 
		Ptr operator->()
		{
			return &_node->_data;
		}
 
		//++it;（迭代器++本质就是指针往后移，加完后还应是个迭代器）
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		//it++;
		Self operator++(int)//加参数以便于区分前置++
		{
			Self tmp(*this);//拷贝构造tmp
			_node = _node->_next;//直接让自己指向下一个结点即可实现++
			return tmp;//注意返回tmp，才是后置++
		}
		//--it;
		Self& operator--()
		{
			_node = _node->_prev;//让_node指向上一个结点即可实现--
			return *this;
		}
		//it--;
		Self operator--(int)//记得传缺省值以区分前置--
		{
			Self tmp(*this);//拷贝构造tmp
			_node = _node->_prev;
			return tmp;
		}
 
		//it != end() 
		bool operator!=(const Self& it)
		{
			//迭代器是否相等只要判断对应节点地址是否相等即可
			return _node != it._node;
		}
		bool operator==(const Self& it)
		{
			return _node == it._node;
		}
 
	};
 
	//3、链表类
	template<class T>
	class list
	{
		typedef __list_node Node;
	public:
		typedef __list_iterator iterator;
		typedef __list_iteratorconst T&,const T*> const_iterator;
 
		iterator begin()
		{
			//第一个位置应该是头结点的下一个节点
			return iterator(_head->_next);//用匿名对象构造iterator类型的
		}
		iterator end()
		{
			//最后一个数据的下一个位置应该是第一个节点，即头结点
			return iterator(_head);
		}
 
		const_iterator begin()const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end()const
		{
			return const_iterator(_head);
		}
 
		//带头双向循环链表的构造函数
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
 
		//拷贝构造：传统写法
		list(const list& lt)
		{
			_head = new Node;//开辟一样的头结点
			_head->_next = _head;
			_head->_prev = _head;
			//1、用迭代器遍历
			/*const_iterator it = lt.begin();
			while (it != lt.end())
			{
				push_back(*it);
				++it;
			}*/
 
			//2、范围for遍历
			//遍历lt1，把lt1的元素push_back到lt2里头
			for (auto e : lt)
			{
				push_back(e);//自动开辟新空间，完成深拷贝
			}
		}
 
	
		//赋值运算符重载（传统写法）
		//lt1 = lt3
		//list& operator=(const list& lt)
		//{
		//	if (this != <)
		//	{
		//		clear();//先释放lt1
		//		for (auto e : lt)
		//			push_back(e);
		//	}
		//	return *this;
		//}
 
		//赋值运算符重载（现代写法）
		//lt1 = lt3
		list& operator=(list lt)//套用传值传参去拷贝构造完成深拷贝
		{
			swap(_head,lt._head);//交换两个list的头结点即可
			//lt出了作用域，析构函数销毁lt1原来的链表，一举两得
			//swap(lt);
			return *this;
		}
 
		//析构函数
		~list()
		{
			clear();//删除除头结点以外的节点
			delete _head;//删去哨兵位头结点
			_head = nullptr;
		}
 
		void clear()
		{//clear不删除头结点，因为万一删除了头结点你还想插入数据怎么办
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
 
		//尾插
		void push_back(const T& x)
		{
			Node* tail = _head->_prev;//找尾
			Node* newnode = new Node(x);//创建一个新的结点
			//_head  tail  newnode
			//使tail和newnode构成循环
			tail->_next = newnode;
			newnode->_prev = tail;
			//使newnode和头结点_head构成循环
			newnode->_next = _head;
			_head->_prev = newnode;
 
		}
		//头插
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
 
		//insert，插入pos位置之前
		iterator insert(iterator pos, const T& x)
		{
			Node* newnode = new Node(x);//创建新的结点
			Node* cur = pos._node; //迭代器pos处的结点指针
			Node* prev = cur->_prev;
			//prev newnode cur
			//链接prev和newnode
			prev->_next = newnode;
			newnode->_prev = prev;
			//链接newnode和cur
			newnode->_next = cur;
			cur->_prev = newnode;
			//返回新插入元素的迭代器位置
			return iterator(newnode);
		}
 
		//erase
		iterator erase(iterator pos)
		{
			assert(pos != end());
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			//prev cur next
			//链接prev和next
			prev->_next = next;
			next->_prev = prev;
			//delete删去结点,因为每一个节点都是动态开辟出来的
			delete cur;
			//返回被删除元素后一个元素的迭代器位置
			//return next;
			return iterator(next);
		}
		//尾删
		void pop_back()
		{
			erase(--end());
			//erase(iterator(_head->prev));//构造个匿名对象
		}
		//头删
		void pop_front()
		{
			erase(begin());
		}
 
	private:
		Node* _head;//头结点
	};
	
	void test1()
	{
		list<int>lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		//类外访问迭代器需要指定类域，类内访问可直接访问
		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
 
	struct Date
	{
		int _year = 0;
		int _month = 1;
		int _day = 1;
	};
 
	void test2()
	{
		Date* p2 = new Date;
		*p2;//取到的是Date
		p2->_year;//取到的是Date类中的成员变量
 
		listlt;
		lt.push_back(Date());
		lt.push_back(Date());
		//list存了个日期类(自定义类型)的类型
		list::iterator it = lt.begin();
		while (it != lt.end())
		{
			//cout << *it << " ";
			cout << it->_year << "-" << it->_month << "-" << it->_day << endl;
			++it;
		}
		cout << endl;
 
	}
 
	void print_list(const list<int>& lt)
	{
		list<int>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
	}
 
	void test3()
	{
		list<int>lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
 
		list<int> lt2(lt1);
		print_list(lt2);
 
		list<int>lt3;
		lt3.push_back(10);
		lt3.push_back(20);
		lt3.push_back(30);
		lt3.push_back(40);
		lt1 = lt3;
		print_list(lt1);
 
	}
}

 test.cpp:

#include
#include
using namespace std;
#include"list.h"
 
int main()
{
	//mz::test1();
	mz::test3();
 
	return 0;
}