58

I'm used to writing loops like this:

for (std::size_t index = 0; index < foo.size(); index++)
{
    // Do stuff with foo[index].
}

But when I see iterator loops in others' code, they look like this:

for (Foo::Iterator iterator = foo.begin(); iterator != foo.end(); iterator++)
{
    // Do stuff with *Iterator.
}

I find the iterator != foo.end() to be offputting. It can also be dangerous if iterator is incremented by more than one.

It seems more "correct" to use iterator < foo.end(), but I never see that in real code. Why not?

4

2 回答 2

89

所有迭代器都是相等可比的。只有随机访问迭代器具有关系可比性。输入迭代器、前向迭代器和双向迭代器在关系上没有可比性。

因此，使用的比较!=比使用的比较更通用和灵活<。

迭代器有不同的类别，因为并非所有元素范围都具有相同的访问属性。例如，

  • 如果你有一个迭代器进入一个数组（一个连续的元素序列），那么对它们进行关系比较是微不足道的；您只需要比较指向元素的索引（或指向它们的指针，因为迭代器可能只包含指向元素的指针）；

  • 如果你有一个链表中的迭代器并且你想测试一个迭代器是否“小于”另一个迭代器，你必须从一个迭代器遍历链表的节点，直到你到达另一个迭代器或者你到达终点的名单。

规则是迭代器上的所有操作都应该具有恒定的时间复杂度（或者，至少是次线性时间复杂度）。您始终可以在恒定时间内执行相等比较，因为您只需要比较迭代器是否指向同一个对象。因此，所有迭代器都是相等可比的。

此外，不允许将迭代器递增到它指向的范围的末尾。因此，如果您最终处于与it != foo.end()不做相同事情的场景中it < foo.end()，那么您已经有未定义的行为，因为您已经迭代超出了范围的末尾。

指向数组的指针也是如此：不允许将指针递增到数组的末尾。这样做的程序表现出未定义的行为。（对于索引显然不是这样，因为索引只是整数。）

一些标准库实现（如 Visual C++ 标准库实现）具有有用的调试代码，当您使用这样的迭代器执行非法操作时，它们会引发断言。

于 2011-07-13T03:33:19.460 回答
12

简短的回答：因为Iterator它不是一个数字，它是一个对象。

更长的答案：集合比线性数组更多。例如，树和散列并不真正适合“这个索引在另一个索引之前”。例如，对于一棵树，两个索引位于不同的分支上。或者，哈希中的任何两个索引——它们根本没有顺序，所以你对它们施加的任何顺序都是任意的。

您不必担心“失踪” End()。它也不是一个数字，它是一个代表集合结束的对象。有一个越过它的迭代器是没有意义的，实际上它不能。

于 2011-07-13T03:38:09.007 回答