STL的迭代器和類型萃取

今天就可以把STL庫中迭代器的實現，和類型萃取好好整理一下了

迭代器的設計思維是STL的關鍵所在，在STL的實際運用和泛型思維，迭代器都扮演著十分重要的角色，STL力求把數據容器和算法的概念分開來，於是就有了STL的兩大部分，容器（container）和泛型算法（algorithms），泛型算法有很多參數都是迭代器。

舉一個栗子！泛型算法find（）的實現！

template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last , const T& value)
{
    while(*first != *last && *first != value)
    {
        ++first;
    }
    return first;
}

接受兩個輸入迭代器的參數

• STL把迭代器分為5個類別
  • trivial迭代器(Trivial Iterator)：只是一個概念，用以區分所有迭代器的定義
  • 輸入迭代器(Input iterator)：提供只讀操作，可讀取其指向元素的值，但不可以改變該元素的值（還包括trivial迭代器中的所有操作（可能是用繼承？））
  • 輸出迭代器(Output Iterator)：提供只寫操作，可改變
  • 前進迭代器(Forward Iterator)：可以改變所指向元素的值，但不可以讀取
  • 雙向迭代器(Bidirectional Iterator)：可以雙向移動
  • 隨機訪問迭代器(Random Iterator)：韓乾各種指針算數能力，可以像訪問順序表一樣隨機訪問

之前發布的智能指針也算是迭代器的一種，原生的指針當然也可以說是迭代器，只是這麼說有些狹隘了迭代器的定義，因為自定義類型的指針功能不夠完善，需要重載一些運算符之類的，為什麼智能指針也不能直接用作迭代器呢？因為無法獲得智能指針所指向的類型！

為什麼這麼說？因為有的時候我們可能想要使用智能指針所指向的類型去創建一些變量，不好弄，即使是使用type_id也只是獲得名字，並不能用來創建變量，有種方法可以用的

template<class T,class U>
 
void Fun_impl(T t ,U u)

{

                U tmp;//we got the type

}
template<class T>

void Fun(T t)

{

                return Fun_impl(t ,*t);

}

這麼做就可以獲得所指向的類型（並且創建了想要的變量）了，但是當我們需要一個這樣的返回值的時候應該怎麼辦嘛，也許還是上面這種方法？看似是那麼的完美，但是編譯之後就無情的擊碎了你的希望，編譯是不通過的

但是我們可以通過內嵌型別聲明來獲取他們的類型（通過typeid是不行的，因為typeid只能獲得類型的名稱，並不能用這個名稱來聲明變量）

這種方法顯然是可以的，但是有個隱晦的陷阱，因為不是所有傳過來的都是迭代器，萬一傳過來的就是一個原生指針，原生指針就沒有內嵌類型（當然沒有，你認為一個int*內部會有內嵌類型麼，話說int*有什麼內部麼）！！！！這就要用到偏特化的知識

那什麼是偏特化呢？使用模板的時候，模版參數設定為多個template<class T, class U>模板是可以特定的

template<class T， class U>
class class1
{
    T a;
    U b;
};
template<class T>
class class1<int>
{
    T a;
    U b;
};

上述代碼中對U進行了特化，嗯！簡單易懂，如果T也特化一下，就是全特化了，偏特化就是沒有全都特化！

但是還有一個問題，當傳過來的的指針是一種指向常值的指針（pointers to const）const int *ptr的時候，，我們很顯然獲得的類型就是const int，這有些不對勁，因為我們得到的類型拿來聲明臨時變量是沒有辦法使用的，就因為他指向了常值，很簡單，再拿取偏特化一下就可以了（就是在上圖中<T*>處改成<const T*>）

traits就扮演了一個類型萃取機的角色，用來萃取出迭代器所指向的類型（類型萃取？！）

為什麼要有這麼多的迭代器呢？你看容器人手一個！因為迭代器中有operator++的實現，每個容器存儲的方式也不盡相同，vector是順序存儲，list是鏈式存儲，operator++內部實現肯定不一樣的，但是又想泛型編程，繼承咯，封裝咯。。。

• 最常使用到的迭代器的相應類別有5種：value_type,difference_type,pointer,reference,iterator_category
• • value_type就是迭代器所指向的對象的型別，每個迭代器都應該定義有自己的value_type內嵌型別
  • difference_type用來表示兩個迭代器之間的距離，因此也可以表示一個容器的最大容量
  • referecne引用？左值，因為有需要const iterator的情況出現，這時候需要一個不能改變所指向對象的迭代器；在C++中，函數如果要傳回左值，都是以by reference的方式進行
    
  • pointer_type就是簡單的迭代器所指向對象的地址，就是圖中第二個
  • iterator_category就是之前用的那個類型萃取，萃取出迭代器的名稱，作為函數參數，激活函數重載機制，就是利用traits實現的

那麼我接下來就講講iterator_category的相關吧

iterator_category干啥的？對下圖中五種迭代器進行分類標識

這張圖中的箭頭並不是代表繼承關系，而是概念強化關系，就是說下層一定是個上層，但上層絕不是個下層，就跟正方形是矩形的一種特殊一樣，但是矩形就不是正方形

1 struct input_iterator_tag {};
2 struct output_iterator_tag {};
3 struct forward_iterator_tag:public input_iterator_tag {};
4 struct bidirectional_iterator_tag :public forward_iterator_tag {};
5 struct random_access_iterator_tag :public bidirectional_iterator_tag {};

這是五種空殼結構體，沒其他用處就是用來標識迭代器類型，用來激活函數重載機制（因為泛型算法中要求的參數都會只給最上層的類型，這樣調用時，下層迭代器來了也接受）

為什麼會有繼承？泛型算法是支持上層迭代器作為參數傳入底層迭代器的形參的！就是在這裡用的，因為迭代器本身沒有繼承，所以用標識名繼承來激活重載機制

例如advance(iterator ,n)泛型函數，它的作用是將傳過來的迭代器往後走n個，每種迭代器的實現肯定不一樣的，像是forward_iterator只能一個一個走，走n次，bidirectional_iterator也一樣，random_access_iterator就可以一下走n個，如果寫成一個，肯定會影響random_access_iterator的效率，所以分開寫，那麼我怎麼知道改調用哪個函數呢？因為我想泛型編程（就是我懶，我想省事）肯定就想只寫一個函數名，傳個參數，讓程序幫我選擇調用哪個函數（我的天！這不就是函數重載麼）,但是程序需要知道我傳的參數是哪種類型的迭代器（就是類型萃取呢！！！）把類型從迭代器中萃取出來！（沒弄全，其他的類似）

參數列表中最後一個就是剛才建立的那五個空殼結構體！！調用_advance的時候最後一個參數給迭代器的iterator_category就行了，對！沒錯就這麼用！讓程序自己判斷用哪個函數！！

具體實現：調用

1 template <class InputIterator ,class Distance>
2 inline void advance(InputIterator& i，Distance n)
3 {
4     _advance(i, n, iterator_traits<InputIterator>::iterator_category());
5 }

1 template<class I>
2 struct iterator_traits 
3 {
　　　 ......　
4     typedef typename I::iterator_category iterator_category;
5 };