迭代器

迭代器 (iterators) 提供一种方法，使其能够按照某种方式、某种顺序依次访问某个容器 (集合) 中的各个元素，并且对调用者隐藏容器 (集合) 的内部实现。

关联类型

迭代器要成为算法与容器之间通用的桥梁，必须要定义关联类型 (associated types)。关联类型就像一组规则，它定义了特定迭代器的底层特性。譬如迭代器所指元素的指针类型、引用类型、值类型与距离类型等。这样使用迭代器完成某种算法时，就能轻易地使用关联类型来定义与迭代器所指的元素同一类型的变量。STL 中的 iterator (其他的迭代器都基本上继承于它) 的定义如下。

/* stl_iterator_base.h : 95 */
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;
};

如上面的代码所示，其中定义了 5 个类型别名，iterator_category、value_type、difference_type、pointer、reference 就是最常用的 5 个关联类型。

当需要定义与某个迭代器相关的关联类型的变量，那么就可以实现用法的统一，而让使用者无需关心迭代器所指向的、具体的底层类型。

此处，我们假设有一个名叫 list 的容器类，类中定义了 iterator 类模板作为迭代器。现在有一个迭代器对象 it 经过一些算法迭代后 ，我们想直接获取 it 所指向的元素的值，并把它传递给我们定义的新变量 n。那么定义这个新变量 n 时，就可以直接使用：

typename list<int>::iterator::value_type n = *it; 

同样地，如果定义一个指针 p，并获取这迭代器 it 所指向元素的地址，同样也可以直接使用：

typename list<int>::iterator::pointer p = it;

所以关联类型就是对某个需要与迭代器操作相关的变量的类型进行统一化处理，这样就可以隐藏迭代器所指向元素的类型特性，用户不需要自我判断并编写元素类型相关的代码。

value_type

顾名思义，value_type指的是迭代器所指对象的类型，任何打算与 STL 算法完美搭配的迭代器类，都应当定义自己的 value_type 内嵌类型。

difference_type

difference_type用来表示两个迭代器之间的距离，因此它也可以用来表示一个容器的最大容量 (对于连续空间的容器而言，首尾的距离就是其最大容量)

reference

reference 表示迭代器所指对象的左值引用类型，当需要取出这个对象的左值，并对其进行相关操作时，可以用此类型来定义所指对象相关的引用。

pointer

pointer 表示迭代器所指对象所对应的指针类型，当需要取得这个对象的地址，并对其进行相关操作时，可以用此类型来定义指向该对象的指针。

iterator_category

顾名思义，这表示迭代器的分类。一般来说，按照行为特性划分，SGI STL 中迭代器被分为 5 类。

• 输入迭代器 (Input Iterator): 迭代器所指的对象不允许外部去改变。即只读 (read-only)。
• 输出迭代器 (Output Iterator): 只写 (write only)。
• 向前迭代器 (Forward Iterator): 允许 “写入型” 算法 (例如 replace()) 在此种迭代器所形成的区间上进行读写操作。
• 双向迭代器 (Bidirectional Iterator): 可双向移动，某些算法需要逆向地访问某个迭代器的区间 (例如逆向拷贝某范围内的元素)，可使用此迭代器。
• 随机访问迭代器 (Random Access Iterator): 可随机 (意) 访问迭代器区间中任意的元素。

通俗地说，输入迭代器、输出迭代器与向前迭代器均是只供应一种指针运算，即 operator++。双向迭代器除了 operator++ 之外还供应了 operator--运算。随机访问迭代器除了提供这两种运算符之外，还涵盖了几乎所有的指针运算，也就是原生指针能做到的所有操作。

这些迭代器的分类存在概念 (concept) 与强化 (refinement) 的关系，如图所示。

注意这并不是 (至少不完全是) 类的继承关系

若一个算法可接受一个向前迭代器，我们将一个随机访问迭代器交给它，那么它也是能够接受的，因为算法将用到 operator+ 运算符，随机访问迭代器也有这种能力，同样可以执行 operator+。只不过算法接受比随机访问迭代器更加强化 (refinement) 的向前迭代器，如果非要使用随机访问迭代器也是可以的，即便这并不是最佳用法，以至于它可能会造成效率问题。

我们使用算法内部常用的一个函数 advance()来说明上面提到的迭代器分类相关的效率问题。advance() 函数有两个参数，迭代器 i 与数值 n 。函数内部将迭代器 i 前进 n 距离。下面有三个定义，分别针对输入迭代器、双向迭代器与随机访问迭代器。

template <class InputIterator, class Distance>
void advance_II(InputIterator &i, Distance n) {
    while (n--) ++i; // 逐次前进
}

template <class BidirectionalIterator, class Distance>
void advance_BI(BidirectionalIterator &i, Distance n) {
    // 区分方向，逐次前进
    if (n >= 0)
        while (n--) ++i;
    else
        while (n++) --i;
}

template <class RandomAccessIterator, class Distance>
void advance_RAI(RandomAccessIterator &i, Distance n) {
    i += n;   // 随机访问，就直接累加，按照正负方向前进就行
}

如果我们使用的是随机访问迭代器，选择使用 advance_RAI 进行操作，时间复杂度为 O(1) ，但是使用 advance_II 进行操作，时间复杂度将飙升到 O(n)。可是当我们选择效率更高的 advance_RAI 函数，它却无法兼容输入迭代器、向前迭代器以及双向迭代器。

如果在程序执行时刻，来判断迭代器的分类，并转发到对应的各个函数中，那么就解决了该问题。

template <class InputIterator, class Distance>
void advance(InputIterator &i, Distance n) {
    if (is_random_access_iterator(i))  // 通过某种形式，进行判断
        advance_RAI(i, n);
    else if (is_bidirectional_iterator(i)) // 通过某种形式，进行判断
        advance_BI(i, n);
    /* ... 此处省略 ... */
}

但是这样在程序执行时刻才决定使用哪个版本的函数，将影响程序执行效率。我们最好能在编译时刻就将函数版本确定下来。这时候，就可以通过给函数加上第三个参数，来标识迭代器的分类 (category)，这样利用函数重载特性完成这个任务。

并且这个参数一定是一个类类型 (class type)，别忘了，我们要利用重载特性，让编译做出重载决议 (overloaded resolution)。下面定义的 5 个类，分别代表这 5 种迭代器分类。

/* stl_iterator_base.h : 42 */
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 {};

这些类只作为标记使用，仅仅只是来利用编译器的函数重载机制。如你所见，类名末尾以 “tag” 结尾。它们之间还存在一些继承关系，这个我们下文会说明。

SGI STL 的 stl_iterator_base.h 头文件中设计了 3 个 __advance() 函数，并加上区分迭代器分类的第三个参数，使得它们形成重载。

/* stl_iterator_base.h : 323 */
template <class _InputIter, class _Distance>
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>
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>
inline void __advance(_RandomAccessIterator& __i, _Distance __n, 
                      random_access_iterator_tag) {
  __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
  __i += __n;
}

我们可以看到，每一个 __advance() 函数的第三个参数都只是声明了类型，但是并没有指定名称，因为它纯粹只是为了使得编译器应用重载机制，就像我们在上文中提到的那样。另外，我们得需要一个对外开放的上层接口，来根据迭代器分类情况调用上述各个重载函数 (注意是编译时刻确定下来的)。因此，设计的上层接口必须有能力直接从迭代器中推导并得到它的所属的迭代器分类，这就是萃取 (traits) 机制。关于这个我们下文会详细说明，此处只需要知道这是一个能从迭代器中得到此迭代器分类的工具。

与输出迭代器 (Output Iterator) 相关的 advance 函数没有被定义的原因是，除了名字外，它的行为与输入迭代器 (Input Iterator) 别无二致。所以此处单单定义了与输入迭代器相关的版本。

上层接口是 advance() 函数，为了方便表述分析，这里写出一个经过简化的版本。

template <class _InputIterator, class _Distance>
inline void advance(_InputIterator& __i, _Distance __n) {
  __advance(__i, __n, iterator_traits<_InputIterator>::iterator_category());
}

其中，迭代器萃取器 iterator_traits将 _InputIterator中的 iterator_category 关联类型萃取出来，并构造出一个临时对象以供函数重载机制使用。像这样，利用迭代器萃取器以及函数重载机制，就可以在编译时刻确定调用的具体函数。

话说回来，这也是迭代器内嵌的关联类型 iterator_category 被设计出来的原因。

传递调用 (forwarding)

刚刚我们讲到 5 个迭代器分类 (category) 之间的继承问题，现在我们来分析一下。

不管对于哪一种迭代器，在使用时都应当使用最强化 (most refined) 的那一个，比如有一个迭代器，既满足随机访问迭代器的特性，又满足向前迭代器的特性，那么按照原则，理应归属为随机访问迭代器以得到最强化。

迭代器分类 (category) 之间通过继承机制，这样在某种情况下我们编写算法时，如果出于需要，不编写针对更强化的迭代器分类的重载函数，只编写针对弱化迭代器分类的重载函数。即便传递一个强化的迭代器，那么编译器就会通过继承机制确定调用这个针对弱化的迭代器分类的重载函数，即传递调用 (forwarding)，这样编译器就不会因为没有定义对应的重载函数而报错。

我们通过 STL 中的 distance() 函数来做一下示例。

distance() 用来计算两个迭代器之间的距离，针对不同的迭代器分类，它有不同的计算方式、带来不同的效率。

/* stl_iterator_base.h : 267 */
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)
{
  __STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);
  __n += __last - __first;
}

template <class _InputIterator, class _Distance>
inline void distance(_InputIterator __first, 
                     _InputIterator __last, _Distance& __n)
{
  __STL_REQUIRES(_InputIterator, _InputIterator);
  __distance(__first, __last, __n, iterator_category(__first));
}

distance() 函数可以接受任何分类的迭代器，它的模板参数之所以命名为 _InputIterator，是为了遵循 STL 算法的命名规范，即以算法所能接受的最弱化的分类来为其参数命名。因为迭代器分类之间存在继承关系，所以也将存在 “传递调用”。或者说，当调用者使用输出迭代器，或者向前迭代器，又或者双向迭代器时，统统都会传递调用 (forwarding) 输入迭代器版本的 __distance() 函数。

迭代器萃取器

类型萃取 (type traits) 是构建迭代器的重要技巧。上文中我们提到关联类型，它的作用是将迭代器所指向元素的类型特性隐藏/封装起来。而本节中介绍的迭代器萃取器，就是通过某种方式将不同特性的迭代器，它们的底层类型进一步封装起来，当需要使用时，就直接从迭代器萃取器中萃取出来。

迭代器萃取器 (iterator traits) 是一个类模板，它还有两个偏特化的版本，它们被定义在头文件 stl_iterator_base.h 中，相关代码如下。

/* stl_iterator_base.h : 108 */
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;
};

template <class _Tp>
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>
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;
};

现在我们考虑一下泛化版本的 iterator_traits 实现，以理解萃取 (traits) 的具体动作。iterator_traits类模板接受一个迭代器型的模板参数_Iterator。进一步地说，当模板参数是 _Iterator 时，萃取器 iterator_traits 萃取出的 value_type 也就是 _Iterator::value_type。这样看来，就像给迭代器又做了一层封装，给萃取器灌入原材料 (迭代器)，它将萃取出萃取物 (关联类型)。

特化版本的作用

iterator_traits 类模板有两个特化版本，其中一个是对于指针类型的特化，另外一个是对于底层 const 指针类型的特化。除了底层 const 的区别之外，它们基本是一样的，都是对于指针这种 “另类的迭代器” 提供了包容性。因为指针并非类类型 (class type)，这种 “另类的迭代器” 不存在任何在类内部定义的关联类型，所以需要与一般的迭代器区分开来特殊对待。

所以，为了对指针也提供这种包容性，或者说想要将指针也作为一种迭代器，这样使用萃取器来萃取迭代器关联类型是很聪明的做法，毕竟用户不可能直接操作单纯的指针类型去取得其中的关联类型 (比如 value_type)，因为它根本不是类类型 (class type)。

迭代器基类 std::iterator

为了符合迭代器设计的规范，无论设计任何的迭代器，最好都继承自 std::iterator，以获得 5 个符合标准的内嵌类型。它被定义于 stl_iterator_base.h 头文件中，在本文开头其实已经给出了它的定义代码，此处为了方便说明，再贴上来一次。

/* stl_iterator_base.h : 95 */
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;
};

可以看出 std::iterator 只包含 5 种内嵌相关类型，所以继承它不会造成任何负担，并且能够简化迭代器的设计，同时也不容易出现问题 (譬如不会出现忘记定义相关类型而产生不良后果的情况)。

一般来说， 继承 std::iterator 时，只需提供前两个模板参数即可，一是迭代器分类 (category)，二是迭代器指向的元素类型。譬如要设计一个名为 list_iterator 的迭代器，那么就可以编写代码如下。

template <class _Tp>
struct list_iterator : public std::iterator<std::forward_iterator_tag, _Tp>
{ /* ... 此处省略代码 ...*/ };

类型萃取器

在上文中，我们领略了迭代器萃取器 (iterator traits) 的威力。正因为其威力强大，因此萃取 (traits) 技巧大量地运用于 STL 的各个实现中，它利用 “内嵌类型” 与模板参数推导功能，增强了 C++ 未能提供的关于类型判别方面的能力，弥补了 C++ 在强类型 (strong typed) 上的短板。

类型萃取器 (type traits) 可以萃取出类型 (type) 的特性。譬如用于判断一个类型是否具有非平凡 (non-trivial) 的默认构造函数、拷贝构造函数、赋值操作符与析构函数，若没有的话，就可以直接使用内存上的相关操作 (如 malloc()、memcpy()、memmove() 等)，而不去调用这些非平凡的函数。这样在一些操作频繁的、承载着 POD 类型 (Plain Old Data) 元素的容器上，可以大幅度提升运行效率。

__type_traits

SGI STL 在头文件 type_traits.h 中定义了类型萃取器 __type_traits。它提供了一种机制，通过萃取得到不同类型的特性，可以在编译时刻完成相应的函数派送 (function dispatch)，即在编译时刻根据不同的类型特性，编译器就确定了对应的、实际执行的代码功能。

类型萃取器 __type_traits 是一个类模板，定义代码如下。

/* type_traits.h : 55 */
struct __true_type {
};

struct __false_type {
};

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;
};

如你所见，这个模板有 6 个内嵌类型，除了第一个之外 (待会儿说到)，我们需要的有 5 个内嵌类型，分别是

• has_trivial_default_constructor: 具有平凡的默认构造函数
• has_trivial_copy_constructor: 具有平凡的拷贝构造函数
• has_trivial_assignment_operator: 具有平凡的赋值操作符
• has_trivial_destructor: 具有平凡的析构函数
• is_POD_type: 是否是 POD (Plain Old Data) 类型

这些内嵌类型要不是被定义为 __true_type 的别名，要么就被定义为 __false_type 的别名，而这两个类型就是跟前文中说到的迭代器分类 (iterator category) 的类似的空 tag 类型，不造成任何负担，这两个 tag 都只是用于参与编译器的参数推导机制，因为编译器的参数推导机制只对类类型 (class type) 有效。

此处将所有内嵌类型都定义为 __false_type，是因为待会儿 SGI STL 要对特定的、已知的标量类型 (scalar type) 定义特化版本的 __type_traits，此处就需要排除特化版本的定义，而给出最保守的值，即不平凡 (non-trivial)。

(? 下文的说法是笔者根据不一定正确的说法以及并不确凿的相关证据进行推断的)

关于 this_dummy_member_must_be_first 内嵌类型，此类型被定义为 __true_type，一般是留给一些特别的编译器 (比如 SGI 自家的编译器 Silicon Graphics N32 和 N64) 用来做出判定。 这些编译器应该是内置了 __type_traits 类型萃取特性，对于代码中定义的各个类型，将自动地给编译器内置的 __type_traits进行特化。也就是说，如果不做处理，编译器内置了与此处这个模板毫无关联的__type_traits，这将在编译时产生歧义 (很可能是同名造成)。但是，若此处定义一个 __true_type 的占位类型的话，通过编译器层面的判定就可以保证在这些编译器上不会产生歧义或者其他副作用。

所以在一般情况下，用户是无需关心这个内嵌类型的。

类型萃取器 __type_traits 模板接受一个模板参数 _Tp，即类型。因此我们可以通过指定不同的类型，定义并完成类型萃取器针对各个类型的特化，通过在特化中定义 __true_type 或者 __false_type 的 5 个内嵌类型，来赋予类型 _Tp 相关的特性。

这 5 个内嵌类型通常是尝试通过以下步骤获得别名定义，直到获得为止。

• 一般实例 (general instantiation): 即之前定义的 __type_traits 模板
• 特化版本: 对所有标量类型 (scalar type) 特化的 __type_traits 模板
• 某些编译器提供的内置的特化版本: 比如 Silicon Graphics N32 和 N64 编译器，上文有说明

在头文件 type_traits.h 中定义了针对标量类型 (scalar type) 特化的 __type_traits 模板。具体代码片段，笔者稍微简化处理了一下，列出如下。

/* type_traits.h : 90 */
// Provide some specializations.  This is harmless for compilers that
//  have built-in __types_traits support, and essential for compilers
//  that don't.

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

template<> 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;
};

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;
};

注意最后一个特化版本，对于原生指针 (native pointer) 类型，也应该被视作标量类型。

类型萃取器的应用

__type_traits 在 SGI STL 中有十分广泛的应用。例如前篇文章说明的 3 个内存处理全局函数的实现代码，其中就有类型萃取器的身影。

这里我们举例一个在头文件 stl_algobase.h 中定义的另外的 copy() 函数，笔者将代码贴在下文中，接着叙述其中巧妙应用之处。

/* stl_algobase.h : 223 */
template <class _InputIter, class _OutputIter, class _BoolType>
struct __copy_dispatch {
  static _OutputIter copy(_InputIter __first, _InputIter __last,
                          _OutputIter __result) {
    typedef typename iterator_traits<_InputIter>::iterator_category _Category;
    typedef typename iterator_traits<_InputIter>::difference_type _Distance;
    return __copy(__first, __last, __result, _Category(), (_Distance*) 0);
  }
};

template <class _Tp>
struct __copy_dispatch<_Tp*, _Tp*, __true_type>
{
  static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
    return __copy_trivial(__first, __last, __result);
  }
};

template <class _Tp>
struct __copy_dispatch<const _Tp*, _Tp*, __true_type>
{
  static _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) {
    return __copy_trivial(__first, __last, __result);
  }
};

template <class _InputIter, class _OutputIter>
inline _OutputIter copy(_InputIter __first, _InputIter __last,
                        _OutputIter __result) {
  __STL_REQUIRES(_InputIter, _InputIterator);
  __STL_REQUIRES(_OutputIter, _OutputIterator);
  typedef typename iterator_traits<_InputIter>::value_type _Tp;
  typedef typename __type_traits<_Tp>::has_trivial_assignment_operator
          _Trivial;
  return __copy_dispatch<_InputIter, _OutputIter, _Trivial>
    ::copy(__first, __last, __result);
}

我们可以忽略细枝末节，直接观察主要部分，__copy_dispatch 结构中包含了静态的 copy 函数各种特化的实现，其中除了中间两个对于指针类型源迭代器 (故必然也是平凡类型) 的特化之外，还有第一个 __copy_dispatch::copy() 函数，它最终调用更底层的 __copy() 函数 (此函数还接受迭代器分类等参数，当然这里也使用了萃取技巧)。

__copy_dispatch::copy() 函数的上层就是最后一个函数，即全局的 copy() 函数，它应用了 __type_traits，先通过 iterator_traits<_InputIter>::value_type 萃取出迭代器的元素类型
_Tp，再通过 __type_traits<_Tp>::has_trivial_assignment_operator 萃取出元素类型是否具有平凡的 (trivial) 赋值操作符，然后给 __copy_dispatch 模板分发 (dispatch) 出去，对，你没猜错，这里利用编译器的模板参数推导以及函数重载机制，最终调用底层实际的功能实现。

下面是笔者对关于萃取技术的小结。

直接作用: 弥补 C++ 作为非强类型其语言能力上的短板

原理: 利用内嵌类型、模板特化、模板参数推导、函数重载机制等融合而成的编程技巧

功能: 迭代器萃取器 (实现迭代器特性的萃取，比如是 iterator_category，便于设计迭代器以及实现容器算法)。类型萃取器 (实现类型特性的萃取，使容器算法在基于元素本身的各种操作更加灵活高效)