迭代器——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.由于刪除元素使得某些元素次序發生變化使得原本指向某元素的迭代器不再指向希望指向的元素。