STL萃取机

两个简单的栗子

template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& x)
{
    while (first != last && *first != x) ++first;
    return first;
}
template <class T>
struct iterator_traits_1 {
    typedef typename T::value_type value_type;
};
template <class T>
typename iterator_traits_1<T>::value_type
sample_func(T iter)
{
    return *iter;
}
int main()
{
    int *p = new int(2);
    cout << sample_func(p) << endl;    // 输出2
    return 0;
}

在第一个栗子中，只要所给迭代器满足运算!=,,++操作，find函数就不用关心迭代器是如何实现的，用什么结构实现的，可以做到算法与容器分离开来。
在第二个栗子中，我们通过typename iterator_traits_1<T>::value_type*提取到迭代器所指对象的类型，这就支持了我们在算法中可以针对迭代器的类型以及迭代器所指值得类型进行优化处理。

迭代器萃取机

上面栗子中，我们只对迭代器(int)的value_type*进行提取，通常我们使用的迭代器，还有如下几种类型是必须的，没有下面这5种内嵌的型别，就不能和STL算法以及其他组件相容。

value_type:迭代器所指对象的型别
difference_type:两个迭代器之间的距离
reference_type:迭代器所指对象的引用型别
pointer:迭代器所指对象的指针型别
iterator_category:迭代器的型别

我们的萃取机要上场了。

template <class T>
struct iterator_traits {
    // 这么定义之后，iterator_category就是类型T里面的iterator_category，下同
    typedef typename T::iterator_category iterator_category;
    typedef typename T::value_type value_type;
    typedef typename T::difference_type difference_type;
    typedef typename T::pointer pointer;
    typedef typename T::reference reference;
};
// 对T*和const T*做偏特化
template <class T>
struct iterator_traits<T*> {
    typedef random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef T* pointer;
    typedef T& reference;
};
// 对T*和const T*做偏特化
template <class T>
struct iterator_traits<const T*> {
    typedef random_access_iterator_tag iterator_category;
    typedef T value_type;
    typedef ptrdiff_t difference_type;
    typedef const T* pointer;
    typedef const T& reference;
};
// 可以通过下面的方式萃取迭代器的5个型别
typename iterator_traits<T>::value_type;
typedef typename iterator<traits<T>::iterator_category category;

下面以函数advance()为例子，来展示一下萃取机的威力，先来一个没有使用萃取机的栗子。

template <class InputIterator, class Distance>
InputIterator advance_II(InputIterator& i, Distance n) {
    while (n--) ++i;
}
template <class BidirectionalIterator, class Distance>
InputIterator advance_BI(BidirectionalIterator& i, Distance n) {
    if (n >=0)
        while (n--) ++i;
    else
        while (n++) --i;
}
template <class RandomIterator, class Distance>
InputIterator advance_RAI(RandomIterator& i, Distance n) {
    i += n;
}
template <class InputIterator, class Distance>
InputIterator advance(InputIterator& i, Distance n) {
    // 下面是错误的示范代码，在运行期决定走哪个分支
    if (is_random_access_iterator(i)) advance_RAI(i, n);
    else if (is_bidirectional_iterator(i)) advance_BI(i, n);
    else advance_II(i, n);
}

上述代码，需要在执行期才知道需要调用哪个版本的advance函数，效率低下，STL采用如下的技巧，可在编译期决定使用哪个版本的函数。

// 5个迭代器类型，都是空壳，没有运行效率和内存上的负担
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 {};
template <class InputIterator, class Distance>
void advance(InputIterator& i, Distance n)
{
    __advance(i, n, iterator_traits<InputIterator>::iterator_category());
}
// 即如果迭代器i的类型是input_iterator_tag，那么一定走这个分支
// 且这个决议是在编译期就已经知道了，下同
template <class InputIterator, class Distance>
void __advance(InputIterator& i, Distance n, input_iterator_tag)
{
    while (n--) ++i;
}
template <class ForwardIterator& i, Distance n>
void __advance(ForwardIterator& i, Distance n, forward_iterator_tag)
{
    __advance(i, n, input_iterator_tag);
}
template <class BidirectionalIterator& i, Distance n>
void __advance(ForwardIterator& i, Distance n, bidirectional_iterator_tag)
{
    if (n > 0)
        while (n--)++i;
    else
        while (n++)--i;
}
template <class RandomIterator& i, Distance n>
void __advance(ForwardIterator& i, Distance n, random_access_iterator_tag)
{
    i += n;
}

在上述代码中，advance函数仅仅是STL算法中的一个，对于不同的迭代器，采用不同的步进策略，以达到最大的运行效率。但是要让迭代器能够自如的和STL中的组件及算法配搭，需要迭代器必须内嵌5种型别：迭代器所指对象的类型、迭代器之间的距离类型、迭代器所指对象的指针类型、迭代器对象的引用类型、迭代器类型，如果没有内嵌这5个类型，那就不能和STL相容。

萃取对象的类型信息

如果说iterator_traits是用来存取迭代器的属性，那么__type_traits就是用来萃取对象(包括内置类型)的属性。理解了上面，这部分就非常简单了。

// 同样是两个空的类，作为tag，没有内存和效率上的损失
struct __true_type {};
struct __false_type {};
// 所有自定义类默认如下
template <class type>
struct __type_traits {
    typedef __true_type this_dummy_member_must_be_first;
    typedef __false_type has_trivial_default_constructor;
    typedef __false_type has_trivial_copy_contructor;
    typedef __false_type has_trivial_assignment_operator;
    typedef __false_type has_trivial_destructor;
    typedef __false_type is_POD_type;
};
// 所有内置类型默认如下，用偏特化实现，仅列出int型
struct __type_traits<int> {
    typedef __true_type has_trivial_default_constructor;
    typedef __true_type has_trivial_copy_contructor;
    typedef __true_type  has_trivial_assignment_operator;
    typedef __true_type has_trivial_destructor;
    typedef __true_type is_POD_type;
};