stl中trait简介

咳咳，今天来说一下迭代器这个东西à iterator。

说实话，当初学stl的时候，就觉得这东西很神奇，很强大，但是又没有深入了解过这个东西，只是觉得这东西像个指针一样，但是又比指针好用。这次看完这这一章之后，对这个东西的理解又深刻了一点。

首先，iterator这个东西是为了将stl当中的容器与算法连接起来而出现的产物，具体开发工作由容器设计者来完成，大概如下：

这样做有两个好处：

1. 将容器的开发工作和算法的开发工作完全分离开来

2. 避免对外界暴露更多容器的实现细节

但是，这样做的话会有一个问题，当算法模板当中需要用到迭代器所指的对象的类型时，心里唱起了凉凉，哎，咋就这么惨呢？聪明的stl设计者们就设计了如下的思路来“萃取”出迭代器所指对象的类型和其他的一些特性，如下图和代码：

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

这里要说明一下iterator_category, 其设计原由就是：stl设计者为了程序执行效率考虑，为每一种容器都设计了不同的迭代器，例如：只允许++操作的forward_iterator，允许++和 --操作的bidirectional_iterator，允许++、--、和+n，-n操作的random_access_iterator。

有了迭代器所指的对象的类型，以及其自身得性质，就轮到stl中算法大显身手了，由于函数模板是可以自行推导出参数类型，进而进行函数调用的，所以，我们只需要在stl函数模板中实现函数重载就ok了，这里就要用到上面说的iterator_category了，具体代码如下：

//先声明一堆空的结构体来确定各个iterator的category：
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>
inline void __distance(InputIterator first, InputIterator last, Distance& n,
                       input_iterator_tag) {
  while (first != last) { ++first; ++n; }
}

template <class RandomAccessIterator, class Distance>
inline void __distance(RandomAccessIterator first, RandomAccessIterator last,
                       Distance& n, random_access_iterator_tag) {
  n += last - first;
}
//甩给外界的接口就是：
template <class InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n) {
  __distance(first, last, n, iterator_category(first));
}

当外界调用distance函数的时候，首先会根据输入的iterator类型，选区不同的category，进而调用不同的内嵌函数模板，这样就完成了之前所说的~~