为什么标准库里要有traits？

我们先回忆一下，标准库提供的算法的一些特征：

参数一般包括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，并使用模板局部特化技术，来解决上面的问题。

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 *>

{

  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;

  typedef T                          value_type;//注意这里不是const T;如果是const T，算法拿到这个类型，用这个类型定义变量后，却无法改变其值，那就没有作用了，所以是T。

  typedef ptrdiff_t                  difference_type;

  typedef const T*                   pointer;

  typedef const T&                   reference;

};

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

算法举例：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方法的效率要高。

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

template <class Iterator>

void distance(Iterator& i){

  if(is_random_access_iterator(i)){

    __distance1();

  }

  if(is_bidirectional_iterator(i)){

    __distance2();

  }

}

标准库的iterator_traits类，定义在stl_iterator.h文件里。

巴特西

stl标准库 iterator_traits

为什么标准库里要有traits？

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

c/c++ 学习互助QQ群：877684253

本人微信：xiaoshitou5854

最新文章

热门文章