SGI STL迭代器概念与traits编程技法

邵鸿福

2023-12-01

1. 迭代器设计思维 ---- STL 关键所在：

《Design Patterns》一书提供有23个设计模式的完整描述，其中 iterator模式定义如下：

提供一种方法，使之能够依序巡访某个聚合物（容器）所含的各个元素，而有无需暴露该聚合物的内部表达方式。

也就是说，迭代器可用于遍历访问容器中的元素，而又无需关注容器中的元素的类型。

STL的中心思想在于：

将数据容器（containers）和算法（algorithms）分开，彼此独立设计，最后再以一帖胶着剂将它们撮合在一起。

STL核心拆分成“容器、算法、迭代器”这三部分。

“容器” 和 “算法” 的泛型化，从技术角度来看并不难，C++的 “类模板” 和 “函数模板” 可分别达成目标。
如何设计出两者之间的良好胶着剂，才是大难题。

2. 迭代器是一种智能指针（也是一个类）：

迭代器也是一个类，是对原生指针的封装，原生指针也可以看做是一种特殊的迭代器；
指针的各种行为中，最常见也最重要的便是“解引用”（*iter）和 “成员访问”（->），因此迭代器对这两种运算符在类内都做了重载；
迭代器为了支持STL中通用的算法，无可避免的会暴露过多的迭代器所指对象的内部实现细节。换句话说，要想实现针对某种容器的迭代器，就必须首先对容器内部的实现细节有非常丰富的了解。因此，在STL的实现中，每一种STL容器都提供有专属的迭代器，封装了容器的实现细节。

3. Traits编程技法 ---- STL源代码门钥：

3.1 typename关键字：

用于声明模板中的一个类型，此时用法与class完全相同，可互为替代：

template <class T>
class A { ... }

template <typename T>
class B { ... }

用于声明一个类型名称：
typename的作用就是告诉C++编译器，typename后面的字符串是一个 “类型名称”，而不是成员函数或者成员变量，这个时候如果前面没有typename，编译器没有任何办法知道 T::LengthType 是一个类型还是一个成员名称（静态数据成员或者静态函数），所有编译不能通过。这种使用场景下，typename是不能用class替代的。例如：

template <class T>
typename iteartor_trais<I>::value_type
func(I ite) 
{ return *ite; }

3.2 模板偏特化：

template partial specialization：模板偏特化：

大致的意义是：
如果一个类模板拥有一个及以上的模板参数时，则可以针对其中某个（或数个，但非全部）模板参数进行特化工作。

换句话说，我们可以在泛化设计中提供一个特化版本（也就是将泛化版本中的某些模板参数赋予明确的指定）。

其实从 “template partial specialization” 字面意思也可以理解“模板偏特化”的含义：

partital： adj. 部分的、不完全的、偏颇、偏袒
specialization： n. 专业化，特化，专门化

直译过来就是“将模板的一部分进行特化”。

例如，假设有如下一个类模板：：

template <typename T>
class C { ... };	//这个泛化模板允许（接受）T为任何型别

它的一个特化版本可以是：

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

“T为原生指针”便是“T为任何型别”的一个更进一步的条件限制。

3.2.1 模板为什么要有偏特化：

因为编译器认为，对于特定的类型，如果你能对某一个功能有更好的实现，那么就该听你的。

3.2.2 “模板偏特化”这一模板特性的作用是：

借助“模板偏特化”，可以实现iterator_traits类的多种“特化版本”，用以支持原生指针、const原生指针等多种特殊迭代器的情况。

3.3 使用traits实现的迭代器：

核心思想：

在“算法函数func()”与“迭代器iter”之间，引入“中间层”萃取类 iterator_traits，进而通过 iterator_traits 模板类的“泛化<T>” 与“偏特化<T*>”两种版本，实现分别对“class type”类类型的迭代器和 “原生指针”类型的迭代器的支持。

实现示例：

#include <iostream>
using namespace std;

template <typename T>
class ListItem {
public:
	ListItem(T val = 0, ListItem* nex = NULL) : _value(val), _next(nex) {}
	T value() const { return _value; }
	ListItem* next() const { return _next; }
private:
	T  _value;
	ListItem* _next;
};

template <typename T>
struct MyIter {
	typedef T value_type;			//iter迭代器类中必须要定义一个value_type，用于返回类型T，这是规定
	T* ptr;
	MyIter(T* p = 0) : ptr(p) {}

	T& operator*() const { return *ptr; }
};

template <class I>
struct iterator_traits_my {			//泛化版模板，用于支持class type类型的迭代器
	typedef typename I::value_type value_type;
};
template <class I>
struct iterator_traits_my<I*> {		//特例化版的模板，用于支持原生指针类型的迭代器
	typedef I value_type;
};

template <class I>
typename iterator_traits_my<I>::value_type
func(I ite) {
	return *ite;		//*ite = *MyIter
}


int main() {
	ListItem<int> item(42);
	MyIter<ListItem<int> > iter(&item);

	ListItem<int> _i = func(iter);
	cout << _i.value() << endl;

	int* _p = new int(43);
	cout << func(_p) << endl;

	return 0;
}

------
42
43

4. 五种最常用到的迭代器型别：

value type
difference type
pointer
reference
iterator catagoly

5. SGI STL的私房菜：__type_traits

STL只对迭代器加以规范，制定出 iterator_traits 这样的东西。
SGI把这种技法进一步扩大到迭代器以外的世界，于是有了所谓的 __type_traits。
双下划线表示这是 SGI STL 内部所用的东西，不是STL标准规范之内。