C++程序设计：原理与实践（进阶篇）16.2　最简单的算法f?ind()

16.2　最简单的算法f?ind()

f?ind()可能是最简单但又很有用的算法，它在一个序列中查找一个给定值：

让我们看看f?ind()的定义。你自然可以无须了解f?ind()的确切实现细节就使用它——实际上，我们已经在前面的章节中使用过f?ind()了（例如15.6.2节）。但是，f?ind()的定义展示了很多有用的设计思想，因此了解其实现是有价值的。

首先，f?ind()对一个序列进行操作，这个序列由一对迭代器定义。它在半开区间[f?irst: last)中查找给定值val。返回结果是一个迭代器，要么指向val在序列中首次出现的位置，要么就是last。在STL中，返回指向尾后位置的迭代器（last）是最常用的报告“未找到”的方法。因此，我们可以像下面这样使用f?ind()：

在本例中，序列照例由一个容器（STL vector）中所有元素组成。我们检查返回的迭代器是否指向序列的结束，来判断是否找到了想要的值。返回值类型与迭代器参数的类型是一致的。

为了避免明确指明返回类型，我们使用了auto。若对象的“类型”定义为auto，则它从其初始化器获取类型。例如：

类型说明符auto在泛型编程中特别有用，例如在f?ind()中明确指明真实类型（本例中是vector<int>::iterator）是很烦人的。

我们现在已经知道如何使用f?ind()了，从而也了解了如何使用那些采用相同规范的算法。在学习更多用法和更多算法之前，让我们再进一步观察f?ind()的定义：

当你第一次看这段代码时，你会注意代码中的循环吗？我们不会。这个循环真的非常简洁、高效，并且直接表达了基础算法。然而，可能在看了若干例子之后，你才会注意到这个循环。让我们用比较常见的方式重写f?ind()，并比较两个版本：

这两个定义在逻辑上是等价的，而且一个真正优秀的编译器能够为它们生成相同的代码。然而，现实中很多编译器都没有那么好，它们无法消除额外的变量（p），也不能重排代码以使所有条件测试都在同一位置执行。我们为什么要为此担忧并加以解释呢？一部分原因在于f?ind()的第一个版本（也是应该优选的版本）的风格已变得十分流行，我们必须学会它以阅读他人编写的代码；另一部分原因是，对于用来处理大量数据且被频繁使用的小函数而言，性能是十分重要的。

试一试

你确定这两个定义在逻辑上是等价的吗？你是如何确定的？试着给出两者等价的论证。然后，用一些数据测试这两个定义。著名的计算机科学家Don Knuth曾经说，“我只是证明了算法的正确性，并没有对它进行测试”。即使是数学证明也可能包含错误。为了证明你的观点，推理和测试缺一不可。

16.2.1　一些一般的应用

f?ind()算法是通用的。这意味着它能用于不同的数据类型。实际上，f?ind()算法的通用性包括两个方面；它能用于：

任何STL风格的序列；

任何元素类型。

下面是一些例子（如果你感到困惑，请参考15.4节中的图表）：

在此例中，f?ind()使用了vector<int>::iterator实现遍历操作；即，++f?irst中的++只是将指针移动到内存中的下一个位置（存储了vector的下一个元素），而*f?irst中的*对该指针进行解引用。迭代器比较（f?irst != last）就是指针的比较，而值的比较（*f?irst != val）就是比较两个整数。

让我们再尝试list：

在本例中，f?ind()使用了list<string>::iterator实现遍历操作。用到的运算符都具有符合要求的喻意，因此代码逻辑与vector<int>的例子相同。但实现是很不同的；即，++f?irst中的++简单地顺着元素的Link部分中的指针指向list下一元素的存储位置，而*f?irst中的*将获得Link的值部分。迭代器比较（f?irst != last）是Link *指针的比较，而值的比较（*f?irst != val）则是使用string的!=运算符比较两个string。

因此，f?ind()是极为灵活的：只要我们遵循了迭代器的简单规则，就可以用f?ind()在我们能想象的任何序列和能定义的任何容器中查找元素。例如，我们可以使用f?ind()在15.6节中定义的Document中查找一个字符：

这种灵活性是STL算法的标志性特点，也使得它们远比初次接触的人所能想象的更为有用。