为什么"!="与迭代器而不是"<"一起使用？

Question

我习惯写这样的循环:

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

但是当我在其他代码中看到迭代器循环时,它们看起来像这样:

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

我发现这iterator != foo.end()是有争议的.如果iterator增加多于一个也可能是危险的.

使用起来似乎更"正确" iterator < foo.end(),但我从未在实际代码中看到过这种情况.为什么不？

Answer 1

所有迭代器都是可比较的.只有随机访问迭代器才具有可比性.输入迭代器,前向迭代器和双向迭代器在关系上不具有可比性.

因此,比较使用!=比使用比较更通用和灵活<.

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

如果你有一个迭代器到一个数组(一个连续的元素序列),关系比较它们是微不足道的; 你只需要比较指向元素的索引(或指向它们的指针,因为迭代器可能只包含指向元素的指针);
如果您将迭代器放入链表并且想要测试一个迭代器是否"小于"另一个迭代器,则必须从一个迭代器中走链接列表的节点,直到您到达另一个迭代器或者到达最后的清单.

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

此外,不允许将迭代器增加到它指向的范围的末尾.因此,如果您最终遇到的情况it != foo.end()不同it < foo.end(),那么您已经有了未定义的行为,因为您已经迭代了范围的末尾.

对于指向数组的指针也是如此:不允许将指针递增到数组的末尾之外; 这样做的程序展示了未定义的行为.(对于指数来说,情况显然不同,因为指数只是整数.)

一些标准库实现(如Visual C++标准库实现)具有有用的调试代码,当您使用这样的迭代器执行非法操作时会引发断言.

+1; 作为支持这个答案的具体例子,很难在小于线性时间内为`std :: list <T> :: iterator`实现`operator <`,但是`operator!=`可以在恒定时间内工作. (9认同)
_此外，不允许将迭代器递增到超过其指向的范围的末尾。因此，如果最终遇到 it != foo.end() 与 it < foo.end() 做的事情不同的情况，那么您已经有未定义的行为，因为您已经迭代到了范围的末尾。 _ 即使您不会取消引用迭代器，而只是将其与带有“<”的 end() 进行比较，情况确实如此吗？ (2认同)
@khuttun:你总是可以将迭代器推进到"过去的"迭代器,但只能***.你不能推进一个"过去的"迭代器; 这导致了UB. (2认同)

Answer 2

简短回答:因为Iterator不是数字,所以它是一个对象.

更长的答案:收集的数量多于线性数组.例如,树和哈希并不真正适用于"此索引在此其他索引之前".例如,对于树,两个索引位于不同的分支上.或者,哈希中的任何两个索引 - 它们根本没有订单,因此您对它们施加的任何订单都是任意的.

你不必担心"失踪" End().它也不是数字,它是表示集合结束的对象.有一个经过它的迭代器是没有意义的,事实上它不能.

@Maxpm,迭代器对于枚举对象也很有用.作为一个具体的例子,你无法根据自己的喜好修复`std :: set <T>`中元素的顺序,但它仍然是可迭代的.而且,并不是说_Impossible_告诉哪个元素是第一个; 可能更确切地说,所需的复杂性大于预期(使用树示例,最糟糕的情况是告知哪个节点首先比一些比较差得多); 因此,最好不要实现该功能,并让用户陷入悲伤的性能陷阱. (5认同)
@Maxpm,当然,每个集合都有一个物理顺序作为在非量子计算机上有限空间中表示的必要性.但是,该顺序完全是任意的,并且不一定与集合的_logical_顺序相关,如果它甚至有一个.因此,即使您可以迭代(通过物理顺序),该顺序也不一定有意义. (2认同)