迭代器——STL關(guān)鍵所在

迭代器基本介紹：

STL的設(shè)計(jì)中心思想在于：將容器和算法分開，彼此獨(dú)立設(shè)計(jì)，最后再以一個(gè)膠合劑連接在一起。而算法和數(shù)據(jù)容器的泛型化從技術(shù)角度來說并不難實(shí)現(xiàn)，而如何將兩者聯(lián)系起來才是問題的關(guān)鍵所在。而迭代器恰恰扮演者這個(gè)角色。迭代器定義的位置最好是在容器內(nèi)，將定義的任務(wù)交給了容器的設(shè)計(jì)者，因?yàn)槊恳环N容器都對(duì)應(yīng)一種迭代器，而定義在內(nèi)部也不會(huì)暴露容器的內(nèi)部元素。

看看下面的find函數(shù)：

       可以看出find接受兩個(gè)迭代器和一個(gè)目標(biāo)對(duì)象。只要給予不同的迭代器find就可以對(duì)不同的容器進(jìn)行查找了。

       迭代器是一種類似指針的對(duì)象，而指針的各種行為中最常見也是最重要的便是內(nèi)容提領(lǐng)和成員訪問。因此，迭代器最重要的編程工作就是對(duì)operator*和operator->進(jìn)行重載。

       在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候list一直是一個(gè)重點(diǎn)，以前也曾模擬實(shí)現(xiàn)過list，如今何不為list設(shè)計(jì)一個(gè)迭代器來將其數(shù)據(jù)容器與算法粘合起來呢？

       其接口及結(jié)點(diǎn)實(shí)現(xiàn)如下：

 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;

};

       模擬實(shí)現(xiàn)簡化版：

       我們自己實(shí)現(xiàn)的List也可以套用find函數(shù)，只需對(duì)其進(jìn)行一個(gè)迭代器的設(shè)計(jì)就OK了。

       具體實(shí)現(xiàn)如下：

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。分別代表這迭代器所指對(duì)象類型，迭代器類型，迭代器所指類型引用，迭代器所指類型指針，用什么類型表示迭代器之間距離（如int類型）。

      這里就不得不說下STL里面為了提取這些迭代器都有的特性用到的一個(gè)技法——trait。

STL為所有的迭代器提供一個(gè)型別類型，我們每定義一個(gè)迭代器都必須繼承該型別類型，這樣就可以保證符合STL的規(guī)范，防止遺漏。

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

       當(dāng)定義迭代器的時(shí)候，必須給定迭代器的特性。STL為提取迭代器的特性，提供了一個(gè)模板類iterator_trait，適用于所有的迭代器和原生指針。

       指針并非類型，因此需要偏特化成一個(gè)模板對(duì)應(yīng)指針的特性，可以看出，指針是隨機(jī)訪問迭代器類型。

       迭代器的類型有五種：輸入、輸出、前向、雙向、隨機(jī)訪問五種迭代器，輸入和輸出分別只讀和只寫，只能向前不能向后，前向迭代器可以進(jìn)行讀寫，只能向前，雙向迭代器可以向前和向后移動(dòng)，但每次只能移動(dòng)一次，隨機(jī)訪問迭代器可以跳躍移動(dòng)，與原生指針操作相同。

       STL中構(gòu)建了這五種類別，用于標(biāo)識(shí)迭代器的類別。

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

       可以看出繼承關(guān)系，使用template元編程技術(shù)，之所以使用結(jié)構(gòu)體或類，是為了進(jìn)行參數(shù)推導(dǎo)，將判斷在編譯期執(zhí)行而非運(yùn)行期，因?yàn)槊總€(gè)迭代器操作不同，因此需要不同的函數(shù)版本對(duì)應(yīng)不同迭代器。

        迭代器失效：

       迭代器就不得不提到一個(gè)問題，迭代器失效。

       以vector為例，當(dāng)我們插入一個(gè)元素時(shí)它的預(yù)分配空間不夠時(shí)，它會(huì)重新申請(qǐng)一段新空間，將原空間上的元素復(fù)制到新的空間上去，然后再把新加入的元素放到新空間的尾部，以滿足vector元素要求連續(xù)存儲(chǔ)的目的。而后原空間會(huì)被系統(tǒng)撤銷或征做他用，于是指向原空間的迭代器就成了類似于“懸垂指針”一樣的東西，指向了一片非法區(qū)域。如果使用了這樣的迭代器會(huì)導(dǎo)致嚴(yán)重的運(yùn)行時(shí)錯(cuò)誤就變得很自然了。這就是由迭代器失效引起的。當(dāng)然刪除一個(gè)元素時(shí)也可能引起迭代器失效。erase操作是在原空間上進(jìn)行的，假設(shè)有一個(gè)存有"12345"序列的vector<int>容器原本指向3的迭代器在我刪除2之后就變成指向4了。

      2.由于刪除元素使得某些元素次序發(fā)生變化使得原本指向某元素的迭代器不再指向希望指向的元素。