一、关于迭代器操作

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

这里主要实现这两个函数的具体实现原理：类型萃取实现函数重载，从而达到不同类型容器中的迭代器都可以进行使用该函数advance和distance函数。并且不同的迭代器类型可以使用不同的方法，从而提高效率（例如随机迭代器正向移动5下，可以使用循环，也直接可以 += 5，很明显随机迭代器使用后者效率将O(n)提到了O(1)）。

二、关于迭代器

迭代器按照功能可分为五类：输入迭代器、输出迭代器、向前迭代器、双向迭代器、随机迭代器
以下是这五类迭代器的继承关系：请添加图片描述

三、实现advance

既然该函数在iterator.h文件中，我们就仿照下
my_iterator.h

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
#ifndef MY_ITERATOR_H
#define MY_ITERATOR_H
namespace pzj
{
	//只读迭代器标记
	class input_iterator_tag {};
	//只写迭代器标记
	class output_iterator_tag {};

	//正向迭代器标记
	class forward_iterator_tag : public input_iterator_tag {};
	//双向迭代器标记
	class bidirectional_iterator_tag : public forward_iterator_tag {};
	//随机迭代器标记
	class random_iterator_tag : public bidirectional_iterator_tag {};

	/*-----------------------------------------------------------*/
	//指针差值类型
	typedef int ptrdiff_t;

	//全局迭代器iterator
	template<class _C, class _Ty,class _D = ptrdiff_t, class _Pointer = _Ty*, class _Reference = _Ty&>
	struct iterator
	{
		typedef _C			iterator_category;	//迭代器类别
		typedef _Ty			value_type;			//数值类型
		typedef _D			difference_type;	//差值类型
		typedef _Pointer	pointer;			//数值指针类型
		typedef _Reference	reference;			//值引用类型
	};

	//正向迭代器
	template<class _Ty, class _D>
	struct _Forit : public iterator<forward_iterator_tag, _Ty, _D>
	{};
	//双向迭代器
	template<class _Ty, class _D>
	struct _Bidit : public iterator<bidirectional_iterator_tag, _Ty,_D>
	{};
	//随机迭代器
	template<class _Ty, class _D>
	struct _Randit : public iterator<random_iterator_tag, _Ty, _D>
	{};

	//迭代器类型萃取类
	template<class _Iterator>
	class iterator_traits
	{
	public:
		//构造函数
		iterator_traits() {}
		typedef typename _Iterator::iterator_category	iterator_category;	//迭代器类别
		typedef typename _Iterator::value_type			value_type;			//数值类型
		typedef typename _Iterator::difference_type		difference_type;	//差值类型
		typedef typename _Iterator::pointer				pointer;			//数值指针类型
		typedef typename _Iterator::reference			reference;			//值引用类型
	};

	/*-----------------------------------------------------------*/
	//input、output、forward迭代器都使用该迭代方式
	template<class _II, class _D>
	inline void __advance(_II& it, _D n, input_iterator_tag)
	{
	/*	while (n--)
		{
			++it;
		}*/
	}
	//双向迭代器的迭代方式
	template<class _BI, class _D>
	inline void __advance(_BI& it, _D n, bidirectional_iterator_tag)
	{
		/*if (n > 0)
		{
			while(n--) ++it;
		}
		else
		{
			while (n++) --it;
		}*/
	}
	//随机迭代器的迭代方式
	template<class _RI, class _D>
	inline void __advance(_RI& it, _D n, random_iterator_tag)
	{
		//it += n;
	}

	//统一接口
	template<class _II, class _D>
	inline void advance(_II& it, _D n)
	{
		//由于未知迭代器的类别标志，所以暂时无法使用__advance()调用对应的函数
		//__advance(it, n, 迭代器类型标志);
	
		//类型萃取出_II的迭代器类型iter_cate
		typedef typename iterator_traits<_II>::iterator_category iter_cate;
		__advance(it, n, iter_cate());
	}

}
#endif

myvector.h

1
2
3
4
5
6
7
8
9
10
11
12
13
#ifndef MYVECTOR_H
#define MYVECTOR_H
#include "my_iterator.h"
template<class _Ty>
class myvector
{
public:
	class const_iterator : public pzj::_Randit<_Ty, int> {};
	class iterator : public const_iterator {};

};

#endif

mylist.h

1
2
3
4
5
6
7
8
9
10
11
12
13
#ifndef MYLIST_H
#define MYLIST_H
#include "my_iterator.h"
template<class _Ty>
class mylist
{
public:
	class const_iterator : public pzj::_Bidit<_Ty, int> {};
	class iterator : public const_iterator {};

};

#endif

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "my_iterator.h"
#include <iostream>
#include "myvector.h"
#include "mylist.h"
using namespace std;
int main()
{
	//cout << typeid(pzj::_Forit<int, int>::iterator_category).name()<< endl;
		
	myvector<int>::iterator vit;
	mylist<int>::iterator lit;
	pzj::advance(vit, 2);
	pzj::advance(lit, 2);
	return 0;
}

四、实现distance

补充my_iterator.h

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
//实现distance
	//输入、输出、正向、双向
	template<class _II>
	inline typename iterator_traits<_II>::difference_type
	__distance(_II first, _II last, input_iterator_tag)
	{
		typename iterator_traits<_II>::difference_type _dist = 0;
		while (first != last)
		{
			++first;
			++_dist;
		}
		return _dist;
	}
	//随机
	template<class _RAI>
	inline typename iterator_traits<_RAI>::difference_type
		__distance(_RAI first, _RAI last, random_iterator_tag)
	{
		return last - first;
	}
	//萃取迭代器类别
	template<class _It>
	inline typename iterator_traits<_It>::iterator_category 
		Iterator_category(_It it)
	{
		typedef typename iterator_traits<_It>::iterator_category iter_cate;
		return iter_cate();
	}

	//统一接口
	template< class InputIt >
	typename iterator_traits<InputIt>::difference_type
	distance(InputIt first, InputIt last)
	{
		//typedef typename iterator_traits<InputIt>::iterator_category iter_cate;
		//__distance(first, last, iter_cate());
		__distance(first, last, Iterator_category(first));
	}