跳至内容
Topos Uranos
中文 (中国)

数组

摘要

到目前为止，本课程中的每个数据都住在自己的变量里，有自己的名字；但许多同类型的数据，比如一周的气温，如果每个都有不同的名字，就无法用循环遍历。本课介绍本课程的第一种数据结构，即带下标的序列：同类型的元素，存放在内存中相邻的位置上，从零开始编号。在现代 C++ 中，它用 std::array 来写，其大小在编译时就已固定。本课研究它的声明、下标的类型 std::size_t 以及两种遍历方式：用下标遍历和用范围 for 遍历。本课确立支配整个单元的规则：下标有效，当且仅当它介于 0 与大小减一之间；在循环中的每次访问时，这种有效性都要用不变式来论证。本课展示规则不成立时会发生什么，那就是未定义行为，并把 [] 与带检查的访问 .at() 相比较。最后介绍 C 风格数组，以便阅读别人的代码。

学习目标

  1. 用下标和范围 for 声明、初始化并遍历 std::array。
  2. 借助循环不变式，论证下标在每次访问时都处于边界之内。
  3. 区分标准不检查的 [] 访问与总是受到检查的 .at() 访问，并说明各自适用的场合。
  4. 阅读使用 C 风格数组的代码，并说明它们相对于 std::array 的缺点。

带下标的序列

许多数据，一个名字

若用到目前为止所学的内容来计算一周气温的平均值，就需要七个变量，monday、tuesday，依此类推直到 sunday，以及一个七项之和。若是一年的气温，就要 365 个，而且没有任何循环能遍历它们，因为在循环体中，一个变量的名字始终是同一个。所缺少的是整个集合的一个名字和每个元素的一个编号，使编号可以是由循环推进的变量。

带下标的序列正是这样的东西：由 nn 个同类型元素组成的集合，这些元素一个接一个地存放在内存中相邻的存储单元里，并由各自的位置来指定，这个位置称为下标。数学早已熟悉这一对象：有限数列 (a0,a1,…,an−1)(a_0, a_1, \dots, a_{n-1})，其中 aia_i 表示位于第 ii 个位置的元素；或者向量，如代数与几何 I 课程中的向量。在 C++ 中写作 a[i]，下标可以是任何整数表达式：2、i、i + 1。

为什么从零开始

在 C++ 中，和当今大多数语言一样，第一个元素的下标是 0，最后一个元素的下标是 n−1n - 1。原因不是任意的约定，而是找到元素的方式：如果序列从某个内存地址开始，并且每个元素占 ss 个字节，那么下标为 ii 的元素就位于起始地址加上 i⋅si \cdot s 处。因此，下标是一个偏移量：从第一个元素开始需要跳过的元素个数。第一个元素与它自身相距零次跳跃。

由此得出支配整个本单元的定义：在含有 nn 个元素的序列中，下标 ii 有效，当且仅当 0≤i<n0 \leq i < n。右边的不等式是严格的，它是处理序列时最常见错误的根源，即差一错误：写成了 i≤ni \leq n，而应当写 i<ni < n；或者从 1 开始，而应当从 0 开始。等于 nn 的下标指的不是最后一个元素，而是紧跟在序列之后、并不属于它的那个存储单元。