• STL--List--与正反向迭代器复写

    文章目录

    前言：

    • 本文介绍STL——list功能复写，重点是迭代器，感受泛型编程，函数重载之美

    • 博主收集的资料New Young，连载中。

    • 博主收录的问题:New Young

    • 转载请标明出处：New Young

    迭代器

    正向迭代器

    思路

    1. list的关键地方是对迭代器的复写，在复写这一过程，可以不断体会C++语言泛型编程，函数重载的魅力

    2. 不同于vector，string，其底层类似数组，它们的迭代器是对元素对象的==“通用指针”,通过指针的运算，就可以完成很多操作：++，解引用等，但是因为结点是在堆上是随机存储的，因此链表的迭代器必然要进行改变，同时为了支持算术运算（++，–…）解引用等操作，链表的迭代器必然要封装成一个结构体==。

    3. 为什么使用结构体？结构体默认成员是public，方便访问成员。

    4. 同时又因为list是有const之分，因此迭代器分为iterarot和const_iterator,（注意这里的const是指节点中的data不可更改，但是迭代器仍是可以改变的，对比常量指针）**但是这2者的功能非常类似，因此这里就通过类模板的模板参数进行区别。----``泛型编程**

    请添加图片描述

    构造函数

    注意拷贝构造函数的形参，是最小权限，可以满足很多情形：匿名对象，类型提升

    //迭代器
	template 
	struct list_iterator
	{
typedef list_iterator					 iterator;
		typedef list_iterator   const_iterator;
		typedef list_node									Node;
		typedef list_iterator						Self;
		Node* _node;
		list_iterator( Node*x)
			:_node(x)
		{
			;
		}
		list_iterator() 
		{}
		//场景：权限缩小的拷贝，同时因为计算需要，生成临时对象时会调用
		//其它的通过默认的拷贝构造和默认赋值运算符即可
		list_iterator(const iterator& x) : _node(x._node)
		{

		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    ++，–

    	typedef list_iterator					 iterator;
		typedef list_iterator   const_iterator;
		typedef list_node									Node;
		typedef list_iterator						Self;
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;
}


    • 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

    *，->

    1. 通过返回值的引用，当*时就可以防止const时，进行的写操作

    2. 对于节点中存放内置类型的数据时，通过*就可以得到数据但是对于自对于类型如果需要访问数据成员时，需要->运算符但是在使用->,为避免出现->->的情况，编译器会进行优化为一个->
      如日期类 cout< < it- > year<<“” << it->month<<“”<< it->day< 本质上要想得到year，需要 (it->) ->year=Date->year,只是编译器优化了一下

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    ！=，==

    依据不同类型的迭代器，可能会因为生产一个临时的同类型的迭代器如：iterator和const iterator进行比较，会生成一个iterator的临时const_iterator的拷贝

    请添加图片描述

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

		}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    反向迭代器

    1. 反向迭代器是对正向迭代器的复用，同时几乎所有的反向迭代器都是正向迭代器的复用，因此这里利用类模板来构造反向迭代器
    2. 反向迭代器的rbegin是正向迭代器的end(),rend()是正向迭代器的begin().
    3. 对于解引用，因为rbegin和rend的特殊性，反向迭代器返回的是迭代器前一个节点的数据

    成员

    	template
	class reverse_iterator
	{
		
	public:
		typedef reverse_iterator self;	
     private:
		Iterator _it;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    构造函数

    template
	class reverse_iterator
	{
		
	public:
		typedef reverse_iterator self;
		//这种形式的形参是最小权限，可以满足任何的拷贝构造
		reverse_iterator(const Iterator& it)
			:_it(it)
		{
			;
		}

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

    ++，–

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

		self operator++(int)
		{
			self tmp = _it--;
			return tmp;
		}

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

		self operator--(int)
		{
			self tmp = _it++;
			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

    *与->

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    ！=与==

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

		bool operator ==(const self& rit)
		{

			return _it == rit._it;
		}
	private:
Iterator _it;

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

    list

    begin()

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

		 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    rbegin()

     reverse_iterator rbegin()
		 {
			 return  reverse_iterator(end());	
		 }
 reverse_const_iterator rbegin()const
		 {

			 return reverse_iterator(end());

		 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    end()

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

		 }


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    rend()

     reverse_iterator rend()
		 {
			 return  reverse_iterator (begin());
			
		 } 
reverse_const_iterator rend()const
		 {

			 return reverse_iterator(begin());

		 }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    inert()

     //pos位置前插入数据
		iterator insert(iterator pos, const T& value)
		 {
			assert(pos != end());
			 Node* prevnode = pos._node->_prev;
			 Node* newnode = new Node(value);
			 newnode->_next = pos._node;
			 newnode->_prev = prevnode;
			 prevnode->_next = newnode;

			 pos._node->_prev = newnode;

			 return iterator(newnode);
		 }


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

    erase()

    //返回删除后下一个节点的迭代器
		iterator erase(iterator pos)
		 {
		 
			 assert(pos != end());
			 Node* prevnode = pos._node->_prev;
			 Node* nextnode = pos._node->_next;
		
			 prevnode->_next = nextnode;
			 nextnode->_prev = prevnode;
			 delete pos._node;
			 return iterator(nextnode);
		 }


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

    全部代码

    Reverse_iterator.h

    #pragma once


namespace My_Rev_It
{

	template
	class reverse_iterator
	{
		
	public:
		typedef reverse_iterator self;
		//这种形式的形参是最小权限，可以满足任何的拷贝构造
		reverse_iterator(const Iterator& it)
			:_it(it)
		{
			;
		}
		self& operator++()
		{
			--_it;
			return *this;
		}

		self operator++(int)
		{
			self tmp = _it--;
			return tmp;
		}

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

		self operator--(int)
		{
			self tmp = _it++;
			return tmp;
		}


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

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

		bool operator ==(const self& rit)
		{

			return _it == rit._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
    • 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

    List.h

    #pragma once
#include
#include  
#include 
#include 
#include
#include
#include
#include"Reverse_iterator.h"
namespace My_List
{
	//节点
	template
	struct  list_node
	{
		list_node(const T &x=T())
			:_next(nullptr),_prev(nullptr),_data(x)
		{
				;
		}
		list_node* _next;
		list_node* _prev;
		T _data;
	};

	//迭代器
	template 
	struct list_iterator
	{
		typedef list_iterator					 iterator;
		typedef list_iterator   const_iterator;
		typedef list_node									Node;
		typedef list_iterator						Self;
		Node* _node;
		list_iterator( Node*x)
			:_node(x)
		{
			;
		}
		list_iterator() 
		{}
		//这种形式的形参是最小权限，可以满足
		// 权限缩小的拷贝，同时因为计算需要进行提升，生成临时对象时会调用
		//其它的通过默认的拷贝构造和默认赋值运算符即可
		list_iterator(const iterator& x) : _node(x._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;
		}
		//通过返回值的引用，当*时就可以防止const时，进行的写操作
		Ref operator*()
		{
			return _node->_data;
		}

	/*	对于节点中存放内置类型的数据时，通过*就可以得到数据
		但是对于自对于类型如果需要访问数据成员时，需要->运算符
		但是在使用->,为避免出现->->的情况，编译器会进行优化为一个->
		如日期类

		cout<year<<"" <month<<""<day<) ->year=Date->year,只是编译器优化了一下*/
		Ptr  operator->()
		{
			return &_node->_data;
		
		}

		//即使是不同类型的迭代器，这里也会因为生产一个临时的同类型的迭代器
		bool operator !=(const Self& it)const 
		{
			return _node != it._node;
		}
		bool operator ==(const Self& it)const
		{
			return _node == it._node;

		}

	};

	//带头双向循环链表
	template
	class list
	{
	public:
		typedef list_node								 Node;
		typedef list_iterator					 iterator;
		typedef list_iterator const_iterator;

		typedef My_Rev_It::reverse_iterator   reverse_iterator;

		typedef My_Rev_It::reverse_iterator  reverse_const_iterator;




		list(const T&value=T())//头节点
		{
			_head = new Node(value);
			_head->_next = _head;
			_head->_prev = _head;
		}

		list(int  n, const T& value = T())
		{

			_head = new Node(value);
			_head->_next = _head;
			_head->_prev = _head;

			for (int  i = 0; i < n; ++i)
				push_back(value);
		}

		//:list lt(5, Date(2022, 1, 2));
		//list lt1(5, 1);
		//当形参进行对比时，对于Date会准确调用list(size_t n, const T& value = T())
		//当为int时，编译器更倾向于list(Inputitator first, Inputitator last)
		//因此重载一份list(int  n, const T& value = T())即可
		list(size_t n, const T& value = T())
		{

			_head = new Node(value);
			_head->_next = _head;
			_head->_prev = _head;
			for (size_t i = 0; i < n; ++i)
				push_back(value);
		}

		//利用迭代器区别初始化list
		template
		list(Inputitator first, Inputitator last)
		{
			//构建头节点
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

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

			list tmp(lt.begin(), lt.end());
			//注意 _head可能是随机指针或者nullptr
			std::swap(_head, tmp._head);
		}

		//赋值运算符
		list& operator=(const list lt)
		{
			clear();
			std::swap(_head, lt._head);
			return *this;
		}

		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				erase(it++);
			}
		}
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
		}
		void push_back(const T &x)
		{
				
			insert(end(),x);
			/*Node* tail = _head->_prev;
			Node* newnode = new Node(x);
			tail->_next = newnode;
			newnode->_next = _head;
			newnode->_prev = tail;
			
			_head->_prev = newnode;	*/
		}
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		void pop_back()
		{
			erase(--end());
		}
		void pop_front()
		{
			
			erase(begin());
		}

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

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

		 reverse_iterator rbegin()
		 {
			 return  reverse_iterator(end());
				
		 }
		 reverse_iterator rend()
		 {
			 return  reverse_iterator (begin());
			
		 }


		 reverse_const_iterator rbegin()const
		 {

			 return reverse_iterator(end());

		 }
		 reverse_const_iterator rend()const
		 {

			 return reverse_iterator(begin());

		 }


		 const_iterator begin()const
		 {
			 return  const_iterator(_head->_next);

		 }
		 const_iterator end()const
		 {
			 return const_iterator(_head);

		 }
		 //pos位置前插入数据
		 //不会出现迭代器失效问题，但是需要返回一个插入位置的迭代器
		 //很显然，constlist是不需要insert的
		iterator insert(iterator pos, const T& value)
		 {
			 Node* prevnode = pos._node->_prev;
			 Node* newnode = new Node(value);
			 newnode->_next = pos._node;
			 newnode->_prev = prevnode;
			 prevnode->_next = newnode;
			 pos._node->_prev = newnode;
			 return iterator(newnode);
		 }

		//返回删除后下一个节点的迭代器
		iterator erase(iterator pos)
		 {
		 
			 assert(pos != end());
			 Node* prevnode = pos._node->_prev;
			 Node* nextnode = pos._node->_next;
		
			 prevnode->_next = nextnode;
			 nextnode->_prev = prevnode;
			 delete pos._node;
			 return iterator(nextnode);
		 }
	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
    • 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

    总结

    复写过程经常遇到类型无法转化问题，大概率是因为权限问题或者

  • 相关阅读:
    北大肖臻老师《区块链技术与应用》系列课程学习笔记[3]比特币系统的具体实现
    激光测距用高精度时间测量(TDC)电路MS1005
    部署velero时restic启动异常：CrashLoopBackOff
    计算机组成原理——数据的表示和运算②
    骑士周游算法（Java）
    ElasticSearch - 基于 docker 部署 es、kibana，配置中文分词器、扩展词词典、停用词词典
    Pytorch：Dataset类和DataLoader类
    如何在Excel中实现手写签名？
    DDD/ABP/EF Core ：新特性Owned Entity Types ，尝试另外一种值对象的配置方式
    数据可视化——pyecharts库绘图
  • 原文地址：https://blog.csdn.net/qq_55439426/article/details/125751148