STL迭代器手札

利用模板来推倒函数返回值

template<class T>
typename T::value_type FunName(PatamType var)
{
    return xxxx;
}

.      T是模板参数，编译器不认识T，同时也并不知道T::value_type代表的是什么。typename告诉编译器这是一个行别。

偏特化，对指针和基础类型做处理

偏特化：就是提供另一份模板定义式，本身仍然是模板。
//泛化版本，允许接T为任何类型
temp<typename T>
class ClassName
{
}

//特化版本，允许接受T为指针类型
temp<typename T>
class ClassName&lt;T*&gt;
{
}

//特化版本，允许接受T为const 指针类型
temp<typename T>
class ClassName&lt;const T*&gt;
{
}

STL迭代器类型

.      如果希望兼容STL迭代器，那么类模板都必须定义一下五种类型：

.      值类型：typedef T::value_type      value_type

.      不同类型：typedef T::difference_type           difference_type

.      指针类型：typedef T::pointer                  pointer

.      参考（引用）类型：typedef T::reference reference

.      迭代器类型：typedef T::iterator_category            iterator_category

.      同时iterator_category必须对传入类型point以及const point两者设计特化版本。

value_type

.      值迭代器所指对象的型别。T

difference_type

.      表示两个迭代器之间的距离，也可以用来表示容器的最大容量。针对相应的偏特化，如果是指针类型那么difference_type为：typedef ptrdiff_t             difference_type

pointer

.     迭代器允许修改所指对象的内容那么为T*，如果不允许修改所指向的内容那么为const T*

reference

.      迭代器允许改变所指对象的内容为T&，如果不允许修改指向的内容那么为const T&

iterator_category

.      迭代器有五项分类：

.      Input Iterator：迭代器所指对象不允许外界修改为“只读”

.      Output Iterator：只写

.      Forward Iterator：允许“写入行”，表示所形成区间上进行读写操作

.      Bidirectional Iterator：可双向移动。

.      Random Access Iterator：上一种在加上“++、–”运算符。并且涵盖所有指针算数能力。p+n、p-n、p[n]、p1-p2、p1<p2.。。。。。

.      他们之间的关系并非“继承”而是“强化”的概念，但是下面以C++类型表示

class Input Iterator{}
class Output Iterator{}
class Forward Iterator : poublic Input Iterator, public Output Iterator{}
class Bidirectional Iterator : public Forward Iterator{}
class Random Access Iterator : public Bidirectional Iterator

.      以上为“强化”关系，而非“继承”关系！！！！

迭代器分类，这到底是什么鬼东西？

.      emmmmmm，迭代器分类，用来做“函数重载”的。不同的iterator_category对其typedef为iterator_category。如：typedef Input_Iterator iterator_category或者是typedef Random_Access_Iterator iterator_category。

.      C++函数可以是相同的函数名称，只要保证函数参数不一致就能够实现“函数重载”。同样，不同的iterator_category是由上面几个不同的“迭代器分类”重新typedef定义为iterator_category的。那么不同的iterator_category将他当成函数传递的“参数类型”时就能够实现“函数重载”。

为什么要iterator_category函数重载？

int find1(vector<int&> vec, int pos)
{    
    return vec[pos];
}
int find2(vector<int>& vec, int pos)
{ 
    vector<int>::iterator it = vec.begin();
    for (; pos--; it++)
        ;
    return *it;
}

.      为了迭代器提速。比如vector支持“[]” find1访问这是最快的方式。那么vector同样也可以实现为find2来进行访问。但是明显find1比find2效率要高出很多。同样，对于STL来说在编译前并不知道迭代器的所指向的类型是什么，用什么方式访问元素最快。那么通过定义不同的iterator_category重载到不同的数据遍历的函数中实现最大效率的数据遍历。

型别特性

.      这玩意儿时SGI私有的将iterator_category的特性从迭代器扩展迭代器之外来使用。用于“萃取”型别的特性。型别特性是指具备：构造、拷贝构造、运算符重载、析构。如果不满足那么可以直接调用系统函数memset、memcopy之类的函数来提速执行。而非调用迭代器慢慢悠悠的一个一个memset、memcopy。

.      它的定义和在<type_traits.h>中。__type_traits中的所有typedef都定义为__false_type。然后下面都是对基本类型进行“特化”，将所有的typedef都定义为__true_type。那么当__type_traits的type为class时，所有的typedef都为__false_type。那么对于基础类型和class类型就可以区分开来做一些“提速”处理。

value_type理解

.      这玩意的实现是在<stl_iterator>当中，具体为：

template <class T>
inline T* value_type(const T*) { return (T*)(0); }

这玩意返回一个T*而不是返回T的原因是T*为一个“指针”类型，指针类型用于都只占用4个字节！如果返回T的话那么所占用的栈空间那么就大了。