STL迭代器

iterator 模式定义如下：提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。

迭代器设计思维

STL 的中心思想在于：将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以一帖胶着剂将它们撮合在一起。容器和算法的泛型化，从技术角度来看并不困难，C++ 的 class templates 和 function templates 可分别达成目标。如何设计出两者之间的良好胶着剂，才是大难题。

迭代器（iterator）是一种 smart pointer

迭代器是一种行为类似指针的对象,而指针的各种行为中最常见也最重要的便是内容提领（dereference）和成员访问（member access），因此，迭代器最重要的编程工作就是对 operator* 和 operator-> 进行重载（overloading）工作。

例如auto_ptr就是一个比较老的智能指针，一份简化版的代码如下：

简化版智能指针

我们需要为它设置一个类似指针的外衣，也就是迭代器，当我们提领(dereference)这一迭代器时，传回的因该是一个对象；当我们递增这个迭代器的时候，它应该指向下一个对象。

一般的实现，为了完成一个针对特定容器而设计的迭代器，我们无可避免的需要暴露太多容器实现的细节；既然这无法避免，干脆就把迭代器的开发工作交给容器的设计者好了。如此一来，所有实现细节反而得以封装起来不被使用者看到。

这正是为什么每一种STL容器都提供有专属迭代器的缘故。

模板template的用法

template的使用大大提高了代码的复用性, 抽象性.

template实例化的时机

首先需要注意下面几点：

1. 类模板实例化时并不是每个成员函数都实例化了, 而是使用到了哪个成员函数, 那个成员函数才实例化.

   例如下面这段代码：

   /* ***** 1 *******/
   template<class T>
   class point
   {
    public:
        point() : x(0), y(0) {}
        point(T x, T y) : x(x), y(y) {}
        T getX() const   { x = y;  return x; }  // 一般是无法通过编译的, x不允许被修改, 但是这里并没有报错
    private:
        T x;
        T y;
   };
   /* ***** 2 *******/
   #define T int
   class point
   {
    public:
        point() : x(0), y(0) {}
        point(T x, T y) : x(x), y(y) {}
        T getX() const   { x = y;  return x; }
    private:
        T x; T y;
   };
   

   成员函数getX()应该无法通过编译, 就像实例2一样, 但是因为模板中没有使用到函数getX(), 也就没有实例化getX, 所以就没有出现编译报错. 实例2必须在编译的时候就要检查所有的成员即函数.

   不是所有的模板都只能在运行时才会被实例化, 比如非类型模板参数就能在编译时期就已经实例化了, 这里主要说的是类模板, 不要混淆了.

2. 可以把类模板和函数模板结合起来, 定义一个含有成员函数模板的类模板.

   例如下面这段代码：

   template<class T>
   class point
   {
    public:
        point() : x(0), y(0) {}
        point(T x, T y) : x(x), y(y) {}
        template<class U>   // 定义了另一个的模板参数类型
            void print(U x);
    private:
        T x;
        T y;
   };
   
   // 这里两个都要写出来
   template<class T>
   template<class U>
   void point<T>::print(U x)
   {
    std::cout << this->x + x;
   }
   
   int main()
   {
    point<int> p;
    p.print(3.14);  // 因为是模板函数, 所以交给编译器自行推导
   
    exit(0);
   }
   

3. 类模板中可以声明static成员, 在类外定义的时候要增加template相关的关键词, 并且需要注意每个不同的模板实例都会有一个独有的static成员对象.

   例如

   template<class T>
   T tmp<T>::t = 0;
   

template之非类型模板参数

非类型参数, 可用在模板中自定义为整型类型, 指针或引用, 不能定义为浮点数等其他类型.

非类型模板参数在编译期间就已经实例化, 所以其模板实参必须是常量表达式.

template<int N>;    // N是编译时就确定的常量表达式
template<size_t N, size_t M>;   // N,M是编译时就确定的常量表达式

可能就是会觉得没有用, 毕竟使用模板就是要用他的模板参数类型啊, 没有这个那还怎么用. 这里就来先看一个例子.

要求: 实现一个函数返回一个数组的真实大小, 如 : int a[100]; ArrSize(a);返回100

嗯? 讲道理传入函数中a就转换为指针了, 怎么用指针能获取其表示范围? 这里就要用到template的非类型参数.

template<class T, std::size_t N>    // 这里的N是编译时期就知道了, 所以可以加上constexpr关键字
    constexpr std::size_t ArrSize(T (&a)[N]) noexcept   
{
    return N;
}
int a[100]; ArrSize(a);

函数模板通过传入a后会自动推导出 T 的类型为 int, N 的大小为 100, 函数通过引用, 所以传入的是一个a而不是一个指针.

重点在于模板参数N能自动推导传入数组的大小.

同样我们可以将strcmp做一个封装, 实现一个字符串比较的模板函数.

template<unsigned N, unsigned M>
bool compare(const char (&a)[N], const char (&b)[M])
{
    return strcmp(a, b);
}

使用template的非类型参数可以自动帮我们获取参数的大小, 省去手动传入参数大小的麻烦等问题. 记住 : 非类型模板参数在编译期间就已经实例化, 所以其模板实参必须是常量表达式.

可以使用虚函数模板吗？

例如下面这段代码：

class point
{
    public:
        template<class T>
            virtual T getX()
            {
                return x;
            }
    private:
        int x;
};

int main()
{
    exit(0);
}

为什么虚函数不能是模板函数?

• 编译器在编译类的定义的时候就必须确定该类的虚表大小.
• 模板只有在运行调用时才能确认其大小, 两者冲突. 结果显而易见.

模板拷贝构造函数

模板与不同模板之间不能直接的赋值(强制转换), 毕竟模板一般都是类和函数都不是普通的类型. 但是类有拷贝构造函数, 所以我们可以对类的构造函数进行修改, 也就成了模板构造函数.

template<class T>
class tmp
{
    public:
        tmp() : x(0) {}
        template<class U>
            tmp(const tmp<U>& t)
            {
                x = t.x;
            }
    private:
        T x;
};

int main()
{
    tmp<int> t1;
    tmp<char> t2;
    t1 = t2;

    exit(0);
}

template之模板中class与typename区别

最开始定义定义模板的方法就是template<class T> , 但是class毕竟都认为是一个类, 在使用时难免会有些点混淆, 也就定义了typename来标志参数类型

typename可以用在嵌套依赖中, 并且表示其类型, 而class并没有这样的功能.

嵌套依赖可以看下面的代码：

template<class T>
class people
{
    public:
        typedef T   value_type;
        typedef T*  pointer;
        typedef T&  reference;
};

template<class T>
struct man 
{
    public:
        typedef typename T::value_type  value_type;
        typedef typename T::pointer     pointer;
        typedef typename T::reference   reference;
        void print()
        {
            cout << "man" << endl;
        }
};

int main()
{
    man<people<int>> Man;
    Man.print();

    exit(0);
}

以上就是typename的嵌套使用. typename告诉编译器这不是一个函数, 也不是一个变量而是一个类型. 这里使用typedef又将参数类型重新定义一次:

1. 增加了一层间接性
2. 使用的时候也不需要在写很长的代码.

这里typename是对people类中定义的类型进行了一次提取, 这里将typename改为class就会出错.

综上所述，typename的主要的作用就是:对于模板参数是类的时候, typename能够提取出该类所定义的参数类型.

template之全特化和偏特化

。。。

Traits 编程技法

在算法中运用迭代器时，很可能会用到其相应型别（associated type）。什么是相应型别? 迭代器所指之物的型别便是其一。假设算法中有必要声明一个变量,以“迭代器所指对象的型别”为型别,如何是好? 毕竟 C++ 只支持 sizeof(),并未支持 typeof（）! 即便动用 RTTI 性质中的 typeid(），获得的也只是型称，不能拿来做变量声明之用。

解决方法：利用函数模板的参数推导机制。

迭代器相应型别（associated types）不只是 “迭代器所指对象的型别”一种而已。根据经验，最常用的相应型别有五种，然而并非任何情况下任何一种都可利用上述的 template 参数推导机制来取得。我们需要更全面的解法。

迭代器所指对象的型别，称为该迭代器的value type。

参数型别推导技巧虽然可用于 value type，却非全面可用：万一 value type 必须用于函数的传回值，就束手无策了，毕竟函数的 “template 参数推导机制”推而导之的只是参数，无法推导函数的返回值类别。

那么声明一个内嵌类型可以是一个方法：

template <class T>
struct MyIter {
    typedef T value_type； // 内嵌型别声明（nested type）
    T* ptr; MyIter(T* p=0) : ptr(p) { } 
    T& operator*() const ( return *ptr; }
    //...
} ;

template <class I> typename I::value_type // 这一整行是 func 的回返值型别
func(I ite) {return *ite；} 
// ...
MyIter<int> ite(new int(8)); 
cout << func(ite); //输出：8

注意，func(）的回返型别必须加上关键词 typename，因为 T 是一个template 参数，在它被编译器具现化之前，编译器对 T 一无所悉，换句话说，编译器此时并不知道 MyIter<T>: ivalue_type 代表的是一个型别或是一个 membe function 或是一个 data member。关键词 typename 的用意在于告诉编译器这是一个型别，如此才能顺利通过编译。

前面的嵌套依赖解决了返回值类型推导的问题，但是现在还是有一个问题，并不是所有的迭代器都是class type，例如原生指针！如果不是 class type，就无法为它定义内嵌型别。但 STL（以及整个泛型思维）绝对必须接受原生指针作为一种迭代器，所以上面这样还不够。

需要对原生指针做特殊化处理！

Partial Specialization （偏特化）- 普通中加上一个特例

Partial Specialization （偏特化）的意义：如果 class template 拥有一个以上的template 参数，我们可以针对其中某个（或数个，但非全部）template 参数进行特化工作。换句话说，我们可以在泛化设计中提供一个特化版本（也就是将泛化版本中的某些 template 参数赋予明确的指定）。

例如我们可以这样特化原生指针：

template<typename T>
class C { ... };    // 这个泛化版本允许（接受）T 为任何型别

特化指针：

template<typename T>
class C<T*> { ... }; // 这个特化版本仅适用于 “T 为原生指针”的情况
                    //“T 为原生指针”便是 “T 为任何型别”的一个更进一步的条件限制

现在解决了有些类型例如原生指针并非class，无法为他们“内嵌型别”的问题，我们通过对 “迭代器之 template 参数为指针”者，设计特化版的迭代器得以解决。

partial specialization的字面意义容易误导我们以为，所谓“偏特化版”一定是对template参数u或v或T（或某种组合）指定某个参数值。其实不然，[Austern99]对于partial specialization的意义说得十分得体：“所谓 partial specialization的意思是提供另一份template定义式，而其本身仍为templatized”。《泛型思维》一书对partial specialization的定义是：“针对（任何）template参数更进一步的条件限制所设计出来的一个特化版本”。

下面引入一个中间层的模板类，专门用来“萃取”迭代器的特性，如下面可以萃取迭代器的value type特性，假如它有定义这个:

template <class I>
struct iterator_traits {    // traits 意为“特性”
    typedef typename I::value_type value_type;
};

那么我们的 func(）可以统一成这样：

template <class I>
typename iterator_traits<I>::value_type // 这一整行是函数回返型别
func(I ite) { return *ite；}

同时，对于原生指针迭代器的特化版本，我们可以很容易的去定义(因为有了中间层“萃取"进行粘合)：

template <class T>
struct iterator_traits<T*> { // 偏特化版——迭代器是个原生指针
typedef T value_type;
};

于是，原生指针int*虽然不是一种class type，亦可通过traits取其value type。这就解决了先前的问题。

针对 “指向常数对象的指针（pointer-to-const）”也可以很方便的做一个特化版本：

template <class T> 
struct iterator_traits<const T*> { //偏特化版——当迭代器是个pointer-to-const 时, 
typedef T value_type;             // 萃取出来的型别应该是 T 而非 const T 
};

traits 所扮演的 “特性萃取机”角色，萃取各个迭代器的特性。这里所谓的迭代器特性，指的是迭代器的相应型别（associated types）。当然，若要这个 “特性萃取机”traits 能够有效运作，每一个迭代器必须遵循约定，自行以内嵌型别定义（nested typedef）的方式定义出相应型别（associated types）。这是一个约定，谁不遵守这个约定，谁就不能兼容于 STL 这个大家庭。

特性萃取机

迭代器相应型别（associated types）

最常用到的迭代器相应型别有五种：value type, difference type,pointer, reference, iterator catagoly。

value type

所谓 value type，是指迭代器所指对象的型别。

difference type

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

如果一个泛型算法提供计数功能，例如STL的count()，其传回值就必须使用迭代器的difference type:

difference type相关代码

针对相应型别diference type，traits的如下两个（针对原生指针而写的）特化版本，以C++内建的ptrdifft（定义于<cstddef>头文件）作为原生指针的difference type:

设置特化版本的diference type

现在，任何时候当我们需要任何迭代器I的difference type，都可以这么写：

typename iterator_traits<I>::difference_type

reference type

从“迭代器所指之物的内容是否允许改变”的角度观之，迭代器分为两种：
不允许改变“所指对象之内容”者，称为constant iterators，例如 const intpic；允许改变“所指对象之内容”者，称为mutable iterators，例如intpi。当我们对一个mutable iterators进行提领操作时，获得的不应该是一个右值（rvalue)，应该是一个左值（lvalue），因为右值不允许赋值操作（assignment)，左值才允许.

在C++中，函数如果要传回左值，都是以by reference的方式进行，所以当p是个mutable iterators时，如果其 value type是T，那么p的型别不应该是T，应该是Ts。将此道理扩充，如果p是一个constant iterators，其value type是T，那么p的型别不应该是constr，而应该是constTs。这里所讨论的*p的型别，即所谓的 reference type。

pointer

pointers和references在C++中有非常密切的关联。如果“传回一个左值，令它代表p所指之物”是可能的，那么“传回一个左值，令它代表p所指之物的地址”也一定可以。也就是说，我们能够传回一个pointer，指向迭代器所指之物。

例如下面这段代码：

指针和引用

iterator_catagoly

迭代器根据移动特性和实施操作被分为5类

1. input iterator(输入迭代器) : 迭代器所指的内容不能被修改, 只读且只能执行一次读操作.

2. output iterator(输出迭代器) : 只写并且一次只能执行一次写操作.

3. forward iterator(正向迭代器) : 支持读写操作且支持多次读写操作.常用于关联容器.

4. bidirectional iterator(双向迭代器) : 支持双向的移动且支持多次读写操作.常用于顺序容器.

5. random access iterator(随即访问迭代器) : 支持双向移动且支持多次读写操作. p+n, p-n等.例如原生指针.

   前四种迭代器都只供应一部分指针算术能力（前三种支持operator++，第四种再加上operator--)，第五种则涵盖所有指针算术能力，包括p+n,p-n,p[n]，pl-p2，p1<p2。

迭代器的分类和从属关系如下：

[图片上传失败...(image-cbfa80-1602082849718)]

设计算法时，如果可能，我们尽量针对某种迭代器提供一个明确定义，并针对更强化的某种选代器提供另一种定义，这样才能在不同情况下提供最大效率。在研究STL的过程中，每一分每一秒我们都要谨记在心，效率是个重要课题。假设有个算法可接受 Forward terator，你以Random Access lterator喂给它，它当然也会接受，因为一个Random Access terator 必然是一个Forward lterator。但是可用并不代表最佳！

为了在编译时期确定调用相应的函数，我们使用函数进行重载，运用了重载的机制以及类继承的特点。

首先定义五种迭代器的类型：

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

这五个类都是空类, 只是为了之后调用时通过类选择不同的重载函数. 继承是为了可以使用传递调用，当不存在某种迭代器类型匹配时编译器会依据继承层次向上查找进行传递, 就可以通过继承关系来决定选择最优的调用.

那么我们重载调用的时候只需要变成这样就可以：

使用继承类型重载

注意上述语法，iterator_traits<Iterator>：:iterator_category()将产生一个暂时对象（道理就像int（）会产生一个int暂时对象一样），其型别应该隶属于前述五个迭代器类型之一。然后，根据这个型别，编译器才决定调用哪一个advance（)重载函数。

Distance例子

distance是用于计算连个迭代器之间的距离, 因为重载就可以通过不同的迭代器类型选择不同的函数来提高效率.

这里distance的iterator_category函数是每个迭代器自己定义的, 跟traits萃取器相关我准备放在下一篇章讲解. 这里只要知道它能通过first参数推断出是哪一类的迭代器从而选择调用哪一个函数.

template <class InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n) 
{
    __distance(first, last, n, iterator_category(first));
}
    
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;
}

从distance源码可以看出来不同的迭代器的计算方式并不一样, random_access_iterator_tag的距离的计算效率最高, 其他都是通过++操作来依次访问. 当然random_access_iterator_tag类的迭代器也是可以调用input_iterator_tag, 但是显然效率很低, 所以不同的迭代器最自己最佳的效率. 通过iterator_category进行最优选择.

std::iterator的保证

为了符合规范，任何选代器都应该提供五个内嵌相应型别，以利于traits萃取，否则便是自别于整个STL架构，可能无法与其它STL组件顺利搭配。然而写代码难免挂一漏万，谁也不能保证不会有粗心大意的时候。如果能够将事情简化，就好多了。STL提供了一个iterators class如下，如果每个新设计的迭代器都继承自它，就可保证符合STL所需之规范：

迭代器的基类

iterator class不含任何成员，纯粹只是型别定义，所以继承它并不会招致任何额外负担。由于后三个参数皆有默认值，故新的迭代器只需提供前两个参数即可。ListIter，如果改用正式规格，应该这么写：

继承迭代器基类保证符合STL规范

​ 设计适当的相应型别（asociated types)，是迭代器的责任。设计适当的迭代器，则是容器的责任。唯容器本身，才知道该设计出怎样的迭代器来遍历自己，并执行迭代器该有的各种行为（前进、后退、取值、取用成员…)。至于算法，完全可以独立于容器和迭代器之外自行发展，只要设计时以迭代器为对外接口就行。
​ traits编程技法大量运用于STL实现品中。它利用“内嵌型别”的编程技巧与编译器的template参数推导功能，增强C++未能提供的关于型别认证方面的能力，弥补C++不为强型别（strong typed)语言的遗憾。了解traits编程技法，就像获得“芝麻开门”的口诀一样，从此得以一窥STL源代码堂奥。

代码分析

五种迭代器的类型：

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

iterator_traits结构体就是使用typename对参数类型的提取(萃取), 并且对参数类型在进行一次命名, 看上去对参数类型的使用有了一层间接性. 以下就是它的定义.

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;           // 迭代器所指对象的类型引用
};

上面的traits结构体并没有对原生指针做处理, 所以还要为特化, 偏特化版本(即原生指针)做统一. 以下便是iterator_traits 的特化和偏特化实现

// 针对原生指针 T* 生成的 traits 偏特化
template <class 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;
};
// 针对原生指针 const T* 生成的 traits 偏特化
template <class T>
struct iterator_traits<const T*> {
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef ptrdiff_t                  difference_type;
  typedef const T*                   pointer;
  typedef const T&                   reference;
};

distance函数

// 根据第三个参数的类型调用相应的重载函数
template <class InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n) 
{
    __distance(first, last, n, iterator_category(first));
}
    
template <class InputIterator, class Distance>
inline void __distance(InputIterator first, InputIterator last, Distance& n, 
                       input_iterator_tag) 
{plate <class InputIterator, class Distance>
inline void __distance(InputIterator first, InputIterator last, Distance& n, 
                       input_iterator_tag) 
{
    while (first != 
    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;
}

这里又列出了两个类型的实现, 这里用到了0可以转换成指针的性质, 相当于返回一个空指针, 但是可以通过它们确定不同的参数类型.

template <class Iterator>
inline typename iterator_traits<Iterator>::difference_type*
distance_type(const Iterator&) {
  return static_cast<typename iterator_traits<Iterator>::difference_type*>(0);
}

template <class Iterator>
inline typename iterator_traits<Iterator>::value_type*
value_type(const Iterator&) {
  return static_cast<typename iterator_traits<Iterator>::value_type*>(0);
}

五类迭代器源码

五类迭代器的结构体, 可以看出来每个类都定义了相同的变量名. 但是每个名的类型不一定一样, 提供统一的名是为了traits进行类型萃取. 每个类的iterator_category都是代表了不同的迭代器, 通过它来选择该迭代器执行的函数.

template <class T, class Distance> struct input_iterator 
{
    typedef input_iterator_tag iterator_category;
    typedef T                  value_type;
    typedef Distance           difference_type;
    typedef T*                 pointer;
    typedef T&                 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 T, class Distance> struct forward_iterator {
  typedef forward_iterator_tag iterator_category;
  typedef T                    value_type;
  typedef Distance             difference_type;
  typedef T*                   pointer;
  typedef T&                   reference;
};


template <class T, class Distance> struct bidirectional_iterator {
  typedef bidirectional_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef Distance                   difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

template <class T, class Distance> struct random_access_iterator {
  typedef random_access_iterator_tag iterator_category;
  typedef T                          value_type;
  typedef Distance                   difference_type;
  typedef T*                         pointer;
  typedef T&                         reference;
};

iterator_category判断传入迭代器的类型:

template <class Iterator>
inline typename iterator_traits<Iterator>::iterator_category
iterator_category(const Iterator&) {
  typedef typename iterator_traits<Iterator>::iterator_category category;
  return category();
}

__type_traits

traits编程技法很棒，适度弥补了C++语言本身的不足。STL只对迭代器加以规范，制定出iterator-traits 这样的东西。SGI把这种技法进一步扩大到迭代器以外的世界，于是有了所谓的type-traits。双底线前缀词意指这是SGISTL内部所用的东西，不在STL标准规范之内。

iterator_traits负责萃取迭代器的特性，type_traits则负责萃取型别（type）的特性。此处我们所关注的型别特性是指：这个型别是否具备 non-trivialdefalt ctor?是否具备 non-trivial copy ctor?是否具备 non-trivial assignmentoperator?是否具备non-trivial dtor?如果答案是否定的，我们在对这个型别进行构造、析构、拷贝、赋值等操作时，就可以采用最有效率的措施（例如根本不调用身居高位，不谋实事的那些 constructor,destructor），而采用内存直接处理操作如ma1loc（）、memcpy（）等等，获得最高效率。这对于大规模而操作频繁的容器，有着显著的效率提升。

两个参数推导：

struct __true_type {};
struct __false_type {};

我们不能将参数设为bool值, 因为需要在编译期就决定该使用哪个函数, 所以需要利用函数模板的参数推导机制, 将__true_type和__false_type表现为一个空类, 就不会带来额外的负担, 又能表示真假, 还能在编译时类型推导就确定执行相应的函数.

__type_traits源码

将基础类型设置为__true_type:

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

...
// 还有int、short、long、float等类型

将指针进行特化处理, 同样是__true_type型别：

#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION

template <class T>
struct __type_traits<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;
};

#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */

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

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

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

SGI将所有的内嵌型别都定义为false_type, 这是对所有的定义最保守的值.

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

从上面的源码可以明白, 所有的基本类型都是设置的为__true_type型别, 而所有的对象都会被特化为__false_type型别, 这是为了保守而不得这样做. 也因为__true_type型别让我们在执行普通类型时能够以最大效率进行对其的copy, 析构等操作.

SGI对traits进行扩展，使得所有类型都满足traits编程规范, 这样SGI STL算法可以通过__type_traits获取类型信息在编译期间就能决定出使用哪一个重载函数, 解决了template是在运行时决定重载选择的问题. 并且通过true和false来确定POD和travial destructor, 让程序能选择更加符合其类型的处理函数, 大大提高了对基本类型的快速处理能力并保证了效率最高.

总结

• 设计适当的相应型别（associated types），是迭代器的责任。设计适当的迭代器，则是容器的责任。唯容器本身，才知道该设计出怎样的迭代器来遍历自己，并执行迭代器该有的各种行为（前进、后退、取值、取用成员…）。至于算法，完全可以独立于容器和迭代器之外自行发展，只要设计时以迭代器为对外接口就行。
• traits 编程技法大量运用于 STL 实现品中。它利用“内嵌型别”的编程技巧与编译器的 template 参数推导功能，增强 C++ 未能提供的关于型别认证方面的能力，弥补C++ 不为强型别（strong typed）语言的遗憾。了解 traits 编程技法，就像获得 “芝麻开门”的口诀一样，从此得以一窥 STL 源代码堂奥。

---

参考：

1. template之全特化和偏特化
2. STL源码分析目录
3. 《STL源码分析》- 侯捷