c++ c++迭代器实现 - 为什么标准迭代器范围[开始,结束]而不是[开始,结束]?




iterator详解 c++迭代器指针 (7)

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

因为:

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

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


使用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++;
}

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

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

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

   +---+---+---+---+
   | 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()成员返回一个无效的迭代器吗?!
两个迭代器已经够痛苦了......

哦, 看到this相关的帖子

也:

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


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

void func(int* array, size_t size)

当您拥有这些信息时[begin, end)转换为半封闭范围[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 ++中的迭代器(并且语法被设计为允许这样做),调用std::find(array, array + size, some_value)要比调用std::find(array, array + size - 1, some_value)

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

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

但是,在全封闭范围内不能轻松完成此任务。 你被困在<=

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


最好的论据很容易就是由迪克斯特拉本人制作的

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

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

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

当你有任何类型的算法处理多重嵌套或迭代调用基于范围的构造时,[begin,end)惯例背后的智慧会得到回报,这种构造自然而然地链接在一起。 相反,使用双闭合范围会产生偏差,并且会产生极其不愉快和嘈杂的代码。 例如,考虑分区[ n 0n 1 ] [ n 1n 2 )[ n 2n 3 ]。 另一个例子是for (it = begin; it != end; ++it)的标准迭代循环,它运行end - begin时间。 如果两端都包含在内,相应的代码可读性就会降低 - 并想象如何处理空白区域。

最后,我们还可以提出一个很好的理由,为什么计数应该从零开始:使用我们刚刚建立的范围的半开公约,如果给出了N个元素的范围(例如枚举数组的成员),那么0是自然的“开始”,因此您可以将范围写为[0, N ),而不会出现任何尴尬的偏移或校正。

简而言之:在范围算法中,我们看不到数字1的事实是[开始,结束]约定的直接后果和动机。


完全是极客,但我将使用这个:

#define as ;while

int main(int argc, char* argv[])
{
    int n = atoi(argv[1]);
    do printf("n is %d\n", n) as ( n --> 0);
    return 0;
}




c++ stl iterator standards