笔记：STL学习（二）-- 迭代器和traits
迭代器设计思维-STL关键所在
STL设计的中心思想在于：将数据容器和算法设计分开，最后通过迭代器将两者结合起来使用，从技术角度来看并不困难，使用class template和function temlpate就可以达成目标，如何设计初两者之间良好的迭代器，才是最关键的地方。
以算法find()为例
telplate <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value){
while(first != last && *first != value)
++first;
return value;
}
上述函数是全局范围内的find()函数，与map.find()是不同的，一个是类的成员方法，一个是普通函数。从上述函数，我们还可以发现，无论是何种函数的容器，它的迭代器都支持operate++操作。
（PS：以前一个面试官问我，普通数组可以使用STL的算法吗？答案应该是可以的，因为传入原生指针，上述算法仍然可以顺利执行，不过容器的成员方法就要视情况具体分析了）
迭代器相应型别
在算法使用迭代器的时候，可能会使用到其相应数据类型，比如迭代器所指数据类型，即使使用RTTI性质中的typeid(),也只能获取到类型别名，并不能用来作为变量的声明。
解决办法：利用function template的参数推导(argument deducation)机制。
template <class I, class T>
void func_impl(I iter, T t)
{
T tmp; // ...
};
template <class I>
inline
void func(I iter)
{
func_impl(iter, *iter);
}
int main()
{
int i;
func(&i);
}
如上述方法，将func()的工作全部放置在func_impl(),就可以得到类型T了，上述理解就是class I就是迭代器，class T就是迭代器所指数据类型。
Traits编程技巧
上述方法虽然能推导出value type。如果value type用于函数的返回值，上面的方法也就行不通了，毕竟函数的"template参数推导机制"推而导之的只是参数，无法推导函数的返回值。
template <class T>
struct MyIter {
typedef T value_type;
T* ptr;
MyIter(T* p=0) : ptr(p){}
T& operator*() const {retrun *ptr;}
//...
};
template <class I>
typename I::value_type
func(I ite)
{ return *ite; }
//...
MyIter<int> ite(new int(8));
cout<< func(ite);
func()的返回型别必须加上关键词typename，因为T是一个template参数，在它被编译器具现化之前，编译器对T一无所悉，换句话说，编译器此时并不知道MyIter<T>::value_type代表的是一个型别或是一个member function或是一个data member。关键词typename的用意在于告诉编译器这是一个型别，才能顺利通过编译。
但并不是所有的迭代器都是class type。原生指针就不是，如果不是class type就无法为其定义内嵌性别。C++采用了template partialspecialization(偏特化)--范围的偏。class template专门用来"萃取"迭代器的特性，而value type正是迭代器的特性之一。
template <class I>
struct iterator_traits{
typedef typename I::value_type value_type;
};
这个所谓的traits，其意义是，如果I定义有自己的value type，那么通过这个traits的作用，萃取出来的value_type就是I::value_type。换句话说，如果I定义有自己的value type，先前那个func()可以写成这样。
template <class I>
typename iterator_traits<I>::value_type
func(I ite)
{ return *ite; }
对于原生指针，如int*，就不是一种class type,通过偏特化的方式，可以解决这个问题。
template <class T>
struct iterator_traits<T*>{
typedef T value_type;
};
上述还有一个问题，如果是指向常数对象的指针（pointer-to-const）
iterator_traits<const int*>::value_type
那萃取出来的，就是一个pointer-to-const的迭代器，无法赋值的临时变量不是我们的预期，需要另外设计一个版本
template <class T>
struct iterator_traits<const T*>{
typedef T value_type;
};
通过上述方法萃取出来的value_type就是一个non-const类型。