How to convert a C++ STL vector iterator to a vector reverse iterator?

Question

I have used a nested for-loop to carry out insertion sort on a C++ STL <vector>. The first for-loop is over an iterator and the second one, over a reverse_itr.

I need to pass the index (iterator pointer value) from the first loop to the second. I have tried the following approach but it gives me this error

error: no match for ‘operator!=’ (operand types are 
‘__gnu_cxx::__normal_iterator<int*, std::vector<int> >’ and 
‘std::vector<int>::reverse_iterator’ {aka 
‘std::reverse_iterator<__gnu_cxx::__normal_iterator<int*, std::vector<int> > >’})

void insertionSort(int size, vector<int> arr) {

    for(auto itr = arr.begin(); itr != arr.end() - 1; ++itr) {

        int element = *(itr + 1);
        cout << "Element being compared with preceding sub-array is : " << element << endl;

        for(auto r_itr = (itr + 1); r_itr != arr.rend(); ++r_itr) {

            if(*(r_itr+1) <= element) {
                *r_itr = element;
                break;
            }
            else {
                *r_itr = *(r_itr+1);
            }
        }
    }
}

I searched up quite a lot online, found a way to convert a reverse iterator to an iterator (using itr.base()) but not the other way round.

Also I am new to C++ STL and algorithms, please feel free to suggest any way to improve my code with respect to the "clean"-ness of code or the algorithm itself!

Answer 1

Try changing it to for(vector<int>::reverse_iterator r_itr(next(itr)); r_itr != arr.rend(); ++r_itr)

To expand on their working, reverse_iterator is not implemented the same as iterator. The logical and physical address for an iterator are the same but for reverse_iterator, the logical and physical address are not the same. For example: s.end() and s.rbegin() have the same physical address but *s.end() will give you an error but *s.rbegin() will give you the last value of the container s.

The code below will make things clear:

#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> S{ 1, 2, 3 };
    
    set<int>::iterator itr = S.find(2);
    cout << *itr << endl;

    set<int>::reverse_iterator r_itr(itr);
    cout << *r_itr << endl;

    cout << itr._Ptr << ' ' << r_itr.base()._Ptr << endl;

    //S.erase(r_itr);       // ERROR!
    S.erase(r_itr.base());

    for (int e : S)
        cout << e << ' ';
}

On my machine, it produced the following output:

2
1
00F85DA8 00F85DA8
1 3