为什么是“！=”？与迭代器一起使用而不是“<”？

发布于 2024-11-19 15:50:17 字数 458 浏览 3 评论 0 原文

我习惯于编写这样的循环：

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() 令人反感。如果迭代器递增超过 1，也可能很危险。

使用 iterator < 似乎更“正确” foo.end()，但我从未在实际代码中看到过它。为什么不呢？

原文

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?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

白昼 2024-11-26 15:50:17

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

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

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

如果您有一个数组（元素的连续序列）的迭代器，则对它们进行关系比较很简单；您只需比较指向元素的索引（或指向它们的指针，因为迭代器可能只包含指向元素的指针）；
如果您将迭代器放入链表中，并且想要测试一个迭代器是否“小于”另一个迭代器，则必须从一个迭代器遍历链表的节点，直到到达另一个迭代器或到达到达列表末尾。

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

此外，不允许将迭代器递增到超过其所指向范围的末尾。因此，如果您最终遇到 it != foo.end() 不执行与 it it 相同的操作的情况foo.end()，您已经有未定义的行为，因为您已经迭代到了范围的末尾。

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

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

All iterators are equality comparable. Only random access iterators are relationally comparable. Input iterators, forward iterators, and bidirectional iterators are not relationally comparable.

Thus, the comparison using != is more generic and flexible than the comparison using <.

There are different categories of iterators because not all ranges of elements have the same access properties. For example,

if you have an iterators into an array (a contiguous sequence of elements), it's trivial to relationally compare them; you just have to compare the indices of the pointed to elements (or the pointers to them, since the iterators likely just contain pointers to the elements);
if you have iterators into a linked list and you want to test whether one iterator is "less than" another iterator, you have to walk the nodes of the linked list from the one iterator until either you reach the other iterator or you reach the end of the list.

The rule is that all operations on an iterator should have constant time complexity (or, at a minimum, sublinear time complexity). You can always perform an equality comparison in constant time since you just have to compare whether the iterators point to the same object. So, all iterators are equality comparable.

Further, you aren't allowed to increment an iterator past the end of the range into which it points. So, if you end up in a scenario where it != foo.end() does not do the same thing as it < foo.end(), you already have undefined behavior because you've iterated past the end of the range.

The same is true for pointers into an array: you aren't allowed to increment a pointer beyond one-past-the-end of the array; a program that does so exhibits undefined behavior. (The same is obviously not true for indices, since indices are just integers.)

Some Standard Library implementations (like the Visual C++ Standard Library implementation) have helpful debug code that will raise an assertion when you do something illegal with an iterator like this.

回复收藏 0 原文