Ch3 迭代器概念与traits编程技法

3.1 迭代器设计思维

STL的中心思想在于：将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以一帖胶着剂将它们撮合在一起，迭代器（iterators）则扮演胶着剂的角色。

3.2 迭代器是一种smart pointer

迭代器最重要的编程工作是，对operator* 和operator-> 进行重载工作。

关于这一点，C++标准程序库有一个auto_ptr可供我们参考。

auto_ptr是一个用来包装原生指针（native pointer）的对象，memory leak问题也可借此解决。

每一种STL容器都提供有专属的迭代器，因为在完成一个针对某STL容器而设计的迭代器时，往往不可避免地暴露了该容器太多的实现细节。

3.3 迭代器相应型别（associated types）

利用function template的参数推导（argument deducation）机制，

以func()为对外接口，但把实际操作全部置于func_impl()之中，

由于func_impl()是一个function template，一旦被调用，编译器会自动进行template参数推导，

于是导出型别T，从而获取迭代器的相应型别。

3.4 Traits编程技法

最常用到的迭代器相应型别有：value type，difference type，pointer，reference，iterator category。

3.4.1 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。从而，func()可以改写为：
template <class I>
typename iteratro_traits<I>::value_type func(I ite){
    return *ite;
}
这样，我们只需更改class type，则不论是常规的class type，还是原生指针（如int*），还是指向常数对象的指针，都可以通过traits来取得器value type。

3.4.2 different type

difference type 用来表示两个迭代器之间的距离，即用来表示一个容器的最大容量。

如STL的count()，其传回值就必须使用迭代器的difference type：

template <class I, class T>
typename iterator_traits<I>::difference_type count(I first, I last, cosnt T& value){
    typename iterator_traits<I>::difference_type n=0;
    for( ; first!=last; ++first){
        if(*first == value)  ++n;
    return n;
}

traits内部的特化：

template <class I>
struct iterator_traits{
    ...
    typedef typename I::difference_type difference_type;
};

//针对原生指针而设计的“偏特化（partial specialization）”版
template <class T>
struct iterator_traits<T*> {
    ...
    typedef ptrdiff_t difference_type;
};

//针对原生的pointer-to-const而设计的“偏特化”版
template <class T>
struct iterator_traits<const T*> {
    ...
    typedef ptrdiff_t difference_type;
};

3.4.3 reference type

constant iterators：不允许改变“所指对象之内容”的迭代器；

mutable iterators：允许改变“所指对象之内容”的迭代器。

对于mutable iterator进行赋值时，应该获得一个左值，因为右值不允许赋值操作（assignment）。

在C++中，函数如果要传回左值，都是以by reference的方式进行，所以当p是一个mutable iterators时，如果其value type是T，那么*p的型别应该是T&，而不是T（const也同理）。

上述*p的型别T&，即reference type。

3.4.4 pointer type

// ListIter class:
Item& operator*() const { return *ptr; }
Item* operator->() cosnt { return ptr; }

Item& :ListIter的reference type；

Item* :ListIter的pointer type。

traits内部对reference type和pointer type这两个相应型别的特化：

template <class I>
struct iterator_traits {
    ...
    typedef typename I::pointer pointer;
    typedef typename I::reference reference;
};

//针对原生指针而设计的“偏特化”版
template <class T>
struct iterator_traits<T*> {
    ...
    typedef T* pointer;
    typedef T& reference;
};

//针对原生的pointer-to-const而设计的“偏特化”版
template <class T>
struct iterator_traits<const T*> {
    ...
    typedef const T* pointer;
    typedef const T& reference;
};

3.4.5 iterator_category

五类迭代器：

Input Iterator：只读，这种迭代器所指的对象，不允许外界改变；
Output Iterator：只写；
Forward Iterator：允许“写入型”算法（如replace()）在此种迭代器所形成的区间上进行读写操作；
Bidrectional Iterator：可双向移动。某些算法需要逆向走访某个迭代器区间，可以使用此迭代器；
Random Access Iterator：涵盖前四种迭代器的算术能力。

其概念的关系如下：

Input It → Forward It → Bidrectional It → Random Access It

Output It →

那么对于一个算法，我们将写好五种迭代器所对应的版本，在编译时（之所以不在执行时才决定，是避免影响程序效率）决定应该使用哪一个版本。

要达到这个目标，可以如下设计：利用重载函数，并通过traits萃取出迭代器的种类（iterator categories），利用“迭代器类型”相应型别作为算法的最后一个参数。

//五个作为标记用的型别（tag types）
struct input_iterator_tag { };
struct ouput_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 { };

这些calsses只作为标记用，故不需要任何成员。

现以advance()为例，利用上述classes重新设计：

/*先设计__advance() */
//由于只在内部使用，所以函数名称前面加了__
template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
    while(n--) ++i;
}

template <class ForwardIterator, class Distance>
inline void __advance(ForwardIterator& i, Distance n, forward_iterator_tag) {
    //进行单纯的传递调用
    __advance(i, n, input_iterator_tag);
}

template <class Bidirectionalterator, class Distance>
inline void __advance(BidirectionalIterator& i, Distance n, bidirectional_iterator_tag) {
    if(n>=0)
        while(n--) ++i;
    else
        while(n++) --i;
}

template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n, random_access_iterator_tag) {
    i+=n;
}

/*增加一个对外开放的上层控制接口，调用上述各个重载的__advance() */
//这里template的第一个参数名称取为InputIterator是因为
//遵守STL算法命名的规则：
//以算法所能接受之最低阶迭代器类型，来为其迭代器型别参数命名
template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n) {
    __advance(i, n, iterator_traits<InputIterator>::iterator_category());
}

/*为traits增加相应型别iterator category */
template <class I>
struct iterator_traits {
    ...
    typedef typename I::iterator_category iterator_category;
};

//针对原生指针而设计的“偏特化”版
template <class T>
struct iterator_traits<T*> {
    ...
    //原生指针是一种Random Access Iterator
    typedef random_access_iterator_tag iterator_category;
};

//针对原生的pointer-to-const而设计的“偏特化”版
template <class T>
struct iterator_traits<const T*> {
    ...
    //原生的pointer-to-const也是一种Random Access Iterator
    typedef random_access_iterator_tag iterator_category;
};

//任何一个迭代器，其类型永远落在“该迭代器所隶属之各种类型中，最强化的那个”
//如int*，既是Random Access Iterator，又是Bidirectional Iterator，也是Forward Iterator，
//也是Input Iterator，那么int*的类型应该是random_access_iterator_tag

为了消除单纯的传递调用，前面用来定义五种迭代器的classes，其中设置好的继承关系，就可以派上用场：

//以I, F, B为例

//classes
struct I { };
struct F : public I { }; //继承I
struct B : public F { }; //继承F

//函数调用
template <class T>
func(T& p, I) {
    cout<<"I version
";
}

template <class T>
func(T& p, B) {
    cout<<"B version
";
}

int main(){
    int* p;
    func(p,I());  //参数与参数完全吻合，输出： “I version”
    func(p,F());  //参数与参数不完全吻合，因继承关系而自动传递调用，
           //输出： “I version”
    func(p,B());  //参数与参数完全吻合，输出： “B version”
}