CODEWITHSUNDEEP
c++algorithmiteratorstdvectorreverse-iterator
Peicherla Asrith Varma
Peicherla Asrith Varma

Reputation: 61

Iterating in reverse direction using rbegin() and begin()

When we are iterating in reverse direction, I see that most people use the following structure:

for (auto it = vec.rbegin(); it != vec.rend(); it++)
{
    // block of code //
}

But for a long time, I have a doubt about using this, and I want to know why the following code does not work.

As we know, the last element will have the highest index than any element index in the array, and the array is going to take contiguous memory.

My primary doubt is when iterating backwards, why shouldn't we use it--?

I want the reason why the following code is not going to work. I am running the loop from rbegin, that is the last element, and I am going until the first element. I am decrementing it by one in every iteration.

for (auto it = vec.rbegin(); it >= vec.begin(); it--)
{
    cout << *it << endl;
}

Even the below code is not working, why?

for(auto it = vec.rbegin(); it >= vec.begin(); it++)
{
    cout << *it << endl;
}

Upvotes: 4

Views: 2872

Answers (3)

Remy Lebeau
Remy Lebeau

Reputation: 597235

Reverse iterators are designed to mimic forward iterators (and iterators in general are designed to mimic pointers), so algorithms can be written in an agnostic way that works with both types. All iterators advance with operator++ and decrement with operator-- , where

  • forward iterators advance in a forward direction and decrement in a backwards direction

  • reverse iterators advance in a backward direction and decrement in a forward direction

Upvotes: 0

JeJo
JeJo

Reputation: 32942

First of all, in the given codes, the for loop's conditions are making issue due to type-mismatch.

The vec.rbegin() gives the std::vector::reverse_iterator, and the vec.begin() gives the std::vector::iterator; those are different types and can not be compared. Hence, you get compiler errors in those places.

When iterating backwards, why shouldn't we use it--?

See the following reference picture from std::reverse_iterator

enter image description here

When you use rbegin(), you start from the last element. In order to advance further (like every iterator implementation) it uses the operator++. Advance here means, iterating backwards direction, because the starting point is the last element. Therefore, you should be using it++ or ++it instead.

For the last for loop example, however, there is only a type-mismatch issue. Using ✱std::reverse_iterator::base(), you could get/ convert the reverse iterator to the corresponding base iterator, and it can be compared with the vec.begin().

That means the following change will make it work:

for (auto it = vec.rbegin(); it.base() != vec.begin(); ++it)
//                           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
{
   std::cout << *it << " ";
}

See a demo

Side Note:

  • Even though, the above is possible, I would strongly suggest use the same iterators for comparison, which provides the code more natural look, and easy to understand for the fellow devs and less error-prone.
  • ✱Read more: Can I convert a reverse iterator to a forward iterator?

Upvotes: 5

Xin Cheng
Xin Cheng

Reputation: 1458

In all, it is just a design issue, the designer designed the begin, rbegin, end, rend in that way.

Take an example of a container with three elements {1,2,3}.

  • begin() points to 1, end() points to the position after 3
  • rbegin() points to 3, rend() points to the position before 1.

You can understand rbegin() as a special data struct of a special pointer (aka iterator) such that + operator would be overloaded into -.

You can but not recommended to mix rbegin() with begin() cause they are different things. And mixing is always error-prone for most of the time.

Upvotes: 0

Related Questions