C++ Primer 算法概述

欢迎阅读我的【C++Primer】专栏

专栏简介：本专栏主要面向C++初学者，解释C++的一些基本概念和基础语言特性，涉及C++标准库的用法，面向对象特性，泛型特性高级用法。通过使用标准库中定义的抽象设施，使你更加适应高级程序设计技术。希望对读者有帮助！

在这里插入图片描述

泛型算法

顺序容器只定义了很少的操作:在多数情况下,我们可以添加和删除元素、访问首尾元素、确定容器是否为空以及获得指向首元素或尾元素之后位置的迪代器。

我们可以想象用户可能还希望做其他很多有用的操作:查找特定元素、替换或删除一个特定值、重排元素顺序等。

标准库并未给每个容器都定义成员函数来实现这些操作,而是定义了一组泛型算法(generical gorithm):称它们为“算法“是因为它们实现了一些经典算法的公共接口,如排序和搜索;称它们是“泛型的“,是因为它们可以用于不同类型的元素和多种容器类型(不仅包括标准库类型,如vector或list,还包括内置的数组类型),以及我们将看到的,还能用于其他类型的序列。

10.1概述

大多数算法都定义在头文件algorithm中。标准库还在头文件nuameric中定义了一组数值泛型算法。

一般情况下,这些算法并不直接操作容器,而是遍历由两个迭代器指定的一个元素范围来进行操作。通常情况下,算法遍历范围,对其中每个元素进行一些处理。例如,假定我们有一个int的vector,希望知道vector中是否包含一个特定值。回答这个问题最方便的方法是调用标准库算法find:

int val=42;//我们将查找的值
// 如果在vec中找到想要的元素,则返回结果指向它,否则返回结果为vec.cend()
auto result=find(vec.cbegin(),vec.cend(),val);
//报告结果
cout<<E"The vle"<<Val<<(result==vec.cend()?"snotpresent":"sPresent")<<endl;

传递给find的前两个参数是表示元素范围的迭代器,第三个参数是一个值。find将范围中每个元素与给定值进行比较。它返回指向第一个等于给定值的元素的迭代器。如果范围中无匹配元素,则find返回第二个参数来表示搜索失败。因此,我们可以通过比较返回值和第二个参数来判断搜索是否成功。我们在输出语句中执行这个检测,其中使用了条件运算符来报告搜索是否成功。

由于find操作的是迭代器,因此我们可以用同样的find函数在任何容器中查找值。例如,可以用find在一个string的1ist中查找一个给定值:

string val= "a value";//我们要查找的值
//此调用在1ist中查找string元素
auto result=find(lst.cbegin(),lst.cend(),val);

类似的,由于指针就像内置数组上的迭代器一样,我们可以用find在数组中查找值:

int ia[] = {27,210,12,47,109,83};
int val = 83;
int*result = find(begin(ta),end(ia),val);

此例中我们使用了标准库begin和end函数来获得指向1a中首元素和尾元素之后位置的指针,并传递给find。

还可以在序列的子范围中查找,只需将指向子范围首元素和尾元素之后位置的迭代器(指针)传递给find。例如,下面的语句在ia[1]、ia[2]和ia[3]中查找给定元素:

// 在从ia[1]开始,直至(但不包含)ia[4]的范围内查找元素
auto result = find(ia+1,ia+4,val);

算法如何工作

为了弄清这些算法如何用于不同类型的容器,让我们更近地观察一下find。find的工作是在一个未排序的元素序列中查找一个特定元素。概伊上,find应执行如下步骤:

访问序列中的首元素。
比较此元素与我们要查找的值。
如果此元素与我们要查找的值匹配,find返回标识此元素的值。
否则,find前进到下一个元素,重复执行步骤2和3。
如果到达序列尾,find应停止。
如果find到达序列末尾,它应该返回一个指出元素未找到的值。此值和步骤3返回的值必须具有相容的类型。

这些步骤都不依赖于容器所保存的元素类型。因此,只要有一个迭代器可用来访问元素,find就完全不依赖于容器类型(甚至无须理会保存元素的是不是容器)。

迭代器令算法不依赖于容器

在上述find函数流程中,除了第2步外,其他步骤都可以用迭代器操作来实现:利用迭代器解引用运算符可以实现元素访问;如果发现匹配元素,find可以返回指向该元素的迭代器;用迭代器递增运算符可以移动到下一个元素;尾后迭代器可以用来判断find是否到达给定序列的末尾;find可以返回尾后迭代器来表示未找到给定元素。

但算法依赖于元素类型的操作

虽然迭代器的使用令算法不依赖于容器类型,但大多数算法都使用了一个(或多个)元素类型上的操作。例如,在步骤2中,find用元素类型的一运算符完成每个元素与给定值的比较。其他算法可能要求元素类型支持<运算符。不过,我们将会看到,大多数<算法提供了一种方法,允许我们使用自定义的操作来代替默认的运算符。