STL_源码剖析之三：迭代器与traits

1、迭代器的的设计思维——stl的关键所在

无论是泛型思维或STL的实际运用，迭代器都扮演着重要角色。STL的中心思想在于将容器和算法翻开，彼此独立。容器和算法的泛型化，从技术角度看并不困难，C++的class template和function template可以分别达成目标，如何设计出两者之间的粘合剂，才是大难题，而迭代器正是扮演了这个重要角色。以下是容器、算法和迭代器的合作演示，以算法find为例：

template <class InputIterator, class T>

InputIterator find(InputIterator first, InputIterator last, const T& value)

{

    while (first!=last && *fist!=value)

        ++first;

    return first;

}

迭代器是一种smart pointer

迭代器是一种类似指针的对象，指针的各种行为中，最重要的就是解引用(dereference,内容提取)和成员访问(member access)；因此迭代器实现最重要的工作就是对operator*和operator->进行重载。

迭代器相应类型

在使用迭代器的算法中，我们很可能需要知道迭代器的相应类型：迭代器所指之物的类型。假设算法中要求宣告一个变量，以迭代器所指的类型为类型，该如何是好？

用函数模板的参数推导机制可以解决这个问题：

template <class I>

void func(I iter)

{

    func_impl(iter,*iter); //func的实现全部移往func_impl

}

template<class I, class T>

void func_impl(I iter, T t)

{

    T temp; //这里解决了问题

    ...

}

可如果迭代器类型要用于函数的返回值就没有办法了，应为函数模板的参数推导只能推导参数，不能推导返回值。

声明嵌套类型似乎是一个好方法，像这样：

template <class I>

struct MyIter

{

    typedef T value_type;   

}

template <class I>

typename I::value_type func(I iter)

{

    return *iter;

}

看起来不错，但还有一个缺陷，并不是所有的迭代器都是class type，比如原生指针类型；如果不是class type，就无法为它声明嵌套类型。但STL必须接受指针作为一种迭代器。

2、traits编程技术-stl源码门轮

traits模板类和partial specilization可以解决上节最后提出的问题。traits，顾名思义，是专门要来提取某个类型特性的类。iterator traits就是用来提取迭代器特性的类。

value_type是traits的特性之一：

template <class I>

struct iterator_traits

{

    typedef typename I::value_type value_type;

}

上面这个traits表明，如果I定义有自己的value_type,那么traits提取的的value_type就是I::value_type。上述那个函数的声明可以改成：

template <class I>

typename iterator_traits<I>::value_type  func(I iter)

{

    return *iter;

}

这里除了多了一层间接性，又带来什么好处呢？好处是traits可以由特化版本，我们定义traits的一个偏特化版本如下：

template <class T>

struct iterator_traits<T*>

{

    typedef T value_type;

}

这样traits就可以提取原生指针类型所指类型了。

traits扮演特性提取机的角色，这里所谓迭代器特性，指的就是迭代器的相应类型。若要这个traits能够有效运作，每一个迭代器必须遵守约定，以嵌套类型定义的方式，声明所需的相关类型，谁不遵守这个约定就不能容于stl这个大家庭。

常用的迭代器相关类型有五种，traits会很忠诚地提取出来：

template <class I>

struct iteraotr_traits

{

typedef typename I::iterator_category  iterator_category;

typedef typename I::value_type value_type;

typedef typename I::deference_type deference_type;

typedef typename I::pointer pointer ;

typedef typename I::reference reference;

}

迭代器相关类型之一：value_type

    迭代器所指对象的类型

迭代器相关类型之二：deference_type

    表示两个迭代器之间距离的类型

迭代器相关类型之三：pointer

    迭代器所指对象的原生指针类型

迭代器相关类型之四：reference

    迭代器所指对象的原生引用类型

迭代器相关类型之五：iterator_category

    表明迭代器的类型。

迭代器的分类

上节提到的iterator_category特性是最复杂的一个特性，我们先讨论下迭代器的分类。

根据迭代器移动特性和行为动作，可以分成五类：

Input Iterator：所指对象只读；

Output Iterator：只写；

Forward Iterator：读写；

Bidirectional Iterator：可双向移动；

Random Access Iterator：前四种只提供一部分指针运算能力，前三种支持operator++，第四种支持operator--。第五种则提供了所有：P+n,p-n,p[n],p1-p2,p1<p2。

上述五种分类之间是一种强化关系：Input Iterator和Output Iterator平级，Forward Iterator强化了这两者，Bidirectional Iterator强化了Forward Iterator，Random Access Iterator强化了Bidirectional Iterator。

从iterator_traits的定义可以推测，最终是以不包含数据的C++类来表示的。

迭代器的分类可以最大化某些算法的执行效率，以advance函数为例：

template <class InputIterator, class Distance>

void advance(InputIterator& i, Distance n)

该函数将会针对不同的迭代器分类采用不同的策略，RandomAccessIterator直接移动n，对其他类型则移动n步。

上面这个函数的签名来自stl源码，它的模板参数命名为InputIterator，这其实是stl的一个约定，以算法所能支持的最低阶的迭代器类命名。

3、SGI STL的私房菜：_type_traits

traits编程技法很棒，大量运用于stl的实现当中，它利用嵌套内省声明和编译器的模板参数推导功能，补强C++未能提供的关于类型认证方面的能力。

stl只对迭代器加以规范，制定出iterator_traits这样的东西。SGI把这一技法扩大到迭代器以外的世界，于是就有了_type_traits。iterator_traits负责提取额迭代器的信息，_type_traits负责提取类型特性。

此处我们关注的类型特性包括：这个类型是否具有non-trivial default ctor；是否具有non-trivial copy ctor；是否具有no-trivial assignment ctor；是否具有non-trivial dtor。这些特性对于对象的创建拷贝移动的效率具有很大的意义。

_type_traits的定义如下：

template <class type>

struct _type_traits

{

typedef _false_type has_trivial_default_ctor;

typedef _false_type has_trivial_copy_ctor;

typedef _false_type has_trivial_assignment_operator;

typedef _false_type has_trivial_dtor;

typedef _false_type is_POD_type;

}

模板_type_traits可以接受任何类型的参数，五个typedef将通过以下渠道获得：

1、一般具现，_type_traits的模板代码采取了最保守的定义，全部为_false_type；

2、特化版本，<type_traits.h>对C++的标量类型定义了对应的特化版本；

3、某些编译器会自动为类型生成适当的的特化版本