一步一步的理解C++STL迭代器

        “指针”对全部C/C++的程序猿来说，一点都不陌生。

在接触到C语言中的malloc函数和C++中的new函数后。我们也知道这两个函数返回的都是一个指针。该指针指向我们所申请的一个“堆”。提到“堆”。就不得不想到“栈”。从C/C++程序设计的角度思考，“堆”和“栈”最大的差别是“栈”由系统自己主动分配而且自己主动回收，而“堆”则是由程序猿手动申请。而且显示释放。假设程序猿不显示释放“堆”。便会造成内存泄漏。内存泄漏的危害大家知道，严重时会导致系统崩溃。

       既然“指针”的使用者一不小心就可能导致内存泄漏，那么我们怎样可以使得指针的使用变得更安全呢？从C++面向对象的角度分析，我们有没有可能将“指针”封装起来，使得用户不直接接触指针，而使用一个封装后的对象来替代指针的操作呢？

        答案是显然的，“智能指针”(smart pointer)正解决这类问题，尤其是在防止内存泄漏方面做得很突出。

C++标准库std中提供了一种“智能指针类”名为"auto_ptr"，先看以下的代码：

void f()
{
	int *p=new int(42);
	////////此处发生异常////
	delete p;
}

       正如上面的代码所看到的。假设在两条语句中间发生异常，会导致指针p所指的那块内存泄漏。由于在执行delete之前发生异常，就不会自己主动释放堆。然而。假设使用auto_ptr对象取代常规指针，将会自己主动释放内存，由于编译器可以保证提前执行其析构函数。这样，我们就行将上述代码改为：

#include<memory>//auto_ptr的头文件
void f()
{
	auto_ptr<int>p(new int (42));
}

       通过以上的分析。我们便对智能指针有了一定的了解。

迭代器iterator就是一种智能指针。它对原始指针进行了封装，而且提供一些等价于原始指针的操作，做到既方便又安全。

       一提到STL，必需要立即想到其基本的6个组成部件，各自是：容器、算法、迭代器、仿函数、适配器和空间分配器。本文主要介绍迭代器。

迭代器是连接容器和算法的一种重要桥梁。

为什么呢？我们举个样例来说明原因。

#include<iostream>
#include<algorithm>//用到find函数
#include<vector>
using namespace std;
int main()
{
	vector<int>vec;
	int i;
	for(i=0;i<10;i++)
	{
		vec.push_back(i);
	}
	if(vec.end()!=find(vec.begin(),vec.end(),7))
	{
		cout<<"find!"<<endl;
	}
	else
	{
		cout<<"not find!"<<endl;
	}
	system("pause");
	return 0;
}

        上述代码中。值得注意的是用到的find函数，find函数的函数原型为：template<class _InIt,class _Ty> _InIt find(_InIt _First, _InIt _last, const _Ty & _val),从find函数原型能够看出find函数是一个函数模板，函数的形參中前两个參数为_InIt。该參数是InputIterator的缩写。最后一个參数则是一个随意类型变量的引用。而我们的程序在使用find函数实。传入的实參为find(vec.begin(),vec.end(),7)。这样我们的形參迭代器就将算法find和容器vector联系起来了，从这个角度我们能够非常easy理解为什么说迭代器是算法和容器的联系的桥梁了。

       为什么上面的形參是一个InputIterator，而可以接受实參vec.begin()呢？为了回答这个问题，须要从迭代器的分类说起。

        在STL中，迭代器主要分为5类。各自是：输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机訪问迭代器。

        输入迭代器：仅仅读。支持++、==、！=；

        输出迭代器：仅仅写，支持++；

        前向迭代器：读写，支持++、==、！=。

        双向迭代器：读写，支持++、--。C++的全部标准库容器都至少在双向迭代器的层次上。；

        随机訪问迭代器：读写，支持++、--、[n]、-n、<、<=、>、>=。

        输入迭代器和输出迭代器是最低级的迭代器。后三种迭代器都是对该迭代器的一种派生，回到刚刚那个问题。为什么实參vec.begin()可以与形參_InIt“虚实结合”呢？我们先看以下的代码：

#include<iostream>
using namespace std;
class A{};
class A1:public A{};//类A1继承A
class B{};
void print(A)//仅仅需指定參数类型
{
	cout<<"This is Base class A!"<<endl;
}
void print(B)//仅仅需指定參数类型
{
	cout<<"This is Base class B!"<<endl;
}
int main()
{
	print(A());
	print(B());
	print(A1());//将一个派生类的对象传递过去
	return 0;
}

       从上面的代码能够看出，在main函数中，我们调用print(A1())。即能够用派生类对象作为实參传递给以基类类型作为形參的函数。所以find函数中的vec.begin()作为实參，以输入迭代器类型作为形參，两者能够达到虚实相结合的目的而不会出错。所以说。迭代器为各类算法和和各类容器提供了一个相互沟通的平台。

        接着。我们从容器本身的角度和算法本身的角度对迭代器做进一步的分析。

        容器的迭代器都是定身制作的，什么意思呢？全部容器都内置一个迭代器。该内置迭代器由容器的设计者实现。

因为现有的容器比較多，不可能每种容器的迭代器都具体介绍下。可是有一点能够确定的是，每一个容器相应的迭代器都是依据容器的特点来实现的，以求达到最高效率。

我们所关心的问题是：哪些操作会使容器的迭代器失效呢？

        迭代器失效？没错。就是迭代器失效。

迭代器失效指的是迭代器原来所指向的元素不存在了或者发生了移动，此时假设不更新迭代器，将无法使用该过时的迭代器。

迭代器失效的根本原因是对容器的某些操作改动了容器的内存状态（如容器又一次载入到内存）或移动了容器内的某些元素。

        使vector迭代器失效的操作

        1.向vector容器内加入元素(push_back,insert)

           向vector容器加入元素分下面两种情况：

            1）若向vector加入元素后，整个vector又一次载入。即前后两次vector的capacity()的返回值不同一时候，此时该容器 内的全部元素相应的迭代器都将失效。

            2）若该加入操作不会导致整个vector容器载入，则指向新插入元素后面的那些元素的迭代器都将失效。

       2,删除操作(erase,pop_back,clear)

           vector运行删除操作后，被删除元素相应的迭代器以及其后面元素相应的迭代器都将失效。

       3.resize操作：调整当前容器的size

           调整容器大小对迭代器的影响分例如以下情况讨论： 

            A.若调整后size>capacity，则会引起整个容器又一次载入，整个容器的迭代器都将失效。

            B.若调整后size<capacity，则不会又一次载入，详细情况例如以下：

                B1.若调整后容器的size>调整前容器的size，则原来vector的全部迭代器都不会失效。

                B2.若调整后容器的size<调整前容器的size，则容器中那些别切掉的元素相应的迭代器都将失效。

      4.赋值操作(v1=v2     v1.assign(v2))

          会导致左操作数v1的全部迭代器都失效，显然右操作数v2的迭代器都不会失效。

     5.交换操作(v1.swap(v2))

          因为在做交换操作时。v1,v2均不会删除或插入元素，所以容器内不会移动不论什么元素。故v1,v2的全部迭代器都不会失效。

     使deque迭代器失效的操作

     1.插入操作（push_front,push_back,insert)

         deque的插入操作对迭代器的影响分两种情况：

         A.在deque容器首部或尾部插入元素不会是不论什么迭代器失效；

         B.在除去首尾的其它位置插入元素会使该容器的全部迭代器失效。

     2.删除操作

         A.在deque首、尾删除元素仅仅会使被删除元素相应的迭代器失效；

         B.在其它不论什么位置的删除操作都会使得整个迭代器失效。

       使list/map/set迭代器失效的操作

       因为list/map/set容器内的元素都是通过指针连接的。list实现的数据结构是双向链表，而map/set实现的数据结构是红黑树，故这些容器的插入和删除操作都只需更改指针的指向，不会移动容器内的元素。故在容器内添加元素时，不会使不论什么迭代器失效，而在删除元素时，只会使得指向被删除的迭代器失效。

        再回顾下find函数。find函数前两个形參都是输入迭代器类型。这两个迭代器并非某个容器特有的迭代器，而是一个一般的迭代器。可将全部标准库容器内部的迭代器视为形參所相应迭代器类的派生类。

以下我们透过stl中迭代器的实现代码来分析迭代器的实现方法.

#include<iostream>
#include<cstddef>//ptrdiff_t相应的头文件
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{};//随机訪问迭代器

//std::iterator,标准迭代器的类模板
template<class Category,class T,class Distance=ptrdiff_t,
         class Pointer=T*,class Reference=T&>
struct iterator//迭代器包括五个经常使用属性
{
	typedef Category iterator_category;//迭代器的类型，五种之中的一个
	typedef T		 value_type;//迭代器所指向的元素的类型
	typedef Distance difference_type;//两个迭代器的差值
	typedef Pointer  pointer;//迭代器的原始指针
	typedef Reference reference;//迭代器所指向元素的引用
};

//定义iterator_traits，用于提取迭代器的属性,该类的对象不应该让用户看到
template<class Iterator>
struct 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*>
{
	//相当于递归终止条件
	typedef random_access_iterator_tag iterator_category;
	typedef T         value_type;
	typedef ptrdiff_t diffrence_type;
	typedef T*		  pointer;
	typedef T&	      reference;
};

//针对指向经常使用的原始指针设计的偏特化版本号
template<class T>
struct iterator_traits<const T*>
{
	typedef random_access_iterator_tag iterator_category;
	typedef	T		   value_type;
	typedef ptrdiff_t  diffrence_type;
	typedef const T *  pointer;//重点在这里
	typedef const T &  reference;//还有这里
};

//定义两个迭代器的差值类型的函数distance_type
template<class Iterator>
inline typename iterator_traits<Iterator>::difference_type *
distance_type(const Iterator&)
{
	return static_cast<typename iterator_traits<Iterator>::difference_type *>(0);
}

//获取迭代器的value_type函数
template<class Iterator>
inline typename iterator_traits<Iterator>::value_type *
value_type(const Iterator&)
{
	return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}

//求两个一般迭代器之间的距离的函数_distance,供distance函数分类调用
template<class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
_distance(InputIterator first,InputIterator last,input_iterator_tag)
{
	typename iterator_traits<InputIterator>::difference_type n=0;
	while(first!=last)
	{
		++first;
		++n;
	}
	return n;
}
//求两个随机訪问迭代器之间的距离的函数_distance，供distance函数分类调用
template<class RandomAccessIterator>
inline typename iterator_traits<RandomAccessIterator>::difference_type
_distance(RandomAccessIterator first,RandomAccessIterator last,
          random_access_iterator_tag)
{
	return last-first;
}

//自适应地调用distance函数
template<class InputIterator>
inline typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first,InputIterator last)
{
	typedef typename iterator_traits<InputIterator>::iterator_category category;
	//从typename能够看出。category是一个类型
	return _distance(first,last,category());//显示调用category类的构造函数，返回该类的一个对象
}

/*****以下的函数用于将指针移动n位的方法*/
//一般迭代器求向前移动的方法，与双向迭代器和随机反问迭代器不同
template<class InputIterator,class Distance>
inline void _advance(InputIterator& i,Distance n,input_iterator_tag)
{
	while(n--)
	{
		++i;
	}
}

//针对双向迭代器移动的方法
template<class BidirectionalIterator,class Distance>
inline void _advance(BidirectionalIterator &iter,Distance n,
	                 bidirectional_iterator_tag)
{
	if(n>=0)//当n大于0时。向后移动
	{
		while(n--)
		{
			++iter;
		}
	}
	else//当n小于0时，向前移
	{
		while(n++)
		{
			--iter;
		}
	}
}

//定义随机訪问迭代器移动的方法
template<class RandomAccessIterator,class Distance>
inline void _advance(RandomAccessIterator &iter,Distance n,
	                 random_access_iterator_tag)
{
	iter+=n;
}

//自适应的调用advance函数
template<class InputIterator,class Distance>
inline void advance(InputIterator &iter,Distance n)
{
	_advance(i,n,iterator_catetory(iter));
}

        1.定义5类迭代器的标志类，该标志类用于实现函数的差别调用（即重载），比如求两迭代器距离函数distance(iter1,iter2,tag)。移动函数advance(iter,n,tag)。

这五个标志类分别为：input_iterator_tag，output_iterator_tag。forward_iterator_tag，bidirectional_iterator_tag，random_access_iterator_tag。

        2.对于每个iterator类，都必须包括5个属性，分别为：iterator_category、value_type、difference_type、pointer、reference。

        3.定义一个迭代器的“属性榨汁机”iterator_traits，用于获取iterator的5中属性值。

        4.定义迭代器的操作。分别为：

           1） 获取iterator的标志----->iterator_category(iter)。

           2）获取两迭代器差值的类型----->distance_type(iter)。

           3）获取迭代器的原始类型--------->value_type(iter)；

           4）求两迭代器的距离---------------->distance(iter1,iter2,tag)；

           5）将迭代器移动n位------------------>advance(iter,n,tag)。

參考文献：

[1]《C++ Primer中文版 第4版》

[2]《STL源代码分析 侯杰》