我正在实现一个有向图数据结构,其中边存在于两个同时链接的列表中:顶点的传出边的列表和相对顶点的传入边的列表。
我已经在事件边缘上定义了迭代器,它遍历任一列表。
我的问题是:如何判断迭代器是否相等?如果它们指向相同的边,它们是否应该比较相等,或者如果它们指向相同的边在同一个列表中?
,它们应该比较相等也就是说,
i == j
是否应该暗示++i == ++j
和--i == --j
(同一次遍历中的相同位置)?或者&*i == &*j
(引用内存中的同一个对象)就足够了吗?
哪一个最符合 STL 迭代器的不变量/期望?
前向迭代器的标准概念是可以多次迭代的序列的迭代器,要求如果
i
和 j
与 i == j
是可解引用迭代器(即不是一次性迭代器)值初始化结束),然后也是 i++ == j++
。
还要求
i == j
当且仅当 i
和 j
都不可解除引用,或者两者都可解除引用并且 *i
和 *j
引用同一个对象。
然而,在标准中,
==
考虑的域是在单个序列上的域。所有迭代器属性始终仅适用于一个特定序列。比较不同序列的迭代器通常没有指定的行为(即标准库中的 UB)。
当然,没有什么可以阻止您扩展该概念以覆盖多个序列之间的
==
,但这不会是标准库算法或使用标准迭代器概念的其他库能够利用的任何内容。
正如问题评论中提到的,在
==
的标准中有一个 std::reverse_iterator
扩展的示例。