【STL】迭代器（iterators）与traits编程_std::iterator

一、概述

迭代器(iterator)是一种抽象的设计理念。他是通过提供一种方法，使之能够依次巡访某个聚合物（容器）所含的各个元素，而又无需暴露该聚合物的内部表述方式。

简言之，通过迭代器可以在不了解容器内部原理的情况下遍历容器。

除此之外，STL中迭代器一个最重要的作用就是作为容器(vector,list等)与STL算法的粘结剂，将数据容器和算法分开，只要容器提供迭代器的接口，同一套算法代码可以利用在完全不同的容器中，这是抽象思想的经典应用。容器和算法的泛化可以通过C++的class template 和function template 来实现，如何设计出一个良好的迭代器才是最大难题。

二、iterator 是一种 smart pointer

迭代器是一种类似指针行为的对象，其中，最重要的就是内容提领（dereference）和成员访问（member access）。所以，迭代器最重要的就是对operator * 和operator -> 进行重载。

下面我们设计一个简单的list迭代器：

//定义single linked list的基本数据结构
template <typename T>
class List {
public:
	void insert_front(T value);
	void insert_end(T value);
	void display(std::ostream &os = std::out) const;
	//...
private:
	ListItem<T>* _end();
	ListItem<T>* _front();
	long _size;
};

template <typename T>
class ListItem {
public:
	T value() const { return _value; }
	ListItem<T>* next const { return _next; }
	//...
private:
	T _value;
	ListItem<T>* _next;
};

template<typename Item>
class ListIter{
    Item *ptr;
public:
    vecIter(Item *p = 0) :ptr(p){}
    //不必实现 copy ctor 和 operator =，因为编译器提供的缺省行为已经足够
    Item& operator*()const{ return *ptr;}
    Item* operator->()const{ return ptr;}
    //pre
    vecIter& operator++(){ ++ptr; return *this; }
    vecIter operator++(int){ vecIter tmp = *this; ++*this; return tmp; }
    bool operator==(const vecIter &iter){ return ptr == iter.ptr; }
    bool operator!=(const vecIter &iter){ return !(*this == iter); }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

从以上实现中，可以看到为完成ListIter的设计，其中暴露了许多List的实现细节，包括数据成员ListItem及其成员函数。对于调用者而言，这些都应该是屏蔽掉的。但是要设计出ListIter，就难免暴露出这些实现细节，也就是说要对List有丰富的了解。因此，惯常做法是由容器的设计者开发该容器的迭代器。如此，所有实现细节对使用者屏蔽，这也是为什么每种STL容器都有专属迭代器的原因。

三、迭代器相应的型别

在迭代器使用中，可能使用到相应的型别（迭代器所指之物的型别），但是C++并不支持typeof()！即使是RTTI性质中的typeid()，获得的也只是型别名称，并不能作为变量声明来使用。

首先，我们要了解到，迭代器所指之物的型别可以分为以下三种情况

1. 迭代器所指对象是c++内置类型；
2. 迭代器所指对象是自定义类型(class type)情形;
3. 迭代器所指对象是原生指针(naive pointer)情形;

解决办法就是：

• function template的参数推导(augument deducation)机制 ；

例如：

template <typename I,typename T>
void func_imp1(I iter,T t){
	T tmp;
	...
}

template <typename I>
inline 
void func(I iter){
	func_imp1(iter,*iter);
}

int main(){
	int i;
	func(&i);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

由于func_imp1()是一个function template ，一旦被调用，编译器会自动进行 template 参数推导。于是导出型别T。

• 声明内嵌类型 ；

例如：

typedef typename std::vector<T>::size_type size_type;
1

将语句中的typename关键字抛开不看，则语句为：

typedef std::vector<T>::size_type size_type;
1

可以感觉到是对std::vector::size_type这个类型进行重命名。那么为什么要加上typename这个关键字呢？

原来，其中T是模板中的类型参数，它只有等到模板实例化时才会知道是哪种类型，更不用说T内部的size_type。所以对于限定依赖名（解释见补充）std::vector::size_type而言，无法判断其是静态成员变量/函数还是嵌套类型，这样会造成语句的二义性，这是不能够容忍的。

若是在std::vector::size_type这个类型前加上typename这一关键字，指明这是一个嵌套类型，而不是T的静态成员或静态成员函数，消除了二义性。

• 利用泛化中偏特化(partial secification)；

需要注意的是，并不是所有的迭代器都是class type的。比如说原生指针(naive pointer)，就无法将其定义为内嵌类型。所以还要对上述的一般化概念中的特殊情况做特殊化处理。

偏特化(template partial specification)：如果class template拥有一个以上的template参数，可以对其中某个(或数个，但非全部)template进行特化工作，其中偏特化有两种形式：

1. 对template参数的部分个参数进行特化；
2. 对template参数的范围进行限定；

例如有一个 class template 如下：

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

偏特化的字面意思容易让人理解成一定对template里面的参数U、V或者T 指定某一个参数值。但其实并不是这样，只要对其参数做进一步限制，即可。如下：

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

四、Traits编程技法

上述三种方法是逐步整合为最终的实现的方案就是 iterator_traits萃取机 机制，它包含了函数模板的参数推导，声明内嵌类型和偏特化所有内容。其作用是萃取出迭代器的相关特性（也即是相应类型的取用），以屏蔽迭代器实现对算法实现的影响。

traits就像一台“特性萃取机”，提取各个迭代器的特性。

若要这个萃取机能够正常运作，每一个迭代器必须遵守约定，自行以内嵌型别定义的方式定义出相应型别。

同时，iterator_traits 必须针对传入型别为 pointer 以及 pointer-to-const 设计特化版本。

template <class T>
struct iterator_traits<const T*> { //偏特化版本——当迭代器是一个pointer-to-const时
	typedef T value_type;          //萃取出的类型应当是T而非常量const T
	//...
};
//附上指针的偏特化萃取实现
struct iterator_traits<T*> {
	typedef T value_type;
	//...
};
1
2
3
4
5
6
7
8
9
10

迭代器中最常用到的迭代器类型有五种，整理出如下表格：

迭代器5种分类：

迭代器的分类和从属关系

五、std::iterator的保证

为符合规范，任何迭代器都应提供五个内嵌相应类别，以利于traits萃取。STL为此提供了一个iterators class，也即std::iterator如下，如果每个新设计的迭代器继承自它，就可保证STL所需之规范：

之前的ListIter可以改写为：

template <class Item>
struct ListIter : public std::iterator<std::forward_iterator_tag, Item> {
	//...
};
1
2
3
4

六、总结

参考资料：
《STL源码剖析》