STL—list—模拟实现【迭代器的实现(重要)】【基本接口的实现】

STL—list—模拟实现

1.list源代码

要想模拟实现list，还是要看一下STL库中的源代码。

_list_node里面装着指向上一个节点的指针prev，和指向下一个节点的指针next，还有数据data

并且它给的是void*，导致后面进行节点指针的返回时需要进行强转

前面的link_type就是节点的指针类型，对(*node).next进行强转。

这样有点麻烦，我自己的模拟实现就不搞这个void*了，直接给节点的指针类型，这样后面不用强转。

2.list模拟实现

为了避免和库里的list发生冲突，我们要自己开辟一个命名空间。名字随意。

首先节点__list_node是一个自定义类型，list是一个带头双向循环链表。

__list_node需要存放三个成员变量，存放的就是一个指向上一个节点的指针_prev，一个指向下一个节点的指针_next，还有存放的数据_data。

list需要存放一个指向头节点（哨兵位）的指针_head

namespace wzf
{
	template<class T>
	struct __list_node
	{
		__list_node<T>* _prev;
		__list_node<T >* _next;
		T _data;
        
        __list_node(const T& x = T()) // 要给缺省值。因为头节点不好给值，用默认的初始值
			:_next(nullptr)
			,_prev(nullptr)
			,_data(x)
		{}
	};

	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;
		typedef Reverse_list_iterator<iterator> reverse_iterator;
		typedef Reverse_list_iterator<const_iterator>const_reverse_iterator;

	private:
		Node* _head; 
	};
}
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

2.1构造函数

list是带头双向循环链表。构造函数的话就开辟一个空间给头节点，然后再让其自身的两个指针指向自己就OK。

		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}
1
2
3
4
5
6

2.2正向迭代器（重要）

在list的模拟实现中，最重要的就是迭代器的实现。因为他不在是简单的指针了，它有一个自定义类型进行了封装，这个类型里面装的还是节点的指针，通过重载++等运算符去实现迭代器的移动。

为什么要这么做？【因为list是链表，链表的节点不是在物理上不是连续的地址，是一块块的，只是由指针链接到了一起而已。如果直接用节点的指针来做迭代器，在进行++等操作就会出现错误。】

list的迭代器实现：

简单来说就是用一个类型去封装节点的指针，从而构成一个自定义类型。再去重载++等操作符，在重载中去实现节点的迭代

对于实现一个迭代器来说，有两种方法。

1. 一种是原生指针，就是之前的vector的迭代器
2. 第二组就是对一个自定义类型进行封装，让它具备指针的功能。

而我们对list的迭代器实现要通过对自定义类型进行封装

因此这个自定义的类，我们要对其进行封装，重载操作符，让其具备基本功能：

1. 能够进行解引用， 因此要重载operator*
2. 能够进行指针的->操作来访问存储的成员的空间， 因此要重载operator->
3. 能够进行迭代器的迭代，比如++等操作。因此要重载++，这里前置和后置++都要重载
4. 由于list是带头双向循环链表，因此可以进行–操作，要重载–，前置和后置–都要重载
5. 迭代器要支持是否相等或者不相等，因此要重载!= 和 ==

还有一个要注意的地方，迭代器的应用场景还有一个const迭代器。因此有些情况我们会将容器作为参数传给一个函数，在该函数当中我们并不想去改变容器对象的本身，因此函数的形参是const，我们就需要用const迭代器。具体的一个场景如下：

下面这个函数只想要打印链表的内容，但是不想去改变链表本身，因此形参是const list<int>& l，这个时候const迭代器就派上用场了。

	void print_list(const list<int>& l)
	{
		// l是const对象，因此cit需要是const的迭代器
		list<int>::const_iterator cit = l.begin();
		while (cit != l.end())
		{
			cout << *cit << " ";
			++cit;
		}
		cout << endl;
	}
1
2
3
4
5
6
7
8
9
10
11

const迭代器可以通过传三个模版参数去控制调用的是const迭代器还是非const的迭代器

• list_iterator<T, T&, T*> -> iterator

• __list_iterator<T, const T&, const T*> -> const_iterator

【要注意不是迭代器这个类型的对象为const对象，不然++等操作会报错】

正向迭代器的代码如下：

	// 迭代器 (通过三个模版参数，来控制调用的是const迭代器还是非const的迭代器)
	// 【要注意不是迭代器这个类型的对象为const对象】
	// __list_iterator<T, T&, T*> -> iterator
	// __list_iterator<T, const T&, const T*> -> const_iterator
	template<class T, class Ref, class Ptr>
	struct __list_iterator
	{
		typedef __list_node<T> Node;
		typedef __list_iterator<T, Ref, Ptr> Self;

		Node* _node; // 迭代器中的_node成员变量，存储着目前迭代器所指向的节点。

		__list_iterator(Node* node = nullptr)
			:_node(node)
		{}
		
		//返回Ref，const就返回const，非const返回非const 
		Ref operator*()
		{
			return _node->_data; // this->_node->_data;
		}

		// Ptr控制返回的是const属性还是非const
		Ptr operator->()
		{
			return &_node->_data;
		}

		// 前置++
		Self& operator++() 
		{
			_node = _node->_next;
			return *this;
		}

		// 后置++
		Self& operator++(int) // 加这个int才能让编译器知道这个是后置++的重载
		{
			/*__list_iterator<T> tmp = *this;
			_node = _node->_next;
			return tmp; */
			// 考虑用代码复用
			Self tmp(this->_node); // Self tmp(*this); 
			// 如果不实现拷贝构造，传*this去调用系统默认的拷贝构造也可以实现，但是是浅拷贝，要注意实际是否会出错
			++(*this);
			return tmp;
		}

		// 前置--
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		// 后置--
		Self& operator--(int)
		{
			/*__list_iterator<T> tmp = *this;
			_node = _node->_prev; 
			return tmp; */
			// 考虑用代码复用
			Self tmp(this->_node);
			--(*this);
			return tmp;
		}

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

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

list的迭代器实现是list的模拟实现的一个重点，这个内容和之前我们的模拟实现不太一样，是通过封装成一个自定义类型实现的，需要仔细思考。

2.3反向迭代器（重要）

反向迭代器其实也可以像正向迭代器那样去实现，但是也可以借助正向迭代器去实现。

反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++。我们只需要对正向迭代器的接口进行包装就行了。

简单来说就是：反向迭代器内部可以包含一个正向迭代器

思路：

反向迭代器的rbegin指向最后一个数据，rend指向头节点。

具体实现如下：

	// 反向迭代器 (借助正向迭代器实现)
	template<class iterator>
	struct Reverse_list_iterator
	{
		// 注意：此处typename的作用是明确告诉编译器，Ref是Iterator类中的一个类型，而不是静态成员变量
		// 否则编译器编译时就不知道Ref是Iterator中的类型还是静态成员变量
		// 因为静态成员变量也是按照 类名::静态成员变量名 的方式访问的
		typedef typename iterator::Ref Ref;
		typedef typename iterator::Ptr Ptr;
		typedef Reverse_list_iterator<iterator> Self;

		iterator _it; // 给一个成员变量是 正向迭代器类型的

		// 构造函数
		Reverse_list_iterator(iterator it)
			:_it(it)
		{}

		// 能够具有指针类似行为的* 和 ->的重载
		Ref operator*()
		{
			iterator temp(_it);
			--temp; // 对于反向迭代器来说，正向迭代器的迭代器整体往后移动一次，才能正常使用。具体可以画图
			return *temp;
		}

		Ptr operator->()
		{
			//return &(operator*()); // 让自己去调用*拿到存储的数据T

			return &(_it._node)->_data; //等价于上面
		}

		// 具备移动能力，对++，--等运算符进行重载
		Self& operator++()
		{
			--_it; // 反向迭代器的++就是正向的--
			return *this;
		}

		Self& operator++(int)
		{
			Self tmp(this->_it); // 也可以Self tmp(*this);
			--_it;
			return tmp;
		}

		Self& operator--()
		{
			++_it;
			return *this;
		}

		Self& operator--(int)
		{
			Self tmp(this->_it);
			++_it;
			return *this;
		}

		// 具备相比的能力
		bool operator!=(const Self& rit) const
		{
			return _it != rit._it;
		}

		bool operator==(const Self& rit) const
		{
			return _it == rit._it;
		}

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

2.3拷贝构造

拷贝构造还是我们老生常谈的问题了，要注意浅拷贝问题的出现。

这里如果有忘记要记得复习之前的内容，这里就直接贴代码了、

	// 拷贝构造
	list(const list<T>& l)
	{
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;

		// 遍历l，进行深拷贝
		const_iterator it = l.begin();
		while (it != l.end())
		{
			push_back(*it);
			++it;
		}
		// 要想代码简洁一点。可以用范围for，反正支持迭代期间就能支持范围for
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.4赋值运算符重载

赋值运算符也要注意浅拷贝问题。

要注意赋值运算符的实现和拷贝构造的区别就是

• l1(l2)时候的l1是不存在的。

• l1 = l2的时候l1是存在的，要注意资源的清理，不然会内存泄漏

传统写法：

		// 赋值运算符重载
		list<T>& operator=(const list<T>& l)
		{
			// 防止自己给自己赋值
			if (this != &l)
			{
				// 先清除掉自身，清除完再尾插。
				clear(); // 不清除会内存泄漏。

				// 直接用范围for。
				for (auto e : l)
					push_back(e);
			}

			return *this;
		}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

现代写法：

	// 赋值运算符——现代写法
	list<T>& operator=(list<T> l) // l通过拷贝构造就是我们要的
	{
		swap(_head, l._head); // 交换一下，把我们不要的给l，结束该作用域l会调用析构函数来销毁，清除我们不要的数据。
		return *this;
	}
1
2
3
4
5
6

2.5析构函数

析构函数我们先清除掉除了头节点的所有节点，然后在清除头节点。不能直接清除头节点，不然会造成内存泄漏

	~list()
	{
		clear(); // 除了头节点，其他节点都已经释放了。
		delete _head; // 释放头节点
		_head = nullptr;
	}

1
2
3
4
5
6
7

2.6 clear()

clear要删除除了头节点的所有节点。

clear通过erase的函数复用

		// clear要注意保留头节点(哨兵位)，因为clear之后可能继续插入数据。
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it++); // ++的处理后，该迭代器不会失效
			}
		}
1
2
3
4
5
6
7
8
9

2.7 erase()

iterator erase(iterator pos)

erase要删除节点，要先将pos位置的节点前后关系处理好，再提前用ret记载好pos位置，

删除pos位置的节点，返回ret。

iterator erase(iterator pos)
{
	assert(pos != end()); // 不能删除哨兵位
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

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

	iterator ret = ++pos; // 要返回pos的下一个节点，因为删除该位置的节点后pos会失效。

	delete cur; // cur是一个指针类型，指向节点（结构体）的指针
	cur = nullptr;

	return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.8 push_back()

list是带头双向循环链表，尾插时要处理好关系。如果忘记其基础物理结构要复习。

		void push_back(const T& x)
		{
			
			// 无论该链表是否有节点，下面这段代码都能完成任务。
			Node* tail = _head->_prev;
			Node* newnode = new Node(x); // 数据已经插入节点了
			// 接下来要做的就是处理节点之间的链接关系
			newnode->_next = _head;
			newnode->_prev = tail; 
			tail->_next = newnode;
			_head->_prev = newnode;

		}
1
2
3
4
5
6
7
8
9
10
11
12
13

实现了insert之后，可以用其代码复用：

		void push_back(const T& x)
		{
			// 实现insert了之后，可以代码复用
			insert(end(), x);
		}
1
2
3
4
5

2.9 pop_back()

直接用erase代码复用

要注意由于erase不能删除头节点，因此要传--end()

		void pop_back()
		{
			// 用erase代码复用
			erase(--end());
		}
1
2
3
4
5

2.10 push_front

这里不再具体实现，直接用erase复现。push_back那边有具体实现

		void push_front(const T& x)
		{
			// 可以和push_back一样，常规实现，也可以用insert代码复用.
			insert(begin(), x);
		}
1
2
3
4
5

2.11 pop_front

		void pop_front()
		{
			// 代码复用
			erase(begin());
		}
1
2
3
4
5

2.12 insert

		void insert(iterator pos, const T& x)
		{
			Node* newnode = new Node(x); // 创建要插入的节点
			Node* cur = pos._node; // cur指向pos位置的节点
			Node* prev = cur->_prev; // prev指向pos位置的上一个节点

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

			newnode->_next = cur;
			newnode->_prev = prev;
		}
1
2
3
4
5
6
7
8
9
10
11
12

3.总结：

list模拟实现的总代码和测试代码：

list-04/list.h · WZF-sang/Cpp-Learn - 码云 - 开源中国 (gitee.com)

list的模拟实现的目的并不是将其实现的多好或者多还原，我模拟实现list只是为了去更好的学习其底层原理。本次模拟实现的重点就是迭代器的实现，list的迭代器是一个自定义类型，其通过三个模版参数实现正向迭代器，和借助正向迭代器实现反向迭代器这个过程有助于我更好的理解和学习list这个容器。

并且list和vector在面试的时候经常问到。

第一个问题：

在STL—vector—模拟实现【深度理解vector】【模拟实现vector基本接口】-CSDN博客的最后有讲解，忘了就复习

第二个问题：

vector的底层是一个动态顺序表，是通过三个原生指针实现的，list是带头双向循环链表，底层由一个_prev和一个__next,还有存储的数据data实现。

第三个问题：

vector的增容涉及到开辟新空间，转移数据，删除旧空间，其耗费的代价相较于list来说更大。list不存在增容操作，需要插入就开辟一个节点的空间，然后存数据然后插入。

第四个问题：

迭代器失效其实就是一个迭代器不在精准的指向容器的位置。在list中，只有在删除节点的时候会存在迭代器失效。坐在vector中迭代器失效有两种情况。一种是删除数据，还有一种情况是给了迭代器之后又插入数据