【C++】模拟实现List的正向和反向迭代器（iterator、reverse_iterator）_c++ const iterator实现

作者：从前慢现在也慢 | 2024-04-09 06:11:50

踩

c++ const iterator实现

文章目录

1、搭建List的基本框架

STL中List容器底层是一个双向带头循环链表。
在这里插入图片描述

这里简单搭建一个List，下面我们不断完善。
思路：
1、List作为一个双向带头链表，所以除了创建一个List类，还需要有一个结点结构体有着可以被外部访问的成员prev、next、data。
2、List应当有一个哨兵结点，所以默认构造必须我们写且初始化一个结点设为哨兵结点。

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

namespace test
{
	template<class T>
	struct Node
	{
		struct Node<T>* _prev;
		struct Node<T>* _next;
		T _data;
		
		//在后续插入建立新结点，初始化
		Node(const T& x = T())
			:_prev(nullptr)
			,_next(nullptr)
			,_data(x)
		{}
	};

	template<class T>
	class list
	{
		typedef struct Node<T> node;
	public:
		void initlist()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0;
		}

		// 构造
		list()
		{
			initlist();
		}
		

	private:
		node* _head;
		size_t _size;
	};


}
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

2、List中iterator和const_iterator

C++中的迭代器iterator虽然在使用上可以当成指针一样用，但是对于List如果要像指针一样，那么就需要对iterator的运算符进行重载实现。
那么可以将iterator封装成一个类进行实现。

有了迭代器，list就可以实现begin()和end()对链表结点进行定位。
并且也能在特定位置实现insert。

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;

namespace test
{
	template<class T>
	struct Node
	{
		...
	};


	template<class T>
	class iterator
	{
		typedef struct Node<T> node;
	public:
		iterator(node* it)
			:_node(it)
		{}

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

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

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

		T& operator*()
		{
			return _node->_data;
		}

		node* getnode()
		{
			return _node;
		}

	private:
		node* _node;
	};


	template<class T>
	class list
	{
		typedef struct Node<T> node;
		typedef iterator<T> iterator;
	public:

		iterator begin()
		{
			return iterator(_head->_next);
		}

		iterator end()
		{
			return iterator(_head); 
		}


		void initlist()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0;
		}

		// 构造
		list()
		{
			initlist();
		}

		//拷贝构造
		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			initlist();

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

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

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

			_size++;

			return iterator(newnode);
		}

		void push_back(T x = T())
		{
			insert(end(), x);
		}
		
	private:
		node* _head;
		size_t _size;
	};
}
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

const_iterator

对于const对象，迭代器也需要用const的。
对于const迭代器，不能写成const iterator it 这修饰的是it，需要修饰的iterator所以需要一个新的类型const_iterator

const_iterator保证的是被指向的结点内容不能变化。
下面看两种情况

对于const和非const类型的改变，可以直接通过模板的类型泛型进行更改。

	// 同一个类模板实例化出的两个类型
	// typedef __list_iterator<T, T&, T*> iterator;
	// typedef __list_iterator<T, const T&, const T*> const_iterator;
	template<class T>
	class list_iterator
	{
		typedef struct Node<T> node;
	public:
		typedef list_iterator<T, Ref, Ptr> Self
		list_iterator(node* it)
			:_node(it)
		{}

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

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

		bool operator!=(list_iterator<T> x) const
		{
			return _node != x._node;
		}

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

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &(_pnode->data);
		}

		node* getnode()
		{
			return _node;
		}

	private:
		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
52
53
54
55

编译器对it->_col这个位置做了一个优化，本来获取data地址后应该是it->->_col，但是编译器做了优化就是it->_col，但it.operator->()->_col这样不会受影响。

	struct Pos
	{
		int _row;
		int _col;

		Pos(int row = 0, int col = 0)
			:_row(row)
			,_col(col)
		{}
	};
	void Print_list(const list<Pos>& lt)
	{
		list<Pos>::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//我们知道it的底层
			//cout << (*it)._col << " " << (*it)._row << endl;
			//cout << (&(*it))->_row << ":" << (*it)._col << endl;
			//普通认为是指针
			cout << it->_col << " " << it->_row << endl;
			//cout << it.operator->()->_col << " " << it.operator->()->_row << 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

3、反向迭代器revser_iterator

反向迭代器就是从链表的尾部到头部。

在这里插入图片描述

在底层rend()其实就是begin()，rbegin()其实就是end()，
并且reverse_iterator其实是一个适配器，通过iterator封装的一个类，
所以如果实现了一个容器的正向迭代器，那么反向迭代器就一定能实现。

#include <iostream>
#include <assert.h>
using namespace std;

namespace test
{
	template <class Iterator, class Ref, class Ptr>
	class ReverseIterator
	{
		typedef ReverseIterator<Iterator, Ref, Ptr> self;
	public:
		ReverseIterator(Iterator it)
			:_it(it)
		{}

		Ref operator*()
		{
			Iterator tmp = _it;
			return *(--tmp);
		}

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

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

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

		bool operator!=(const self& s) const
		{
			return _it != s._it;
		}
	private:
		Iterator _it;
	};


	template <class T>
	struct ListNode
	{
		struct ListNode<T>* _next;
		struct ListNode<T>* _prev;
		T data;

		ListNode(T x = T())
			:_next(nullptr)
			,_prev(nullptr)
			,data(x)
		{}
	};

	template <class T, class Ref, class Ptr>
	struct list_iterator
	{
		typedef struct ListNode<T> node;
		typedef struct list_iterator<T, Ref, Ptr> Self;

		list_iterator(node* p)
			:_pnode(p)
		{}

		bool operator!=(Self x) const
		{
			return _pnode != x._pnode;
		}

		bool operator==(Self x) const
		{
			return _pnode == x._pnode;
		}

		Ptr operator->()
		{
			return &(_pnode->data);
		}

		Ref operator*()
		{
			return _pnode->data;
		}

		Self& operator++() 
		{
			_pnode = _pnode->_next;
			return *this;
		}

		Self operator++(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}

		Self& operator--() 
		{
			_pnode = _pnode->_prev;
			return *this;
		}

		Self operator--(int)
		{
			Self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}

		node* _pnode;
	};


	template <class T>
	class list
	{
		typedef struct ListNode<T> node;
	public:
		//简化类型
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;

		typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
		typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_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);
		}

		reverse_iterator rbegin()
		{
			return end();
		}

		reverse_iterator rend()
		{
			return begin();
		}

		const_reverse_iterator rbegin() const
		{
			return end();
		}

		const_reverse_iterator rend() const
		{
			return begin();
		}

		void initlist()
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0;
		}

		//构造
		list()
		{
			initlist();
		}

		//构造
		template <class InputIterator>
		list(InputIterator first, InputIterator last)
		{
			initlist();

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

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

		list(const list<T>& lt)
		{
			initlist();

			list<T> tmp(lt.begin(), lt.end());
			swap(tmp);
		}

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

		bool empty() const
		{
			return _size == 0;
		}

		size_t size() const
		{
			return _size;
		}
		
		~list()
		{
			clean();
			delete _head;
			_head = nullptr;
		}

		void push_back(T x = T())
		{
			insert(end(), x);
		}

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

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

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

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

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

			_size++;

			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());

			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* next = cur->_next;
			delete cur;
			prev->_next = next;
			next->_prev = prev;

			_size--;

			return iterator(next);
		}

		void clean()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

	private:
		node* _head;
		size_t _size;
	};
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

总结：
list迭代器为了重载其多个操作符，所以弄了一个封装类。迭代器在不同场景经过操作符函数返回了不同类型，其中还要区别const类型，通过模板泛型能方便我们应对这些情况。

反向迭代器是对正向迭代器的封装，所以实现了正向迭代器就能实现反向迭代器。

本节完~

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/从前慢现在也慢/article/detail/390802