STL中迭代器设计思维与原理

迭代器设计思维

关于迭代器的基础原理和作用我以前有一个博客提到过: STL迭代器的原理以及迭代器失效  我不推荐不够了解迭代器的读者直接来看这个博客，因为你

会觉得我在做一些无意义的事情，并且理解上面也会存在脱节，我们这个博客主要写的是STL当中stl_iterator这个头文件当中的源代码信息. 这里面

是有难度的，我也只是将一些基础的框架拿了出来. 不可能将所有源码拿出来一句一句注释. 我们理解的只是一个框架.

不论是泛型编程或者STL的实际运用，迭代器都扮演这重要的角色. STL的中心思想在于: 将数据容器和算法分开，彼此独立设计，最后再用胶水将他们

撮合在一起. 容器和算法的泛型化，从技术角度来看并不困难,C++的class template 和 function template可分别达成目标. 如何设计出两者之间良

好 的胶水，这才是最难得！ 也就是我们的迭代器设计思维！ 我们来看一个例子感受一下STL当中iterator的强大！

//摘自 SGI<stl_algo.h>
/*template<class InputIterator,class T>
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
	while (first != last && *first != value)
	{
		++first;
	}
	return first;
}
*/

//接下来,我们来调用这个函数！ 看看它的威力
#include<vector>
#include<list>
#include<deque>
#include<algorithm>
#include<iostream>

using namespace std;

int main()
{
	const int arraySize = 7;
	int ia[arraySize] = { 0, 1, 2, 3, 4, 5, 6 };

	vector<int> ivect(ia, ia + arraySize);
	list<int> ilist(ia, ia + arraySize);
	deque<int> ideque(ia, ia + arraySize);

	vector<int>::iterator it1 = find(ivect.begin(), ivect.end(), 4);
	list<int>::iterator it2 = find(ilist.begin(), ilist.end(), 4);
	deque<int>::iterator it3 = find(ideque.begin(), ideque.end(), 4);
	int* it4 = find(ia, ia + arraySize, 4);


	cout << *it1 << endl;
	cout << *it2 << endl;
	cout << *it3 << endl;
	cout << *it4 << endl;

	system("pause");
	return 0;
}

template<class InputIterator,class T>
InputIterator find(InputIterator first, InputIterator last, const T& value)
{
	while (first != last && *first != value)
	{
		++first;
	}
	return first;
}

一看STL-iterator当中的源代码后，你就会明白了，为了满足上述的大团圆的结局，STL做了多少的努力. 因为将算法和容器分开独立设计，最后又想

用迭代器将他们粘合在一起. 难度是非常之高的！ 不要觉得是这个算法的功劳，功劳大多都是都是在算法的传参上的迭代器. 其实fin d函数也不会只

有这一种类型，如果你使用map,set容器，那么find肯定就不会这样设计了. 那么我们来认识一下这个神奇的迭代器.

迭代器是一种行为类似指针的对象，而指针的各种行为中最常见也最重要的便是内容提领(dereference)和成员访问（member access),因此迭代器最

重要的编程工作就是对operator* 和 operator->进行重载工作. 关于这点跟C++11当中的智能指针就很相似.很巧我写了一篇博客就是关于 智能指针

看完它再回来理解迭代器就是事半功倍的感觉. 现在开始！ 

迭代器的五种相应类型

根据移动特性与施行操作，迭代器被分为五类:

>Input Iterator:这种迭代器所指的对象，不允许外界改变. 只读(read only).

>Output Iterator:只写(不解释).

的 算术能力，包括p+n,p-n,p[n],p1-p2,p1<p2.

这些迭代器的分类与从属关系，可以看下面这个图表示，直线与箭头代表的并非C++的继承关系，而是所谓的concpt(概念)与refinement(强化)的关系.

我们在设计算法的时候，如果可能，我们尽量针对上面的迭代器给一个明确的定义，这样才能在不同情况下提供最大的效率. 在研究STL过程当中，每

一分每一秒我们都要铭记于心，效率是一个非常重要的课题. 假设一个算法可以接受 Forward Iterator，你使用一个 RandomAccess IteratorTag喂给

他,它当然也会接受，因为一个 RandomAccess IteratorTag必然是一个 Forward Iterator但是可用，并不代表就是最佳的.我们使用advanced()为例子.

拿advance()来说，该函数有两个参数，迭代器p和数值n;函数内部将p累进n次. 下面有三分定义，一份针对于 Input Iterator 一分针对于

Bidirectional IteratorTag,一份针对于 RandomAccess IteratorTag. 倒是没有针对 Forward Iteratorer而设计的版本,因为那个针对 Input Iterator

没有什么区别.

template <class InputIterator, class Distance>
inline void __advanceII(InputIterator& i, Distance n) {
  while (n--) ++i;
}

template <class BidirectionalIterator, class Distance>
inline void __advanceBI(BidirectionalIterator& i, Distance n) {
  if (n >= 0)
    while (n--) ++i;
  else
    while (n++) --i;
}

template <class RandomAccessIterator, class Distance>
inline void __advanceRAI(RandomAccessIterator& i, Distance n) {
  i += n;
}

的操作变成了O(N)的操作. 如果选择 __advanceRAI()，则它无法接受 Input Iterator。 我们需要将三者合一。 我们为了程序的效率，最好能够在编译

器就选择正确的版本. 让他们三个函数进行重载就可以达到这个目标. 前述三个advance_xx()都有两个函数参数，型别都未定. 为了令其同名，形成

重载函数，我们必须加上一个型别已确定的函数参数,使函数重载机制得以有效运行起来. 我们来看看STL是如何解决的.

下面定义五个classes，代表五种迭代器类型:

//五个作为标记用的型别

struct InputIteratorTag{};

struct OutputIteratorTag{};

struct ForwardIteratorTag :public InputIteratorTag{};

struct BidirectionalIteratorTag :public ForwardIteratorTag{};

struct RandomAccessIteratorTag :public BidirectionalIteratorTag{};

数名称加上特定的前导符)，并加上第三参数，使它们形成重载:

template <class InputIterator, class Distance>
inline void __advance(InputIterator& i, Distance n, input_iterator_tag) {
  while (n--) ++i;
}

template <class BidirectionalIterator, class Distance>
inline void __advance(BidirectionalIterator& i, Distance n, 
                      bidirectional_iterator_tag) {
  if (n >= 0)
    while (n--) ++i;
  else
    while (n++) --i;
}

template <class RandomAccessIterator, class Distance>
inline void __advance(RandomAccessIterator& i, Distance n, 
                      random_access_iterator_tag) {
  i += n;
}

注意上述的语法，每一个__advance()的最后一个参数都只声明型别，并未指定参数名称，因为它纯粹是为了激活重载机制，函数之中根本不使用该参

数.如果硬要加上参数名称也可以，画蛇添足. 现在我们大体的思想已经有啦. 也就是根据迭代器的类型来确定那个重载函数的调用. 比如我这个

Advance()函数，list,deque,vector,map,set. 这些容器的访问方式好多都不同的. 所以他们对应的Advance()函数也不同.所以我们可以使用迭代器的

五种 类型区分他们. 比如List就是 BidirectionalIteratorTag，又比如forward_list就是 ForwardIteratorTag. 所以这样我们可以很容易的 想到在相应

地容器当中标记自己的 迭代器类型，比如list的话，我们看看源代码怎么搞的:

//摘自SGI STL 3.0源代码
template<class T, class Ref, class Ptr>
struct __list_iterator {
  typedef __list_iterator<T, T&, T*>             iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;
  typedef __list_iterator<T, Ref, Ptr>           self;

  typedef bidirectional_iterator_tag iterator_category;
  typedef T value_type;
  typedef Ptr pointer;
  typedef Ref reference;
  typedef __list_node<T>* link_type;
  typedef size_t size_type;
  typedef ptrdiff_t difference_type;
  .
  .
  .
  .
}

我们看到了，List当中将自己的迭代器类型typedef成了 iterator_category. 其实不仅仅是list，其他容器基本都这么做了. 所以我们每次调用刚刚

的advance()函数的时候，就简单的多了. 下面的代码就可以进行对应的容器调用对应的重载函数：

//只是外层的一个封装，它会萃取出你传进来的迭代器类型当中的iterator_category 然后启动__advance的重载机制.
	template <class InputIterator,calss Distance>
	inline InputIterator::difference_type advance(InputIterator& i, Distance n)
	{
			typedef typename InputIterator::iterator_category category;
			return __advance(first, n, category());
	}

然 后传进__advance()函数，触发重载函数机制. 调用指定的重载函数. 另外我们还在list源码中看到了几个别的typedef，我在其他容器中也能找到

这几个typedef.

//摘自SGI STL 3.0 源代码
template <class Category, class T, class Distance = ptrdiff_t,
          class Pointer = T*, class Reference = T&>
struct iterator {
  typedef Category  iterator_category;
  typedef T         value_type;
  typedef Distance  difference_type;
  typedef Pointer   pointer;
  typedef Reference reference;
};

他们就是迭代器当中的相应型别，也就是这么讲  每一个迭代器当中都需要有这几个型别，他们各自有各自的作用，他们的存在就是提高迭代器的效率

和复用机制. 一般我们的容器迭代器都会继承上面这个类(vector除外)，然后对它进行初始化，这样它里面的5大型别就创建好了，就可以随意使用了.

迭代器相应型别之一>valueType

所谓valueType，是指迭代器所指对象是型别. 任何一个打算与STL算法有完美搭配的class，都应该定义自己的ValueType内嵌型别.  

迭代器相应型别之二>differenceType

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

其最大容量.

迭代器相应型别之三>referenceType

从"迭代器所指之物的内容是否允许改变"的角度观之，迭代器分为两种: 不允许改变"所指对象之内容"者 称之为constant iterators 允许改变"所指

对象之内容"者，称为mutable iterators. ValueType&是非常常用的，所以使用referenceType来标识他.

迭代器相应型别之四>pointType.

pointers和reference在C++中有非常密切的联系，如果"传回一个左值，令它代表p所指之物" 是可能的. 那么"传回一个左值，令它代表p所指之物的地

址"也一定可以. 也就是说我们能够传回一个pointer，指向迭代器所指之物. 使用pointType来标识他.

迭代器相应型别之五>iterator_category

上面讨论的迭代器五种类型就为了引出来这个 iterator_category,它的重要性不言而喻. 我们接下来还是要继续围绕着它来继续探索，你以为上面的

advance()函数就解决了，对应的容器迭代器类型调用对应重载函数的问题了吗？ 并没有，你去想一想如果你的容器是vector,那么你的Iteratoe就是

T*. 这个时候Iterator:: iterator_category 能取到内容吗？？ 别的容器比如list，map，set他们的Iterator都是封装出来的一个类，可以在类中

定义迭代器的5个型别，然后初始化后进行使用，但是vectro可以吗？ vector的迭代器就是T* 它里面不可能定义任何东西，所以想取vector的Iteraor

:: iterator_category. 是一件很抽象的事情.  但是我们的STL又做到了，这里就要引出我们的 Traits编程技法-STL源代码的门匙.

Traits编程技法

任何一个完整的C++书籍当中都会介绍到偏特化，它的概念为如果class template拥有一个以上的template参数，我们可以针对其中某个template参数

进行特化工作. 换句话说，我们可以在泛化设计中提供一个特化版本(也就是将泛化版本中的某些template参数赋予明确的指定)

假设有一个class template如下:

template<typename U,typename V,typename T>
class C	{...};

是:针对template参数更进一步的条件限制所设置出来的一个特化版本.

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

我们便很容易接受它有一个形式如下的偏特化:

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

有了这个利器我们对刚刚碰到的 vector中的迭代器无法提取出 iterator_category问题就有一点周旋的余地了. 因为原生指针并非class,因为无法对他

们定义内嵌类别. 现在，我们可以针对"迭代器之template参数为指针"者，设计特化版的迭代器. 敲敲黑板(！！！)  下面这个class template专门

用来"萃取"迭代器的特性，而valueType正是迭代器的特性之一:

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

多了一层封装，有点多此一举的感觉. 但是你再好好思考一下.traits可以萃取出value_type. 那他肯定也可以萃取出 iterator_category. 既然当我们

的迭代器是原生指针的时候，没有办法给Iterator当中定义内嵌型别. 但是我们可以在traits中做手脚啊. 我们可以进行特化，让T*类型的迭代器拥有

自己的特化版本，然后让traits返回一个 RandomAccessIterator即可. 让正常的迭代器返回自己的 iterator_category. 然后我们最常用到的迭代器相

应型别分别有5种:iterator_category,  value_type difference_type pointer reference. 我们干脆让traits全帮你萃取出来吧. 我们来看源代码:

//"榨汁机" 将有用的东西帮你榨取出来了.
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偏特化版本.
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;
};

//针对原声指针而设计的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;
};

template<typename InputIterator>
size_t advance(InputIterator it, int n)
{
	typedef typename iterator_traits<InputIterator>::iterator_category Category;
	return __advance(it, n, Category());
}

过advance函数，调用到自己合适的重载函数. 这就是traits编程的思想. 通过traits后，无论是原生指针或者class-type iterator，都可以让外界方

便地取其相应的类型.

我自己实现了一份简单的STL迭代器的代码，虽然没有STL那么严密，但是框架相似可以简易的跑起来，我摘出核心的部分帮我们理解运行过程:

//迭代器的类型
struct InputIteratorTag{};

struct OutputIteratorTag{};

struct ForwardIteratorTag :public InputIteratorTag{};

struct BidirectionalIteratorTag :public ForwardIteratorTag{};

struct RandomAccessIteratorTag :public BidirectionalIteratorTag{};

//
template <class Category, class T, class Distance = size_t>
struct baseiterator {
	typedef Category  IteratorCategory;
	typedef T        ValueType;
	typedef T*       Pointer;
	typedef T&       Reference;
	typedef Distance  DifferenceType;
};

//这里
template<typename Iterator>
struct IteratorTraits
{
	typedef typename Iterator::IteratorCategory IteratorCategory;
	typedef typename Iterator::ValueType ValueType;
	typedef typename Iterator::Pointer Pointer;
	typedef typename Iterator::Reference Reference;
	typedef typename Iterator::DifferenceType DifferenceType;
};

//专门为vector等... 直接传T所做的贡献与准备.
template<typename T>
struct IteratorTraits<T*>
{
	typedef  RandomAccessIteratorTag IteratorCategory;
	typedef  T ValueType;
	typedef  T& Pointer;
	typedef  T* Reference;
	typedef  size_t DifferenceType;
};

template<typename T>
struct IteratorTraits<const T*>
{
	typedef  RandomAccessIteratorTag IteratorCategory;
	typedef  T ValueType;
	typedef  const T& Pointer;
	typedef  const  T* Reference;
	typedef  size_t DifferenceType;
};

template<typename InputIterator>
size_t Advance(InputIterator it, int n)
{
	typedef typename IteratorTraits<InputIterator>::IteratorCategory Category;
	return __Advance(it, n, Category());
}

template<typename InputIterator>
typename IteratorTraits<InputIterator>::DifferenceType Distance(InputIterator first, InputIterator last)
{
	typedef typename IteratorTraits<InputIterator>::IteratorCategory Category;
	return __Distance(first, last, Category());
}


template<typename InputIterator>
typename IteratorTraits<InputIterator>::DifferenceType __Distance(InputIterator first, InputIterator last, RandomAccessIteratorTag)
{
	return last - first;
}


template<typename InputIterator>
typename IteratorTraits<InputIterator>::DifferenceType __Distance(InputIterator first, InputIterator last, InputIteratorTag)
{
	size_t count = 0;

	while (first != last)
	{
		++count;
		++first;
	}

	return count;
}

template<typename InputIteratorTag>
InputIteratorTag __Advance(InputIteratorTag it, int num, InputIteratorTag)
{
	assert(num >= 0);

	while (num--)
	{
		++it;
	}

	return it;
}

template<typename InputIteratorTag>
InputIteratorTag __Advance(InputIteratorTag it, int num, BidirectionalIteratorTag)
{
	if (num > 0)
	{
		while (n--)
		{
			++it;
		}
	}
	else
	{
		while (n++)
		{
			--it;
		}
	}

	return it;
}

template<typename InputIteratorTag>
RandomAccessIteratorTag __Advance(InputIteratorTag it, int num, RandomAccessIteratorTag)
{
	it += n;

	return it;
}

我画一张图帮我们理解这个迭代器的调用过程 以及 框架结构 ，还有traits的作用 :

traits编程技法大量运用于STL的实现品当中，它利用"内嵌类别"的编程技巧与编译器的template参数推导功能，增强C++未能提供的关于型别认证方面

的能力，弥补了C++不为强型别语言的遗憾. 了解traits编程技法，就像获得"芝麻开门"的口诀一样，从此得以一窥STL源代码的堂奥.

说实话，理解这个框架是有难度的，阅读懂源码再然后自己尝试写一个山寨版本的STL框架是学习STL最好的方法. 至少对于我是这样的. 这个博客围绕

5种迭代器的类型，5种迭代器内嵌类型，traits编程技法. 这就是迭代器的重点，理解了它们那么你差不多就能明白了STL迭代器的原理. 接下来还有

我们的constIterator和ReverseIterator我们下一篇博客当中就会提到，并且实现. 如果想看STL_iterator的源代码 我的github: STL_iterator源代码

参照资料： 《STL源码剖析》 -侯捷