c++ - 如何找出迭代器是否在一个范围内？

Question

假设我有一个包含三个迭代器的容器it1，it2和it3。现在我正在使用it1并it2定义一个范围，例如传递给一些标准算法。

我如何找出是否在andit3定义的范围内？it1it2

it1我知道将临时迭代器从to推进并在每一步it2检查的蛮力方法。it3有更快的方法吗？

首选的解决方案是标准 C++，没有诸如 boost 之类的库。

编辑：它没有先验地ìt3作用于给定容器的同一实例，因为it1总是it2如此。所以另一个问题是：有没有办法找出两个迭代器属于同一个容器实例？

Answer 1

随机访问迭代器具有可比性。就这样做it1 < it3 && it2 > it3-如果它们属于同一个集合。

您可以在支持 O(1) 索引的集合上获得随机访问迭代器，例如vector、 deque和array。

编辑：检查一个交互器是否属于给定的集合显然是不可行的，这应该是一个完全不同的问题。有关更多详细信息，请参阅此问题。（tl;博士：你不能。）

Answer 2

对于前向迭代器：

• 1 将它们全部滚动到容器的末尾并计算偏移量
• 2 比较偏移量

对于随机访问迭代器，请立即比较它们。

Answer 3

没有对所有类型的容器都有效的方法，但通用方法是使用std::distance并检查其符号。

auto dist1 = std::distance(it1, it3); // should be 0 or +ve
auto dist2 = std::distance(it3, it2); // should be 0 or +ve

唯一的要求是迭代器满足InputIterator要求。

请注意，如果任何迭代器彼此无法访问，则行为未定义。

Answer 4

如果您不知道它来自哪里，请不要使用迭代器。<g>您所做的任何比较仅在迭代器指向范围内时才有效，因此您不能使用迭代器比较来做出该确定。

但是，在大多数情况下，您可以使用蛮力：

while (first != last)
    if (&*first == &*questionable)
        // in sequence

假设迭代器的 value_type 没有operator&以某种时髦的方式重载。