C++程序设计：原理与实践（进阶篇）16.9　容器算法

16.9　容器算法

到目前为止，我们都是用元素序列来定义标准库算法。序列用迭代器指明：一个输入序列定义为一对迭代器[b:e)，其中b指向序列首元素，e指向序列尾元素之后位置（见15.3节）。一个输出序列简单地用一个迭代器指定，该迭代器指向序列的首元素。例如：

这种方式很好、也很通用。例如，我们可以排序vector的一半内容：

但是，指明元素范围有些啰嗦，而大多数情况下，我们需要排序整个vector而不是一半。因此，大多数情况下，我们希望这样编写代码：

标准库未提供sort()的这种变形，但我们可以自己定义：

实际上，我们发现这个版本如此有用，因此将其加入到了std_lib_facilities.h中。

像这样可以很容易地处理输入序列，但为了保持简单性，我们倾向于还是保持返回类型为迭代器。例如：

Iterator<C>自然是C的迭代器类型。

简单练习

在每一步操作（每个练习）之后打印vector。

1. 定义一个struct Item{string name; int iid; double value; /*…*/};，创建一个vector<item>类型的对象vi，读取来自一个文件中的10个Item填入vi。

2. 按name对vi排序。

3. 按iid对vi排序。

4. 按value对vi排序，按value的降序打印（即先打印最大的值）。

5. 插入Item("horse shoe", 99, 12.34)和Item("Canon S400", 9988, 499.95)。

6. 按name指定两个Item，从vi中删除（擦除）它们。

7. 按iid指定两个Item，从vi中删除（擦除）它们。

8. 采用list<Item>而不是vector<Item>重复上述练习。

现在尝试map：

1. 定义一个map<string, int>类型的对象msi。

2. 插入10个（名字，值）对，例如，msi["lecture"] = 21。

3. 输出（名字，值）对到cout，输出的格式由你自行定义。

4. 删除msi中的（名字，值）对。

5. 编写一个函数，该函数能够从cin中读取值对并将其存入msi之中。

6. 从输入读入10个值对，并将它们存入msi中。

7. 将msi的元素写入cout。

8. 输出msi中（整型）数值的总和。

9. 定义一个map<int,string>类型的对象mis。

10. 将msi中的值存入mis；即，如果msi的元素为（"lecture", 21），则mis应具有元素（21, "lecture"）。

11. 输出mis的元素到cout。

更多vector练习：

1. 从一个文件中读入一些浮点值（至少16个），并将其存入一个vector<double>类型的对象vd之中。

2. 输出vd到cout。

3. 定义一个vector<int>类型的对象vi，且vi具有的元素数量与vd相同；将vd的元素拷贝至vi之中。

4. 输出（vd[i], vi[i]）值对到cout，每行输出一个值对。

5. 输出vd元素的总和。

6. 输出vd元素总和与vi元素总和的差值。

7. 标准库中有一个称为reserve的算法，接受一个序列（由一对迭代器定义）作为参数；反转vd，并输出vd到cout。

8. 计算vd中元素的平均值，并将结果输出。

9. 定义一个vector<double>类型的对象vd2，并将vd中所有值低于（小于）平均值的元素拷贝至vd2之中。

10. 对vd进行排序，并输出vd。

思考题

1. 有用的STL算法的例子有哪些？

2. f?ind()有什么用途？至少给出五个例子。

3. count_if()有什么用途？

4. sort(b,e)的排序标准是什么？

5. STL算法如何将一个容器作为其输入参数？

6. STL算法如何将一个容器作为其输出参数？

7. STL算法通常如何表示“未找到”或“失败”？

8. 什么是函数对象？

9. 函数对象与函数之间有哪些区别？

10. 什么是断言？

11. accumulate()有什么用途？

12. inner_product()有什么用途？

13. 什么是关联容器？至少给出五个例子。

14. list是一个关联容器吗？为什么不是？

15. 二叉树的基本序性质是什么？

16. 对于一棵树而言，对其进行平衡意味着什么？

17. map的每一元素占用了多少空间？

18. vector的每一元素占用了多少空间？

19. 当可用一个（有序的）map时，为什么我们还会使用unordered_map？

20. set与map有何区别？

21. multi_map与map有何区别？

22. 当我们能够“仅仅编写一个简单的循环”时，为什么还应使用copy()算法？

23. 什么是二分搜索？

术语

accumulate() 　f?ind_if() searching（搜索）

algorithm（算法） 　function object（函数对象） sequence（序列）

application：()（应用：()） 　generic（泛型） set

associative container（关联容器） 　hash function（哈希函数） sort()

balanced tree（平衡树） 　inner_product() sorting（排序）

binary_search() 　lambda stream iterator（流迭代器）

copy() 　lower_bound() unique_copy()

copy_if() 　map unordered_map

equal_range() 　predicate（断言） upper_bound()

f?ind()

习题

1. 浏览本章所有内容，并完成所有你未完成的“试一试”练习。

2. 找到一个可靠的STL文档资源，列举所有标准库算法。

3. 实现count()并对其进行测试。

4. 实现count_if()并对其进行测试。

5. 如果我们不能通过返回end()表示“未找到”，那应该怎么办？重新设计并实现f?ind()和count()，它们接受指向第一个和最后一个元素的迭代器。将新实现与标准版本进行比较。

6. 在16.6.5节的水果例子中，我们将Fruit对象拷贝至set中。如果我们不希望拷贝Fruit对象呢？我们可以用set<Fruit *>作为替代。然而，为了这么做，我们还需要为这个集合定义一个比较操作。通过set<Fruit *, Fruit_comparison>实现水果例子，并讨论两种实现之间的差别。

7. 为vector<int>编写一个二分搜索函数（不使用标准函数）。你可以选择任何你喜欢的接口。对该函数进行测试。你如何确认你的二分搜索是正确的？现在为list<string>编写一个二分搜索函数。对该函数进行测试。这两个二分搜索函数的相似程度如何？如果你不了解STL，你觉得这两个二分搜索函数的相似程度会如何？

8. 修改16.6.1节中词频的例子，使它能够按频率顺序输出（而不是按字典序）。一个例子是，应该输出行3: C++而不是C++:3。

9. 定义一个Order类，该类包含（顾客）姓名、地址、数据与vector<Purchase>等成员。Purchase是一个包含（产品）name、unit_price和count等成员的类。定义一种将Order内容写入文件以及从文件中读入Order内容的机制。构建一个至少包含10个Order的文件，将该文件内容读入一个vector<Order>中，按（顾客）姓名进行排序，然后写回文件。构建另一个至少包含10个Order的文件，其中大约1/3内容与第一个文件相同，将文件内容读入一个list<Order>中，按（顾客）地址进行排序，然后写回文件。用std::merge()将两个文件合并，写入另一个文件。

10. 计算上一题中两个文件中订单的总价值。一个Purchase的价值为unit_price*count。

11. 设计一个GUI接口能输入Order信息写入文件。

12. 设计一个GUI接口能查询Order文件；例如，“查找Joe的所有订单”，“查询文件Hardware中订单的总价值”以及“列出文件Clothing中所有订单”。提示：首先设计一个非GUI接口；然后，在此基础上实现GUI接口。

13. 编写一个程序，该程序能够对文本文件进行“清理”以便结果能用于一种单词查询程序；具体来说，用空白符替换标点符号，将单词转换为小写形式，用do not（等等）替换don’t，以及去除复数形式（例如，ships变为ship）。不要野心太大。例如，确定复数形式通常而言是很困难的，因此如果你同时找到了单词ship和ships，那么你简单删除s就可以了。将程序用于一个真实的至少包含5000个单词的文本文件（例如一篇研究论文）。

14. 编写一个程序（使用上一题程序的输出作为输入），该程序能够回答诸如“文件中单词ship出现了多少次？”“哪一个单词出现最频繁？”“文件中最长的单词是什么？”“哪个单词最短？”“列出所有以s开头的单词”“列出所有包含四个字符的单词”之类的问题。

15. 为上一题的程序设计一个GUI接口。

附言

STL是ISO C++标准库中关于容器和算法的部分。它提供了非常通用、灵活和有用的基本工具。它能够节省我们的很多工作：重新发明轮子可能是有趣的，但毫无效率可言。我们应该优先选用STL容器和基本算法，除非我们有充分的理由不这样做。而且，STL是泛型编程的一个例子，它展示了具体问题及具体解决方案是如何构成一个有用且通用的工具集的。如果你需要处理数据——大部分程序的确需要——STL提供了一个例子、一些思想以及一种有用的方法。