使用索引还是迭代器? 从 0 开始还是从 1 开始? 左闭右开还是左开右闭? 亦或是全闭/全开区间? 索引产生的微小错误让人混乱? (这也叫差一错误 (off-by-one error)). 如果你曾为这些问题困扰, 那么元素间索引的思想或许可以帮助你.
本文的灵感来自于 Nelson Elhage 的博客.
数组是什么? 如果你熟悉主流编程语言, 你可能给出如下答案:
+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+
方框内的是索引, 从 0 开始. 也有从 1 开始的索引方式, 这里为了方便, 用最常见的 0 开始. 以下称这种方法为普通索引方法.
元素间索引使用如下的方式索引
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+
0 1 2 3 4 5 6
每个索引指向元素之间的空隙. 这样, 原来用单个索引表示的元素现在用一个二元组表示. 例如, 原来的 A[0] 现在变成了二元组 (0, 1).
这样有什么好处呢? 显而易见的一个好处是易于表示范围.
范围的表示
假设我们用 X 表示范围:
0 1 2 3 4 5
+---+---+---+---+---+---+
| | X | X | X | | |
+---+---+---+---+---+---+
0 1 2 3 4 5 6
用普通索引方式会产生多种表示:
- 左闭右开区间
[1, 4). - 全闭区间
[1, 3]. - 左开右闭区间
(0, 3]. - 全开区间
(0, 4). - 索引加长度有序对
(1, 3). - 反向索引. 数组最后一个元素的索引是 -1, 然后向前递减, 继而再次引申出使用负数的前面几种表示.
- …
这么多的选择, 如果不始终坚持一种写法, 很容易引发错误. 即使始终坚持一种写法, 也可能由于不符合直觉引发错误. 一般, 我们选择左闭右开的写法, 后面会对这一选择的原因进行讨论.
对于元素间索引, 如果要表示范围, 答案是唯一的: (1, 4). 而且, 它是相当符合直觉的. 不会在写大量操作索引的代码的时候突然懵了: 最左边的元素被包含吗? 最右边的元素被包含吗?
这种方式表示范围还有一个好处是易于表示区间之间的关系. 例如, 对于用元素间索引表示的两个区间 A: (a, b), B: (c, d), 有六种关系:
- B 在 A 的右边且和 A 不重叠. 即满足
b <= c. - B 在 A 的左边且和 A 不重叠. 即满足
d <= a. - B 在 A 的左边且和 A 重叠.
a < c < b < d. - B 在 A 的右边且和 A 重叠.
c < a < d < b. - B 包含 A.
c <= a < b <= d. - A 包含 B.
a <= c < d <= b.
只要画一下图, 上述结果很容易导出, 而且导出的结果也很直观, 具有对称性.
快速回答一下: 元素间索引表示的区间 (1, 4) 和 (2, 5) 是什么关系? 无需看上面的六种关系, 你可以直接得出结论: (1, 4) 在 (2, 5) 左边且和 (2, 5) 部分重叠.
再次快速回答一下: 对于左闭右开表示法, [1, 4) 和 [2, 5) 是什么关系? 可能在经过数秒的思考后, 你才能得出结论.
元素间索引表示的范围可以轻松计算元素数量: 对于 (2, 5), 元素数量为 5 - 2 = 3. 无需进行加/减 1.
更无需判断是哪种表示法, 然后再判断加 1 还是减 1, 因为元素间索引只有一种表示.
完美! 但是, 怎么在实践中使用它呢? 难道要重写现有的基于普通索引方法的代码吗? 不! 只要你转变思想, 你就可以轻松的以元素间索引的方法思考并看待问题.
实践的例子
Python 中的切片可以轻松访问一个序列的子序列:
>>> [3, 4, 5, 6, 3][2:4]
[5, 6]
切片是以左闭右开的方式进行, 例如上面的切片包含索引为 2 的元素, 不包含索引为 4 的元素. 但是, 如果你想象它使用的是元素间索引的方法, 你会发现结果也对得上! 如果切片 API 使用的是其他的表示法, 例如左开右闭, 或是全开/全闭, 那么我们就不能把思想无缝切换到元素间索引表示法了. 左闭右开的方法之所以如此流行, 或许也有这种原因, 即它体现了元素间索引的思想.
Edsger W. Dijkstra 写过一些笔记阐述了一些推荐使用左闭右开的原因.
Python 中的负数索引有时也挺让人头大. 快速回答一下: 执行 "0123456789"[-7:5] 的结果是多少?
数了一会儿, 你决定写代码看结果.
>>> "0123456789"[-7:5]
'34'
我们给它标上普通索引, 负数索引, 元素间索引:
-10 -9 -8 -7 -6 -5 -4 -3 -2 -1
+---+---+---+---+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
+---+---+---+---+---+---+---+---+---+---+
0 1 2 3 4 5 6 7 8 9 10
-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0
对于元素间索引, 从右往前从 0 开始编号而不是从 -1 开始, 这样我们可以用 (-7, 5) 来表示 '34'. 这样, 还可以轻松的把负数索引转换成正数索引, 只要加上数组长度就可以了. 例如 -7 转换为正数索引变成了 -7 + 10 = 3. 我们依旧可以用 (3, 5) 表示同一个范围! 类似的有 (3, -5), (-7, -5). 写代码时, 我们可以不必有任何思维负担, 写上这四种中的任意一种都是正确的, 即使该 API 使用的是左闭右开表示法. 或者说, 能这样做恰好是因为该 API 使用了左闭右开表示法.
C++ 中 begin(), end(), rbegin() 和 rend() 方法很常用, 其中 end() 和 rend() 分别指向尾后元素和反向尾后元素(即第一个元素前面的位置)
+---+---+---+---+---+---+
rend | | | | | | | end
+---+---+---+---+---+---+
| |
begin rbegin
元素间索引这样思考:
rend end
| |
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+
| |
begin rbegin
看起来整齐多了! 也更易于理解. 值得注意的是, 对 rend 和 end 解引用会引发错误. 对 begin 解引用得到的是 (begin, begin+1) 表示的元素, 对 rbegin 解引用得到的是 (rbegin-1, rbegin) 表示的元素.
有时会有特殊的需求: 将 reverse_iterator 转换为 iterator:
auto iter = rev_iter.base();
从普通索引的角度看, 实际上 iter 和 rev_iter 指向的不是一个位置:
rev_iter
|
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+
|
iter
base() 方法对 rev_iter 加了一个偏移再返回. 元素间索引这样思考:
rev_iter
|
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+
|
iter
即没有偏移. 这样, 迭代器转换就变得很自然, 只不过, 对于 iter, 解引用得到的是 (iter, iter + 1), rev_iter 解引用得到的是 (rev_iter - 1, rev_iter).
数组操作
对于数组处理, 元素间索引也有好处. 假设我们处理一个数组: 遍历的同时执行某种操作, 我们会使用一个索引表示处理到的位置, 这个索引左边是已处理的部分, 右边是未处理的部分. 那么索引本身指向的位置是处理过的还是未处理过的? 这有时会引发一些问题. 使用元素间索引, 我们不会再有歧义, 因为索引不再指向元素.
索引从 0 开始还是从 1 开始
在索引从 1 开始的代码(或算法描述)和从 0 开始的代码之间转换有时会费点功夫.
假设一个数组如下所示:
1 2 3 4 5 6
+---+---+---+---+---+---+
| 0 | 1 | 2 | 3 | 4 | 5 |
+---+---+---+---+---+---+
0 1 2 3 4 5 6
如果我们始终以元素间索引的方式思考, 例如 (3, 4), 如果使用从 0 索引的编程语言, 用二元组的第一个元素解引用相当于 A[3], 如果使用从 1 开始的编程语言, 用二元组的第二个元素解引用即 A[4]. 这无疑简化了思考. 即使对于元素间索引使用 1 索引法, 也会变成 (4, 5), 相对于原来的 (3, 4), 这也是对二元组加 1. 十分容易.
总结
元素间索引的方法对于处理和理解索引相关的问题很有益.