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

Question

如何为双向迭代器定义运算符<？ (列表::迭代器)

(我想使用列表而不是 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( )。如果您的迭代器对是均匀分布的，这可能有更好的预期运行时间。