C++ STL中的 iterator_traits

一、基本概念

iterator_traits 是 C++ 标准库中的一个模板类，位于 <iterator> 头文件中。它的主要作用是为迭代器提供统一的接口，允许算法以一致的方式访问迭代器的相关类型信息，而不用关心迭代器的具体类型。

在 STL 标准库提供的算法一般有以下特征：

• 参数一般包括 iterator
• 要根据 iterator 的种类，和 iterator 包装的元素的类型等信息，来决定使用最优化的算法，例如：
  • 如果是 vector 的 iterator，那么就可以使用 +、- 操作；
  • 如果是 list 的 iterator，那么就不能使用 +、- 操作

所以算法必须知道一些关于 iterator 的信息。

有一些容器对应的 iterator 是个类，所以在这个类里，定义了如下的信息：

template<typename T>
struct __list_iterator { 
  typedef bidirectional_iterator_tag     iterator_category;
  typedef T                              value_type;
  typedef T*                             pointer;
  typedef T&                             reference;
  typedef ptrdiff_t                      difference_type;
};

有了上面定义的定义，算法就能够知道 iterator 的信息了，算法就可以正常工作了。到这里位置貌似跟 traits 没什么关系。

但是，vector、array 的 iterator 并不是类，而是 C++ 里内置的指针，当把内置指针当参数传递给算法后，算法无法获取 iterator 里定义的 iterator_category、value_type、difference_type 等信息，算法就无法工作。怎么办？

这时候就可以加一个中间层，也就是创建一个 iterator_traits 类，它包装了 iterator，并使用模板局部特化技术（见 C++ 模板），来解决上面的问题。

通过 traits 来提取类型信息，也就是说 iterator_traits 提供了一个统一的方式来获取这些信息，无论迭代器是指针还是类类型。

见下：

//使用iterator提供的信息
template<typename Iterator>
struct iterator_traits
{
  typedef typename Iterator::iterator_category iterator_category;
  typedef typename Iterator::value_type        value_typep;
  typedef typename Iterator::difference_type   difference_type;
  typedef typename Iterator::pointer           pointer;
  typedef typename Iterator::reference         reference;
};

//由于无法使用iterator的信息，所以traits自己提供了。
//局部特化，c++内置指针。
template<typename T>
struct iterator_traits<T *>
{
  // 特别注意：指针默认被认为是 random_access_iterator_tag
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

//由于无法使用iterator的信息，所以traits自己提供了。
//局部特化，c++内置指针。
template<typename T>
struct iterator_traits<const T *>
{
  typedef random_access_iterator_tag iterator_category;
  //注意这里不是const T;如果是const T，算法拿到这个类型，用这个类型定义变量后，却无法改变其值，那就没有作用了，所以是T。
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef const T*                   pointer;
  typedef const T&                   reference;
};

// 也可以写作下面的形式

template <typename T>
struct iterator_traits<T*> {
    using iterator_category = std::random_access_iterator_tag;
    using value_type        = T;
    using difference_type   = std::ptrdiff_t;
    using pointer           = T*;
    using reference         = T&;
};

template <typename T>
struct iterator_traits<const T*> {
    using iterator_category = std::random_access_iterator_tag;
    using value_type        = T; 
    using difference_type   = std::ptrdiff_t;
    using pointer           = const T*;
    using reference         = const T&;
};

算法向 iterator_traits 类要它需要的信息，iterator_traits 再向 iterator 要，如果要到了，就使用；如果没有要到就使用 iterator_traits 提供的。

类型成员含义如下：

• difference_type: 两个迭代器之间距离的类型（通常为ptrdiff_t）
• value_type: 迭代器指向的元素的类型
• pointer: 指向元素的指针类型
• reference: 元素的引用类型
• iterator_category: 迭代器类别标签(输入、输出、前向、双向、随机访问)

二、示例

见下例：list 类的 size 方法

size_type size() const {
  size_type result = 0;
  distance(begin(), end(), result);
  return result;
  //return distance(begin(), end());    
}

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 Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
  typedef typename iterator_traits<Iterator>::iterator_category category; //--①
  return category();
}

template <class InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n)
{
  __distance(first, last, n, iterator_category(first));
}

在 ①处，算法向 iterator_traits 要 iterator_category 的信息，如果 iterator 能提供，就使用 iterator 里的iterator_category，如果 iterator 不能提供，就使用 iterator_traits 里的 iterator_category。得到 iterator_category 后，就可以在编译阶段确定调用哪一个 __distance 方法了。

注意：是在编译阶段就可以确定，比在运行阶段确定调用哪个 __distance 方法的效率要高。

下面代码是没有 traits 技术，是在运行阶段才能确定调用哪个 __distance 方法。

template <class Iterator>
void distance(Iterator& i){
  if(is_random_access_iterator(i)){
    __distance1();
  }  
  if(is_bidirectional_iterator(i)){
    __distance2();
  }
}