312-STL的迭代器(1)

超、凢脫俗 2022-10-20 05:23 144阅读 0赞

## STL的迭代器(1) ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]  
hash\_table是正向迭代器  
std::slist是正向迭代器（单链表）  
list是双向迭代器  
dequee是双向迭代器  
map和set也是双向迭代器  
**只有随机迭代器才可以比较大小**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]  
**例子如下**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]

## 迭代器的图示理解 ##

**假设有一个链表，结点有value,prev,next**  
我们可以通过迭代器知道它的值（数据类型），引用类型（引用的是对象的别名），指针类型（返回的是迭代器指向的结点的数据的地址，即对象实体的地址），差值类型（两个迭代器之间的距离，有几个元素），随机迭代器。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]

## 迭代器的讲解 ##

R代表随机迭代器  
BI代表双向迭代器  
FI代表正向迭代器  
栈，队列，优先级队列 没有迭代器  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 13]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 14]  
**advance函数对不同的容器实现的方式是不一样的。  
如果对所有容器的操作是统一的，对有的容器不适合，对有的容器是适合，我们要对不同的容器采取不同的方案。**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 15]  
上面代码表明 ：程序在运行的过程中才能调用这些函数。  
我们希望程序在编译的过程中就可以确定调用哪个函数。  
我们要获取当前迭代器的类型。  
我们采取萃取方案。

## STL的迭代器实现 ##

**运用了模板的重载**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 16]  
**榨汁机的讲解**  
编译的时候就可以确定是双向迭代器  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 17]  
**测试代码**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 18]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 19]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 20]

## STL的迭代器代码 iterator.h ##

#ifndef yhp_iterator_h
    #define yhp_iterator_h
    namespace yhp
    {
        
    typedef int ptrdiff_t;
    
    //
    template<class _T1, class _T2> 
    struct pair 
    {
        
    	typedef _T1 first_type;
    	typedef _T2 second_type;
    public:
    	pair(): first(_T1()), second(_T2()) {
        }
    
    	pair(const _T1& _V1, const _T2& _V2): first(_V1), second(_V2) {
        }
    
    	//template<class U, class V>
    	//pair(const pair<U, V> &p): first(p.first), second(p.second) {}
    
    	_T1 first;
    	_T2 second;
    };
    
    template<class _T1, class _T2> inline
    	bool __cdecl operator==(const pair<_T1, _T2>& _X,
    		const pair<_T1, _T2>& _Y)
    	{
        return (_X.first == _Y.first && _X.second == _Y.second); }
    
    template<class _T1, class _T2> inline
    	bool __cdecl operator!=(const pair<_T1, _T2>& _X,
    		const pair<_T1, _T2>& _Y)
    	{
        return (!(_X == _Y)); }
    
    template<class _T1, class _T2> inline
    	bool __cdecl operator<(const pair<_T1, _T2>& _X,
    		const pair<_T1, _T2>& _Y)
    	{
        return (_X.first < _Y.first ||
    		!(_Y.first < _X.first) && _X.second < _Y.second); }
    
    template<class _T1, class _T2> inline
    	bool __cdecl operator>(const pair<_T1, _T2>& _X,
    		const pair<_T1, _T2>& _Y)
    	{
        return (_Y < _X); }
    
    template<class _T1, class _T2> inline
    	bool __cdecl operator<=(const pair<_T1, _T2>& _X,
    		const pair<_T1, _T2>& _Y)
    	{
        return (!(_Y < _X)); }
    
    template<class _T1, class _T2> inline
    	bool __cdecl operator>=(const pair<_T1, _T2>& _X,
    		const pair<_T1, _T2>& _Y)
    	{
        return (!(_X < _Y)); }
    
    template<class _T1, class _T2> inline
    	pair<_T1, _T2> __cdecl make_pair(const _T1& _X, const _T2& _Y)
    	{
        return (pair<_T1, _T2>(_X, _Y)); }
    ///
    
    struct input_iterator_tag {
        }; 
    struct output_iterator_tag {
        };
    struct forward_iterator_tag : public input_iterator_tag {
        };//正向迭代器 
    struct bidirectional_iterator_tag: public forward_iterator_tag {
        };//双向迭代器 
    struct random_access_iterator_tag: public bidirectional_iterator_tag  {
        };//随机迭代器 
    
    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 _Iterator>
    struct iterator_traits//榨汁机 
    {
        
    	//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;
    };
    
    template<class T>//部分特化 
    struct iterator_traits<T*>  // Int 
    {
        
    	//iterator_traits() { }
    	typedef random_access_iterator_tag iterator_category;
    	typedef T                          value_type;
    	typedef int                        difference_type;
    	typedef T *                        pointer;
    	typedef T &                        reference;
    };
    
    template<class T>
    struct iterator_traits<const T*>
    {
        
    	//iterator_traits() { }
    	typedef random_access_iterator_tag iterator_category;
    	typedef T                          value_type;
    	typedef int                        difference_type;
    	typedef const T *                        pointer;
    	typedef const T &                        reference;
    };
    //
    // SGI
    template<class _II>
    inline typename iterator_traits<_II>::iterator_category
    iterator_category(const _II &)
    {
        
    	typedef typename iterator_traits<_II>::iterator_category category;
    	return category();
    }
    template<class _II>
    inline typename iterator_traits<_II>::value_type *
    value_type(const _II &)
    {
        
    	 return static_cast< typename iterator_traits<_II>::value_type * > (0);
    }
    
    template<class _II>
    inline typename iterator_traits<_II>::difference_type *
    difference_type(const _II &)
    {
        
    	 return static_cast< typename iterator_traits<_II>::difference_type * > (0);
    }
    ///
    // 
    template<class _C, class _Ty, class _D> inline
    _C _Iter_cat(const iterator<_C, _Ty, _D>&)
    {
        
    	_C _IterCatTag;
    	_C* _pIterCatTag;
    	_pIterCatTag = &_IterCatTag;	
    	return (_IterCatTag); 
    }
    template<class _Ty> inline
    random_access_iterator_tag __cdecl _Iter_cat(const _Ty *)
    {
        
    	random_access_iterator_tag _RandIterTag;
    	random_access_iterator_tag* _pRandIterTag;
    	_pRandIterTag = &_RandIterTag;	
    	return (_RandIterTag); 
    }
    
    template<class _Ty,class _D>
    struct _Bidit : public iterator<bidirectional_iterator_tag,_Ty,_D> {
        };//双向迭代器 
    // List // Map  // Set
    template<class _Ty,class _D>
    struct _Ranit: public iterator<random_access_iterator_tag,_Ty,_D> {
        };//随机迭代器 
    // dequeu // vector
    template<class _Ty,class _D>
    struct _Forit: public iterator<forward_iterator_tag,_Ty,_D> {
        };//正向迭代器 
    // slist //  hashtable;
    
    template<class _II,class _D>
    inline void __advance(_II &i,_D n,input_iterator_tag )
    {
        
    	while(n--) ++i;
    }
    
    template<class _BI,class _D>
    inline void __advance(_BI &i,_D n,bidirectional_iterator_tag )
    {
        
    	if(n >= 0)
    	{
        
    		while(n--) ++i;
    	}
    	else
    	{
        
    		while(n++) --i;
    	}
    }
    
    template<class _RI,class _D>
    inline void __advance(_RI &i,_D n,random_access_iterator_tag )
    {
        
    	i += n;
    }
    template<class _II,class _D>
    inline void advance(_II &i,_D n)
    {
        
    	//iterator_traits<_II>();
    	//typedef typename iterator_traits<_II>::iterator_category  cate;
    	//__advance(i,n,cate());
    	__advance(i,n,iterator_category(i));
    }
    
    template<class _II>
    inline typename iterator_traits<_II>::difference_type 
    __distance(_II _F , _II _L, input_iterator_tag)
    {
        
    	typename iterator_traits<_II>::difference_type  n = 0;
    	while(_F != _L)
    	{
        
    		++_F;
    		++n;
    	}
    	return n;
    }
    
    template<class _II>
    inline typename iterator_traits<_II>::difference_type 
    __distance(_II _F , _II _L, random_access_iterator_tag)
    {
        
    	return _L - _F;
    }
    template<class _II>
    inline typename iterator_traits<_II>::difference_type 
    distance(_II _F , _II _L)
    {
        
    	typedef typename iterator_traits<_II>::iterator_category  cate;
    	return __distance(_F,_L,cate());
    }
    
    }
    
    #endif

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221020/e5b959061bfc4976a4e8dc00c95a5c1a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221020/e8ae37df3e18454c861b12055c5dd865.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221020/4f3cbbb8073848d9babd0d25aa4a96f9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221020/781a06fe34bc440db720db6647807ac2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221020/b8db950093b7415e92a01d2340690fb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221020/52ba71a402d949cf9f60835dd008d842.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221020/d6108a5a099a4f1483a4e87d1a4da0ec.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221020/7ecdadb3f5b94f89aa33d825a76b0fef.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221020/0f64dbf21b5049f9b420fc44209eadbb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221020/4b1368e170a34c3aa5ecfa810506fc39.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221020/3ad2933553cb4adb8948dd8651f1a946.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221020/e0096123a71740b18e97511f6730bb53.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221020/774a5123b09246be93870797497d243d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 13]: /images/20221020/3d0632d94e5e4e33942db9c167e49a7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 14]: /images/20221020/5c871171c5504c2f92abcb5657c9f205.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 15]: /images/20221020/c10a96282bda4d22b35d69a17d4eb7a9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 16]: /images/20221020/8a2cb89c785147a59527ab6ccce38d7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 17]: /images/20221020/5c37d1a25f2848dabfed5c22d06201cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 18]: /images/20221020/37ebe135627f41a3a2369fcad31eaa64.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 19]: /images/20221020/98205612a8bd4cd1a930909bd83e4696.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center 20]: /images/20221020/f7f336457cd441a2809713317edc7cc1.png