By using bidirectional iterator or random access iterator (see Iterator Categories in C++) it’s possible to traverse the sequence in backward direction by using operator -- or by using the special adapter template class std::reverse_iterator. But why to bother with reverse iterators if the operator -- is available for iterators with bidirectional traversing capabilities? The answer is straightforward: because reverse iterators are reusable by the algorithms implemented by using the ordinary iterators such as std::find, for example:
|
1 2 3 4 5 6 7 8 9 10 11 |
bool is_exists_reverse(const std::vector<int>& numbers) { const auto rb = crbegin(numbers); // getting constant reverse iterator // which points to the first element // of the imaginary reversed sequence const auto re = crend(numbers); // getting constant reverse iterator // which points to the one-past-the-last // element of the imaginary reversed // sequence return find(rb, re, 1983) != re; // returns `true` if 1983 was found } |
Note that such a re-usability is possible because reverse iterators implements it’s operators “inversely”, for example, consider the following exposition of the possible operator’s ++ implementation:
|
1 2 3 4 5 6 7 |
template<typename Iter> auto& reverse_iterator<Iter>::operator++() { --current; // current points to the element return *this; // after the one pointed to by *this // (See more on "current" below.) } |
As described in the Introduction to C++ Iterators the range of sequence is always considered as half-opened: [begin, end), where end serves as the element one-past-the-last element of sequence. However when the sequence is considered in the reverse order one-past-the-last element is
the one-before-the-beginning element of the original sequence. And this imaginary element is inaccessible because it’s not existent in fact. Since the std::reverse_iterator template class adapter is implemented under the hood by using ordinary iterator called current, to get the
half-open range in reverse order without access violation problems, current always points to the element that follows the element referred by reverse iterator, i.e. *reverse == *(current - 1). Therefore, the sequence in reverse order is always considered in range [end - 1, begin - 1), where begin and end corresponds to first and one-past-the-last elements of the original sequence accordingly.
Please note, that it’s always possible to get the underlying current iterator by calling reverse_iterator::base() member function. Finally note, that in order to get the range of sequence of any STL-container in reverse order the standard library provides four functions, demonstrated in the example below:
|
1 2 3 4 5 6 7 8 |
void foo(std::vector<int> numbers) { auto const_rb = crbegin(numbers); // constant reverse auto const_re = crend(numbers); // iterators auto rb = rbegin(numbers); // mutable reverse auto re = rend(numbers); // iterators } |
