泛型编程

有了一些使用 STL 的经验后来看一看底层理念。STL 是一种泛型编程(geniric programming)。面向对象编程关注的是编程的数据方面而泛型编程关注的是算法。它们之间的共同点是抽象和创建可重用代码但它们的理念决然不同。

泛型编程旨在编写独立于数据类型的代码。在 C++ 中完成通用程序的工具是模板。当然模板使得能够按泛型定义函数或类而 STL 通过通用算法更进了一步。模板让这一切成为可能但必须对元素进行仔细地设计。为解模板和设计是如何协同工作的来看一看需要迭代器的原因。

为何使用迭代器

理解迭代器是理解 STL 的关键所在。模板使得算法独立于存储的数据类型而迭代器使算法独立于使用的容器类型。因此它们都是 STL 通用方法的重要组成部分。

为了解为何需要迭代器我们来看如何为两种不同数据表示实现 find 函数然后来看如何推广这种方法。首先看一个在 double 数组中搜索特定值的函数可以这样编写该函数

double * find_ar(double * ar, int n, const double & val){
	for (int i = 0; i < n; i++){
		if(ar[i] == val )
			return &ar[i];
	}
	return 0;	// or, in C++11, return nullptr;
}

如果函数在数组中找到这样的值则返回该值在数组中的地址否则返回一个空指针。该函数使用下标来遍历数组。可以用模板将这种算法推广到包含==运算符、任意类型的数组。尽管如此这种算法仍然与一种特定的数据结构数组关联在一起。

下面来看搜索另一种数据结构——链表的情况第12章使用链表实现了 Queue 类。链表由链接在一起的 Node 结构组成

struct Node {
	double item;
	Node * p_next;
};

假设有一个指向链表第一个节点的指针每个节点的 p_next 指针都指向下一个节点链表最后一个节点的 p_next 指针被设置为 0 则可以这样编写 find_ll() 函数

Node * find_ll (Node * head, const double & val) {
	Node * start;
	for (start = head; start !=0; start = start->p_next){
		if (start->item == val){
			return start;
		}
	}
	return 0;
}

同样也可以使用模板将这种算法推广到支持==运算符的任何数据类型的链表。然而这种算法也是与特定的数据结构——链表关联在一起。

从实现细节上看这两个 find 函数的算法是不同的一个使用数组索引来遍历元素另一个则将 start 重置为 start -> p_next。但从广义上说这两种算法是相同的将值依次与容器中的每个值进行比较直到找到匹配的为止。

泛型编程旨在使用同一个 find 函数来处理数组、链表或任何其他容器类型。即函数不仅独立于容器中存储的数据类型而且独立于容器本身的数据结构。模板提供了存储在容器中的数据类型的通用表示因此还需要遍历容器中的值得通用表示迭代器正是这样的通用表示。

要实现 find 函数迭代器应具备哪些特征呢下面是一个简短的列表

• 应能够对迭代器执行解除引用的操作以便能够访问它引用的值。即如果p是一个迭代器则应对 *p 进行定义。
• 应能够将一个迭代器赋给另一个。即如果p和q都是迭代器则应对表达式 p=q 进行定义。
• 应能够将一个迭代器与另一个进行比较看它们是否相等。即如果p和q都是迭代器则应对 p==qp!=q 进行定义。
• 应能够使用迭代器遍历容器中的所有元素这可以通过为迭代器p定义++p和p++来实现。

迭代器也可以完成其他的操作但有上述操作功能对find函数就足够了。实际上STL按功能的强弱定义了多种级别的迭代器这将在后面介绍。顺便说一句常规指针就能满足迭代器的要求因此可以这样重新编写 find_arr() 函数

typedef double * iterator;
iterator find_ar(iterator ar, int n, const double & val) {
	for (int i = 0; i < n; i++, ar++){
		if(*ar == val)
			return ar;
	}
	return 0;
}

然后可以修改函数参数使之接受两个指示区间的指针参数其中的一个指向数组的起始位置另一个指向数组的超尾同时函数可以通过返回尾指针来指出没有找到要找的值。下面的 find_ar() 版本完成了这些修改

typedef double * iterator;
iterator find_ar(iterator begin, iterator end, const double & val){
	iterator ar;
	for (ar = begin; ar != end; ar++){
		if (*ar == val){
			return ar;
		}
	}
	return end;	// indicates val not found
}

对于 find_ll() 函数可以定义一个迭代器类其中定义了运算符* 和 ++

struct Node{
	double item;
	Node * p_next;
};

class iterator {
	Node * pt;
public:
	iterator() : pt(0) {}
	iterator (Node * pn) : pt(pn) {}
	double operator*() { return pt->item;}
	iterator & operator++() {		// for ++it
		pt = pt -> next;
		return *this;
	}
	iterator operator++(int) {	// for it++
		iterator temp = *this;
		pt = pt->p_next;
		return temp;
	}
// ... operator==(), operator!=(), etc.
};

为区分++运算符的前缀版本和后缀版本C++将operator++作为前缀版本将operator++(int)作为后缀版本其中的参数永远也不会被用到所以不必指定其名称。

这里重点不是如何定义 iterator 类而是有了这样的类后第二个 find 函数就可以这样编写

iterator find_ll(iterator head, const double & val) {
	iterator start;
	for (start = head; start!=0; ++start){
		if(*start == val){
			return start;
		}
	}
	return 0;
}

这和 find_ar() 几乎相同差别在于如何谓词已到达最后一个值。find_ar() 函数使用超尾迭代器而find_ll() 使用存储在最后一个节点中的空值。除了这种差别外这两个函数完全相同。例如可以要求链表的最后一个元素后面还有一个额外的元素即让数组和链表都有超尾元素并在迭代器到达超尾位置时结束搜索。这样find_ar() 和 find_ll() 检测数据尾的方式相同从而成为相同的算法。注意增加超尾元素后对迭代器的要求变成了对容器类的要求。

STL遵循上面介绍的方法。首先每个容器类vector、list、deque等定义了相应的迭代器类型。对于其中的某个类迭代器可能是指针而对于另一个类则可能是对象。不管实现方式如何迭代器都将所需的操作如* 和 ++ 有些类需要的操作可能比其他类多。其次每个容器类都有一个超尾标记当迭代器递增到超越容器的最后一个值后这个值将被赋给迭代器。每个容器类都有 begin() 和 end() 方法它们分别返回一个指向容器的第一个元素和超尾位置的迭代器。每个容器类都使用++操作让迭代器从指向第一个元素逐步指向超尾位置从而遍历容器中的每一个元素。

使用容器类时无需知道其迭代器是如何实现的也无需知道超尾是如何实现的而只需知道它有迭代器其 begin() 返回一个指向超尾位置的迭代器即可。例如假设要打印 vector<double> 对象中的值则可以这样做

vector<double>::iterator pr;
for (pr = scores.begin(); pr != scores.end(); pr++ ){
	cout << *pr << endl;
}

其中下面的代码行将 pr 的类型声明为 vector<double> 类的迭代器

vector<double> class;
vector<double>::iterator pr;

如果要使用 list<double> 类模板来存储分数则代码如下

list<double>::iterator pr;
for (pr = scores.begin(); pr != scores.end(); pr++){
	cout << *pr << endl;
}

唯一不同的是pr的类型。因此STL 通过为每个类定义适当的迭代器并以统一的风格设计类能够对内部表示绝然不同的容器编写相同的代码。

使用C++11新增的自动类型推断可进一步简化对于vector 或 链表都可使用如下代码

for (auto pr = scores.begin(); pr != scores.end(); pr++){
	cout << *pr << endl;
}

实际上作为一种编程风格最好避免直接使用迭代器而应尽可能使用 STL 函数如 for_each()来处理细节。也可使用 C++11 新增的基于范围的 for 循环

for(auto x : scores) cout << x << endl;

来总结一下 STL 方法。首先是处理容器的算法应尽可能用通用的术语来表达算法使之独立于数据类型和容器类型。为使通用算法能够适用于具体情况应定义能够满足算法需求的迭代器并把要求加到容器设计上。即基于算法的要求设计基本迭代器的特征和容器特征。

迭代器类型

不同的算法对迭代器的要求也不同。例如查找算法需要定义++运算符以便迭代器能够遍历整个容器它要求能够读取数据但不要求能够写数据它指示查看数据并不修改数据。而排序算法要求能够随机访问以便能够交换两个不相邻的元素。如果 iter 是一个迭代器则可以通过定义+运算符来实现随机访问这样就可以使用像 iter+10 这样的表达式了。另外排序算法要求能够读写数据。

STL 定义了 5 种迭代器并根据所需的迭代器类型对算法进行了描述。这5种迭代器分别是输入迭代器、输出迭代器、正向迭代器、双向迭代器和随机访问迭代器。例如find() 的原型与下面类似

template<class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& value);

这指出这种算法需要一个输入迭代器。同样下面的原型指出排序算法需要一个随机访问迭代器

template<class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

对于这5种迭代器都可以执行解除引用操作即为它们定义了*运算符也可进行比较看其是相等使用==运算符可能被重载了还是不相等使用!=运算符可能被重载了。如果两个迭代器相同则对它们执行解除引用操作得到的值相同。即如果表达式 iter1 == iter2 为真则下述表达式也为真

*iter1 == *iter2

当然对于内置运算符和指针来说情况也是如此。因此这些要求将指导您如何对迭代器类重载这些运算符。下面来看迭代器的其他特征。

1. 输入迭代器
   术语“输入”是从程序的角度说的即来自容器的信息被视为输入就像来自键盘的信息对程序来说是输入一样。因此输入迭代器可被程序用来读取容器中的信息。具体地说对输入迭代器解除引用将使程序能够读取容器中的值但不一定能让程序修改值。因此需要输入迭代器的算法将不会修改容器中的值。

   输入迭代器必须能够访问容器中所有的值这是通过支持++运算符前缀格式和后缀格式来实现的。如果将输入迭代器设置为指向容器中的第一个元素并不断将其递增直到到达超尾位置则它将依次指向容器中的每一个元素。顺便说一句并不能保证输入迭代器第二次遍历容器时顺序不变。另外输入迭代器被递增后也不能保证其先前的值仍然可以被解除引用。基于输入迭代器的任何算法都应当是单通行single-pass的不依赖于前一次遍历时的迭代器值也不依赖于本次遍历中前面的迭代器值。

   注意输入迭代器是单向迭代器可以递增但不能倒退。

2. 输出迭代器

   STL 使用术语“输出”来指用于将信息从程序传输给容器的迭代器因此程序的输出就是容器的输入。输出迭代器与输入迭代器相似只是解除引用让程序能够修改容器值而不能读取。也许您会感到奇怪能够写却不能读。发送到显示器上的输出就是如此cout 可以修改发送到显示器的字符流却不能读取屏幕上的内容。STL足够通用其容器可以表示输出设备因此容器也可能如此。另外如果算法不用读取作容器的内容就可以修改它如通过生成要存储的新值则没有理由要求它使用能够读取内容的迭代器。
   简而言之对于单通行、只读算法可以使用输入迭代器而对于单通行、只写算法则可以使用输出迭代器。

3. 正向迭代器
   与输入迭代器和输出迭代器相似正向迭代器只使用++运算符来遍历容器所以它每次沿容器向前移动一个元素然而与输入和输出迭代器不同的是它总是按相同的顺序遍历一系列值。另外将正向迭代器递增后仍然可以对前面的迭代器值解除引用如果保存了它并可以得到相同的值。这些特征使得多次通行算法成为可能。

   正向迭代器既可以使得能够读取和修改数据也可以使得只能读取数据

   int *pirw;			// read-write iterator
   const int * pir;		// read-only iterator
   

4. 双向迭代器
   假设算法需要能够双向遍历容器情况将如何呢例如reverse 函数可以交换第一个元素和最后一个元素、将指向第一个元素的指针加1、将指向第二个元素的指针减1并重复这种处理过程。双向迭代器具有正向迭代器的所有特性同时支持两种前缀和后缀递减运算符。

5. 随机访问迭代器
   有些算法如标准排序和二分检索要求能够直接跳到容器中的任何一个元素这叫做随机访问需要随机访问迭代器。随机访问迭代器具有双向迭代器的所有特性同时添加了支持随机访问的操作如指针增加运算和用于对元素进行排序的关系运算符。下表列出了除双向迭代器的操作外随机访问迭代器还支持的操作。其中X表示随机迭代器类型T表示被指向的类型a 和 b 都是迭代器值n 为整数r 为随机迭代器变量或引用。

表达式	描述
a + n	指向a所指向的元素后的第n个元素
n + a	与 a + n 相同
a - n	指向 a 所指向的元素前的第 n 个元素
r += n	等价于 r = r + n
r -= n	等价于 r = r - n
a[n]	等价于 *(a+n)
b - a	结果为这样的 n 值即 b = a + n
a < b	如果 b - a > 0则为真
a > b	如果 b < a 则为真
a >= b	如果 !(a<b)则为真
a <= b	如果 !(a>b)则为真

像 a+n 这样的表达式仅当 a 和 a+n 都位于容器区间包括超尾内时才合法。

迭代器层次结构

您可能已经注意到迭代器类型形成了一个层次结构。正向迭代器具有输入迭代器和输出迭代器的全部功能同时还有自己的功能双向迭代器具有正向迭代器的全部功能同时还有自己的功能随机访问迭代器具有双向迭代器的所有功能同时还有自己的功能。下表总结了主要的迭代器功能。其中i 为迭代器 n 为整数。

迭代器功能	输入	输出	正向	双向	随机访问
解除引用读取	有	无	有	有	有
解除引用写入	无	有	有	有	有
固定和可重复排序	无	无	有	有	有
++i i++	有	有	有	有	有
–i i–	无	无	无	有	有
i[n]	无	无	无	无	有
i+n	无	无	无	无	有
i-n	无	无	无	无	有
i+=n	无	无	无	无	有
i-=n	无	无	无	无	有

根据特定迭代器类型编写的算法可以使用该种迭代器也可以使用具有所需功能的任何其他迭代器。所以具有随机访问迭代器的容器可以使用为输入迭代器编写的算法。

为何需要这么多迭代器呢目的是为了在编写算法时尽可能使用要求最低的迭代器并让它适用于容器的最大区间。这样通过使用级别最低的输入迭代器find() 函数便可用于任何包含可读取值的容器。而sort() 函数由于需要随机访问迭代器所以只能用于支持这种迭代器的容器。

注意各种迭代器的类型并不是确定的而只是一种概念性描述。正如前面指出的每个容器类都定义了一个类级 typedef 名称——iterator因此 vector<int> 类的迭代器类型为 vector<int>::iterator。然而该类的文档将指出vector迭代器是随机访问迭代器它允许使用基于任何迭代器类型的算法因为速记访问迭代器具有所有迭代器的功能。同样list<int> 类的迭代器类型为 list<int>::iterator。STL 实现了一个双向链表它使用双向迭代器因此不能使用基于随机访问迭代器的算法但可以使用基于要求较低的迭代器的算法。