简介

迭代器在容器中扮演着重要角色。在使用算法的过程中，我们也需要用到迭代器。迭代器可以看作是smart pointer，它是标准库中定义的一个class type。

Iterator 定义

下面这段代码是标准库中对list_iterator的一个定义。

template<class T, class Ref, class Ptr>
struct __list_iterator{
    typedef bidirectional_iterator_tag iterator_category;
    typedef T value_type;
    typedef Ptr pointer;
    typedef Ref reference;
    typedef ptrdiff_t difference_type;
}

从定义中我们可以看到iterator内部有5种类型，而算法在在调用iterator过程中需要知道这5种类型是什么，然后才有接下来的操作。这时候就会出现一个问题，那么我们怎么区分普通的指针和iterator呢？普通指针也是可以用于标准算法的，例子如下：

1 2	vector<int> vec = { 1, 4, 8,10 }; auto m = find_if(vec.begin(), vec.end(), [](const int &a) {return a > 6; });

而对于iterator我们获取其中的5种类型方式是：

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

Iterator_traits是萃取机，用于获取不同迭代器或者指针对应的5种类型。这种方式对于普通指针肯定是不行的，下面就利用了partial template specialization 的方法。代码如下：

//partial specialization
template <class T>
struct iterator_traits(T*) {
    typedef T value_type;
}
template <class T>
struct iterator_traits(const T*) {
    typedef T value_type;
}

于是当我们需要知道指针或者Iterator的类型时就可以这样写：

//需要知道I的value type时可这么写:
template <typename I, ...>
void algorithm()
{
    typename iterator_traits<I>::value_type v1;
}

这里实际上是用了template的参数推导机制。根据变量I的类型来进行选择，这样就得到了相应的5种类型，使得普通指针也能用到我们的Algorithm中。

声明

若有错误，欢迎讨论。严禁抄袭，仅用于学习。