迭代器——STL关键所在

迭代器基本介绍：

STL的设计中心思想在于：将容器和算法分开，彼此独立设计，最后再以一个胶合剂连接在一起。而算法和数据容器的泛型化从技术角度来说并不难实现，而如何将两者联系起来才是问题的关键所在。而迭代器恰恰扮演者这个角色。迭代器定义的位置最好是在容器内，将定义的任务交给了容器的设计者，因为每一种容器都对应一种迭代器，而定义在内部也不会暴露容器的内部元素。

看看下面的find函数：

       可以看出find接受两个迭代器和一个目标对象。只要给予不同的迭代器find就可以对不同的容器进行查找了。

       迭代器是一种类似指针的对象，而指针的各种行为中最常见也是最重要的便是内容提领和成员访问。因此，迭代器最重要的编程工作就是对operator*和operator->进行重载。

       在学习数据结构的时候list一直是一个重点，以前也曾模拟实现过list，如今何不为list设计一个迭代器来将其数据容器与算法粘合起来呢？

       其接口及结点实现如下：

 template <class T>
struct __ListNode
{
	__ListNode<T>* _next;
	__ListNode<T>* _prev;
	T _data;

	__ListNode(const T& x = T())
		:_next(NULL)
		, _prev(NULL)
		, _data(x)
	{}
};

template <class T>
class List
{
public:
	typedef __ListNode<T> Listnode;
	
	List()
	{
		_head = new Listnode;
		_head->_next = _head;
		_head->_prev = _head;
	}

	~List()
	{}
	void Insert(const T& x)；

	Iterator Erase(const T& x)；

protected:
	Listnode* _head;

};

       模拟实现简化版：

       我们自己实现的List也可以套用find函数，只需对其进行一个迭代器的设计就OK了。

       具体实现如下：

template<class T,class Ref,class Ptr>
struct __ListIterator
{
	typedef __ListIterator<T, Ref, Ptr> Self;
	typedef T ValueType;
	typedef Ptr Pointer;
	typedef Ref Reference;

	__ListNode<T>* _node;

	__ListIterator(__ListNode<T>* x)
		:_node(x)
	{}
	__ListIterator()
	{}


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

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

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

	/*Reference operator->()
	{
		return _node->_data;
	}*/
	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;
	}
};

       迭代器型别和trait编程：

       迭代器的型别主要有五种：value_type,catalog,reference,pointer,diffrence。分别代表这迭代器所指对象类型，迭代器类型，迭代器所指类型引用，迭代器所指类型指针，用什么类型表示迭代器之间距离（如int类型）。

      这里就不得不说下STL里面为了提取这些迭代器都有的特性用到的一个技法——trait。

STL为所有的迭代器提供一个型别类型，我们每定义一个迭代器都必须继承该型别类型，这样就可以保证符合STL的规范，防止遗漏。

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;  
};

       当定义迭代器的时候，必须给定迭代器的特性。STL为提取迭代器的特性，提供了一个模板类iterator_trait，适用于所有的迭代器和原生指针。

       指针并非类型，因此需要偏特化成一个模板对应指针的特性，可以看出，指针是随机访问迭代器类型。

       迭代器的类型有五种：输入、输出、前向、双向、随机访问五种迭代器，输入和输出分别只读和只写，只能向前不能向后，前向迭代器可以进行读写，只能向前，双向迭代器可以向前和向后移动，但每次只能移动一次，随机访问迭代器可以跳跃移动，与原生指针操作相同。

       STL中构建了这五种类别，用于标识迭代器的类别。

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元编程技术，之所以使用结构体或类，是为了进行参数推导，将判断在编译期执行而非运行期，因为每个迭代器操作不同，因此需要不同的函数版本对应不同迭代器。

        迭代器失效：

       迭代器就不得不提到一个问题，迭代器失效。

       以vector为例，当我们插入一个元素时它的预分配空间不够时，它会重新申请一段新空间，将原空间上的元素复制到新的空间上去，然后再把新加入的元素放到新空间的尾部，以满足vector元素要求连续存储的目的。而后原空间会被系统撤销或征做他用，于是指向原空间的迭代器就成了类似于“悬垂指针”一样的东西，指向了一片非法区域。如果使用了这样的迭代器会导致严重的运行时错误就变得很自然了。这就是由迭代器失效引起的。当然删除一个元素时也可能引起迭代器失效。erase操作是在原空间上进行的，假设有一个存有"12345"序列的vector<int>容器原本指向3的迭代器在我删除2之后就变成指向4了。

      2.由于删除元素使得某些元素次序发生变化使得原本指向某元素的迭代器不再指向希望指向的元素。