为什么标准迭代器范围是 [begin, end) 而不是 [begin, end]?

2022-01-07 00:00:00 standards iterator c++ stl

为什么标准将 end() 定义为末尾之后,而不是实际末尾?

Why does the Standard define end() as one past the end, instead of at the actual end?

推荐答案

最容易的论据是 迪杰斯特拉本人:

  • 您希望范围的大小是一个简单的差异 end   begin;

  • You want the size of the range to be a simple difference end − begin;

当序列退化为空序列时,包括下限更自然",而且因为替代方案(排除下限)需要存在前一-the-beginning"哨兵值.

including the lower bound is more "natural" when sequences degenerate to empty ones, and also because the alternative (excluding the lower bound) would require the existence of a "one-before-the-beginning" sentinel value.

您仍然需要证明为什么从零而不是从 1 开始计数,但这不是您问题的一部分.

You still need to justify why you start counting at zero rather than one, but that wasn't part of your question.

当您有任何类型的算法处理对基于范围的构造的多个嵌套或迭代调用时,[begin, end) 约定背后的智慧会一次又一次地得到回报,这些构造是自然链接的.相比之下,使用双闭范围会导致不合一的代码以及极其令人不快和嘈杂的代码.例如,考虑一个分区 [n0, n1)[n1, n2)[n2,n3).另一个例子是标准的迭代循环 for (it = begin; it != end; ++it),它运行 end - begin 次.如果两端都包含在内,相应的代码的可读性就会大大降低.并想象一下您将如何处理空范围.

The wisdom behind the [begin, end) convention pays off time and again when you have any sort of algorithm that deals with multiple nested or iterated calls to range-based constructions, which chain naturally. By contrast, using a doubly-closed range would incur off-by-ones and extremely unpleasant and noisy code. For example, consider a partition [n0, n1)[n1, n2)[n2,n3). Another example is the standard iteration loop for (it = begin; it != end; ++it), which runs end - begin times. The corresponding code would be much less readable if both ends were inclusive – and imagine how you'd handle empty ranges.

最后,我们还可以很好地论证为什么计数应该从零开始:根据我们刚刚建立的范围的半开放约定,如果给定一个 N 元素的范围(比如枚举数组的成员),那么 0 是自然的开始",这样您就可以将范围写为 [0, N),没有任何尴尬的偏移或更正.

Finally, we can also make a nice argument why counting should start at zero: With the half-open convention for ranges that we just established, if you are given a range of N elements (say to enumerate the members of an array), then 0 is the natural "beginning" so that you can write the range as [0, N), without any awkward offsets or corrections.

简而言之:事实上,我们在基于范围的算法中没有随处看到数字 1,这是 [begin, end) 约定的直接结果和动机.

In a nutshell: the fact that we don't see the number 1 everywhere in range-based algorithms is a direct consequence of, and motivation for, the [begin, end) convention.

相关文章