笔记：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类型。