如何定义运算符<用于双向迭代器？

Question

如何为双向迭代器定义运算符<？ （目录::迭代器）

（我想用列表，而不是载体。）

Answer 1

不可能。您可能需要步行至end，为此您需要知道list的来源，这不是list::iterator中的编码。

（尽管如此，您可以为此创建一个函数对象，它将list或origin作为构造函数参数。请注意，查明一个迭代器是否少于另一个会花费O（n）次）。

Answer 2

你不能这样做，因为你必须知道列表的开始和/或结束，才能做出这样的比较。只有随机访问迭代器定义operator<。

Answer 3

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

---

编辑：如果两个迭代器都靠近列表的末尾，这将表现不佳。如果你想获得更看中的，你可以写一些探索性的算法，从两个迭代器向外移动：

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

你会基本保持两个副本的每个，fwd1/rev1和fwd2/rev2，你递减rev*迭代器，直到您点击x.begin()并提前迭代器fwd*，直到您点击x.end()。如果你的迭代器对是均匀分布的，这可能会有更好的预期运行时间。

Answer 4

假设++(list.end())不是未定义的行为，等于list.end()，有一种方法。但我不确定这个假设。

如果它是有效的，你可以定义一个简单的算法来获得你想要的结果。