The code:
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;
Output:
Iterators crossed
*left_it = 2, *right_it = 1
We use std::distance in combination with std::reverse_iterator::base() to determine the relative positions of the two iterators. If the distance is zero, the iterators have reached the same element; if the distance is negative, they have crossed.
(Note: the negative case requires C++11 or later, calling std::distance with the first parameter "after" the second was undefined behavior before C++11).
Explanation:
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.
