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

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

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

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

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

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

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

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

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

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

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

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

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

解决办法就是：

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

例如：

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

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

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

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

• 声明内嵌类型 ；

例如：

typedef typename std::vector::size_type size_type;

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

typedef std::vector::size_type size_type;

可以感觉到是对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
class C {...};

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

template
class C {...};

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

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

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

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

template 
struct iterator_traits { //偏特化版本——当迭代器是一个pointer-to-const时
	typedef T value_type;          //萃取出的类型应当是T而非常量const T
	//...
};
//附上指针的偏特化萃取实现
struct iterator_traits {
	typedef T value_type;
	//...
};

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

迭代器5种分类：

迭代器的分类和从属关系

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

之前的ListIter可以改写为：

template 
struct ListIter : public std::iterator {
	//...
};

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