list 的函数用法与 STL 库中其他的大差不差，本文章难度有些上升，将针对前面忽略的迭代器和模版进行深度解析，真正了解到底什么是迭代器，和迭代器的实现原理

学习list底层的重要性

list 底层是双向带头循环链表，在链表的任意位置进行插入和删除操作的时间复杂度都是 O(1)。这是因为链表插入或删除节点只需要修改相邻节点的指针。例如，在实现一个任务调度系统时，任务可能会随时被添加或移除，如果使用 std::list 来存储任务，就可以高效地处理这些操作

为了与库里的 list 进行区分，所有的类和函数都放在自定义的命名空间 bit 进行区分

节点模版

1
2
3
4
5
6
7
8
9
10
11
12
13
template<class T>
struct list_node
{
	list_node<T>* _next;
	list_node<T>* _prev;
	T _val;

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

经过数据结构的学习我们知道，每个节点都是一个结构体，因为是双向循环链表，所以有 prev 和 next，使用初始化列表进行常规的初始化

🔥值得注意的是：

  1. 这里使用 struct 而不是 class，是因为 struct 的默认访问权限是 public，class 的默认访问权限是 private ，虽然用 class＋友元 的方式也是可行的，但不如用 struct 来的方便
  2. 构造函数参数部分为 const T& val = T() ，而不是常写的 0 ，是因为 T 无法确定是自定义类型还是内置类型，所以当没有参数传入时就调用各自类型的默认构造函数进行传参

迭代器模版及实现

迭代器就是一个桥梁，让容器能通过迭代器实现算法

容器 <–> 迭代器 <–> 算法

根据迭代器的容器底层结构决定的性质，可以大致分为三类：

  1. 单向迭代器（forward iterator）：支持运算符重载 ++，常用容器为 forward_list、unordered_map、unordered_set
  2. 双向迭代器（bidirectional iterator）：支持运算符重载 ++、--，常用容器为 list、map、set
  3. 随机迭代器（random access iterator）：支持运算符重载 ++、--、+、-，常用容器为vector、string、deque

从下往上为依次包含的关系，比如 list 迭代器为双向，那么既可以用双向，也可以用单向，不能用随机。通常 std 库里的是随机迭代器

因此这也解释了为什么 vector 迭代器可以使用 std::iterator，也可以使用 vector<T>::iterator。但是 list 迭代器不可以使用 std::iterator，一般使用 list<T>::iterator

初步实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void test_list1()
{
	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;

	for (auto e : lt)
	{
		cout << e << " ";
	}
	cout << endl;
}

剖析底层代码先从功能入手，通常我们实现迭代器如代码所示

迭代器模版

那么要先实现基本的迭代器模版

1
2
3
4
5
6
7
8
9
10
template<class T>
struct _list_iterator
{
	typedef list_node<T> Node;
	Node* _node;

	_list_iterator(Node* node)
		:_node(node)
	{}
};

实现基本的构造函数，_node 是一个指向 Node 类型对象的指针，它用于存储当前迭代器所指向的链表节点

实现 push_back 往链表中放置数据，实现方式还是和双线链表中一样，可以去数据结构专题中回顾

push_back

传送门：【初阶数据结构】逆流的回环链桥：双链表

1
2
3
4
5
6
7
8
9
10
void push_back(const T& x)
{
	Node* tail = _head->_prev;
	Node* newnode = new Node(x);
	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;
	//insert(end(), x);
}

begin和end

接下来实现 begin() 和 end() ，还是比较简单的，这里直接展示放在 list 模版中的效果，后续就只单独列出实现功能的代码了

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
template<class T>
class list
{
	typedef list_node<T> Node;
public:
	typedef _list_iterator<T> iterator;
	iterator begin() const
	{
		return _head->_next;
	}

	iterator end() const
	{
		return _head;
	}

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

private:
	Node* _head;
};

list 模版有一个头节点，作为哨兵位，实现了双链表的构造函数，看似简单的代码，实则隐藏了很多的细节

🔥值得注意的是：

  1. begin() 和 end() 返回的是 iterator 类型，C++ 标准库提供了大量基于迭代器的通用算法（如 std::find、std::sort、std::for_each 等）。当自定义容器的 begin() 函数返回迭代器时，这些通用算法可以直接应用到自定义容器上，实现代码的复用
  2. iterator 是 _list_iterator<T> 模版的重命名，更符合使用习惯
  3. begin() 和 end() 返回的值看似是 Node* 类型，实际上单参数的函数支持隐式转换，Node* 隐式转换为 iterator 类型，return _head->_next 其实是 return iterator(_head->_next)
  4. begin() 和 end() 函数都用 const 修饰，使函数更具普遍性，包括 const 变量的情况，普通类型调用也是权限的缩小，两种情况共用一个函数

*解引用运算符重载

1
2
3
4
T& operator*()
{
	return _node->_val;
}

这里 _node 应该是一个指向链表节点的指针，_val 是链表节点中存储的数据成员。该函数返回节点数据 _val

++运算符重载

1
2
3
4
5
6
7
8
9
10
11
12
13
//前置
_list_iterator<T>& operator++()
{
	_node = _node->_next;
	return *this;
}
//后置
_list_iterator<T> operator++(int)
{
	self temp(*this);
	_node = _node->_next;
	return temp;
}

为了区分前置后置，前置 ++ 和后置 ++ 虽然是运算符重载，但是形式上也构成函数重载，后置 ++ 增加这个 int 参数不是为了接受具体的值，仅仅是占位，跟前置 ++ 构成重载， int 这个位置传任何值都可以，实际调用的时候前置 ++ 和后置 ++ 可能分别为 operator++() 和 operator++(0) ，括号内的值是随机的

🔥值得注意的是： 前置 ++ 返回的对象还存在，所以可以用引用，而后置 ++ 返回的对象是个临时对象，所以不能返回引用

!=运算符重载

1
2
3
4
bool operator!=(const _list_iterator<T>& it) const
{
	return _node != it._node;
}

该函数通过比较当前对象的 _node 成员变量和传入对象 it 的 _node 成员变量来判断两个对象是否不相等。如果 _node 和 it._node 不相等，则返回 true，表示两个对象不相等；否则返回 false，表示两个对象相等

🔥值得注意的是： 调用 end() 时传值返回，具有常性，所以 != 重载要参数加 const

以上就已经基本实现了迭代器，能够跑起来实现正常功能，范围 for 的底层也是迭代器，所以也能够使用了，但是还有很多需要完善的

在这里插入图片描述

再完善实现

通常迭代器分为 iterator 和 const_iterator

那么我们难道再写一个来实现吗，显然是不符合编程范式的，代码就显得太冗余了

有人或许会想到这么写：

1
2
typedef _list_iterator<T> iterator;
typedef const _list_const_iterator<T> const_iterator;

这样看起或许可行，但是我们要思考 const 的使用

举个例子：

1
2
const T* ptr1;
T* const ptr2;

这两段代码的含义分别为：不可以修改指向对象的内容，不可以修改指向别的对象

显然 typedef const _list_const_iterator<T> const_iterator 是第一种 const 的使用，在 ++ 运算符重载中有 _node = _node->_next ，需要通过这段代码来到下一个节点，按照我们这样加 const 就和这段代码冲突了。我们只是不想修改其内容，而不是无法跳转节点

所以发明 STL库的人真是个天才，想到了巧妙的办法：

1
2
3
4
5
6
迭代器模版
template<class T, class Ref>
......
list模版
typedef _list_iterator<T, T&> iterator;
typedef _list_iterator<T, const T&> const_iterator;

iterator 和 const_iterator 的区别就在于 * 运算符重载返回的值是否能够被修改，因此增加一个新的模版参数，当使用对应的迭代器就会调用相应的模版

最终完善实现

在查看STL库里的list底层代码时，会发现实际上的迭代器代码有三个参数，单纯去看是很难发现为什么要有第三个参数的，必须要结合实际的应用场景

举个例子：

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
struct A
{
	A(int a1 = 0, int a2 = 0)
		:_a1(a1)
		,_a2(a2)
	{}

	int _a1;
	int _a2;
};

void test_list2()
{
	list<A> lt;
	lt.push_back(A(1, 1));
	lt.push_back(A(2, 2));
	lt.push_back(A(3, 3));
	lt.push_back(A(4, 4));
	list<A>::iterator it = lt.begin();
	while (it != lt.end())
	{
		/*cout << (*it)._a1 << " " << (*it)._a2 << endl;*/
		cout << it->_a1 << " " << it->_a2 << endl;
		++it;
	}
	cout << endl;
}

假设有个类A，需要遍历输出，通常我们会写成 cout << (*it)._a1 << " " << (*it)._a2 << endl ，但是这并不符合编程范式

可是为什么写成 cout << it->_a1 << “ “ << it->_a2 << endl 也能通过？

严格来说，应该写成 it->->_a2，才符合语法，因为运算符重载要求可读性，所以编译器特殊处理，省略一个 ->

->运算符重载

所以我们可以写出 -> 运算符重载

1
2
3
4
Ptr operator->()
{
	return &(_node->_val);
}

同样的道理，为了实现iterator 和 const_iterator两种迭代器，再增加一个模版参数，同时因为模版参数有点过多，导致类型太长了，对类型也进行重命名

1
2
3
4
5
6
7
迭代器模版
template<class T, class Ref, class Ptr>;
typedef _list_iterator<T, Ref, Ptr> self;
......
list模版
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;

其余list函数功能实现

析构函数

1
2
3
4
5
6
~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

拷贝构造函数

1
2
3
4
5
6
7
8
9
10
11
list(const list<T>& lt)
{
	_head = new Node;
	_head->_prev = _head;
	_head->_next = _head;
	//万一拷贝的是string、vector等代价就大了，所以用&
	for (auto& x : lt)
	{
		push_back(x);
	}
}

=运算符重载

1
2
3
4
5
list<T>& operator=(list<T> lt)
{
	swap(lt);
	return *this;
}

swap

1
2
3
4
void swap(list<T>& lt)
{
	std::swap(_head, lt._head);
}

clear

1
2
3
4
5
6
7
8
void clear()
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}

insert

1
2
3
4
5
6
7
8
9
10
11
12
13
iterator insert(iterator pos, const T& x)
{
	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* newnode = new Node(x);

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

	return newnode;
}

erase

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;

	delete cur;
	return next;
}

push_front、pop_back、pop_front

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void push_front(const T& x)
{
	insert(begin(), x);
}

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

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

size

1
2
3
4
5
6
7
8
9
10
11
size_t size()
{
	size_t sz = 0;
	iterator it = begin();
	while (it != end())
	{
		++sz;
		++it;
	}
	return sz;
}

–运算符重载

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//前置
self& operator--()
{
	_node = _node->_prev;
	return *this;
}

//后置
self operator--(int)
{
	self temp(*this);
	_node = _node->_prev;
	return temp;
}

==运算符重载

1
2
3
4
bool operator==(const self& it) const
{
	return _node == it._node;
}

list模拟实现代码及测试代码展示

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
#pragma once
#include <iostream>
using namespace std;
#include <assert.h>

namespace bit
{
	//节点模版
	template<class T>
	struct list_node
	{
		list_node<T>* _next;
		list_node<T>* _prev;
		T _val;

		list_node(const T& val = T())
			:_next(nullptr)
			, _prev(nullptr)
			, _val(val)
		{}
	};
	//迭代器模版
	template<class T, class Ref, class Ptr>
	struct _list_iterator
	{
		typedef list_node<T> Node;
		typedef _list_iterator<T, Ref, Ptr> self;
		Node* _node;

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

		//const T& operator*()就可以实现const_iterator
		Ref& operator*()
		{
			return _node->_val;
		}
		
		Ptr operator->()
		{
			return &(_node->_val);
		}
		//前置
		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		//后置
		self operator++(int)
		{
			self temp(*this);
			_node = _node->_next;
			return temp;
		}

		self operator--(int)
		{
			self temp(*this);
			_node = _node->_prev;
			return temp;
		}

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

		bool operator==(const self& it) const
		{
			return _node == it._node;
		}
	};
	//list类模版
	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 const _list_const_iterator<T> const_iterator;
		//不能这样写，因为++没法next,就没法遍历了
		iterator begin() const
		{
			return iterator(_head->_next);
			//单参数的函数支持隐式转换
		}

		iterator end() const
		{
			return _head;
		}
		
		list()
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}

		list(const list<T>& lt)
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
			//万一拷贝的是string、vector等代价就大了，所以用&
			for (auto& x : lt)
			{
				push_back(x);
			}
		}

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

		list<T>& operator=(list<T> lt)
		{
			swap(lt);
			return *this;
		}
		
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		void 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);
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;*/
			insert(end(), x);
		}

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

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

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

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

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

			return newnode;
		}

		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;

			delete cur;
			return next;
		}

		size_t size()
		{
			size_t sz = 0;
			iterator it = begin();
			while (it != end())
			{
				++sz;
				++it;
			}
			return sz;
		}
	private:
		Node* _head;
	};

	void test_list1()
	{
		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();
		//调用end的函数时传值返回，具有常性,所以!=重载要参数加const
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}

	struct A
	{
		A(int a1 = 0, int a2 = 0)
			:_a1(a1)
			,_a2(a2)
		{}

		int _a1;
		int _a2;
	};

	void test_list2()
	{
		list<A> lt;
		lt.push_back(A(1, 1));
		lt.push_back(A(2, 2));
		lt.push_back(A(3, 3));
		lt.push_back(A(4, 4));
		//严格来说，应该写成it->->_a2，才符合语法
		//因为运算符重载要求可读性，所以编译器特殊处理，省略一个->
		list<A>::iterator it = lt.begin();
		while (it != lt.end())
		{
			/*cout << (*it)._a1 << " " << (*it)._a2 << endl;*/
			cout << it->_a1 << " " << it->_a2 << endl;
			++it;
		}
		cout << endl;
	}

	void test_list3()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		lt.push_front(5);
		lt.push_front(6);
		lt.push_front(7);
		lt.push_front(8);

		lt.pop_front();
		lt.pop_back();

		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		
		lt.clear();
		lt.push_back(10);
		lt.push_back(20);
		lt.push_back(30);
		lt.push_back(40);
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
		cout << lt.size() << endl;
	}

	void test_list4()
	{
		list<int> lt1;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		for (auto e : lt1)
		{
			cout << e << " ";
		}
		cout << endl;
		list<int> lt2;
		lt2 = lt1;
		for (auto e : lt2)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！

请添加图片描述