复合数据：总结与挑战

摘要

本课结束本课程的第六单元，这一单元专讲复合数据。本课重建从带下标的序列通向记录的概念链，途经会增长的序列、算法的代价、查找与排序以及表格；把其中适用于任何语言的内容与 C++ 特有的内容区分开；汇总本单元的未定义行为，连同库会拦下什么、检测器会拦下什么、以及什么谁也不会指出；在结业测评中重复入门测评的各项技能；最后给出六道综合整个单元的挑战题。

学习目标

用合适的类型（数组、向量、表格或记录）表示集合与实体，并根据数据的形态说明选择的理由。
用正确的算法处理集合：或者亲手编写并用不变式论证，或者取自库并遵守其前置条件。
通过数出算法的主导操作来估计它的代价，并用测量来检验这一估计。
识别本单元的未定义行为（越界访问、失效的引用、溢出的中点、违反库的前置条件），并改写程序使之不再出现。
在本单元所学的内容中，区分适用于任何语言的内容与 C++ 特有的内容。

本单元的收获

本单元的目标是教会表示数据的集合，并用基本算法处理它们，同时估计其代价。这一目标已经达成，所依靠的只是导言声明为已知的内容：带不变式的循环、函数及其传递方式、整数的算术。记录得分的程序曾用五个变量而对多出的数据默不作声，现在用一个向量来写；关于并列的问题，若检查所有数对，一百万个数据要花上几分钟，现在通过排序后比较相邻元素来回答。

数组

数组一课介绍了 std::array，即大小固定的序列，它的下标从零开始计数，因为下标就是偏移量。这一课确立了：下标 $i$ 有效，当且仅当 $0 \leq i < n$ ；每次用 [] 访问都要求用循环的不变式证明这一点；越界访问是未定义行为，而 .at() 把它变成确定的终止；它还引入了 std::size_t，并教会阅读 C 风格数组。

向量

向量一课介绍了用 push_back 增长的序列，并确定了何时必须保存一列数据：只要对某个数据的某项决定依赖于后面的数据。它确立了规范遍历（累积、过滤、变换）及其不变式和在库中的简写（std::ranges::count、std::ranges::max、std::ranges::fold_left），向量的传递规则，以及大小与容量的区别；由这一区别得出 push_back 平均为常数的代价，以及向量搬家时引用的失效。

算法的代价

算法的代价一课加上了第二个问题：在最坏情况下数出主导操作，按增长阶分类，预测 $n$ 加倍的效果，并用 std::chrono::steady_clock 测量，要开启优化、不带检测器、重复多次并取中位数。

查找与排序

查找与排序一课用不变式和度量论证了二分查找；编写了选择排序和插入排序，并数出它们的比较次数；介绍了范围库的算法及其有序这一前置条件，而这个条件没有人检查；并计算了何时先排序再查找更划算。

表格

表格一课按行和按列遍历表格，计算了转置和矩阵的乘积及其立方阶的代价，在不越出边缘的情况下统计相邻格，并用下标 $i \cdot \mathit{columns} + j$ 把表格保存在扁平向量中。

记录

记录一课用 struct 取代了并行数组，每个字段都有初始值；它教会传递和返回记录，借助投影按某个字段对记录排序和查找，用 std::ranges::stable_sort 按多个关键字排序，以及用包含记录和向量的记录为问题建模。