c++ - 减去和比较随机访问迭代器 : why and where?

Question

我正在为我的工作开发一个小型库，我从标准 random-access iterator category 派生了一些类。这让我可以使用诸如迭代器特征之类的东西，并且在使用标准库(例如 algorithm)时不必太担心。当然，我知道我不必这样做，我可以选择 bidirectional category，甚至可以实现我自己的。但这不是重点。

IMO，双向和随机访问类别之间的“差距”太大，我不明白减法和比较运算符在迭代器之间的必要性——即:a-b , a<b 和 a>b(及其松散变体)。

为什么标准强制执行这些运算符，有人可以给我举个例子，其中(不)相等测试、混合迭代器-标量算术(复合或非复合)运算符和偏移取消引用运算符是不够的吗？

Answer 1

您需要迭代器之间的差异的一个常见情况是二分查找:不知道距离，您将不知道需要向左侧的迭代器添加多少才能到达 O(1) 的中点。时间。知道距离后，您可以应用混合迭代器-标量算术到达中间，同样是在常数时间内。

请注意，您可以通过重复递增一个迭代器直到到达另一个迭代器来找到距离，但这需要 O(n)时间。

您还需要 a < b比较来知道哪个迭代器在左边，哪个在右边。如果没有这种比较，您将无法验证二进制搜索算法的输入。

I find confusing [that] the subtraction operator should return an int, and not an iterator, even though "logically" I would expect that an arithmetic operation between two objects of the same type returns an object of that type too.

减法就是距离——从一点到另一点的步数。这是一个标量数，与迭代器的类型无关。这里的对称性很简单:因为

iteratorA + scalar = iteratorB

简单的算术规则告诉我们

scalar = iteratorB - iteratorA