Erasing last element from a set in C++

Question

    #include <bits/stdc++.h>
    #define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
    #define SZ(s) int(s.size())
    using namespace std;
    typedef long long ll;
    int main()
    {
        FIN;
        set<ll>s;
        ll N, M;
        cin >> N >> M;
        ll x;
        for(ll i = 0; i < N+M; i++)
        {
            cin >> x;
            if(x==-1)
            {
                auto x = *s.rbegin();
                cout<<x<<'\n';
//-------------------------------------------------------------------------------------------------
                s.erase( --s.end() ); // --s.end() when replaced with s.rbegin(), gives an error
//------------------------------------------------------------------------------------------------
            }
            else
            {
                s.insert( x );
            }
        }
        
    }

in the code between the horizontal lines, I am trying to erase last element from the set.

when I write s.erase( s.rbegin( ) ) instead of s.erase( --s.end( ) ) , it gives me a compilation error saying:

 **error: no matching function for call to ‘std::set<long long int>::erase(std::set<long long int>::reverse_iterator)’
   20 |    s.erase( s.rbegin() );**

arent s.rbegin() and --s.end() pointing to the same element?

Answer 1

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

Answer 2

std::set::rbegin returns a reverse_iterator, which technically points to the same thing, yet the set doesn't have an erase method that receives a reverse_iterator as an argument.