为什么在迭代器中使用"!="而不是"<"？

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() 这种方式似乎更为"正确"，但我在实际的代码中从未见过。为什么呢？

- Maxpm

---

如果迭代器的增量超过1，也可能会有危险。 <-- 其实不是这样。如果迭代器超出了“end”，那么您已经产生了未定义行为。 - Billy ONeal

在 STL 容器中，end() 指向序列中最后一个对象的下一个位置，因此尝试对其进行解引用操作时会出现错误。这也是为什么可以安全地使用 iter != sequence.end() 来判断是否遍历完整个序列，而不必担心遗漏最后一个元素。 - zneak

@Maxpm: 我根本没有谈论解除引用。无论是否解除引用，将任何迭代器递增到end之后都是未定义的行为。 - Billy ONeal

哪个容器？例如对于链表，这很简单，只需在迭代器中有一个空指针，而不是指向节点的有效指针。对于向量，只需将指针指向内部分配数组的末尾即可。 - GManNickG

@Maxpm：是的，但在我的示例实现中，我从未说过要指向无效位置。指向数组末尾的下一个位置是可以的。 - GManNickG

Answer 1

所有迭代器都可以进行等式比较。只有随机访问迭代器可以进行关系比较。输入迭代器、正向迭代器和双向迭代器不能进行关系比较。

因此，使用 "！=" 的比较更加通用和灵活，而使用 "<" 的比较则较为特定。

不同的迭代器分类是因为不同范围的元素具有不同的访问属性。例如:

如果您有一个指向数组（连续的元素序列）的迭代器，那么将它们进行关系比较就很容易; 您只需要比较所指向的元素的索引（或指向它们的指针，因为迭代器可能仅包含指向元素的指针）;

如果您有指向链表的迭代器并且想要测试一个迭代器是否小于另一个迭代器，则必须从一个迭代器遍历链表节点，直到达到另一个迭代器或到达列表的末尾。

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

此外，您不能将迭代器递增到其所指向的范围之外。因此，如果您在一个场景中发现it != foo.end()与it < foo.end()不做相同的事情，那么您已经出现了未定义行为，因为您已经遍历到范围之外。

对于指向数组的指针也是如此：您不能将指针递增到数组的一端之外; 这样做的程序表现出未定义行为。（对于索引而言显然不是这样，因为索引只是整数。）

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

- James McNellis

---

作为支持这个回答的具体例子，对于std::list<T>::iterator实现operator<将很难在少于线性时间内完成，但是operator!=可以在常数时间内完成。 - zneak

你可能想表达的是 it < foo.end() 而不是 it <= foo.end()。 - zneak

此外，你不能将迭代器递增到超出其指向范围的末尾。因此，如果你遇到这样的情况：it != foo.end() 与 it < foo.end() 不会执行相同的操作，则已经产生了未定义的行为，因为你已经超出了范围的末尾。即使您不会对迭代器进行解引用，而只是使用“<”将其与 end() 进行比较，这种情况仍然是如此。 - khuttun

@khuttun：你总是可以将迭代器推进到“过去的最后”迭代器，但只能一次。 你不能推进一个“过去的最后”迭代器; 这会导致未定义行为。 - Nicol Bolas

你不能将迭代器递增到其指向的范围末尾之后，是否有任何标准参考可以确认这个说法？抄送 @NicolBolas，@Billy ONeal - The Dreams Wind

Answer 2

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

较长的回答：有比线性数组更多的集合。例如树和哈希表，它们并不适用于“此索引在另一个索引之前”的概念。对于树来说，例如生存在不同分支上的两个索引。或者，哈希表中的任意两个索引--它们根本没有顺序，所以你强加给它们的任何顺序都是任意的。

您不必担心“缺失”End()。它也不是一个数字，它是表示集合结尾的对象。具有超过它的迭代器是没有意义的，事实上它不能这样做。

- Mike Caron

---

但是，如果一个结构体的元素不能表示为彼此的“之前”或“之后”，那么是否有必要为其创建迭代器呢？毕竟，您将无法执行Iterator++操作，而迭代器的整个目的就是迭代。 - Maxpm

@Maxpm，迭代器也可用于枚举对象。以具体例子来说，您无法按照自己的喜好对 std::set<T> 中元素的顺序进行固定，但它仍然可迭代。此外，并不是说无法确定哪个元素排在第一位；可能是所需的复杂度比预期更大（使用树的示例，确定哪个节点排在第一位的最坏情况比几次比较要糟糕得多）；因此，最好不要实现该特性，让用户避免陷入悲惨的性能陷阱。 - zneak

@Maxpm，当然，每个集合都必须具有物理顺序，以便在非量子计算机上呈现出有限的空间。但是，该顺序完全是任意的，并且不一定与集合的逻辑排序相关，即使它确实存在。因此，即使您可以通过物理顺序进行迭代，该顺序也不一定有意义。 - Mike Caron

这个答案离谱了。@zneak是正确的，问题不在于没有合理的方法在像std::set这样的集合上实现operator<（毕竟它是有序的），而在于它需要高于常数的复杂度。 - Fred Foo