检查反向迭代器是否已经越过正向迭代器

Question

我有一个vector<int>::iterator和一个vector<int>::reverse_iterator如图所示：

vector<int>::iterator start = array.begin();
vector<int>::reverse_iterator end = array.rend();
while (true)
{
    if (*start == *end && start <= end)
    {
        start++;
        end++;
    }
}

在 while 循环中，我必须检查 start 和 end 处的值是否相等以及 start 没有越过 end。这样做start <= end是给我错误。有人可以指导我通过正确的方法吗？

错误：

开始 <= 结束。二元运算符 '<=' 不能应用于 vector::iterator 和 reverse_iterator 类型的表达式。

Answer 1

编码：

std::vector<int> test_vector{0, 1, 2, 3};
std::vector<int>::iterator left_it = test_vector.begin();
std::vector<int>::reverse_iterator right_it = test_vector.rbegin();
while (std::distance(left_it, right_it.base() - 1) > 0) {
  ++left_it;
  ++right_it;
}
std::cout << "Iterators crossed" << std::endl;
std::cout << "*left_it = " << *left_it << ", *right_it = " << *right_it << std::endl;

输出：

std::vector<int> test_vector{0, 1, 2, 3};
std::vector<int>::iterator left_it = test_vector.begin();
std::vector<int>::reverse_iterator right_it = test_vector.rbegin();
while (std::distance(left_it, right_it.base() - 1) > 0) {
  ++left_it;
  ++right_it;
}
std::cout << "Iterators crossed" << std::endl;
std::cout << "*left_it = " << *left_it << ", *right_it = " << *right_it << std::endl;

我们std::distance结合使用std::reverse_iterator::base()来确定两个迭代器的相对位置。如果距离为零，则迭代器已经到达相同的元素；如果距离为负，则它们已交叉。

（注意：否定的情况需要C++11 或更高版本，std::distance使用第一个参数“after”调用，第二个参数在 C++11 之前是未定义的行为）。

解释：

In order to get a basis on which to compare reverse iterators to forward iterators, we need to use the std::reverse_iterator::base() function. However, due to an implementation trick (see below for why) used by reverse iterators, this gives you a result that's one element to the right of what you might expect.

To demonstrate briefly, we can iterate through a vector and check the offset of the current address from the address of the vector's first element. First forwards, we have:

std::vector<int> test_vector{0, 1, 2, 3};
for (auto it = test_vector.begin(); it != test_vector.end(); ++it) {
  std::cout << &*it - &test_vector.front() << " ";
}

which outputs the following as expected.

0 1 2 3

If we go backwards, the output is reversed:

for (auto rit = test_vector.rbegin(); rit != test_vector.rend(); ++rit) {
  std::cout << &*rit - &test_vector.front() << " ";
}

yields

3 2 1 0

However, if we check the address of the std::reverse_iterator::base() iterator instead, we see something different:

for (auto rit = test_vector.rbegin(); rit != test_vector.rend(); ++rit) {
  std::cout << &*rit.base() - &test_vector.front() << " ";
}

yields

4 3 2 1

So, we need to subtract 1 from the address of the .base() iterator to get the correct corresponding forwards iterator. This is confirmed by the line from the documentation given below (however, I found their explanation unclear and difficult to grasp, which is why I decided to experiment tangibly):

That is &*(rit.base() - 1) == &*rit.

I couldn't possibly summarize this better than Mankarse's comment does:

A simple way of thinking about iterators is that they are cursors at positions between elements. A forwards iterator will produce the element after the cursor when dereferenced, a reverse iterator will produce the element before the cursor when dereferenced. Equivalent forwards and reverse iterators are cursors that are at the same position.

Why off by one?

It may seem strange to you that reverse iterators have this innate off-by-1 discrepancy. It seems as though when a reverse iterator is at position i, it's actually pointing to the element at position i-1, i.e. the element before i.

There's an innate asymmetry in iterators that can explain this. Consider forward iterators: what are the "earliest" and "latest" iterators we can have?

The earliest iterator is the iterator pointing to the first element, while the latest iterator points after the last element of the collection.

When we iterate in reverse, we need this same functionality in reverse. Our earliest reverse iterator should point directly to the last element, and our latest reverse iterator must point before the first element (or from a reversed perspective, after the first element). These are the basic semantics that allow us to iterate through the collection and know when we have visited every element.

We now see the natural correspondence between the forward and reverse views induces this off-by-one effect. If we envision our collection sequenced from left to right, the last element lies at the second to rightmost position visited in forwards order but the rightmost position visited in reverse order. However, the first element lies at the leftmost position in forwards order and the second to leftmost position in reverse order.

Here is a concrete example. When our reverse iterator's base corresponds to position 0, that indicates it has already gone past the beginning (or the reverse end) and is done iterating. So it points to the element at position 0 one step earlier, which occurs when its base is at position 1. However, the forward iterator simply references the element at position 0 when it is at position 0.