【C++】一文带你走进list的模拟实现

🌈欢迎来到C++专栏~~list模拟实现

---

• (꒪ꇴ꒪(꒪ꇴ꒪ )🐣,我是Scort
• 目前状态：大三非科班啃C++中
• 🌍博客主页：张小姐的猫~江湖背景
• 快上车🚘，握好方向盘跟我有一起打天下嘞！
• 送给自己的一句鸡汤🤔：
• 🔥真正的大师永远怀着一颗学徒的心
• 作者水平很有限，如果发现错误，可在评论区指正，感谢🙏
• 🎉🎉欢迎持续关注！
  

上问我们得知：list即带头双向循环链表，支持在任意位置O(1)的插入和删除

一. list大框架

list_node节点

namespace ljj
{
	template<class T>
	class list_node
	{
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		//构造
		list_node(const T& x = T())//全缺省 ~ 构造匿名对象
			:data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
	
	template<class T>
	class list
	{
		typedef list_node<T> Node;
	public:
		list()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

	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
31
32

为了测试，我们迅速实现一个尾插吧，忘记的话可以画图（我画的有点丑）

		//尾插
		void push_back(const T& x)
		{
			Node* tail = _head->_prev;
			Node* newnode = new Node(x);

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

二 .迭代器（狠重要）

🌍相比vector和string那些连续的物理空间，原生指针就是天生的迭代器，但对于list在空间上不连续的数据结构，解引用不能取到数据，++也不能到不了下一个节点

为此，对于链表的迭代器，我们用自定义类型对结点的指针进行封装，底层仍然是结点的指针。C++的自定义类型支持运算符重载，原本的运算符编程变成函数调用，这样就可以实现像内置类型一样使用运算符，这就是c++厉害的地方 up！

构造迭代器，仅需要一个节点就可以构造了

	template<class T>
	struct __list_iterator
	{
		typedef ListNode<T> Node;
		typedef __list_iterator<T,Ref,Ptr> Self;
		Node* _node;//节点指针

		__list_iterator(Node* x)//提供一个节点构造
			: _node(x)
		{}
    };
1
2
3
4
5
6
7
8
9
10
11

迭代器的拷贝构造&赋值重载都不需要我们自己实现，因为我们要的就是浅拷贝，用编译器默认生成的即可

灵魂发问：迭代器需不需要析构函数，把节点释放掉？不要，释放节点归链表管，迭代器是借助结点指针来访问修改链表的，不属于迭代器管，好比人家借东西给你用，你却把人家东西故意弄丢了，很可笑

🌍iterator & const_iterator

• 我们在list中进行typedef，这样所有容器迭代器名字统一都是iterator
• 我们知道const迭代器和普通迭代器的唯一区别就是：普通迭代器返回的是T&，可读可写；const迭代器返回的是const T&，可读不可写。我们当然可以再继续封装一个类（此处不能重载，因为返回值不同），__const_list_iterator类，但是会造成代码冗余，看了源码我们发现：传入模板参数解决了这个问题，这也是迭代器的精华

🎨重载 *

*it 就是要取迭代器指向的数据，并且返回这个数据的引用，可以修改

//*it -> it.opeartor*()    可读可写
T& operator*()
{
	return _node->_data;
}
1
2
3
4
5

🎨重载 ->

如果T不是int等内置类型，而是自定义类型，我们访问其中的成员，需要重载->

	struct pos
	{
		int _a1;
		int _a2;

		pos(int a1 = 0 , int a2 = 0)
			:_a1(a1)
			,_a2(a2)
		{}
	};

	void test_list2()
	{
		int x = 10;
		int* p1 = &x;

		cout << *p1 << endl;

		pos aa;
		pos* p2 = &aa;
		p2->_a1;
		p2->_a2;//找结构体成员

		list<pos> lt;
		lt.push_back(pos(10, 20));
		lt.push_back(pos(20, 50));

		list<pos>::iterator it = lt.begin();
		while (it != lt.end())
		{
		    //cout << *it << endl; // 错误示范，请勿模仿
            // 因为Date是自定义类型，需要重载<<来打印，但要就是不给你提供呢，下面这样是可以的,很别扭
			//cout << (*it)._a1 << ":" << (*it)._a2 << endl;
			cout << it->_a1 << ":" << it->_a2 << endl;
			++it;
		}
		cout<< endl;
	}
}
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

迭代器it是去模仿指针的行为。在list中，如果节点中是int这样的内置类型，解引用(本质调用函数)访问数据即可；而像这里一个结构体的指针，我们固然可以(*it)拿到日期类对象.访问成员，但我们更希望能->访问成员，因此我们还需要重载->

		//  ->    
 		T* operator->()
		{
			return &(operator*());//调用了operator*() -> &(_node->data)
		}
1
2
3
4
5

这里本来应该是it->->_year，但是这样写运算符可读性太差了，所以编译器进行了优化，省略了一个->，对于cosnt对象，就是返回const指针，也就是添加了ptr参数的原因

🎨++ / – 和 == / !=

此处比较简单，直接上代码了

        //  ++it  返回值还是迭代器   日期类++返回的是日期类
		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		// it++
		iterator& operator++(int)
		{
			iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		//--it
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		// it--
		iterator& operator--(int)
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
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

🌍反向迭代器(迭代器适配器)

反向迭代器就是对正向迭代器的封装，这样它可以是任意容器的反向迭代器。

• 二者的不同之处：++调的是正向迭代器的–；–调的是正向迭代器的++
• 源码中为了对称的设计，使正向迭代器&反向迭代器的开始和结束保持对称，解引用*取前一个位置（我的开始就是你的结束）

为啥要这样子对称设计呢？直接解引用当前位置（哨兵位）的值，可能是随机值，出错

对于vector的反向迭代器，如果是我们预想的那样(解引用取的是当前位置)，会有越界访问问题

为了获取数据类型T，我们还需要增加两个类模板参数Ref、Ptr，同时也可以区分普通参数与const参数。源码中不带这两个参数，是通过迭代器萃取技术实现的（难难难）

namespace ljj
{
	//复用, 迭代器适配器  给list就出list的反向迭代
	template<class Iterator, class Ref, class Ptr>
	struct __reverse_iterator
	{
		Iterator _cur;
		typedef __reverse_iterator<Iterator, Ref, Ptr> RIterator;

		__reverse_iterator(iterator it)
			:_cur(it)
		{}

		RIterator operator++()
		{
			--_cur;
			return *this;
		}

		RIterator operator++(int)
		{
			RIterator(tmp);
			--_cur;
			return tmp;
		}

		RIterator operator--()
		{
			++_cur;
			return *this;
		}

		RIterator operator--(int)
		{
			RIterator(tmp);
			++_cur;
			return tmp;
		}

		Ref operator*()
		{
			Iterator tmp = _cur;
			return *(--tmp);//解引用上一个位置
		}

		Ptr operator->()
		{
			//return _cur.operator->();
			return &(operator*());
		}

		bool operator!=(const RIterator& it)
		{
			return _cur != it._cur;
		}

		bool operator==(const RIterator& it)
		{
			return _cur == it._cur;
		}
	};
}
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

反向迭代器：迭代器适配器，可以适配支持符合的反向迭代器

三. 增删查改

⚡insert & erase

💦insert

• 插入的位置是pos的上一个
• 返回值是newnode位置的迭代器
• list的insert会导致迭代器失效吗？我们知道vector中迭代器失效的原因：扩容导致的野指针；pos意义改变，显然这里都不符合，所以不会发生

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

			Node* newnode = new Node(x);

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

			return iterator(newnode);//构造迭代器返回
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

💦erase

• 注意哨兵位的头结点不能删
• 返回值是删除位置的下一个数据的迭代器
• erase后迭代器必定失效，节点都被干掉了，pos你说指向哪里？

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

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

			return iterator(next);
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

⚡push_back & push_front

注意插入位置

		//尾插
		void push_back(const T& x)
		{
			insert(end(), x);
		}

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

⚡pop_back & pop_front

也是要注意删除的位置

		//尾删
		void pop_back()
		{
			erase(--end());
		}

		//头删
		void pop_front()
		{
			erase(begin());
		}
1
2
3
4
5
6
7
8
9
10
11

四. list的默认成员函数

🌈构造

✨无参构造

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

✨迭代器区间构造

	//迭代器区间构造
	template <class InputIterator>  
	list(InputIterator first, InputIterator last)
	{
		while (first != last)
		{
			push_back(*first);//前提是已经构造了头结点
			++first;
		}
	}
1
2
3
4
5
6
7
8
9
10

所以我们干脆实现一个empty_init来初始化，

	void empty_init()
	{
	    //创建并初始化哨兵位的头结点
		_head = new Node;
		_head->_next = _head;
		_head->_prev = _head;
	}
1
2
3
4
5
6
7

注意必须给一个头，否则_head是一个随机值，换给tmp后出作用域调用析构函数，clear时获取begin()要解引用 _head-> _next会崩溃

🌈~析构 & clear

🌍claer
查阅文档发现库中还提供了一个clear的函数

注意要给给it ，因为erase后此结点失效，返回下一个节点的迭代器

	//clear 不清理头结点
	void clear()
	{
		iterator it = begin();
		while (it != end())
		{
			it = erase(it);//注意要给给it ，因为erase后此结点失效，返回下一个节点的迭代器
		}
	}
1
2
3
4
5
6
7
8
9

🌍析构函数

因此析构可以直接复用clear，但头结点也要一并释放

	//析构  全部都清理，生命周期到了
	~list()
	{
		clear();
		delete _head;
		_head = nullptr;
	}
1
2
3
4
5
6
7

🌈拷贝构造

此处的浅拷贝会导致：

• 二者修改的都是同一个链表的数据
• 析构两次会崩溃的问题

所以我们要实现深拷贝—— ps:（this）的哨兵位不释放，已经换给lt2，tmp出作用域要释放

✅传统写法：利用范围for🍬尾插——

	list(const list<T>& lt)
	{
		 empty_init();
	     for(auto& e : lt)
	     {
	     	push_back(e);
	     }
	}
1
2
3
4
5
6
7
8

✅现代写法：

	//lt2(lt1)
	list(const list<T>& lt)
	{
		empty_init();
		list<T> tmp = (lt.begin(), lt.end());
		swap(tmp);
	}
1
2
3
4
5
6
7

也实现了swap函数

	void swap(list<T>& x)//这里的不是list也可以，因为在这个类里面
	{
		std::swap(_head, x._head);
	}
1
2
3
4

🌈赋值重载

✅传统写法：

     //lt1 = lt3
    list<T>& operator=(const list<T>& lt)
    {
        if (this != &lt)
        {
            clear(); //清理lt1
            for (auto e : lt)
            {
                push_back(e);
            }
        }
        return *this;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

✅现代写法：（压榨思路）

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

🌈小细节

我们可以看见文档里面的list都没有加类型

• 在类的外面必须要有模板参数:list , 类名不是类型，带模板参数才是类型
• 在类里面：可以用类名代表类型（真心不建议）

五. list & vector 区别和联系

【面试题】 list & vector的区别和联系

附源码

list.h

#pragma once
#include

using namespace std;

namespace ljj
{
	template<class T>
	class list_node
	{
	public:
		friend class list<T>;

		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;

		//构造
		list_node(const T& x = T())//全缺省 ~ 构造匿名对象
			:_data(x)
			,_next(nullptr)
			,_prev(nullptr)
		{}
	};
	 

	//  typedef __list_iterator
	//  typedef __list_iterator


	template<class T, class Ref, class Ptr>//模板参数泛型化
	struct __list_iterator
	{
		typedef list_node<T> Node;
		typedef __list_iterator<T,Ref,Ptr> iterator;



		typedef bidirectional_iterator_tag iterator_category;
		typedef T value_type;
		typedef Ptr pointer;
		typedef Ref reference;
		typedef size_t size_type;
		typedef ptrdiff_t difference_type;

		Node* _node;//节点指针

		__list_iterator(Node* node)//提供一个节点构造
			:_node(node)
		{}

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

		bool operator==(const iterator& it) const
		{
			return _node == it._node;
		}
		
		//*it -> it.opeartor*()    可读可写
		//const T& operator*()    不能重载，因为返回值不同
		//T& operator*()
		Ref operator*()
		{
			return _node->_data;
		}

		//  ->    
		//T* operator->()
		Ptr operator->()
		{
			return &(operator*());
		}

		//  ++it  返回值还是迭代器   日期类++返回的是日期类
		iterator& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		// it++
		iterator& operator++(int)
		{
			iterator tmp(*this);
			_node = _node->_next;
			return tmp;
		}

		//--it
		iterator& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		// it--
		iterator& operator--(int)
		{
			iterator tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
	};

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

		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;

			empty_init();
		}

		//拷贝构造
		//lt2(lt1)
		list(const list<T>& lt)
		{
			empty_init();
			list<T> tmp = (lt.begin(), lt.end());
			swap(tmp);
		}

		//赋值重载
		//lt1 = lt3
		list<T>& operator= (list<T> lt)
		{
			swap(tmp);
			return *this;
		}

		void swap(list<T>& x)//这里的不是list也可以，因为在这个类里面
		{
			std::swap(_head, x._head);
		}

		void empty_init()
		{
			//创建并初始化哨兵位的头结点
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		//迭代器区间构造
		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			empty_init();
			while (first != last)
			{
				push_back(*first);//前提是已经构造了头结点
				++first;
			}
		}
		
		//析构  全部都清理，生命周期到了
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		//clear 不清理头结点
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);//注意要给给it ，因为erase后此结点失效，返回下一个节点的迭代器
			}
		}

		


		//尾插
		void push_back(const T& x)
		{
			//Node* tail = _head->_prev;
			//Node* newnode = new Node(x);

			_head      tail     newnode
			//tail->_next = newnode;
			//newnode->_prev = tail;
			//newnode->_next = _head;
			//_head->_prev = newnode;

			//复用insert
			insert(end(), x);
		}

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

		//插入
		iterator insert(iterator pos, const T& x)
		{
			Node* cur = pos._node;//迭代器是struct，就能访问其成员
			Node* prev = cur->_prev;

			Node* newnode = new Node(x);

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

			return iterator(newnode);//构造迭代器返回
		}


		//尾删
		void pop_back()
		{
			erase(--end());
		}

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

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

			return iterator(next);
		}

	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);
		lt.push_back(5);

		//只能迭代器遍历
		list<int>::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		it = lt.begin();
		while (it != lt.end())
		{
			*it *= 2;
			++it;
		}
		cout << endl;
	}


	struct pos
	{
		int _a1;
		int _a2;

		pos(int a1 = 0 , int a2 = 0)
			:_a1(a1)
			,_a2(a2)
		{}
	};

	void test_list2()
	{
		int x = 10;
		int* p1 = &x;

		cout << *p1 << endl;


		pos aa;
		pos* p2 = &aa;
		p2->_a1;
		p2->_a2;//找结构体成员

		list<pos> lt;
		lt.push_back(pos(10, 20));
		lt.push_back(pos(20, 50));

		list<pos>::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_back(5);

		list<int> copy = lt;
		for (auto e : lt)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}
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

📢写在最后

不上课被辅导员抓去谈话了