c++stlerasereverse-iterator

How to remove previous element in an std::list with a reverse_iterator?


Look at this simple algorithm that remove elements around specific ones :

void forwardRemoveAlgorithm(std::list<int> &list, int removeAround)
{
    for(std::list<int>::iterator it=list.begin(); it!=list.end(); ++it)
    {
        if(*it==removeAround)
        {
            list.erase(std::prev(it));
            list.erase(std::next(it));
        }
    }
}

it works well and everything is fine (I don't mind side-effects for now)

std::list<int> myList = {1,2,3,4,5};
forwardRemoveAlgorithm(myList,3);
for(int elem : myList) std::cout<<elem<<std::endl;  // displays 1 3 5

But now, I need the reverse counterpart. And the problem becomes apocalyptic. It should look like this :

void reverseRemoveAlgorithm(std::list<int> &list, int removeAround)
{
    for(std::list<int>::reverse_iterator it = list.rbegin(); it!=list.rend(); ++it)
    {
        if(*it==removeAround)
        {
            std::list<int>::iterator forwardEquivalent = std::next(it).base();
            list.erase(std::prev(forwardEquivalent)); // invalidate it and causes a crash at next iteration
            list.erase(std::next(forwardEquivalent));
        }
    }
}

Since std::list does not have an erase() function for reverse_iterators, a new step appears in order to find the forward iterator equivalent. And an evil offset of one element separates the two iterators. This means that now, the algorithm deletes and invalidate the underlying forward iterator of the main reverse iterator it.

I wonder what is the stl way to solve this? Also, I am looking for a template version able to go backward or forward on demand.


Solution

  • The solution is to reset your it (reverse iterator), so you can use std::make_reverse_iterator function.

    Could you check the following code:

    void reverseRemoveAlgorithm(std::list<int>& list, int removeAround)
    {
        for (std::list<int>::reverse_iterator it = list.rbegin(); it != list.rend(); ++it)
        {
            if (*it == removeAround)
            {
                std::list<int>::iterator forwardEquivalent = std::next(it).base();
                list.erase(std::prev(forwardEquivalent)); // invalidate it and causes a crash at next iteration
                list.erase(std::next(forwardEquivalent));
                it = std::make_reverse_iterator(std::next(forwardEquivalent));
            }
        }
    }