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

3.1 迭代器设计思维—— STL 关键所在

中心思想在于将数据容器和算法分开。

3.2 迭代器是一种智能指针

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

每一种 STL 容器都提供有专属迭代器以隐藏容器的设计细节。

3.3 迭代器相应型别

运用迭代器时有时需要获取对应的型别，某些情况下可以通过模板推导。

3.4 traits 编程技法—— STL 源代码门钥

设计模板类专门用于萃取迭代器的特性，包括迭代器指向的数据类型，使用方法如下

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

在实例化前，typedef 并不知道 I::value_type 是什么，可能为数据成员或成员函数或嵌套类型，因此加上 typename 关键字告知 typedef 它是一个类型。这样在迭代器中就可以使用迭代器指向的数据类型了，比如

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

但当迭代器指向类型为指针或 const 指针时，则需要特化模板函数，使用

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

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

即可萃取正确的类型。

3.4.1 迭代器相应型别之一：value_type

value_type 是迭代器所指向对象的型别，定义方法同上。

3.4.2 迭代器相应型别之二：difference_type

difference_type 表示两个迭代器之间的距离，也可以表示最大容量。如果泛型算法提供计数功能，则必须返回 difference_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;
}

针对其他型别，有

// Provide type ptrdiff_t
#include <cstddef>

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

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

3.4.3 迭代器相应型别之三：reference_type

3.4.4 迭代器相应型别之四：pointer_type

这两种型别分别对应迭代器的引用和指针类型，使用方法如下

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

template<class I>
struct iterator_traits<I*> {
    typedef I* pointer;
    typedef I& reference;
}

template<class I>
struct iterator_traits<const I*> {
    typedef const I* pointer;
    typedef const I& reference;
}

3.4.5 迭代器相应型别之五：iterator_category

迭代器可以被分为五类，只读、只写、区间读写 ++、双向移动 --、随机访问。因为访问方法不同，因此调用函数时需要针对不同的迭代器类型设计不同的函数，最后根据 traits 获取迭代器类型，根据多态使用不同函数。

// Predefined tag
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_iterator_tag : public bidirectional_iterator_tag { };

// Design function for different iterator
template<class InputIterator, class Distance>
inline void __advance(InputIterator & i, Distance n, input_iterator_tag) { ... }
template<class ForwardIterator, class Distance>
inline void __advance(ForwardIterator & i, Distance n, forward_iterator_tag) { ... }
template<class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator & i, Distance n, random_access_iterator_tag) { ... }

// Main function
template<class InputIterator, class Distance>
inline void advance(InputIterator & i, Distance n) {
    __advance(i, n, iterator_traits<InputIterator>::iterator_category());
}

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

template<class I>
struct iterator_traits<T*> {
    typedef random_access_iterator_tag iterator_category;
}

template<class I>
struct iterator_traits<const T*> {
    typedef random_access_iterator_tag iterator_category;
}

3.5 std::iterator 的保证

任何迭代器都拥有以上的五个内嵌型别，STL 提供了 iterator 基类，设计的迭代器继承自它，就可以满足 STL 规范。

template<class Category, class T, class Distancee = 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;
}

它是纯粹的型别定义，不包含任何成员。

3.6 iterator 源代码完整重列

3.7 SGI STL 的私房菜：__type_traits