STL 源码剖析读书笔记二:迭代器与traits

时间:2022-09-25 04:18:04

1. 迭代器概述

迭代器是一种抽象的设计概念,现实程序语言中并没有直接对应这个概念的实物。《设计模式》中对于迭代器模式的定义为:提供一种方法,使之能够依序访问某个聚合物所含的各个元素,而又无需暴露该聚合物的内部表述方式。

STL 的中心思想在于:将数据容器和算法分开,彼此独立设计,再以迭代器粘合。容器和算法的泛型化在技术角度来看并不困难,C++ 的类模板和函数模板可分别达成目标。如何设计出两者的良好粘合剂,才是大难题。

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

2. traits 编程技法

假设算法中需要声明一个变量,以“迭代器所指对象的型别”为型别,如何是好?毕竟C++只支持 sizeof(),并未支持 typeof()。即使使用 RTTI 性质中的 typeid(),获得的也只是型别名称,不能用于声明变量。

解决方法是:利用 function template 的参数推导机制。

template <class I, class T>
void func_impl(I iter, T t)
{
    T tmp;
    //...
}
template<class I>
void func(I iter)
{
    func_impl(iter, *iter);
}

最常用的迭代器相应型别有 5 种:

  • value type
  • difference type
  • pointer
  • reference
  • iterator catagoly

然而并非任何情况下任何一种都能利用上述的参数推导机制来取得。

当 value type 必须用于函数的返回值,上述方法不适用了,毕竟参数推导只是推导参数。替代方法是:声明内嵌型别。

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 iter) { return *iter; }

//...
MyIter<int> iter(new int(8));
cout << func(iter);

注意,func 的返回值型别必须加上关键字 typename,因为 T 是一个template 参数,他在被编译器具现化之前,编译器对 T 一无所知,必须加上typename 明确告诉编译器这个是一个型别。

但是,并不是所有迭代器都是 class type,原生指针就不是,即无法为它定义内嵌型别。而 STL 绝对必须接受原生指针作为一种迭代器,所以上面这样还不够,这里需要用到模板偏特化。偏特化是指:针对 template 参数更进一步的条件限制设计出来的一个特化版本。

template <class T>
class C { ... };        // 接受 T 为任何型别

一个偏特化如下:

template <class T>
class C<T*> { ... };   // 仅适用于 T 为原生指针的情况

下面这个 class template 专门用来“萃取”迭代器的特性,而 value type 正是迭代器特性之一:

template <class I>
struct iterator_traits
{
    typedef typename I::value_type value_type;
}

所谓 traits,其意义是,如果 I 定义有自己的 value type,那么通过这个 traits 的作业,萃取出来的 value_type 就是 I::value_type。换句话说,如果 I 定义有自己的 value type,先前那个 func() 可以改写为:

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

但这除了多一层间接性,又带来什么好处?好处是 traits 可以拥有特化版本。现在,我们令 iterator_traits 拥有一个 偏特化版本如下:

template <class T>
struct iterator_traits<T*>
{
    typedef T value_type;
};

于是,原生指针虽然不是 class type,亦可通过 traits 取其 value type。而对 指向常数对象的指针,需要另外设计一个特化版本:

template <class T>
struct iterator_traits<const T*>
{
    typedef T value_type;
};

traits 就像一台“特性萃取性“,榨取各个迭代器的特性(相应型别):

STL 源码剖析读书笔记二:迭代器与traits

template <class I>
struct iterator_traits
{
    typedef typename I::iterator_category iterator_category;
    typedef typename I::value_type value_type;
    typedef typename I::difference_type difference_type;
    typedef typename I::pointer pointer;
    typedef typename I::reference reference;
};

3. 迭代器相应型别

  • 迭代器相应型别之一:value type。value type 是指迭代器所指对象的型别。任何一个打算与 STL 算法有完美搭配的 class,都应该定义自己的 value type 内嵌型别。
  • 迭代器相应型别之二:difference type。difference type 用来表示两个迭代器之间的距离,因此它也可以用来表示一个容器的最大容量,因为对于连续空间的容器而言,头尾之间的距离就是其最大容量。
  • 迭代器相应型别之三:reference type。在 C++ 中,函数如果要返回左值,都是以 引用的方式进行的,所以当 p 是个允许改变所指对象的内容的迭代器,其 value type 是 T,那么 *p 的型别不应该是 T, 而是 T&。当 p 是个不允许改变所指对象的内容的迭代器,其 value type 是 T,那么 *p 的型别是 const T&。
  • 迭代器相应型别之四:pointer type。如果“传回一个左值,令他代表 p 所指之物”是可能的,那么“传回一个左值,令他代表 p 所指之物的地址”也一定可以。即传回一个指针,指向迭代器所指之物。
  • 迭代器相应型别之五:iterator_catagory。

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

  • Input Iterator:只读
  • Output Iterator:只写
  • Forward Iterator:允许进行区间读写
  • Bidirectional Iterator:可以双向移动访问某个迭代器区间
  • Random Access Iterator:前四种都只供应一部分指针算术能力(前三种支持 operator++,第四种再加上 operator–),第五种则涵盖所有指针算术能力,包括 p+n, p-n, p[n], p1-p2, p1>p2。

迭代器的分类与从属关系如下图所示:

STL 源码剖析读书笔记二:迭代器与traits

设计算法时,如果可能,我们尽量针对上图中某种迭代器提供一个明确定义,并针对更强化的某种迭代器提供另一定义,这样才能在不同情况下提供最大效率。

假设有个算法接受 Forward Iterator,你以 Random Access Iterator 喂给它,也可用,但是可用不一定最佳。

traits 可以萃取出迭代器的种类,我们便可利用这个迭代器相应型别作为函数参数,这个型别一定需要是 class type,因为编译器需要依赖他进行重载决议,定义五个 classes 代表五种迭代器类型:

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

任何一个迭代器,其类型应永远落在“该迭代器所隶属之各种类型中”最强化的那个。例如 int * 既是 Random Access Iterator,又是Bidirectional Iterator,同时也是Forward Iterator,而且也是 Input Iterator,那么其类型应该归属于 Random Access Iterator。

STL 算法的一个命名规则:以算法所能接受之最低阶迭代器类型,来为其迭代器型别参数命名。

4. std::iterator 的保证

STL 提供了一个 iterator class 如下,如果每个新设计的迭代器都继承自它,就可保证符合 STL 所需之规范:

template <class Catagory,
          class T,
          class Distance = ptrdiff_t,
          class Pointer = T*,
          class Reference = T&>
struct iterator
{
    typedef Catagory        iterator_catagory;
    typedef T               value_type;
    typedef Distance        difference_type;
    typedef Pointer         pointer;
    typedef Reference       reference;  
}

5. __type_traits

SGI 把 traits 技法进一步扩大到迭代器以外的世界,即 __type_traits。

iterator_traits 负责萃取迭代器的特性,__type_traits 则负责萃取型别的特性。这里关注的型别特性是指:这个型别是否具备 non-trivial default ctor ?是否具备 non-trivial copy ctor?是否具备 non-trivial assignment operator?是否具备non-trivial dtor?如果答案是否定的,我们在对这个型别进行构造、拷贝、赋值、析构等操作时,就可以采用最有效率的措施,而采取内存直接处理操作如 malloc、memcpy 等,获得效率。这对大规模而操作频繁的容器有着显著的效率提升。



struct __true_type { }; struct __false_type { }; 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; };

SGI 把所有内嵌型别都定义为 __false_type,定义为最保守的值,然后再针对每一个标量型别设计适当的特化版本。