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

Question

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;
}

++ is the operator to use to advance iterators, even backward ones. You go back one extra step (thus ++). Note in C++20 you can also use https://en.cppreference.com/w/cpp/ranges/reverse_view which might make more sense to you — Pepijn Kramer, Oct 22 '22 at 05:17
Can you explain _why_ you think `FOR(auto it=vec.rbegin();it>=arr.begin();it++)` would work? `FOR` - is that a macro? `vec` and `arr` ? Comparing a reverse iterator with a normal iterator? — Ted Lyngmo, Oct 22 '22 at 05:19
You can understand `rbegin()` as a data struct of a special pointer such that `++` operator would be overloaded into `--`. And in all, it is just a design issue. If you used it more, you might realize such a uniform design has many benefits in use. — Xin Cheng, Oct 22 '22 at 05:22
You'd better not compare `rbegin()` pointer with `begin()` cause they are different things. Thinking about a list `{1,2}`, `begin()` points to 1, `rbegin()` points to 2, `end()` points to the position **after** 2, `rend()` points to the position **before** 1 — Xin Cheng, Oct 22 '22 at 05:27
[std::rbegin](https://en.cppreference.com/w/cpp/iterator/rbegin) and [std::rend](https://en.cppreference.com/w/cpp/iterator/rend) and for `std::vector` specifically [std::vector::rbegin](https://en.cppreference.com/w/cpp/container/vector/rbegin) and [std::vector::rend](https://en.cppreference.com/w/cpp/container/vector/rend) Plain-Jane vanilla C++ since C++11 (C++14 for general non-vector iterators) — David C. Rankin, Oct 22 '22 at 05:28
@Peicherla Asrith Varma, a workable demo was in my solution's edit history. Hope it helps. — Xin Cheng, Oct 22 '22 at 06:46
"not working" is not very useful in describing the issue. You should read the compiler error message, usually it holds a lot of useful information. If you dont understand the error message, no problem, include it in the question then others can explain — 463035818_is_not_an_ai, Oct 22 '22 at 09:42

JeJo · Answer 1 · 2022-10-22T06:55:57.747

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

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?

Xin Cheng · Answer 2 · 2022-10-22T06:18:46.570

0

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.

edited Oct 22 '22 at 06:18

answered Oct 22 '22 at 05:43

Xin Cheng

1,432
10
17

That's just for a demo. showing the `begin()` and `rbegin()` . It does not mean to show base usage. The purpose of the above example is not show the correct way, it just for comparing and showing the idea of my description. Thanks @JeJo – Xin Cheng Oct 22 '22 at 05:54

Remy Lebeau · Answer 3 · 2022-10-22T15:40:20.943

0

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

edited Oct 22 '22 at 15:40

answered Oct 22 '22 at 06:07

Remy Lebeau

555,201
31
458
770

Yes but i have also written it++ for reverse iterator as well separately but the code is not working yet and my exact doubt is that i am starting from vec.rbegin() ie the last element and going till vec.begin() which is the first element but the code is not running ,pls clarify this doubt for me. – Peicherla Asrith Varma Oct 22 '22 at 06:28
@PeicherlaAsrithVarma as others have already pointed out, you are mixing different types of iterators, which is *undefined behavior*. When using `rbegin()`, you need to iterate towards `rend()` instead of `begin()`. They are NOT the same thing. Have you read https://en.cppreference.com/w/cpp/iterator/reverse_iterator yet? – Remy Lebeau Oct 22 '22 at 16:09

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

3 Answers3