每周技巧 #227：小心空容器和无符号算术

本文翻译自 Abseil 官网的 Tip of the Week #227: Be Careful with Empty Containers and Unsigned Arithmetic。

原文最初作为 TotW #227 发布于 2023 年 11 月 16 日。

作者：James Dennett

更新于 2024 年 3 月 11 日。

快捷链接：abseil.io/tips/227

基于索引的循环（仍有用途）

现代 C++ 代码在有了基于范围的 for 循环之后，使用基于索引的 for 循环少了很多，但仍有一些时候我们需要在迭代时使用索引。并行迭代多个容器是一种情况；另一种是想处理单个容器中的多个相邻元素。本技巧会讨论第二种场景中的陷阱。

看似合理的代码

先看一段可能正确的代码：

1
2
3

for (int64_t i = 0; i < v.size() - 1; ++i) {
  ProcessPair(v[i], v[i+1]);
}

这段代码明智地在调用 ProcessPair() 前小心检查了有效索引，那为什么我们说它只是“可能”正确呢？一个细心的单元测试（或几乎任何 fuzz test）都会覆盖 v 为空的情况。如果 for 循环周围的代码确保这种情况下永远不会到达该循环，那一切都好。但如果我们用空的 v 执行循环，C++ 就会给我们制造麻烦。

无符号类型帮倒忙

回忆一下，风格指南警告我们不要在 C++ 中使用 unsigned 类型。风格指南还说：

由于历史偶然，C++ 标准也使用无符号整数来表示容器大小；许多标准委员会成员认为这是错误，但到现在实际上已经不可能修复。

（强调为原文所有）

仔细看可以发现，我们的例子正好踩中了风格指南讨论的问题。检查是否有有效的 v[i] 和 v[i+1] 元素时，我们看似正确地检查 i 是否小于 v.size() - 1，因为两个元素都必须有效。然而，对于空容器，v.size() 是零（到目前为止没问题！），但因为 v.size() 的类型是无符号的，当我们从零减一时，得到的不是 -1，而是该类型的最大值。于是检查 i 是否小于 v.size() - 1 对任何小的 i 都会求值为 true，代码因此会用越界索引访问 v，产生未定义行为。

应该如何修复？

有趣的是，如果让代码更直接地表达意图，问题就消失了。

“更直接地表达意图”是什么意思？这里的意图是什么？循环条件的目的，是确保用于索引 v 的 i 和 i + 1 都有效。

鉴于 C++ 中索引从零开始，我们通过检查 i < v.size() 来测试某个（非负）索引 i 对容器是否有效。同时检查两个索引是否有效是冗余的（虽然如果愿意也可以这么做）：如果 i + 1 有效，那么我们知道 i 也有效（因为这里 i 永远不为负）。"i + 1 有效" 直接翻译成 C++ 就是 i + 1 < v.size()。原代码 i < v.size() - 1 并不能如此直接地翻译成关于索引有效性的陈述。

重写后的代码 i + 1 < v.size() 看起来几乎和 i < v.size() - 1 一样，但关键区别是我们从不做减法，因此避免了回绕成巨大正值的危险。我们是否把这个风险换成了计算 i + 1 时的溢出风险？只有当 i 已经是其类型（int64_t）最大值时才会如此，所以我们是安全的。这种差异有时会被表述为：int64_t 的常见有用值距离溢出很远，而对于 uint64_t 这样的无符号类型，极常见的值 0 是该类型最小值，因此更容易无意中回绕。

修复后的代码，不怕 fuzz

做出这个小改动后，我们现在健壮的代码如下：

1
2
3

for (int64_t i = 0; i + 1 < v.size(); ++i) {
  ProcessPair(v[i], v[i+1]);
}

索引 v 的操作明显安全，不需要去更远处查看 v 是否可能为空。

现在我们可以放心让 fuzzer 跑在修复后的代码上，并愉快地感到这个 for 循环没有 bug 且对 reviewer 友好。

注意：这只是编写该循环的一种（健壮）方式；还有很多其他写法。

总结

虽然修复没有改变多少源代码字节，但它触及了多个想法：

• 正如风格指南所说，警惕 C++ 中无符号类型上的算术。
• 记住 container.size() 产生无符号类型。
• 偏好可以尽可能局部验证正确性的代码。
• 尽量让代码尽可能直接地对应底层意图。