STL源码剖析——迭代器

梦里梦外; 2022-08-12 01:13 194阅读 0赞

## 前言 ##

在STL的思想中，容器和算法是彼此独立设计的，再通过某种方式使它们连接；而迭代器是使算法独立于使用的容器类型，即迭代器是连接算法和容器的方法。由于迭代器是一种行为类似指针的对象，也就说迭代器是一种广义指针，即迭代器对解除引用操作（operator\*）和访问成员操作（operator->）进行重载。然而要对这两个操作符进行重载，对容器内部对象的数据类型和存储结构有所了解，于是在 STL 中迭代器的最终实现都是由容器本身来实现的，每种容器都有自己的迭代器实现。本文介绍的不是针对某种特定的容器。在迭代器的设计中，一个最重要的编程技巧那就是Traits技术了，有关[《Traits编程技术》][Traits]在前面博文中已经介绍了。

## 迭代器 ##

### 迭代器的分类 ###

在SGI STL中根据读写和访问方式，在源码中迭代器大致可分为五类：

1.  输入迭代器input\_iterator：只读，且只能一次读操作，支持操作：\++p,p++,!=,==,=\*p,p->；
2.  输出迭代器output\_iterator：只写，且只能一次写操作，支持操作：\++p,p++；
3.  正向迭代器forward\_iterator：可多次读写，支持输入输出迭代器的所有操作；
4.  双向迭代器bidirectional\_iterator：支持正向迭代器的所有操作，且支持操作：\--p,--p；
5.  随机访问迭代器random\_access\_iterator：除了支持双向迭代器操作外，还支持：p\[n\],p+n,n+p,p-n,p+=n,p-=n,p1-p2,p1<p2,p1>p2,p1>=p2,p1<=p2；

/*This program is in the file of stl_iterator_base.h form line 42 to 92*/
    //迭代器类型标签
    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 _Tp, class _Distance> struct input_iterator {
      typedef input_iterator_tag iterator_category;
      typedef _Tp                value_type;
      typedef _Distance          difference_type;
      typedef _Tp*               pointer;
      typedef _Tp&               reference;
    };
    
    struct output_iterator {
      typedef output_iterator_tag iterator_category;
      typedef void                value_type;
      typedef void                difference_type;
      typedef void                pointer;
      typedef void                reference;
    };
    
    template <class _Tp, class _Distance> struct forward_iterator {
      typedef forward_iterator_tag iterator_category;
      typedef _Tp                  value_type;
      typedef _Distance            difference_type;
      typedef _Tp*                 pointer;
      typedef _Tp&                 reference;
    };
    
    
    template <class _Tp, class _Distance> struct bidirectional_iterator {
      typedef bidirectional_iterator_tag iterator_category;
      typedef _Tp                        value_type;
      typedef _Distance                  difference_type;
      typedef _Tp*                       pointer;
      typedef _Tp&                       reference;
    };
    
    template <class _Tp, class _Distance> struct random_access_iterator {
      typedef random_access_iterator_tag iterator_category;
      typedef _Tp                        value_type;
      typedef _Distance                  difference_type;
      typedef _Tp*                       pointer;
      typedef _Tp&                       reference;
    };

### 迭代器的型别与traits技巧 ###

在STL的算法设计中需要迭代器的型别，根据不同要求和不同型别，有不同的技巧解决；如：使用模板参数推导机制推导出局部变量类型；内嵌型别求出返回值类型；traits技术解决返回值类型和偏特化traits技术解决原生指针问题；这些都在前面博文[《Traits编程技术》][Traits]介绍。迭代器的型别如下代码所示：

template <class _Iterator>
    /*Traits技术，萃取出类型的相关信息*/
    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;//引用
    };

通过 Traits技术 我们可以获得迭代器的相关类型的信息iterator\_traits<…>::…，下面给出Traits技术的相关源码：

/*为用户自行开发的迭代器提供方便，用户自行开发的迭代器最后继承该iterator class，以便使用Traits技术*/
    template <class _Category, class _Tp, class _Distance = ptrdiff_t,
              class _Pointer = _Tp*, class _Reference = _Tp&>
    struct iterator {
      typedef _Category  iterator_category;
      typedef _Tp        value_type;
      typedef _Distance  difference_type;
      typedef _Pointer   pointer;
      typedef _Reference reference;
    };
    #endif /* __STL_USE_NAMESPACES */
    
    #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    
    template <class _Iterator>
    /*Traits技术，萃取出类型的相关信息*/
    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;
    };
    
    template <class _Tp>
    /*针对原生指针Tp*生成的Traits偏特化版本*/
    struct iterator_traits<_Tp*> {
      typedef random_access_iterator_tag iterator_category;
      typedef _Tp                         value_type;
      typedef ptrdiff_t                   difference_type;
      typedef _Tp*                        pointer;
      typedef _Tp&                        reference;
    };
    
    template <class _Tp>
    /*针对原生指针const Tp*生成的Traits偏特化版本*/
    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;
    };

在迭代器中，为了能够在编译时确定函数调用，应用了函数重载。因为五种迭代器操作能力是不同的，例如random acess iterator是操作能力最强的，可以在O(1)时间操作指定位置，而这个用其他的迭代器可能需要O(n)。所以为了提高效率，使用迭代器类型最匹配的算法函数去调用：

1.  首先通过traits技术获得迭代器类型iterator\_category；
2.  在函数调用时生成相应迭代器类型的临时对象作为实参传递，编译器就会调用相应的重载函数。

为了重载函数识别， SGI STL 有对应的 5 种迭代器标识类：继承是为了可以使用传递调用，当不存在某种迭代器类型匹配时编译器会依据继承层次向上查找进行传递。

/*五中迭代器类型*/
    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 {};

例如下面是 advance() 函数的调用，针对不同的迭代器类型，对函数进行重载：

/*函数重载，使迭代器能在编译时期就确定调用哪个函数*/
    template <class _InputIter, class _Distance>
    /*迭代器类型为input_iterator_tag的函数定义*/
    inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) {
      while (__n--) ++__i;
    }
    
    
    template <class _BidirectionalIterator, class _Distance>
    /*迭代器类型为bidirectional_iterator_tag的函数定义*/
    inline void __advance(_BidirectionalIterator& __i, _Distance __n, 
                          bidirectional_iterator_tag) {
      __STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator);
      if (__n >= 0)
        while (__n--) ++__i;
      else
        while (__n++) --__i;
    }
    
    
    template <class _RandomAccessIterator, class _Distance>
    /*迭代器类型为random_access_iterator_tag的函数定义*/
    inline void __advance(_RandomAccessIterator& __i, _Distance __n, 
                          random_access_iterator_tag) {
      __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
      __i += __n;
    }
    
    template <class _InputIterator, class _Distance>
    /*决定调用哪个函数，这是一个对外接口*/
    inline void advance(_InputIterator& __i, _Distance __n) {
      __STL_REQUIRES(_InputIterator, _InputIterator);
      __advance(__i, __n, iterator_category(__i));
    }

### SGI STL迭代器完整源码剖析 ###

以下对整个源码进行剖析，给出相应的注释：

#ifndef __SGI_STL_INTERNAL_ITERATOR_BASE_H
    #define __SGI_STL_INTERNAL_ITERATOR_BASE_H
    
    // This file contains all of the general iterator-related utilities.
    // The internal file stl_iterator.h contains predefined iterators, 
    // such as front_insert_iterator and istream_iterator.
    
    #include <concept_checks.h>
    
    __STL_BEGIN_NAMESPACE
    /*五中迭代器类型*/
    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 {};
    
    // The base classes input_iterator, output_iterator, forward_iterator,
    // bidirectional_iterator, and random_access_iterator are not part of
    // the C++ standard.  (They have been replaced by struct iterator.)
    // They are included for backward compatibility with the HP STL.
    
    /*五中迭代器类型的结构*/
    template <class _Tp, class _Distance> struct input_iterator {
      typedef input_iterator_tag iterator_category;
      typedef _Tp                value_type;
      typedef _Distance          difference_type;
      typedef _Tp*               pointer;
      typedef _Tp&               reference;
    };
    
    struct output_iterator {
      typedef output_iterator_tag iterator_category;
      typedef void                value_type;
      typedef void                difference_type;
      typedef void                pointer;
      typedef void                reference;
    };
    
    template <class _Tp, class _Distance> struct forward_iterator {
      typedef forward_iterator_tag iterator_category;
      typedef _Tp                  value_type;
      typedef _Distance            difference_type;
      typedef _Tp*                 pointer;
      typedef _Tp&                 reference;
    };
    
    
    template <class _Tp, class _Distance> struct bidirectional_iterator {
      typedef bidirectional_iterator_tag iterator_category;
      typedef _Tp                        value_type;
      typedef _Distance                  difference_type;
      typedef _Tp*                       pointer;
      typedef _Tp&                       reference;
    };
    
    template <class _Tp, class _Distance> struct random_access_iterator {
      typedef random_access_iterator_tag iterator_category;
      typedef _Tp                        value_type;
      typedef _Distance                  difference_type;
      typedef _Tp*                       pointer;
      typedef _Tp&                       reference;
    };
    
    #ifdef __STL_USE_NAMESPACES
    
    /*为用户自行开发的迭代器提供方便，用户自行开发的迭代器最后继承该iterator class，以便使用Traits技术*/
    template <class _Category, class _Tp, class _Distance = ptrdiff_t,
              class _Pointer = _Tp*, class _Reference = _Tp&>
    struct iterator {
      typedef _Category  iterator_category;
      typedef _Tp        value_type;
      typedef _Distance  difference_type;
      typedef _Pointer   pointer;
      typedef _Reference reference;
    };
    #endif /* __STL_USE_NAMESPACES */
    
    #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    
    template <class _Iterator>
    /*Traits技术，萃取出类型的相关信息*/
    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;
    };
    
    template <class _Tp>
    /*针对原生指针Tp*生成的Traits偏特化版本*/
    struct iterator_traits<_Tp*> {
      typedef random_access_iterator_tag iterator_category;
      typedef _Tp                         value_type;
      typedef ptrdiff_t                   difference_type;
      typedef _Tp*                        pointer;
      typedef _Tp&                        reference;
    };
    
    template <class _Tp>
    /*针对原生指针const Tp*生成的Traits偏特化版本*/
    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;
    };
    
    // The overloaded functions iterator_category, distance_type, and
    // value_type are not part of the C++ standard.  (They have been
    // replaced by struct iterator_traits.)  They are included for
    // backward compatibility with the HP STL.
    
    // We introduce internal names for these functions.
    
    template <class _Iter>
    /*求出迭代器的类型*/
    inline typename iterator_traits<_Iter>::iterator_category
    __iterator_category(const _Iter&)
    {
      typedef typename iterator_traits<_Iter>::iterator_category _Category;
      return _Category();
    }
    
    template <class _Iter>
    /*求出迭代器的distance_type*/
    inline typename iterator_traits<_Iter>::difference_type*
    __distance_type(const _Iter&)
    {
      return static_cast<typename iterator_traits<_Iter>::difference_type*>(0);
    }
    
    template <class _Iter>
    /*求出迭代器的value_type*/
    inline typename iterator_traits<_Iter>::value_type*
    __value_type(const _Iter&)
    {
      return static_cast<typename iterator_traits<_Iter>::value_type*>(0);
    }
    
    template <class _Iter>
    /*根据迭代器的类型标签求出迭代器类型*/
    inline typename iterator_traits<_Iter>::iterator_category
    iterator_category(const _Iter& __i) { return __iterator_category(__i); }
    
    
    template <class _Iter>
    inline typename iterator_traits<_Iter>::difference_type*
    distance_type(const _Iter& __i) { return __distance_type(__i); }
    
    template <class _Iter>
    inline typename iterator_traits<_Iter>::value_type*
    value_type(const _Iter& __i) { return __value_type(__i); }
    
    #define __ITERATOR_CATEGORY(__i) __iterator_category(__i)
    #define __DISTANCE_TYPE(__i)     __distance_type(__i)
    #define __VALUE_TYPE(__i)        __value_type(__i)
    
    #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    /*以下是求出偏特化版本的迭代器的各种类型*/
    template <class _Tp, class _Distance> 
    inline input_iterator_tag 
    iterator_category(const input_iterator<_Tp, _Distance>&)
      { return input_iterator_tag(); }
    
    inline output_iterator_tag iterator_category(const output_iterator&)
      { return output_iterator_tag(); }
    
    template <class _Tp, class _Distance> 
    inline forward_iterator_tag
    iterator_category(const forward_iterator<_Tp, _Distance>&)
      { return forward_iterator_tag(); }
    
    template <class _Tp, class _Distance> 
    inline bidirectional_iterator_tag
    iterator_category(const bidirectional_iterator<_Tp, _Distance>&)
      { return bidirectional_iterator_tag(); }
    
    template <class _Tp, class _Distance> 
    inline random_access_iterator_tag
    iterator_category(const random_access_iterator<_Tp, _Distance>&)
      { return random_access_iterator_tag(); }
    
    template <class _Tp>
    inline random_access_iterator_tag iterator_category(const _Tp*)
      { return random_access_iterator_tag(); }
    
    template <class _Tp, class _Distance> 
    inline _Tp* value_type(const input_iterator<_Tp, _Distance>&)
      { return (_Tp*)(0); }
    
    template <class _Tp, class _Distance> 
    inline _Tp* value_type(const forward_iterator<_Tp, _Distance>&)
      { return (_Tp*)(0); }
    
    template <class _Tp, class _Distance> 
    inline _Tp* value_type(const bidirectional_iterator<_Tp, _Distance>&)
      { return (_Tp*)(0); }
    
    template <class _Tp, class _Distance> 
    inline _Tp* value_type(const random_access_iterator<_Tp, _Distance>&)
      { return (_Tp*)(0); }
    
    template <class _Tp>
    inline _Tp* value_type(const _Tp*) { return (_Tp*)(0); }
    
    template <class _Tp, class _Distance> 
    inline _Distance* distance_type(const input_iterator<_Tp, _Distance>&)
    {
      return (_Distance*)(0);
    }
    
    template <class _Tp, class _Distance> 
    inline _Distance* distance_type(const forward_iterator<_Tp, _Distance>&)
    {
      return (_Distance*)(0);
    }
    
    template <class _Tp, class _Distance> 
    inline _Distance* 
    distance_type(const bidirectional_iterator<_Tp, _Distance>&)
    {
      return (_Distance*)(0);
    }
    
    template <class _Tp, class _Distance> 
    inline _Distance* 
    distance_type(const random_access_iterator<_Tp, _Distance>&)
    {
      return (_Distance*)(0);
    }
    
    template <class _Tp>
    inline ptrdiff_t* distance_type(const _Tp*) { return (ptrdiff_t*)(0); }
    
    // Without partial specialization we can't use iterator_traits, so
    // we must keep the old iterator query functions around.  
    
    #define __ITERATOR_CATEGORY(__i) iterator_category(__i)
    #define __DISTANCE_TYPE(__i)     distance_type(__i)
    #define __VALUE_TYPE(__i)        value_type(__i)
    
    #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    
    
    /*
    *这是distance()函数，求出两个迭代器之间的距离，为了在编译期间确定调用的函数，
    *这里针对不同迭代器的类型进行的函数重载；
    */
    template <class _InputIterator, class _Distance>
    /*迭代器为input_iterator_tag的distance()函数版本*/
    inline void __distance(_InputIterator __first, _InputIterator __last,
                           _Distance& __n, input_iterator_tag)
    {
      while (__first != __last) { ++__first; ++__n; }
    }
    
    template <class _RandomAccessIterator, class _Distance>
    /*迭代器为random_access_iterator_tag的distance()函数版本*/
    inline void __distance(_RandomAccessIterator __first, 
                           _RandomAccessIterator __last, 
                           _Distance& __n, random_access_iterator_tag)
    {
      __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
      __n += __last - __first;
    }
    
    template <class _InputIterator, class _Distance>
    /*对外接口的distance()函数*/
    inline void distance(_InputIterator __first, 
                         _InputIterator __last, _Distance& __n)
    {
      __STL_REQUIRES(_InputIterator, _InputIterator);
      __distance(__first, __last, __n, iterator_category(__first));
    }
    
    #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    /*以下是偏特化版本的distance()函数*/
    template <class _InputIterator>
    inline typename iterator_traits<_InputIterator>::difference_type
    __distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
    {
      typename iterator_traits<_InputIterator>::difference_type __n = 0;
      while (__first != __last) {
        ++__first; ++__n;
      }
      return __n;
    }
    
    template <class _RandomAccessIterator>
    inline typename iterator_traits<_RandomAccessIterator>::difference_type
    __distance(_RandomAccessIterator __first, _RandomAccessIterator __last,
               random_access_iterator_tag) {
      __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
      return __last - __first;
    }
    
    template <class _InputIterator>
    inline typename iterator_traits<_InputIterator>::difference_type
    distance(_InputIterator __first, _InputIterator __last) {
      typedef typename iterator_traits<_InputIterator>::iterator_category 
        _Category;
      __STL_REQUIRES(_InputIterator, _InputIterator);
      return __distance(__first, __last, _Category());
    }
    
    #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    
    /*对advance()进行重载，重载的作用是为了迭代器在编译时期就能确定调用哪种类型迭代器的函数*/
    template <class _InputIter, class _Distance>
    /*迭代器类型为input_iterator_tag的函数定义*/
    inline void __advance(_InputIter& __i, _Distance __n, input_iterator_tag) {
      while (__n--) ++__i;
    }
    
    #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    #pragma set woff 1183
    #endif
    
    template <class _BidirectionalIterator, class _Distance>
    /*迭代器类型为bidirectional_iterator_tag的函数定义*/
    inline void __advance(_BidirectionalIterator& __i, _Distance __n, 
                          bidirectional_iterator_tag) {
      __STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator);
      if (__n >= 0)
        while (__n--) ++__i;
      else
        while (__n++) --__i;
    }
    
    #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
    #pragma reset woff 1183
    #endif
    
    template <class _RandomAccessIterator, class _Distance>
    /*迭代器类型为random_access_iterator_tag的函数定义*/
    inline void __advance(_RandomAccessIterator& __i, _Distance __n, 
                          random_access_iterator_tag) {
      __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
      __i += __n;
    }
    
    template <class _InputIterator, class _Distance>
    /*决定调用哪个函数，这是一个对外接口*/
    inline void advance(_InputIterator& __i, _Distance __n) {
      __STL_REQUIRES(_InputIterator, _InputIterator);
      __advance(__i, __n, iterator_category(__i));
    }
    
    __STL_END_NAMESPACE
    
    #endif /* __SGI_STL_INTERNAL_ITERATOR_BASE_H */
    
    
    
    // Local Variables:
    // mode:C++
    // End:

### SGI STL的\_\_type\_traits技术 ###

前面介绍的Traits技术在STL中弥补了C++模板的不足，但是在STL中，Traits技术只是用来规范迭代器，对于迭代器之外的东西没有加以规范。因此，SGI将该技术扩展到迭代器之外的东西，称为\_\_type\_traits。iterator\_traits是萃取迭代器的特性，而\_\_type\_traits是萃取型别的特性。萃取的型别如下：

1.  是否具备non-trivial default ctor?
2.  是否具备non-trivial copy ctor?
3.  是否具备non-trivial assignment operator?
4.  是否具备non-trivial dtor?
5.  是否为POD（plain old data）型别？

其中non-trivial意指非默认的相应函数，编译器会为每个类构造以上四种默认的函数，如果没有定义自己的，就会用编译器默认函数，如果使用默认的函数，我们可以使用memcpy(),memmove(),malloc()等函数来加快速度，提高效率。  
 定义在SGI<type\_traits.h>中\_\_type\_traits，提供了一种机制，针对不同型别的特性，在编译时期完成函数派送决定。

template <class _Tp>
    struct __type_traits { 
       typedef __true_type     this_dummy_member_must_be_first;
                       /* Do not remove this member. It informs a compiler which
                          automatically specializes __type_traits that this
                          __type_traits template is special. It just makes sure that
                          things work if an implementation is using a template
                          called __type_traits for something unrelated. */
    
       /* The following restrictions should be observed for the sake of
          compilers which automatically produce type specific specializations 
          of this class:
              - You may reorder the members below if you wish
              - You may remove any of the members below if you wish
              - You must not rename members without making the corresponding
                name change in the compiler
              - Members you add will be treated like regular members unless
                you add the appropriate support in the compiler. */
     
    
       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;
    };

其中返回真假的“对象”是：

struct __true_type {
    };
    
    struct __false_type {
    };

将 bool, char, short, int, long, float, double 等基本的数据类型及其相应的指针类型的这些特性都定义为\_\_true\_type，这意味着，这些对基本类型进行构造、析构、拷贝、赋值等操作时，都是使用系统函数进行的。而除了这些类型之外的其他类型，除非用户指定了它的这些特性为 \_\_true\_type ，默认都是  \_\_false\_type  的，不能直接调用系统函数来进行内存配置或赋值等，而需要调用该类型的构造函数、拷贝构造函数等。下面是整个 \_\_type\_traits 源码剖析：

#ifndef __TYPE_TRAITS_H
    #define __TYPE_TRAITS_H
    
    #ifndef __STL_CONFIG_H
    #include <stl_config.h>
    #endif
    
    /*
    This header file provides a framework for allowing compile time dispatch
    based on type attributes. This is useful when writing template code.
    For example, when making a copy of an array of an unknown type, it helps
    to know if the type has a trivial copy constructor or not, to help decide
    if a memcpy can be used.
    
    The class template __type_traits provides a series of typedefs each of
    which is either __true_type or __false_type. The argument to
    __type_traits can be any type. The typedefs within this template will
    attain their correct values by one of these means:
        1. The general instantiation contain conservative values which work
           for all types.
        2. Specializations may be declared to make distinctions between types.
        3. Some compilers (such as the Silicon Graphics N32 and N64 compilers)
           will automatically provide the appropriate specializations for all
           types.
    
    EXAMPLE:
    
    //Copy an array of elements which have non-trivial copy constructors
    template <class T> void copy(T* source, T* destination, int n, __false_type);
    //Copy an array of elements which have trivial copy constructors. Use memcpy.
    template <class T> void copy(T* source, T* destination, int n, __true_type);
    
    //Copy an array of any type by using the most efficient copy mechanism
    template <class T> inline void copy(T* source,T* destination,int n) {
       copy(source, destination, n,
            typename __type_traits<T>::has_trivial_copy_constructor());
    }
    */
    
    /*定义两个返回对象*/
    struct __true_type {
    };
    
    struct __false_type {
    };
    
    template <class _Tp>
    /*该结构能够满足返回值只有__true_type或者__false_type*/
    struct __type_traits { 
       typedef __true_type     this_dummy_member_must_be_first;
                       /* Do not remove this member. It informs a compiler which
                          automatically specializes __type_traits that this
                          __type_traits template is special. It just makes sure that
                          things work if an implementation is using a template
                          called __type_traits for something unrelated. */
    
       /* The following restrictions should be observed for the sake of
          compilers which automatically produce type specific specializations 
          of this class:
              - You may reorder the members below if you wish
              - You may remove any of the members below if you wish
              - You must not rename members without making the corresponding
                name change in the compiler
              - Members you add will be treated like regular members unless
                you add the appropriate support in the compiler. */
     
    
       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;
    };
    
    
    
    // Provide some specializations.  This is harmless for compilers that
    //  have built-in __types_traits support, and essential for compilers
    //  that don't.
    /*下面是针对特定类型的type_traits技术，例如：bool,char,short,int,long,float,double*/
    #ifndef __STL_NO_BOOL
    
    __STL_TEMPLATE_NULL struct __type_traits<bool> {
       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;
    };
    
    #endif /* __STL_NO_BOOL */
    
    __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;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<unsigned 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;
    };
    
    #ifdef __STL_HAS_WCHAR_T
    
    __STL_TEMPLATE_NULL struct __type_traits<wchar_t> {
       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;
    };
    
    #endif /* __STL_HAS_WCHAR_T */
    
    __STL_TEMPLATE_NULL struct __type_traits<short> {
       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<unsigned short> {
       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<int> {
       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<unsigned int> {
       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<long> {
       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<unsigned long> {
       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;
    };
    
    #ifdef __STL_LONG_LONG
    
    __STL_TEMPLATE_NULL struct __type_traits<long long> {
       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<unsigned long long> {
       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;
    };
    
    #endif /* __STL_LONG_LONG */
    
    __STL_TEMPLATE_NULL struct __type_traits<float> {
       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<double> {
       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<long double> {
       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;
    };
    
    #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
    /*以下是一个针对原生指针的偏特化版本*/
    template <class _Tp>
    struct __type_traits<_Tp*> {
       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;
    };
    
    #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    
    __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;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<unsigned 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<const 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<const 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;
    };
    
    __STL_TEMPLATE_NULL struct __type_traits<const unsigned 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;
    };
    
    #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
    
    
    // The following could be written in terms of numeric_limits.  
    // We're doing it separately to reduce the number of dependencies.
    
    template <class _Tp> struct _Is_integer {
      typedef __false_type _Integral;
    };
    
    #ifndef __STL_NO_BOOL
    
    __STL_TEMPLATE_NULL struct _Is_integer<bool> {
      typedef __true_type _Integral;
    };
    
    #endif /* __STL_NO_BOOL */
    
    __STL_TEMPLATE_NULL struct _Is_integer<char> {
      typedef __true_type _Integral;
    };
    
    __STL_TEMPLATE_NULL struct _Is_integer<signed char> {
      typedef __true_type _Integral;
    };
    
    __STL_TEMPLATE_NULL struct _Is_integer<unsigned char> {
      typedef __true_type _Integral;
    };
    
    #ifdef __STL_HAS_WCHAR_T
    
    __STL_TEMPLATE_NULL struct _Is_integer<wchar_t> {
      typedef __true_type _Integral;
    };
    
    #endif /* __STL_HAS_WCHAR_T */
    
    __STL_TEMPLATE_NULL struct _Is_integer<short> {
      typedef __true_type _Integral;
    };
    
    __STL_TEMPLATE_NULL struct _Is_integer<unsigned short> {
      typedef __true_type _Integral;
    };
    
    __STL_TEMPLATE_NULL struct _Is_integer<int> {
      typedef __true_type _Integral;
    };
    
    __STL_TEMPLATE_NULL struct _Is_integer<unsigned int> {
      typedef __true_type _Integral;
    };
    
    __STL_TEMPLATE_NULL struct _Is_integer<long> {
      typedef __true_type _Integral;
    };
    
    __STL_TEMPLATE_NULL struct _Is_integer<unsigned long> {
      typedef __true_type _Integral;
    };
    
    #ifdef __STL_LONG_LONG
    
    __STL_TEMPLATE_NULL struct _Is_integer<long long> {
      typedef __true_type _Integral;
    };
    
    __STL_TEMPLATE_NULL struct _Is_integer<unsigned long long> {
      typedef __true_type _Integral;
    };
    
    #endif /* __STL_LONG_LONG */
    
    #endif /* __TYPE_TRAITS_H */
    
    // Local Variables:
    // mode:C++
    // End:

## 总结 ##

1.  Traits编程技法对迭代器加以规范，获得了对象的类型相关信息，从而使得算法可以通过类型信息来优化效率。
2.  使用重载函数来解决if-else条件在编译时期和运行时期的不同步，使其能在编译时期确认调用哪个函数。
3.  SGI对traits进行扩展，使得所有类型都满足traits编程规范，这样SGI STL算法可以通过\_\_type\_traits获取类型信息后。

参考文献：

[【1】][1]，[【2】][2]，[【3】][3]

[Traits]: http://blog.csdn.net/chenhanzhun/article/details/39230529
[1]: http://www.cnblogs.com/HappyAngel/archive/2011/04/19/2021413.html
[2]: http://ibillxia.github.io/blog/2014/06/21/stl-source-insight-2-iterators-and-traits/
[3]: http://www.xuebuyuan.com/1591997.html