摘要
Programming: Principles and Practice Using C++, Second Edition
容器和迭代器
只做一件事，并把它做好。多个程序协同工作。
——Doug McIlory
本章和下一章将分别介绍C++标准库（STL）中的容器和算法部分。STL是一个用于处理C++程序中数据的可扩展框架。我们首先通过一个简单的例子来说明STL的设计理念和基本概念，然后详细讨论迭代器、链表和STL中的容器。STL通过序列（sequence）和迭代器（iterator）的概念将容器（数据）和算法（处理）关联起来。本章的内容为下一章介绍通用和高效的算法奠定了基础。作为示例，本章实现了一个文字编辑器的基本框架。
15.1 存储和处理数据
在处理数据量很大的问题之前，我们先来看一个简单的例子，它说明了解决一般数据处理问题的基本方法。Jack和Jill分别负责测量来往车辆的速度，结果用浮点数来表示。Jack是一个C语言的程序员，所以将测量值保存到一个数组中，而Jill将测量值保存到一个vector对象中。如果我们要在程序中使用他们的数据，该如何操作呢？
我们可以让Jack和Jill的程序将结果分别写到某个文件中，然后再从文件中读入数据。使用这种方法，我们的程序将与Jack和Jill所选用的数据结构和接口彻底无关。通常，这种程序之间的独立性是一种很好的特性，此时我们可以采用第10和11章中介绍的方法来获得输入数据，并利用vector<double>对象来进行计算。
但是，如果我们的任务不适合使用文件呢？假设我们必须每秒钟调用一次数据生成函数来获得一组新的数据。例如，下面的程序每秒都会调用Jack和Jill的函数来获得将要处理的数据：
上面这段代码假设我们要自己安排存储数据的空间，而且在用完这些数据之后要自己负责删除。另一个假设是我们不能重写Jack和Jill的代码，而且通常我们也不想这样做。
15.1.1 处理数据
显然，这个例子过于简单，但是它与很多实际问题并没有本质区别。如果我们能够很好地解决这个例子，就能够处理一大类通用的编程问题。问题的关键在于我们无法控制提供数据的程序以什么形式来存储数据。我们可以自由决定是沿用原有的数据格式，还是转换为另一种形式来进行存储和处理。
我们想要如何处理数据？排序？找出最大值？找出平均值？找出大于65的值？比较Jill和Jack的数据？处理需求多种多样，我们只能根据具体任务来编写处理程序。这里，我们主要是学习怎样处理数据，完成大量数据的计算。首先从简单的处理开始：找到数据集合中的最大值。我们可以将fct()函数中内容为“…处理…”的注释行替换为下面这段代码：
注意访问Jill数据时使用的语法(*jill_data)[i]。get_from_jill()函数返回一个指向vector对象的指针，即vector<double>*。为了获得数据内容，我们首先要解引用指针以获得vector——*jill_data，然后对其使用下标操作。然而，*jill_data[i]并不是我们想要的结果，因为运算符[]的优先级要高于运算符*，所以这个表达式的含义是*(jill_data[i])，必须在*jill_data外使用括号，结果即为(*jill_data)[i]。
试一试
如果可以修改Jill的代码，应该如何修改代码的接口来避免复杂的数据访问方法？
15.1.2 泛化代码
我们希望使用统一的方法来访问和处理数据，这样可以避免因为每次获得的数据格式不同而编写不同的处理代码。下面我们以Jack和Jill的代码为例，讨论如何让我们的代码更通用、更统一。
显然，我们对Jack和Jill的数据的处理方法很相似。但是两段代码有一些恼人的差异：jack_count和jill_data->size()，jack_data[i]和(*jill_data)[i]。我们可以通过使用引用来避免第二个不同之处：
这段代码已经非常接近处理Jack数据的代码了。接下来如何编写一个可以同时处理Jack和Jill数据的函数呢？方法有很多（参考习题3），出于通用性的考虑（这一点在接下来的两章中十分明显），我们选择下面这种基于指针的方法：
使用这个函数，数据处理代码可以改写为：
这段代码更加简洁：不仅省去了很多变量的定义，并且只出现了一段循环代码（在high()中）。如果我们想要得到最大值，只需查看*jack_high和*jill_high，例如：
注意，high()函数要求所处理的数据保存在一个数组中，所以“找出最大值”的算法返回的是指向数组元素的指针。
试一试
这段程序中有两个潜在的严重错误。其中一个会导致程序崩溃，另一个会导致high()函数返回错误的结果。下面将要介绍的通用技术会充分暴露出这两个错误，并给出系统的避免方法。现在我们只需要找出这两个错误，并提出修改意见。
high()函数的局限性在于只能处理某个特定的问题：
只能处理数组。vector的元素必须保存在数组中，但实际上数据的存储方式还有可能是list和map（见15.4节和15.6.1节）。
可以处理double类型的vector或数组，但是无法处理其他类型的元素，例如vector<double*>或char[10]。
只能找出最大值，无法完成其他简单的数据计算功能。
下面，我们探讨如何在更通用的数据集合上进行计算。
通过指针的方式来实现“找出最大值”的算法会带来一个意想不到的通用性：我们不仅可以找出整个数组或vector中的最大值，还可以找出数组或vector的某个部分的最大值，例如：
这里high1指向vecotr中前半部分的最大值，high2指向vecotr中后半部分的最大值。下面是这个结果的图示：
high()函数的参数是指针，这样的代码偏于底层，更容易引起错误。我们怀疑对于大多数程序员来说，找出vector中最大值的代码显然应像下面这样：
然而，这段代码失去了我们“偶然”从high()所获得的灵活性——我们不能用f?ind_highest()来查找vector某一部分中的最大值。我们实际上只是为了同时处理数组和vector才决定“摆弄指针”，但却意外地获得了某种灵活性。应该记住：代码泛化可以获得适用于多个问题的通用函数。
15.2 STL理念
C++标准库为处理数据序列提供了一个专门的框架，称为STL。STL是标准模板库（Standard Template Library）的简称。STL是ISO C++标准库的部分，它提供了容器（例如vector、list和map）和通用算法（例如sort、f?ind和accumulate）。因此我们可以称vector这类对象为STL或标准库的一部分。标准库的其他部分，例如ostream（第10章）和C风格的字符串处理函数（附录C.10.3），并不属于STL。为了更好地理解STL，我们首先考虑在处理数据时必须要解决的问题和对求解方案的理念。
计算过程包含两个主要方面：计算和数据。有时我们只关注计算方面，谈论if语句、循环、函数和错误处理等。有时我们关注的是数据，谈论数组、向量、字符串和文件等。然而，要完成真正的工作我们需要同时考虑计算和数据。如果对大量数据不进行分析、可视化和查找“感兴趣的部分”，则数据是无法理解的。相反，我们可以随心所欲地进行计算，但是只有与实际数据关联之后，才能避免枯燥乏味的无意义计算。而且，“计算部分”要优雅地与“数据部分”进行交互。
当谈起数据时，我们会想到很多类型的数据：数十个形状、数百个温度值、数千个日志记录、数百万个点、数十亿个网页等，即我们在讨论数据的容器、数据流等。特别地，我们并不是要讨论如何为一个小对象（例如，一个复数、一个温度读数或一个圆形等）选择最恰当的数值。对于这些类型，可以参看第9、11和19章。
考虑我们需要对“大量数据”进行的一些简单操作：
按照字典序排序。
根据姓名在电话本中找到对应的电话号码。
找出温度的最高值。
找出所有大于8800的值。
找出第一个值为17的元素。
根据单元编号对遥测记录进行排序。
根据时间戳对遥测记录进行排序。
找出第一个值大于“Petersen”的元素。
找出最大值。
找出两个序列的第一个不同之处。
计算两个序列中对位元素两两之积。
找出一个月中每天的最高气温。
在销售记录中找出最畅销的10件商品。
统计“Stroustrup”在网页中出现的次数。
计算各个元素之和。
注意，我们在讨论上述数据处理任务时，并没有提到数据如何存储。很显然，我们必须使用链表、向量、文件和输入流等来完成这些任务，但是我们不必了解这些数据存储（或收集）的细节，即可讨论如何对它们进行处理。重要的是这些值或对象的类型（元素类型），我们如何访问这些值或对象，以及要对它们进行什么操作。
这些任务非常常见，我们自然希望能编写代码简单高效地完成这些任务。与之相对，我们需要考虑的问题是：
数据类型（“数据种类”）变化万千。
数据集存储方法多到让人眼花缭乱。
我们想对数据集执行的任务也数量繁多。
为了尽可能降低这些问题的影响，我们希望编写的代码能够处理各种数据类型，处理各种数据存储方法，适用于各种处理任务。换句话说，我们想通过泛化代码来适应各种变化。我们要避免对每一个问题都从头开始寻找处理方法，那样会浪费大量的时间。
为了编写能够达到上述目的的代码，首先用更加抽象的方式来看待我们要对数据进行的处理工作：
收集数据并装入容器。
例如vector、list和数组。
组织数据。
用于打印；
用于快速访问。
提取数据。
通过索引（例如，第42个元素）；
通过值（例如，年龄字段是7的第一条记录）；
根据属性（例如，所有温度字段大于32小于100的记录）。
修改容器。
增加数据；
减少数据；
排序（根据某种标准）。
进行简单的数值运算（例如，将每一个元素乘以1.7）。
我们在完成上述任务时要避免陷入各种细节之中：各种容器间的差别、各种数据元素访问方法间的差别以及各种数据类型间的差别。如果我们能够做到这一点，就等于向编写简单高效的通用代码的目标迈出了一大步。
回顾前面几章介绍的编程工具和技术，我们（已经）可以编写功能相似但与数据类型无关的代码：
使用int与使用double基本没有差异。
使用vector<int>与使用vector<string>基本没有差异。
使用double类型的数组与使用vector<double>基本没有差异。
我们希望通过合理组织代码，实现只有当我们想要完成一些全新的任务时才需要编写新的代码。特别是，我们希望编写一些完成基本任务的代码，使得我们不必每次发现一种新的数据存储方式或数据解释方式时都重写整个程序。
在vector中查找一个值与在数组中查找一个值差异不大。
查找string时不区分大小写与区分大小写的差异不大。
绘制实验数据图时使用准确值与使用四舍五入值的差异不大。
拷贝文件与拷贝vector对象的差异不大。
根据上面的发现，我们希望编写的代码具有以下特点：
容易阅读。
容易修改。
规范。
简短。
快速。
为了简化编程工作，我们会：
使用统一的方式访问数据。
与数据存储方法无关；
与数据类型无关。
使用类型安全的方式访问数据。
便于遍历数据。
紧凑存储数据。
快速
读取数据；
增加数据；
删除数据。
对通用算法提供标准实现。
例如拷贝、查找、搜索、排序、求和等。
STL提供了上述功能以及更多。我们不应仅仅将它看作一个强大的功能库，更应看作一个兼顾灵活性与性能的函数库设计的典范。STL由Alex Stepanov设计，提供了一个作用于数据结构之上的通用、正确和高效的算法框架。其设计理念满足简单性、通用性和数学上的优雅。
除了使用设计理念和原则清晰的框架来处理数据之外，另一种策略是让程序员使用最基本的语言特性从头开始编写每个程序，并采用一些当时看起来不错的思想。这种方式费时费力，而且得到的程序代码往往非常糟糕，毫无章法可言，除作者之外的人很难理解，而且在其他场合能够复用的可能性微乎其微。
在介绍完STL的设计初衷和理念之后，我们会给出STL的一些基本定义，最后通过例子展示如何在实际应用中运用这些基本理念：编写更好的处理数据的代码，而且让编写过程更简单。
15.3 序列和迭代器
序列是STL中的核心概念。从STL的角度来看，数据集合就是一个序列。序列具有头部和尾部。我们可以对一个序列从头到尾进行遍历，对序列中的元素进行有选择的读写操作。我们利用一对迭代器来表示序列头部和尾部。迭代器（iterator）是一种可以标识序列中元素的对象。我们可以按照如下方式来看待一个序列：
这里的begin与end就是迭代器，它们标识了序列的头部和尾部。我们通常称STL的序列是“半开”的，因为由begin所标识的元素是序列的一部分，而迭代器end通常指向序列尾部之后的一个位置。在数学中，这种序列（区间）可以表示为[begin: end)。两个元素间的箭头表示如果有一个指向第一个元素的迭代器，那么我们就可以得到一个指向第二个元素的迭代器。
那么究竟什么是迭代器呢？迭代器是一个相当抽象的概念：
迭代器指向序列中的某个元素（或者序列末端元素之后）。
可以使用==和!=来对两个迭代器进行比较。
可以使用单目运算符*来访问迭代器所指向的元素。
可以利用操作符++来令迭代器指向下一个元素。
例如，如果p和q是两个指向同一个序列的迭代器：
标准迭代器的基本操作
p==q 当且仅当p和q指向序列中的同一个元素或都指向序列末端元素之后为真
p!=q !(p==q)
*p 表示p所指向的元素
*p=val 对p所指向的元素进行写操作
val=*p 对p所指向的元素进行读操作
++p 使p指向序列中的下一个元素或序列末端元素之后
很明显，迭代器的概念与指针（见12.4节）相关。实际上，指向数组中某一元素的指针就是一个迭代器。但是，许多迭代器不仅仅是指针。比如说，我们可以定义一个边界检查的迭代器，当试图使它指向[begin: end)之外时抛出一个异常。把迭代器作为一种抽象的概念而不是类型可以给我们带来很大的灵活性和通用性。本章和下一章将会举例说明这一点。
试一试
编写一个函数void copy(int* f1, int* e1, int* f2)，该函数把[f1: e1)定义的int型数组复制到数组[f2: f2+(e1-f1))中。注意只能使用上面所提到的迭代器操作（不能用索引）。
我们可以利用迭代器来实现代码（算法）与数据的连接。程序编写人员了解迭代器的使用方法（并不需要了解迭代器实际是如何访问数据的），数据提供者向用户提供相应的迭代器而不是数据存储的细节信息。这样得到的是一个简单的程序结构，而且使算法和容器之间保持了很好的独立性。正如Alex Stepanov所说：“STL算法和容器可以共同完成很强大的功能，而这却是因为它们根本不知道对方的存在。”但是，它们都知道由一对迭代器所定义的序列。
换句话说，我们的代码不再需要知道存储和访问数据的不同方法，它只需要对迭代器有一定的了解。另一方面，作为数据提供方，我们不再需要为不同的用户分别编写代码，而只需要为我们的数据配备好合适的迭代器。实际上，最简单的迭代器只是由*、++、==、!=等操作所定义的，这无疑会令它既方便又快速。
STL框架包含大概10种容器和60种由迭代器相连接的算法（参见第16章）。另外，许多组织和个人都在开发符合STL风格的容器和算法。STL可能是目前最著名的泛型编程的例子（见14.3.2节）。只要你了解了它的基本概念和一些简单的例子，就可以很容易掌握其他相关的内容。
15.3.1 回到实例
下面我们来看看如何使用STL来描述问题“查找序列中的最大元素”：
注意我们去掉了用来存储当前最大元素的变量h。当我们不能确定序列中元素的类型时，使用-1来完成初始化看起来非常随意和奇怪。这是因为它确实非常随意和奇怪！其中还隐藏着潜在错误：在我们的例子中-1能奏效仅仅是因为恰好不会存在负的速度。我们要记住像-1这样的“魔数”是非常不利于程序的维护的（见4.3.1节、7.6.1节、10.11.1节等）。在本例中，我们可以看到它还会限制函数的用途，并意味着我们对问题求解方案还没有形成一个比较全面的认识，也就是说，“魔数”是一种偷懒的表现。
注意这里的high()可以被用于所有可以使用<进行比较的元素类型。比如说，我们可以利用high()来查找vector<string>中按字典序最靠后的字符串（见习题7）。
high()模板函数可以用于任何由一对迭代器定义的序列。举例来说，我们可以严格复制例程：
这里的两个调用中，high()的Iterator模板参数的类型为double*。除了（最终）确保high()被正确实现外，这和我们之前的例子没有任何区别。更准确地说，所运行的代码并没有什么不同，但在代码的通用性上却有很大的区别。high()的模板版本适用于任何由一对迭代器所定义的序列。在进一步了解STL规范细节和所提供的能免除我们编写常见繁琐代码之苦的算法之前，我们先来集中了解数据元素集合的存储方法。
试一试
在我们的程序中有一个严重的错误。请找到并修改它，提出一种针对这种问题的通用解决方法。