迭代器设计

为什么要有萃取技术

既然迭代器是一种智能指针，iterator也要对一个原生指针进行封装，而问题就来源于此，当我们需要这个原生指针所指向对象的类型的时候(比如声明变量)，我们应该怎么办。

Case1:对于函数的局部变量

例如，有一个函数template<class T> void func (T iter),其中T是指向某个特定对象的指针，那么如果在func中需要指针指向对象类型的变量应该怎么办？
这种情况可以采用模版的参数推导机制。

template<class T>
void func(T t) {
    func_imple(t, *t);  // forward the task to func_impl
}

tempalte<class T, class U>
void func_impl(T t, U u) {
    U temp;             // got the type
}

通过模板的推导机制，我们轻而易举的或得了指针所指向的对象的类型，但是事情往往不那么简单。例如，如果我想把传递给func的这个指针参数所指的类型作为返回值，显然这个方法不能凑效了，这就是我们的case 2。

Case2:对于函数的返回值

比如说我们想这样,我们可以在func_impl中把U作为返回值，但问题是用户需要调用的是func来返回这个指针所指向的相应型别。下面的*T是错误的。

template<class T>
(*T) func(T t) {        // wrong code!!!
    return func_impl(t, *t);
}

tempalte<class T, class U>
U func_impl(T t, U u) {
    U temp;             // got the type
    ....
    return temp
}

解决方案
可以定义一个iterator，在定义的时候为期指向的对象类型制定一个别名,如下,而后只要需要其指向的对象的类型，只要直接引用就好了。

注意，关键词typename必须加上，用意在于告诉编译器这是一个型别，否则编译器不知道MyIter<T>::valuetyepe代表的是一个型别或是member function或者data member。

template<class T>
struct MyIter{
    typedef T value_type;
    T* ptr;
    MyIter(T* p = 0) : ptr(p) {}
    T& operator*() const {return *ptr;}
}

template<class I>
typename I::value_type func(I iter) {
    return *iter;
}

等等，还有问题。。。
并不是所有迭代器类型都是class type，原生指针就不是!
如果不是class type,就无法为它定义内嵌型别。
因为func如果是一个泛型算法，那么它也绝对要接受一个原生指针作为迭代器，但是显然，你无法让下面的代码编译通过：

int *p = new int(52); // 原生指针
cout<<func(p)<<endl;  // !!!Is there a int::value_type?? Wrong Code here

解决方案：模版偏特化
如果class template拥有一个以上的template参数，我们可以针对其中某个(或数个，或全部)template参数进行特化工作。换句话说，我们可以再泛化设计中提供一个特化版本。
假如有一个class template如下：

template<typename T>
class C{ ... };

所谓的partial specialization的意思是：针对任何template参数更进一步的条件设置所涉及出来的一个特化版本。我们可以使上面的class template，使之接受一个形式如下的partial specialization:

template<typename T>
class C<T*> { ... };

这个特化版本仅适用于“T为原生指针”的情况，T为原生指针便是T为任意类型的一个进一步的条件限制。

有了这个模版偏特化的利器，我们可以解决前述“内嵌型别”未能解决的问题。先前的问题是，原生指针并非class,因此无法为它们定义内嵌型别，现在我们可以设计特化版本的迭代器。

所以，我们设计一个专门的class template用来萃取迭代器的特性

注意，value_type只是迭代器特性之一，而非全部。比如说还有difference_type,reference等

tempalte<class I>
struct iterator_traits { // traits意为“特性”
    typedef typename I::value_type   value_type;
}

意思就是，如果I定义有自己的value_type,那么通过这个traits的作用，萃取出来的value_type就是I::value_type。也就是说，前面的func()可以改写成：

template<class I>
typename iterator_traits<I>::value_type func(I iter) {
    return *iter;
}

我们再为iterator_traits有一个偏特化版本,这就解决了原生指针不是class type的问题.

tempalte<class T>
struct iterator_traits<T*> { // traits意为“特性”
    typedef T   value_type;
}

还不够！
我们需要声明一个value_type类型的左值，但是却给iterator_traits传递了一个const int，显然结果有问题，于是，为const T也另起炉灶。

template<class T>
struct iterator_traits<const T*> {
    typedef T value_type;
}

设计迭代器

常用的迭代器相应型别有五种,traits会很忠实地将原汁原味榨取出来。

template <class I>
struct iterator_traits {
    typedef typename I::iterator_category iterator_category;
    typedef typename I::value_type value_type;
    typedef typename I::difference_type difference_type;
    typedef typename I::pointer pointer;
    typedef typename I::reference reference;
}

value_type

如上。

difference_type

这用来表示两个迭代器之间的距离，它可以表示一个容器的最大容量，STL的count()其返回值就必须使用这个diffrence_type。

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

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

template <class I>
class iterator_traits<I*> {
    typedef ptrdiff_t difference_type;
}

// typedef long int ptrdiff_t;

reference

迭代器分为两种：不允许改变“所指对象的内容”(const int* p)，允许改变“所指对象的内容”(int* p)。当我们对一个mutable iterator进行提领操作(解引用)时,不获得的不应该是右值，应该是一个左值，因为右值不能够被赋值操作。

int* pi = new int(5);
const int* pic = new int(9);

*pi = 7; //mutable iterators，获得左值，允许赋值
*pic = 1; //constant iterator, 提领获得右值，不允许赋值

这里，reference type指的是迭代器封装对象的类型的引用。这个类型的出现主要是为了解决对指针进行解引用的时候，返回什么样的对象的问题。

• 当p是一个mutable iterator时,如果value_type是T，那么*p的型别不应该是T，应该是T&
• 当p是一个constant iterator时,如果value_type是T，那么*p的型别不应该是const T，应该是const T&

pointer_type

C++中指针和引用总是有着密切的关系。如果我们想返回迭代器封装的对象的地址，就需要用到这里的pointer_type。
我们把reference_type和pointer_type这两个相应型别分别加入traits:

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

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

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

iterator_category

在STL中，共有以下5种迭代器类型：

• Input Iterator: 只读
• Output Iterator: 只写
• Forward Iterator: 读写
• Bidirectional Iterator: 可双向移动
• Random Access Iterator: 支持p+n,p-n,p[n],p1-p2,p1<p2

在STL的各种算法中，遍历元素是很常用的，于是我们就用advance()这个函数作个例子，看看每个迭代器的类型，这个函数负责把迭代器移动特定的长度：

// The input iterator version, an O(N) algorithm 
template <class InputIterator, class Distance>
void Advance_II(InputIteraotr& i, Distance n) {
    while(n--) i++; // This is step by step moving
}

// The bidirectional iterator version, an O(N) algorithm
template <class BidirectionalIterator, class Distance>
void Advance_BI(BidirectionalIterator& i, Distance n) {
    if(n >= 0)
        while(n--) i++;
    else
        while(n++) i++;
}

// The random access version, an O(1) algorithm
template <class RandomAccessIterator, class Distance>
void Advance_RAI(RandomAccessIterator& i, Distance n) {
    i += n;
}

最后，我们可以构想一个把这3个函数封装起来的函数advance，专门负责迭代器的移动。

template <class InputIterator, class Distance>
void advance(InputIterator& I, Distance n) {
    if(is_ramdom_access_iterator(i)) // How to judge?
        advance_RAI(I, i);
    else if(is_bidirectional_iterator(i)) // How to judge?
        Advance_BI(I, i);
    else
        Advance_II(I, i);
}

如果traits有能力萃取出迭代器的种类，我们便可以利用这个“迭代器类型相应型别”作为advance的第三个参数。这个相应型别一定必须是一个class type，因为编译器需要仰赖它进行重载决议。下面定义的5个class，代表五种迭代器类型：

// five tag classes
struct input_iterator_tag { }
struct output_iterator_tag { }
struct forward_iterator_tag : public input_iterator_tag { }
struct bidirectional_iterator_tag : public forward_iterator_tag { }
struct random_access_tag : public bidirectional_iterator_tag { }

template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n) {
    // Forward the correct messages
    __advance(i, n, type_traits<i>::iterator_category());
}

为了满足上述行为，traits必须再增加一个相应的型别

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

template<class I>
struct iterator_traits<T*> {
    ...
    // 注意，原生指针是一种 Random Access Iterator
    typedef random_access_iterator_tag  iterator_category;
}

template<class I>
struct iterator_traits<const T*> {
    ...
    // 注意，原生pointer-to-const是一种 Random Access Iterator
    typedef random_access_iterator_tag  iterator_category;
}

总结

设计适当的相应型别，是迭代器的责任，设计适当的迭代器，是容器的责任。唯容器本身，才知道设计什么类型的迭代器访问自己，并执行各种行为。

在STL中，所有的迭代器都遵从上面的设计原则，都要提供上面说过的五种类型，但是，人总会有挂一漏万的时候，为了设计上的方便，STL提供了一个标准的迭代器壳：

template <class Category,
class T,
class Distance = ptrdiff_t
class Pointer = T*
class Reference = T&>
struct iterator {
    typedef Category iterator_category;
    typedef T       value_type;
    typedef Distance difference_type;
    typedef Pointer  pointer;
    typedef Reference reference;
};

这样就免去了声明这些类型的麻烦，当你想自定义一个迭代器的时候：

template <class Item>
struct MyIter : public std::iterator<std::forward_iterator_tag, Item> { … }