list模拟实现【C++】

全部的实现代码放在了文章末尾

准备工作

创建两个文件，一个头文件mylist.hpp，一个源文件test.cpp

【因为模板的声明和定义不能分处于不同的文件中，所以把成员函数的声明和定义放在了同一个文件mylist.hpp中】
mylist.hpp：存放包含的头文件，命名空间的定义，成员函数和命名空间中的函数的定义

test.cpp：存放main函数，以及测试代码

---

包含头文件

1. iostream：用于输入输出

2. assert.h：用于使用报错函数assert

---

定义命名空间

在文件mylist.hpp中定义上一个命名空间mylist
把list类和它的成员函数放进命名空间封装起来，防止与包含的头文件中的函数/变量重名的冲突问题

---

类的成员变量

参考了stl源码中的list的实现，stl中list的底层链表是双向带头循环链表
【可以看我这篇文章了解双向带头循环链表的实现：链表的极致——带头双向循环链表】
成员变量只有一个，就是指向双向带头循环链表的头节点的指针。

节点类：

为什么节点类是用struct而不是class呢？

因为节点类里面的成员变量在实现list的时候需要经常访问，所以需要节点类的成员变量是公有的【使用友元也可以，但是比较麻烦】
struct的默认访问权限就是公有，不用加访问限定符了，stl中实现的节点类也是struct
class的默认访问权限是私有的

---

list类：

为什么要写get_head_node?

因为插入节点之前必须要有头节点
所以把创建初始头节点的操作写成了一个函数，用于
所有构造函数插入节点之前进行申请头节点

---

迭代器

因为list存储数据的方式是创建一个一个的节点存储数据
所以存储数据的空间不是连续的，所以不能直接用指针作为迭代器

因为指向一个节点的指针直接++,是不一定能指向下一个节点的

所以要把迭代器实现成一个类，这样才可以正确地支持++，- -，*等操作

迭代器在list类里的实例化和重命名

普通迭代器

template<class T, class R, class F>
struct Iterator
{
	把自己的类型重命名一下
	typedef Iterator<T, R, F> Self;


	成员变量的类型是 双向带头循环链表的节点类型
	listnode<T>* _n;

	Iterator(listnode<T>*l=nullptr) 构造函数
	{
		_n = l;
	}
	Self& operator++()前置++
	{
		++就是指向下一个节点
		_n = _n->_next;
		return *this;
	}
	Self operator++(int)  后置++
	{
		Self tmp =*this;  先记录一下++之前的值

		_n = _n->_next;  再++

		return tmp;
	}
	Self& operator--()  前置--
	{
		--就是指向上一个节点
		_n = _n->_prev;
		return *this;
	}
	Self operator--(int) 后置--
	{
		Self tmp = *this; 先记录一下--之前的值

		_n = _n->_prev;  再--
		return tmp;
	}

	R operator*()const
	{
		 类比指针
		*就是获取  节点中存储的数据
		return _n->_data;
	}
	F operator->()const
	{
		返回  节点中 存储数据的成员变量的  地址
		return &(_n->_data);
	}
	bool operator!=(const Self&obj)const![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/f3d8c3b768b14a04a69d04a69c2d9829.png#pic_center)

	{
		return _n != obj._n;
	}
	bool operator==(const Self& obj)
	{
		return !(*this != obj);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

operator->()的作用是什么？

为了实现：
当节点中存储的数据是自定义类型的变量时，可以直接使用 迭代器->访问自定义类型中的成员
【原来访问需要调用两次->，为了可读性，省略了一个->】

例

---

const迭代器

const迭代器与普通迭代器的区别是什么？
区别就只有==不能通过const迭代器改变节点中存储的数据==

转换一下就是：

1. 不能使用迭代器的operator*()改变节点中存储的数据，即把operator*()的返回值改成const T&就可以了
2. 不能使用迭代器的operator->()改变节点中存储的数据的成员，即把operator->()的返回值改成const T*就可以了

所以const迭代器与普通迭代器的区别就只有两个函数的返回值类型不同，所以增加两个模板参数：R和F

普通迭代器实例化时:R就是T&，F就是T*
const迭代器实例化：R就是const T&，F就是const T*

---

反向迭代器

反向迭代器与普通迭代器的实现上的区别就是：
普通迭代器++是指向下一个节点
反向迭代器++是指向上一个节点
普通迭代器- -是指向上一个节点
反向迭代器- -是指向下一个节点

template<class T, class R, class F>
struct Reverse_iterator
{
	把自己的类型重命名一下
	typedef Reverse_iterator<T, R, F> Self;

	成员变量的类型是 双向带头循环链表的节点类型
	listnode<T>* _n;


	Reverse_iterator(listnode<T>* l) 构造函数
	{
		_n = l;
	}

	Self& operator++()
	{
		反向迭代器++，是移动到  前  一个节点
		_n = _n->_prev;
		return *this;
	}
	Self operator++(int)
	{
		Self tmp = *this;
		_n = _n->_prev;
		return tmp;
	}
	Self& operator--()
	{
		反向迭代器--，是移动到  后  一个节点
		_n = _n->_next;
		return *this;
	}
	Self operator--(int)
	{
		Self tmp = *this;
		_n = _n->_next;
		return tmp;
	}
	R operator*()const
	{
		return _n->_data;
	}
	F operator->()const
	{
		return &(_n->_data) ;
	}
	bool operator!=(const Self& obj)const
	{
		return _n!=obj._n;
	}
	bool operator==(const Self& obj)const
	{
		return !(*this != obj);
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

---

迭代器的获取

iterator begin()
{
	头节点的下一个节点 才是第一个节点
	return _head->_next;
}

const修饰的对象只能调用const修饰的成员函数
const_iterator begin()const
{
	头节点的下一个节点 才是第一个节点
	return _head->_next;
}

iterator end()
{
	最后一个节点的下一个节点是  头节点
	因为是循环链表
	return _head;
}

const修饰的对象只能调用const修饰的成员函数
const_iterator end()const
{
	return _head;
}


reverse_iterator rend()
{
	反向迭代器的rend返回的是第一个节点的   前一个节点
	return _head;
}

const修饰的对象只能调用const修饰的成员函数
const_reverse_iterator rend()const
{
	return _head;
}
reverse_iterator rbegin()
{
	反向迭代器的rbegin()返回的是  最后一个节点
	最后一个节点是  头节点的前一个
	因为是循环链表
	return _head->_prev;
}

const_reverse_iterator rbegin()const
{
	return _head->_prev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

---

构造函数

默认构造

---

使用n个val构造

---

迭代器区间构造

---

解决迭代器区间构造 和 用n个val构造的冲突

当重载了迭代器区间构造和使用n个val构造的时候
如果传入的两个参数都是int类型的话就会报错

为什么？
因为在模板函数构成重载时，编译器会调用更合适的那一个
什么叫更合适？
就是不会类型转

如果传入的两个参数都是int类型，那么调用的应该是使用n个值构造，因为没有int类型的迭代器

但是使用n个值构造的第一个参数是size_t , int传进去要隐式类型转换
而调用迭代器区间构造，两个int的实参传进去，就会直接把InputIterator推导成int，不会发生类型转换，所以编译器会调用迭代器区间构造

解决方法：
再重载一个使用n个值构造的函数，把第一个参数改成int，这样根据模板偏特化，就会在都不类型转换时优先调用第一个参数特化成int的那个构造函数

---

initializer_list构造

写了这个构造函数，就可以支持直接使用{}初始化了
例

initializer_list是iostream库里面的自定义类型，它可以直接接收{ }里面的值 进行初始化，而且有迭代器

所以可以直接使用迭代器循环+尾插进行对list的构造

---

拷贝构造

---

析构函数

---

swap

只需要交两个list对象的头指针中存储的地址就可以了

因为两个list对象都有头结点，交换了头指针中存储的地址，就相当于把这两个对象的头指针的指向交换了，
而链表的所有节点都是由头节点出发去找到的

void swap(list& obj)
{
	调用库里面的swap，交换头指针
	std::swap(_head, obj._head);
}
1
2
3
4
5

---

赋值运算符重载

list& operator= (list obj)
{
	swap(obj);

	return *this;
}
1
2
3
4
5
6

为什么上面的两句代码就可以完成深拷贝呢？
这是因为：

使用了传值传参，会在传参之前调用拷贝构造，再把拷贝构造出的临时对象作为参数传递进去

赋值运算符的左操作数，*this再与传入的临时对象obj交换，就直接完成了拷贝

在函数结束之后，存储在栈区的obj再函数结束之后，obj生命周期结束

obj调用析构函数，把指向的从*this那里交换来的不需要的空间销毁

---

erase

删除pos迭代器指向的节点

为什么要返回next？

因为使用了erase之后的迭代器会失效，需要提供更新的方法

为什么使用了erase之后的迭代器会失效？

因为pos指向的节点erase之后，节点被释放了

stl库里面规定erase的返回值是指向删除数据的下一个数据的迭代器，下一个数据就是next指向的数据，所以返回next【没有接收返回值的迭代器，在检测较严格的编译器中，不管指向的位置是否正确，都会禁止使用，使用了就报错】

---

删除迭代器区间

---

insert

在迭代器pos之前插入一个节点

为什么要返回newnode?

list的迭代器pos在使用完insert之后其实是不会失效的

但是为了与其他容器的nsert的返回值进行统一，所以也返回了指向新插入的节点的迭代器

---

在迭代器pos之前插入一个迭代器区间的数据

---

push_back

复用insert即可

void push_back(const T&val)
{
	insert(end(), val);
}
1
2
3
4

---

push_front

复用insert即可

void push_front(const T& val)
{
	insert(begin(), val);
}
1
2
3
4

---

pop_front

复用erese即可

void pop_front()
{
	erase(begin());
}
1
2
3
4

---

pop_back

复用erese即可

void pop_back()
{
	erase(--end());
}
1
2
3
4

---

size

---

empty

---

back

---

front

---

assign

---

resize

---

clear

复用erase

---

全部代码

#include<iostream>
#include<assert.h>

using namespace std;

namespace mylist
{
	template<class T>
	struct listnode//双向带头循环链表的节点类
	{
		T _data;//节点存储的数据

		listnode* _next;//指向下一个节点的指针

		listnode* _prev;//指向前一个节点的指针
	};
	
	

	template<class T, class R, class F>
	struct Iterator
	{
		//把自己的类型重命名一下
		typedef Iterator<T, R, F> Self;

		//成员变量的类型是 双向带头循环链表的节点类型
		listnode<T>* _n;


		Iterator(listnode<T>*l=nullptr)//构造函数
		{
			_n = l;
		}
		Self& operator++()//前置++
		{
			//++就是指向下一个节点
			_n = _n->_next;
			return *this;
		}
		Self operator++(int)//后置++
		{
			Self tmp =*this;//先记录一下++之前的值

			_n = _n->_next;//再++

			return tmp;
		}
		Self& operator--()//前置--
		{
			//--就是指向上一个节点
			_n = _n->_prev;
			return *this;
		}
		Self operator--(int)//后置--
		{
			Self tmp = *this;//先记录一下--之前的值

			_n = _n->_prev;//再--
			return tmp;
		}

		R operator*()const
		{
			//类比指针
			//*就是获取  节点中存储的数据
			return _n->_data;
		}
		F operator->()const
		{
			//返回  节点中 存储数据的成员变量的  地址
			return &(_n->_data);
		}
		bool operator!=(const Self&obj)const
		{
			return _n != obj._n;
		}
		bool operator==(const Self& obj)
		{
			return !(*this != obj);
		}
	};

	template<class T, class R, class F>
	struct Reverse_iterator
	{
		//把自己的类型重命名一下
		typedef Reverse_iterator<T, R, F> Self;

		//成员变量的类型是 双向带头循环链表的节点类型
		listnode<T>* _n;


		Reverse_iterator(listnode<T>* l)//构造函数
		{
			_n = l;
		}

		Self& operator++()
		{
			//反向迭代器++，是移动到  前  一个节点
			_n = _n->_prev;
			return *this;
		}
		Self operator++(int)
		{
			Self tmp = *this;
			_n = _n->_prev;
			return tmp;
		}
		Self& operator--()
		{
			//反向迭代器--，是移动到  后  一个节点
			_n = _n->_next;
			return *this;
		}
		Self operator--(int)
		{
			Self tmp = *this;
			_n = _n->_next;
			return tmp;
		}
		R operator*()const
		{
			return _n->_data;
		}
		F operator->()const
		{
			return &(_n->_data) ;
		}
		bool operator!=(const Self& obj)const
		{
			return _n!=obj._n;
		}
		bool operator==(const Self& obj)const
		{
			return !(*this != obj);
		}
	};

	template<class T>
	class list
	{
		//把双向带头循环链表的节点类型重命名成node
		typedef listnode<T> node;

	private:
		node* _head;//唯一的成员变量

		//获取初始头结点
		node* get_head_node()
		{
			//申请一个节点大小的空间
			node* tmp = new node;

			//最开始的头节点的prev和next都指向自己
			tmp->_next = tmp;
			tmp->_prev = tmp;

			return tmp;
		}

	public:
		
		typedef  Iterator<T, T&, T*> iterator;//普通迭代器

		typedef  Iterator<T, const T&, const T*>  const_iterator;//const迭代器

		typedef  Reverse_iterator<T, T&, T*>  reverse_iterator;//反向迭代器

		typedef  Reverse_iterator<T, const T&, const T*> const_reverse_iterator;//const反向迭代器


		list()
		{
			//获取头结点
			//为之后的插入操作做准备
			_head=get_head_node();
		}


		list(size_t n, const T& val=T())
		{
			//必须先获取头节点，才能进行插入数据
			_head = get_head_node();

			for (int i = 0; i < n; i++)
			{
				push_back(val);//尾插n次
			}
		}


		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			//必须先获取头节点，才能进行插入数据
			_head = get_head_node();

			while (first != last)
			{
				//把解引用之后的值，一个一个尾插进去
				push_back(*first);
				first++;
			}
		}


		list(int n, const T& val = T())
		{
			//必须先获取头节点，才能进行插入数据
			_head = get_head_node();


			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}


		list(initializer_list<T> il)
		{
			//必须先获取头节点，才能进行插入数据
			_head = get_head_node();

			auto it = il.begin();
			while (it != il.end())
			{
				//把解引用之后的值，一个一个尾插进去
				push_back(*it);
				it++;
			}
		}


		list(const list& obj)
		{
			//必须先获取头节点，才能进行插入数据
			_head = get_head_node();

			//使用const迭代器接收  const修饰的对象的迭代器
			const_iterator it = obj.begin();

			while (it != obj.end())
			{
				//把解引用之后的获得的值，一个一个尾插进去
				push_back(*it);
				it++;
			}
		}


		~list()
		{
			//先把list里面除了头结点
			//以外的节点全部删除
			clear();

			//再把头结点申请的空间释放
			delete _head;

			_head = nullptr;
		}


		list& operator= (list obj)
		{
			swap(obj);

			return *this;
		}


		void swap(list& obj)
		{
			//调用库里面的swap，交换头指针
			std::swap(_head, obj._head);
		}


		iterator begin()
		{
			//头节点的下一个节点 才是第一个节点
			return _head->_next;
		}

		//const修饰的对象只能调用const修饰的成员函数
		const_iterator begin()const
		{
			//头节点的下一个节点 才是第一个节点
			return _head->_next;
		}

		iterator end()
		{
			//最后一个节点的下一个节点是  头节点
			//因为是循环链表
			return _head;
		}
		//const修饰的对象只能调用const修饰的成员函数
		const_iterator end()const
		{
			return _head;
		}


		reverse_iterator rend()
		{
			//反向迭代器的rend返回的是第一个节点的   前一个节点
			return _head;
		}
		//const修饰的对象只能调用const修饰的成员函数
		const_reverse_iterator rend()const
		{
			return _head;
		}
		reverse_iterator rbegin()
		{
			//反向迭代器的rbegin()返回的是  最后一个节点
			//最后一个节点是  头节点的前一个
			//因为是循环链表
			return _head->_prev;
		}


		const_reverse_iterator rbegin()const
		{
			return _head->_prev;
		}
		

		void push_back(const T&val)
		{
			/*node* tail = _head->_prev;

			node* newnode = new node;
			newnode->_data = val;
			newnode->_next = _head;
			newnode->_prev = tail;

			tail->_next = newnode;

			_head->_prev = newnode;*/
			insert(end(), val);
		}


		iterator erase(iterator pos)
		{
			//不能  把 头节点 给删了
			assert(pos!=end());

			//记录pos的前一个节点（prev） 
			// 和后一个节点（next）
			node* prev = pos._n->_prev;
			node* next = pos._n->_next;
			
			//让prev的下一个节点变成next
			prev->_next = next;

			//让prev的上一个节点变成next
			next->_prev = prev;

			//释放pos指向的节点
			delete pos._n;

			//返回被删除的节点的下一个节点
			//用于更新迭代器
			return next;
		}


		iterator erase(iterator first, iterator last)
		{
			iterator it = first;
			while (it != last)
			{
				//删除it指向的节点
				//删除后让it接收返回值，进行更新
				it = erase(it);
			}
			//返回被删除的  最后一个节点  的下一个节点
			//用于更新迭代器
			return last;
		}

		bool empty() const
		{
			//size==0就   是空    返回true
			//size!=0就   不是空  返回false
			return size() ==0 ;
		}

		size_t size()const 
		{
			//用count记录节点个数
			size_t count = 0;

			//使用const迭代器接收  const修饰的对象的迭代器
			const_iterator it = begin();

			//遍历链表
			while (it != end())
			{
				count++;
				++it;
			}
			return count;
		}

		T& back()
		{
			//list不能为空，为空就报错
			assert(!empty());

			//end（）返回的迭代器指向  头结点
			//头结点的上一个节点就是，最后一个节点
			//因为是循环链表
			return *(--end());
		}

		//const修饰的成员，只能调用const修饰的成员函数
		const T& back() const
		{
			assert(!empty());

			return *(--end());
		}


		T& front()
		{
			//list不能为空，为空就报错
			assert(!empty());

			//begin()返回的迭代器  就指向第一个节点
			return *begin();
		}

		//const修饰的成员，只能调用const修饰的成员函数
		const T& front()const
		{
			assert(!empty());

			return *begin();
		}


		template <class InputIterator>
		void assign(InputIterator first, InputIterator last)
		{
			//先把数据现有的节点(除了头结点)都删除
			clear();

			//再循环把数据一个一个尾插进去
			while (first != last)
			{
				//尾插
				push_back(*first);
				first++;
			}
		}
		

		void assign(size_t n, const T& val)
		{
			clear();

			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
		void assign(int n, const T& val)
		{
			clear();

			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		iterator insert(iterator pos, const T& val)
		{
			//记录指向 pos 前一个节点的指针
			node* prev = pos._n->_prev;

			//申请新节点的空间
			node* newnode = new node;
			//存储数据
			newnode->_data = val;

			newnode->_next = pos._n;
			newnode->_prev = prev;

			prev->_next = newnode;
			pos._n->_prev = newnode;

			//返回指向新插入的节点的迭代器
			//用于更新迭代器
			return newnode;
		}


		template <class InputIterator>
		void insert(iterator pos, InputIterator first, InputIterator last)
		{
			while (first!=last)
			{
				//循环插入即可
				//因为list的迭代器使用完insert之后 不会失效
				//所以不用接收返回值  也可以
			    insert(pos,*first);
				first++;
			}
		}


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


		void resize(size_t n, const T& val = T())
		{
			//获取一下size，加快后续比较效率
			//因为获取size()的时间复杂度为  O(N)
			size_t size = this->size();

			if (n > size)
			{
                //缺失的数据用val填上
				//填到size()==n为止
				while (size < n)
				{
					push_back(val);
					++size;
				}
			}
			else 
			{
				//把多出来的数据（节点）删除
				//删除到n==size()为止
				while (n < size)
				{
					pop_back();
					n++;
				}
			}
		}

		void clear()
		{
			//[begin(),end())之间的数据
			//就是所有的有效数据(节点)
			//复用erase删除即可
			erase(begin(), end());
		}
	};
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570