C++：关于模拟实现vector和list中迭代器模块的理解

文章目录

list和vector的迭代器对比
list的实现过程
完整代码

本篇是关于vector和list的模拟实现中，关于迭代器模块的更进一步理解，以及在前文的基础上增加对于反向迭代器的实现和库函数的对比等

本篇是写于前面模拟实现的一段时间后，重新回头看迭代器的实现，尤其是在模板角度对list中迭代器封装的部分进行解析，希望可以对迭代器的封装实现有更深层次的理解，同时将与库内的实现做对比进行优化处理

list和vector的迭代器对比

list和vector的迭代器实现是不一样的，在vector中的迭代器就是一个原生指针，因此在实现的时候也就是用的原生指针即可，但是对于list来说不能这样，list的迭代器中例如++和--这样的操作，是不能和vector中的原生指针一样直接去实现的，而是需要用next或者是prior来模拟这个过程，还有例如*和->这样的访问数据的模式，因此在list的迭代器实现中是使用了封装来进行实现的

STL中有六大组件，其中迭代器算其中一个，那么也就意味着迭代器具有通用的功能，例如下面的代码，在使用构造函数时可以使用迭代器进行构造，而这个构造的过程使用的迭代器对于各种容器来说都是通用的：

#include 
#include 
#include 
using namespace std;

int main()
{
	vector<int> v1{ 1,2,3,4,5,3,2,2 };
	vector<int> v2(v1.begin(), v1.end());
	list<int> l1(v1.begin(), v1.end());
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12

那么就意味着，在实现迭代器的过程中也是就可以根据迭代器来进行不同容器间的构造

list的实现过程

首先，在list的实现过程中要有下面几个部分组成：list中包含的节点，list的迭代器访问，list的节点之间的关系

那么首先就是list中节点的定义，用到了模板，现在再对该部分进行解析，其实就是在创建的时候可以根据需要的内容开辟出对应的节点类型

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

	list_node(const T& x = T())
		:_data(x)
		, _next(nullptr)
		, _prev(nullptr)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13

有了节点信息，就可以对list做一些基础的操作，例如头插头删，尾插尾删等操作，但对于insert和erase这些操作还不能够实现，因此就要实现迭代器模块的内容

不管是对于vector还是list，迭代器的本质就是用一个原生指针去进行访问等等，但是list和vector不同的是，list的存储地址并不是连续的，因此在访问的过程中就需要对迭代器进行一定程度的封装，例如在++或者--的操作符上可以进行一些体现，因此list迭代器的实现是需要进行单独的封装的

// 定义正向迭代器
template <class T, class Ref, class Ptr>
class __list_iterator
{
public:
	typedef list_node<T> Node;
	typedef __list_iterator<T, T&, T*> self;
	__list_iterator(Node* node)
		:_node(node)
	{}

	self& operator++()
	{
		_node = _node->_next;
		return *this;
	}
	self& operator++(int)
	{
		self tmp(*this);
		_node = _node->_next;
		return tmp;
	}
	self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}
	self& operator--(int)
	{
		self tmp(*this);
		_node = _node->_prev;
		return tmp;
	}
	Ref operator*()
	{
		return _node->_data;
	}
	Ptr operator->()
	{
		return &_node->_data;
	}
	bool operator !=(const self& s)
	{
		return _node != s._node;
	}
	bool operator ==(const self& s)
	{
		return _node == s._node;
	}
	Node* _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

上面的片段对list进行了一些封装，实现了它的一些基础功能，从代码中也能看出来，迭代器的本质确确实实就是指针，用指针来进行一系列的操作，对下面这几个片段单独进行解析：

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

这是对于迭代器中解引用的运算符重载，这里使用的是&_node->_data的写法，看似很怪，但是实际上这里的函数调用过程应该是这样

在这里插入图片描述
也就是说，这里对于->进行运算符重载后，还需要进行解引用，这个运算符重载函数返回的是一个指针，而这个指针还要继续进行解引用才能得到用户想要得到的值，编译器在这里进行了特殊处理，两个->使得可读性下降，因此将两个->进行了一定程度的合并，只需要一个->就可以实现解引用的目的

其次是对模板的使用部分

template <class T, class Ref, class Ptr>

	typedef list_node<T> Node;
	typedef __list_iterator<T, T&, T*> self;
1
2
3
4

这里在最开始定义的时候，就定义了数据类型，引用和指针三种模板参数，借助这个参数就可以用模板将复杂的内容实现简单化，只需要一份代码，模板就可以直接实例化出用户在调用的时候需要的代码，在进行封装const迭代器的时候，只需要提供的参数改为const版本就可以实现目的，很便捷

这样就实现了正向迭代器的普通版本，而对于const迭代器的版本也只需要进行不同的模板参数就可以实例化出const版本的迭代器

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
1
2

有了迭代器，在实现链表的各种函数功能就更加方便，例如可以实现erase和insert的操作，实现了这两个函数，在进行头插头删，尾插尾删的时候就更加方便，只需要进行原地的调用即可

	// Modifiers
	void push_front(const T& val)
	{
		//Node* newnode = new Node;
		//newnode->_data = val;
		//newnode->_next = _head->_next;
		//_head->_next->_prev = newnode;
		//_head->_next = newnode;
		//newnode->_prev = _head;
		//_size++;
		insert(begin(), val);
	}
	void pop_front()
	{
		//Node* delnode = _head->_next;
		//_head->_next = _head->_next->_next;
		//_head->_next->_prev = _head;
		//delete delnode;
		//delnode = nullptr;
		//_size--;
		erase(begin());
	}
	void push_back(const T& val)
	{
		//Node* newnode = new Node;
		//newnode->_data = val;
		//newnode->_prev = _head->_prev;
		//_head->_prev->_next = newnode;
		//newnode->_next = _head;
		//_head->_prev = newnode;
		//_size++;
		insert(end(), val);
	}
	void pop_back()
	{
		//Node* delnode = _head->_prev;
		//delnode->_prev->_next = _head;
		//_head->_prev = delnode->_prev;
		//delete delnode;
		//delnode = nullptr;
		//_size--;
		erase(--end());
	}
	iterator insert(iterator pos, const T& val)
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* newnode = new Node(val);

		_size++;
		prev->_next = newnode;
		newnode->_prev = prev;
		newnode->_next = cur;
		cur->_prev = newnode;
		return iterator(newnode);
	}
	iterator erase(iterator pos)
	{
		Node* cur = pos._node;
		Node* prev = cur->_prev;
		Node* next = cur->_next;

		delete cur;
		cur = nullptr;
		_size--;

		prev->_next = next;
		next->_prev = prev;
		return iterator(next);
	}
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

那么上面是对前面已经有过的内容进行的重新温故，但是上面的代码其实是没有实现反向迭代器的，而在STL的库中，反向迭代器的定义和正向迭代器其实并不相同，它是直接借助正向迭代器对反向迭代器进行适配，有些类似于用vector，list或者deque对栈和队列进行的适配，也体现了封装和代码复用

template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
public:
	typedef ReverseIterator<Iterator, Ref, Ptr> Self;

	ReverseIterator(Iterator it)
		:_it(it)
	{}

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

	Ref operator*()
	{
		return *_it;
	}

	Ptr operator->()
	{
		return _it.operator->();
	}

	bool operator!=(const Self& s)
	{
		return _it != s._it;
	}
private:
	Iterator _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

上面的代码就是对于反向迭代器的封装，从中可以看出反向迭代器是使用了正向迭代器的，并且在它的基础上进行的修改，因此这个反向迭代器是可以适配于vector也可以适配于list的

整体来说，对于反向迭代器就是用正向迭代器进行适配出来的，体现了模板的好处

完整代码

#pragma once

namespace mylist
{
	// 定义节点内容
	template <class T>
	struct list_node
	{
		list_node(const T& x = T())
			:_data(x)
			, _next(nullptr)
			, _prev(nullptr)
		{}
		T _data;
		list_node<T>* _next;
		list_node<T>* _prev;
	};

	// 定义正向迭代器
	template <class T, class Ref, class Ptr>
	class __list_iterator
	{
	public:
		typedef list_node<T> Node;
		typedef __list_iterator<T, T&, T*> self;
		__list_iterator(Node* node)
			:_node(node)
		{}

		self& operator++()
		{
			_node = _node->_next;
			return *this;
		}
		self& operator++(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}
		self& operator--(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		Ref operator*()
		{
			return _node->_data;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		bool operator !=(const self& s)
		{
			return _node != s._node;
		}
		bool operator ==(const self& s)
		{
			return _node == s._node;
		}
		Node* _node;
	};

	// 定义反向迭代器
	template<class Iterator, class Ref, class Ptr>
	class reverse_iterator
	{
		typedef reverse_iterator<Iterator, Ref, Ptr> self;
	public:
		reverse_iterator(Iterator it)
			:_it(it)
		{}

		self& operator++()
		{
			_it--;
			return *this;
		}
		self& operator++(int)
		{
			self tmp(*this);
			_it--;
			return tmp;
		}
		self& operator--()
		{
			_it++;
			return *this;
		}
		self& operator--(int)
		{
			self tmp(*this);
			_it++;
			return tmp;
		}
		Ref operator*()
		{
			Iterator cur = _it;
			return *(--cur);
		}
		Ptr operator->()
		{
			return &(operator*());
		}
		bool operator !=(const self& s)
		{
			return _it != s._it;
		}
		bool operator ==(const self& s)
		{
			return _it == s._it;
		}

		Iterator _it;
	};

	// 定义链表
	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_iterator<iterator, T&, T*> reverse_iterator;
		//typedef reverse_iterator const_reverse_iterator;
		// Constructor
		list()
		{
			empty_init();
		}
		list(const list<T>& lt)
		{
			for (auto x : lt)
			{
				push_back(x);
			}
		}
		list(iterator begin, iterator end)
		{
			empty_init();
			while (begin != end)
			{
				push_back(begin._node->_data);
				begin++;
			}
		}
		//list(reverse_iterator rbegin, reverse_iterator rend)
		//{
		//	empty_init();
		//	while (rbegin != rend)
		//	{
		//		push_back(rbegin._node->_data);
		//		rbegin++;
		//	}
		//}

		// Destructor
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		// Operator=
		list<T>& operator=(const list<T>& lt)
		{
			swap(lt);
			return *this;
		}

		// Iterators
		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);
		}
		reverse_iterator rbegin()
		{
			return reverse_iterator(end());
		}
		reverse_iterator rend()
		{
			return reverse_iterator(begin());
		}
		//const_reverse_iterator rbegin() const
		//{
		//	return const_reverse_iterator(end());
		//}
		//const_reverse_iterator rend() const
		//{
		//	return const_reverse_iterator(begin());
		//}

		// Capacity
		bool empty()
		{
			return _size == 0;
		}
		size_t size()
		{
			return _size;
		}

		// Element access
		T& front()
		{
			return begin()._node->_data;
		}
		T& back()
		{
			return (--end())._node->_data;
		}

		// Modifiers
		void push_front(const T& val)
		{
			//Node* newnode = new Node;
			//newnode->_data = val;
			//newnode->_next = _head->_next;
			//_head->_next->_prev = newnode;
			//_head->_next = newnode;
			//newnode->_prev = _head;
			//_size++;
			insert(begin(), val);
		}
		void pop_front()
		{
			//Node* delnode = _head->_next;
			//_head->_next = _head->_next->_next;
			//_head->_next->_prev = _head;
			//delete delnode;
			//delnode = nullptr;
			//_size--;
			erase(begin());
		}
		void push_back(const T& val)
		{
			//Node* newnode = new Node;
			//newnode->_data = val;
			//newnode->_prev = _head->_prev;
			//_head->_prev->_next = newnode;
			//newnode->_next = _head;
			//_head->_prev = newnode;
			//_size++;
			insert(end(), val);
		}
		void pop_back()
		{
			//Node* delnode = _head->_prev;
			//delnode->_prev->_next = _head;
			//_head->_prev = delnode->_prev;
			//delete delnode;
			//delnode = nullptr;
			//_size--;
			erase(--end());
		}
		iterator insert(iterator pos, const T& val)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* newnode = new Node(val);

			_size++;
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			return iterator(newnode);
		}
		iterator erase(iterator pos)
		{
			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			delete cur;
			cur = nullptr;
			_size--;

			prev->_next = next;
			next->_prev = prev;
			return iterator(next);
		}
		void swap(const list<T>& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		void clear()
		{
			Node* cur = _head->_next;
			while (cur != _head)
			{
				Node* next = cur->_next;
				delete(cur);
				cur = next;
			}
			_head->_next = _head;
			_head->_prev = _head;
		}


		void empty_init()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			_head->_data = T();
			_size = 0;
		}

		void Print()
		{
			Node* cur = _head->_next;
			while (cur != _head)
			{
				cout << cur->_data << "->";
				cur = cur->_next;
			}
			cout << "null" << endl;
		}
	private:
		Node* _head;
		size_t _size;
	};

	void test_iterator()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		cout << "iterator constructor:";
		list<int> lt1(lt.begin(), lt.end());
		lt1.Print();
		cout << "front():" << lt.front() << endl;
		cout << "back():" << lt.back() << endl;
		mylist::__list_iterator<int, int&, int*> it = lt.begin();
		while (it != lt.end())
		{
			std::cout << *it << " ";
			it++;
		}
		cout << endl;
	}
	void test_clear()
	{
		list<int> lt1;
		cout << "push_back:" << endl;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.Print();
		lt1.clear();
		lt1.push_back(5);
		lt1.push_back(6);
		lt1.push_back(7);
		lt1.push_back(8);
		lt1.Print();
	}
	void test_push_pop()
	{
		list<int> lt1;
		cout << "push_back:" << endl;
		lt1.push_back(1);
		lt1.push_back(2);
		lt1.push_back(3);
		lt1.push_back(4);
		lt1.Print();
		cout << "pop_back:" << endl;
		lt1.pop_back();
		lt1.Print();

		list<int> lt2;
		cout << "push_front:" << endl;
		lt2.push_front(1);
		lt2.push_front(2);
		lt2.push_front(3);
		lt2.push_front(4);
		lt2.Print();
		cout << "pop_front:" << endl;
		lt2.pop_front();
		lt2.Print();
	}
	void test_reverse_iterator()
	{
		list<int> lt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		cout << "iterator constructor:";
		//list lt1(lt.rbegin(), lt.rend());
		//lt1.Print();
		cout << "front():" << lt.front() << endl;
		cout << "back():" << lt.back() << endl;
		mylist::list<int>::reverse_iterator rit = lt.rbegin();
		while (rit != lt.rend())
		{
			std::cout << *rit << " ";
			rit++;
		}
		cout << endl;
	}

	void test()
	{
		test_reverse_iterator();
		//test_push_pop();
		//test_clear();
	}
}
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

相关阅读:
如何通过JoinQuant实现一个最简单的策略？
streamlit报错：AxiosError: Request failed with status code 403
【Web前端入门】HTML+CSS 万字总结——带你深入学习掌握
 C++学习笔记（十五）
Midjourney如何实现人物角色的一致性？
stm32F103RCT6使用FFT运算分析波形详解（非常新手）
无人驾驶: 对多传感器融合的一些思考(雷达与相机)
吃透Chisel语言.37.Chisel实战之以FIFO为例（二）——基于FIFO的串口通信：串口发送“Hello World!”
Python学习----Day07
2022钉钉杯初赛A题（银行卡电信诈骗危险预测）
原文地址：https://blog.csdn.net/qq_73899585/article/details/133708996