STL源码解析(3)-traits特性

算法和迭代器

• 在STL中绝大多数容器均提供了迭代器, 迭代器提供了访问/遍历容器中元素的手段

• 同时提供了如: sort、copy、find等针对于迭代器的函数, 对于不同迭代器提供了相同的接口

迭代器的问题?

• 1, 运算符问题, 例: 迭代器p1和p2, 能够进行如p2-p1的操作? vector的迭代器是可以的, list是不可以的

• 2, 原生指针问题, 接下来介绍

内嵌类型声明

• 迭代器很多时候是容器内部类型的指针, 或者提供了*运算符的重载; 如果需要返回迭代器所指向的类型, 那要怎么办呢?

template <class T>
struct MyIter {
    typedef T value_type;
    T * ptr;
    MyIter(T * p = 0) : ptr (p) {};
    T& operator* () const { return *ptr;}
};

template <class I>
typename I::value_type  func(I ite) {
    return *iter;
}

答案是: 内嵌类型声明, 内部通过typedef将类型保存了下来

原生指针问题

• 原生指针也是一种迭代器, 比如 vector; 那么对于原生指针应该怎么推导其返回类型呢?

template <class I>
typename I::value_type  func(I ite) {
    /* 函数 */
}

int main()
{
    char *str = NULL;
    func(str);
}

• 原生指针并不是一个类, 以上的代码当然是不可行的

iterator_traits

template <class _Iterator>
struct iterator_traits {
  typedef typename _Iterator::iterator_category iterator_category;  // 迭代器类别
  typedef typename _Iterator::value_type        value_type;         // 迭代器解除引用后所得到的值的类型
  typedef typename _Iterator::difference_type   difference_type;    // 两个迭代器之间的距离
  typedef typename _Iterator::pointer           pointer;            // 指向被迭代类型的指针
  typedef typename _Iterator::reference         reference;          // 被迭代类型的引用类型
};

• 定义在: stl_iterator_base.h中

• 以上就是iterator_traits的结构体, 下面先以deque的迭代器做一个示例

deque的迭代器

template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator {
    typedef _Deque_iterator<_Tp, _Tp&, _Tp*>             iterator;
    typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
    static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }

    typedef random_access_iterator_tag iterator_category;  // Random access iterator
    typedef _Tp value_type;
    typedef _Ptr pointer;
    typedef _Ref reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    typedef _Tp** _Map_pointer;

  ...

typedef _Deque_iterator<_Tp,_Tp&,_Tp*>             iterator;

• iterator_category: 迭代器的类型, 之后再进行介绍
• value_type: deque中存储的值的类型
• difference_type: 两个指针之间的距离, 直接使用ptrdiff_t即可
• pointer: 被迭代类型的指针
• referenc: 被迭代类型的引用

traits的实现原理

template <class _Iterator>
struct traits {
  typedef typename _Iterator::value_type        value_type;         // 迭代器解除引用后所得到的值的类型
};

template <>
struct traits<char*> {
  typedef char        value_type;         // 迭代器解除引用后所得到的值的类型
};

int main()
{
    printf("%d\n", sizeof(traits<deque<int>::iterator>::value_type));
    printf("%d\n", sizeof(traits<char*>::value_type));
}

//结果
4
1

• 如上代码, iterator_traits作为模板类接受各种迭代器: 然后指定value_type等等类型

• 额外的可以通过偏特化处理, 额外指定char*类型的类

• 以下是iterator_traits的完整实现, 额外对指针和const指针做了特殊的类实现

// traits 获取各个迭代器的特性(相应类型)-----类型特性类
template <class _Iterator>
struct iterator_traits {
  typedef typename _Iterator::iterator_category iterator_category; // 迭代器类别
  typedef typename _Iterator::value_type        value_type;  // 迭代器解除引用后所得到的值的类型
  typedef typename _Iterator::difference_type   difference_type; // 两个迭代器之间的距离
  typedef typename _Iterator::pointer           pointer;      // 指向被迭代类型的指针
  typedef typename _Iterator::reference         reference;   // 被迭代类型的引用类型
};

// 针对原生指针(native pointer)而设计的 traits 偏特化版
template <class _Tp>
struct iterator_traits<_Tp*> {
  typedef random_access_iterator_tag iterator_category;
  typedef _Tp                         value_type;
  typedef ptrdiff_t                   difference_type;  // C++ 内建的 ptrdiff_t 类型
  typedef _Tp*                        pointer;
  typedef _Tp&                        reference;
};

// 针对原生之 pointer-to-const 而设计的 traits 偏特化版
template <class _Tp>
struct iterator_traits<const _Tp*> {
  typedef random_access_iterator_tag iterator_category;
  typedef _Tp                         value_type;
  typedef ptrdiff_t                   difference_type;
  typedef const _Tp*                  pointer;
  typedef const _Tp&                  reference;
};

迭代器类别说明

1 所有迭代器均支持如下操作

p++                              后置自增迭代器
++p                              前置自增迭代器

2 输入迭代器: input_iterator_tag

*p                                  解引用
p=p1                                将一个迭代器赋给另一个迭代器
p==p1                               比较迭代器的相等性
p!=p1                               比较迭代器的不等性

3 输出迭代器: output_iterator_tag

*p                                 复引用迭代器，作为左值
p=p1                                将一个迭代器赋给另一个迭代器

4 正向迭代器: forward_iterator_tag

struct forward_iterator_tag : public input_iterator_tag {};  继承于输入迭代器

5 双向迭代器: bidirectional_iterator_tag

struct bidirectional_iterator_tag : public forward_iterator_tag {};         //继承于正向迭代器
--p                                前置自减迭代器
p--                                后置自减迭代器

6 随机迭代器: random_access_iterator_tag

struct random_access_iterator_tag : public bidirectional_iterator_tag {};   //继承于疏散共享迭代器
p+=i                             将迭代器递增i位
p-=i                             将迭代器递减i位
p+i                              在p位加i位后的迭代器
p-i                              在p位减i位后的迭代器
p[i]                             返回p位元素偏离i位的元素引用
p<p1                             如果迭代器p的位置在p1前，返回true，否则返回false
p<=p1                            p的位置在p1的前面或同一位置时返回true，否则返回false
p>p1                             如果迭代器p的位置在p1后，返回true，否则返回false
p>=p1                            p的位置在p1的后面或同一位置时返回true，否则返回false

vector/deque就是随机迭代器

结果

• 实现了traits<CLASS>::value_type这样的通用接口, 可以返回该迭代器关联的各种类型

type_traits

type traits的出现和STL对于性能的要求有着千丝万缕的联系; 比如对于vector来说, 如果存储的是POD类型那么直接使用mem族函数, 可以不用考虑析构问题等等

template <class _Tp>
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_constructor;            //拷贝构造函数是否有意义?  
   typedef __false_type    has_trivial_assignment_operator;         //拷贝赋值操作是否有意义?  
   typedef __false_type    has_trivial_destructor;                  //析构函数是否有意义?  
   typedef __false_type    is_POD_type;                             //是否是POD类型
};

__STL_TEMPLATE_NULL struct __type_traits<char> {
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};

__STL_TEMPLATE_NULL struct __type_traits<signed char> {
   typedef __true_type    has_trivial_default_constructor;
   typedef __true_type    has_trivial_copy_constructor;
   typedef __true_type    has_trivial_assignment_operator;
   typedef __true_type    has_trivial_destructor;
   typedef __true_type    is_POD_type;
};

• 举个栗子: 对于vector来说, 根据has_trivial_destructor就可以判断去掉无意义的析构函数

• 额外对一些基本的类型做了偏特化处理

实例

template <class _BidirectionalIter1, class _BidirectionalIter2, 
          class _Distance>
inline _BidirectionalIter2 __copy_backward(_BidirectionalIter1 __first, 
                                           _BidirectionalIter1 __last, 
                                           _BidirectionalIter2 __result,
                                           bidirectional_iterator_tag,
                                           _Distance*)
{
  while (__first != __last)
    *--__result = *--__last;
  return __result;
}

template <class _RandomAccessIter, class _BidirectionalIter, class _Distance>
inline _BidirectionalIter __copy_backward(_RandomAccessIter __first, 
                                          _RandomAccessIter __last, 
                                          _BidirectionalIter __result,
                                          random_access_iterator_tag,
                                          _Distance*)
{
  for (_Distance __n = __last - __first; __n > 0; --__n)
    *--__result = *--__last;
  return __result;
}

• 对于如上的算法而言, vector(_RandomAccessIter)可以采用第二种方式, 因为支持__last - __first

• 而对于list(_BidirectionalIter1), 则只能采用第一种方式, 链表不支持两个指针相减的运算