如何为双向迭代器定义 operator<？（列表::迭代器）
（我想使用列表而不是向量。）
问问题
412 次
4 回答
7
你不能直接做，但你可以计算std::distance(x.begin(), it1)和std::distance(x.begin(), it2)比较它们。鉴于列表没有随机访问，您希望通过遍历整个列表来为这样的查询付出代价。
编辑：如果两个迭代器都在列表的末尾附近，这将表现不佳。如果你想更花哨，你可以编写一些从两个迭代器向外移动的探索算法：
[ .... <-- it1 --> .... <-- it2 --> .... ]
你基本上会为每个fwd1/rev1和fwd2/保留两个副本rev2，并且你递减rev*迭代器直到你击中x.begin()并推进fwd*迭代器直到你击中x.end(). 如果您的迭代器对是均匀分布的，那么这可能具有更好的预期运行时间。
于 2011-07-22T15:51:58.057 回答
2
您不能这样做，因为您必须知道列表的开头和/或结尾才能进行此类比较。只有随机访问迭代器定义operator<.
于 2011-07-22T15:50:14.947 回答
2
不可能的。您可能需要步行到end，为此您需要知道list原点，它未编码在 a 中list::iterator。
（不过，您可以为此目的创建一个函数对象，它将listor origin 作为构造函数参数。请注意，找出一个迭代器是否小于另一个迭代器需要 O(n) 时间。）
于 2011-07-22T15:46:37.227 回答
1
假设++(list.end())不是未定义的行为和 equals list.end()，有一种方法。但我不确定这个假设。
如果有效，您可以定义一个简单的算法来获得您想要的结果。
于 2011-07-22T15:55:22.697 回答