摘要

Programming: Principles and Practice Using C++, Second Edition

算法和映射

理论上，实践是简单的。

——Trygve Reenskaug

本章将完成我们对STL基本思想的介绍以及对STL所提供工具的纵览。在本章中，我们主要关注算法。我们的主要目的是给你介绍一些最有用的算法，它们能够节省你大量时间，即使达不到以月计，也能达到以天计。每个算法都将通过其使用示例和支持的编程技术来介绍。本章的另一个目的是提供足够的工具，令你在需要标准库和其他库之外的特性时有能力自己编写优雅高效的算法。另外，本章还将介绍三种容器：map、set和unordered_map。

16.1　标准库算法

标准库大约提供了80种有用的算法。所有算法都至少在某些场景下对某些人是有用的；我们将在本章着重介绍其中一些对很多人通常都有用的算法以及一些对某些人极为有用的算法：

挑选的标准算法

r = f?ind(b,e,v) r指向[b:e)中v首次出现的位置

r = f?ind_if(b,e,p) r指向[b:e)中令p(x)为true的第一个元素x

x = count(b,e,v) x为v在[b:e)中出现的次数

x = count_if(b,e,p) x为[b:e)中满足p(x)为true的元素的个数

sort(b,e) 用<运算符对[b:e)排序

sort(b,e,p) 用谓词p对[b:e)排序

copy(b,e,b2) 将[b:e)拷贝至[b2:b2+(e-b))；b2之后应有足够的空间用于存储元素

unique_copy(b,e,b2) 将[b:e)拷贝至[b2:b2+(e-b))；不拷贝相邻的重复元素

merge(b,e,b2,e2,r) 将有序序列[b2:e2)和[b:e)合并，并放入[r:r+(e-b)+(e2-b2))之中

r = equal_range(b,e,v) r是有序范围[b:e)的一个子序列，且其中所有元素值均为v，本质上是通过二分搜索查找v

equal(b,e,b2) [b:e)和[b2:b2+(e-b))的所有元素对应相等？

x = accumulate(b,e,i) x是将i与[b:e]中所有元素进行累加的结果

x = accumulate(b,e,i,op) 与accumulate类似，但用op进行“求和”运算

x = inner_product(b,e,b2,i) x是[b:e)与[b2:b2+(e-b))的内积

x = inner_product(b,e,b2,i,op,op2) 与inner_product类似，但用op和op2取代内积的+和*

 

默认情况下，相等比较用==进行，而序则是基于<（小于）的。标准库算法可在<algorithm>找到。如果想获得更多信息，请参考附录C.5和16.2～16.5节中列出的资源。这些算法接受一个或几个序列。一个输入序列由一对迭代器定义，一个输出序列由一个指向首元素的迭代器定义。通常，一种算法可以由一个或多个操作参数化，这些操作可以定义为函数对象或函数。这些算法通常会通过返回输入序列尾来报告“失败”。例如，如果f?ind(b,e,v)未找到v，则返回e。