摘要
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才决定“摆弄指针”，但却意外地获得了某种灵活性。应该记住：代码泛化可以获得适用于多个问题的通用函数。
