C++程序设计:原理与实践(进阶篇)16.2 最简单的算法f?ind()-阿里云开发者社区

开发者社区> 华章出版社> 正文

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算法的标志性特点,也使得它们远比初次接触的人所能想象的更为有用。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:

华章出版社

官方博客
官网链接