c++ - 确定集合迭代器的顺序

Question

我有两个迭代器(比如 it1 和 it2 )到同一个 std::set<int> .它们是通过lower_bound获得的和 upper_bound ，因此取消引用它们是不安全的(它们可能等于 end() )。 有没有一种简单而安全的方法来判断哪个先走？

我可以调用 std::distance(it1, it2)和 std::distance(it2, it1) , 但这似乎没有帮助，因为如果 it1 != it2那么其中一个电话是 UB。我可以测试 *it1 < *it2 , 但前提是没有迭代器指向 end() .最后，我可以先测试结束迭代器，然后再对值进行上述比较。

是否有一个完全基于迭代器而不涉及值的优雅解决方案，即取消引用？我愿意使用最多 c++14 和可能的 boost。

编辑(回应评论): 我使用集合是因为​​我想要快速查找和插入，特别是比线性复杂度快得多。排序 vector 是一种可能的替代方案，它可以轻松解决问题，但插入和删除是线性时间操作。

Answer 1

在我看来，最好的方法是修复你的代码逻辑，让 [it1,it2) 始终是一个有效的范围；如果事实证明这是不可能的(但怎么可能呢？)，你可以使用像

这样的东西

// O(N), forward iterators, it1, it2 should belong to range
template<class Iter>
bool precedes_or_is_equal( Iter it1, Iter it2, Iter end )
{
  while( it1 != end && it1 != it2 ) ++it1;

  return it1 == it2;
}