如何为双向迭代器定义operator <？

Question

如何为双向迭代器定义operator <？(list :: iterator)

(我想用list而不是vector.)

Answer 1

你不能直接这样做,但你可以计算std::distance(x.begin(), it1)和std::distance(x.begin(), it2)和比较的.鉴于列表没有随机访问权限,您必须通过遍历整个列表来支付此类查询的价格.

编辑:如果两个迭代器都接近列表的末尾,这将表现不佳.如果你想获得更多的花哨,你可以写一些探索算法从两个迭代器向外移动:

[ .... <-- it1 --> .... <-- it2 --> .... ]

你基本上会为每个fwd1/ rev1和fwd2/ 保留两个副本rev2,然后递减rev*迭代器,直到你点击x.begin()并推进fwd*迭代器直到你命中x.end().如果您的迭代器对是均匀分布的,那么这可能具有更好的预期运行时间.