为什么标准迭代器范围而不是?

为什么标准将end()定义为一个结束,而不是实际结束?

最好的论据很容易就是Dijkstra本人所做的:

  • 你希望范围的大小是一个简单的差异结束开始 ;

  • 包括下界在序列退化为空时更为“自然”,还因为替代( 不包括下界)需要存在一个“开始之前”的前哨值。

你仍然需要certificate为什么你从零开始计算,而不是一个,但这不是你的问题的一部分。

当你有任何一种处理多重嵌套或迭代调用基于范围的构造的algorithm时,[begin,end)惯例背后的智慧就会得到回报。 相反,使用双闭合的范围会产生错误的代码和非常不愉快的代码。 例如,考虑一个分区[ n 0n 1 ] [ n 1n 2 ] [ n 2n 3 ]。 另一个例子是for (it = begin; it != end; ++it)的标准迭代循环,它运行end - begin时间。 如果两端都包含在内,那么相应的代码将不太可读,并想象如何处理空白区域。

最后,我们还可以提出一个很好的理由,为什么计数应该从零开始:对于我们刚刚build立的范围的半开公约,如果给出了一个N元素的范围(比如枚举数组的成员),那么0是自然的“开始”,所以你可以写范围为[0, N ),没有任何尴尬的偏移或校正。

简而言之:在范围algorithm中我们没有看到数字1的事实是[begin,end]约定的直接后果和动机。

为什么标准将end()定义为一个结束,而不是实际结束?

因为:

  1. 它避免了空的范围的特殊处理。 对于空范围, begin()等于end()
  2. 它使遍历元素的循环的结束标准变得简单:只要没有达到end() ,循环就会继续。

实际上,如果考虑到迭代器不是指向序列的元素,而是介于两者之间 ,并且取消引用访问下一个元素,那么很多迭代器相关的东西突然变得更有意义。 然后,“一个过去的结束”迭代器突然立即有意义:

  +---+---+---+---+ | A | B | C | D | +---+---+---+---+ ^ ^ | | begin end 

显然begin指向序列的开始,并指向相同序列的结尾。 解引用begin访问元素A ,解引用end没有意义,因为没有元素正确。 另外,在中间添加一个迭代器给出

  +---+---+---+---+ | A | B | C | D | +---+---+---+---+ ^ ^ ^ | | | begin i end 

你马上就会看到,从begini的元素范围包含元素AB而从iend的元素范围包含元素CD 解引用i给它的权利,这是第二个序列的第一个元素。

即使反向迭代器的“off-by-one”突然变得明显:反转该序列给出:

  +---+---+---+---+ | D | C | B | A | +---+---+---+---+ ^ ^ ^ | | | rbegin ri rend (end) (i) (begin) 

我在下面的括号中写了相应的非反向(基)迭代器。 你看,属于i的反向迭代器(我已经命名为ri仍然指向元素BC之间。 但是由于倒序,现在元素B在它的右边。

因为呢

 size() == end() - begin() // For iterators for whom subtraction is valid 

而且你不必做尴尬的事情

 // Never mind that this is INVALID for input iterators... bool empty() { return begin() == end() + 1; } 

而且你不会意外地写错误的代码

 bool empty() { return begin() == end() - 1; } // a typo from the first version // of this post // (see, it really is confusing) bool empty() { return end() - begin() == -1; } // Signed/unsigned mismatch // Plus the fact that subtracting is also invalid for many iterators 

另外: 如果end()指向一个有效的元素, find()返回什么?
真的想要另一个成员invalid()返回一个无效的迭代器吗?!
两个迭代器已经够痛苦了…

哦, 看到这个相关的职位


也:

如果end在最后一个元素之前,那么如何在真正的末尾insert()

半封闭范围[begin(), end())的迭代器惯用法原本是基于普通数组的指针运算。 在这种操作模式下,您可以使用传递数组和大小的函数。

 void func(int* array, size_t size) 

当你有这样的信息时[begin, end)转换到半closures范围[begin, end)是非常简单的:

 int* begin; int* end = array + size; for (int* it = begin; it < end; ++it) { ... } 

要使用全封闭的范围,这很难:

 int* begin; int* end = array + size - 1; for (int* it = begin; it <= end; ++it) { ... } 

由于指向数组的指针是C ++中的迭代器(并且语法被devise为允许这样做),调用std::find(array, array + size, some_value)要比调用std::find(array, array + size - 1, some_value)


此外,如果您使用半closures范围,则可以使用!=运算符来检查结束条件,因为(如果您的运算符被正确定义) <隐含!=

 for (int* it = begin; it != end; ++ it) { ... } 

然而,用全封闭的范围来做这件事并不容易。 你被困在<=

在C ++中唯一支持<>操作的迭代器是随机访问迭代器。 如果必须为C ++中的每个迭代器类编写一个<=运算符,则必须使所有迭代器完全可比,而且创build能力较低的迭代器的select较less(例如std::list上的双向迭代器std::list或在iostreams上运行的input迭代器)如果C ++使用全封闭范围。

end()指向一个结尾,很容易用for循环迭代一个集合:

 for (iterator it = collection.begin(); it != collection.end(); it++) { DoStuff(*it); } 

end()指向最后一个元素,循环会更复杂:

 iterator it = collection.begin(); while (!collection.empty()) { DoStuff(*it); if (it == collection.end()) break; it++; } 
  1. 如果一个容器是空的, begin() == end()
  2. C ++程序员倾向于在循环条件中使用!=而不是< (小于),因此end()指向一个位置是非常方便的。