Why erase-remove idiom not working for reverse iterator

Question

My aim was to try a solution for this question:Removing all empty elements in a vector from end. using erase-remove idiom.

The idea is to remove all elements starting from the end which are empty (equal to white-space) in a given a std::vector<std::string> of strings. The removal of elements should stop when a non-empty element is found.

Example:

vec = { " ", "B", " ", "D", "E", " ", " ", " " };

After the removal:

vec = { " ", "B", " ", "D", "E"};

Here is the solution I tried:

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iterator>

int main()
{
    std::vector<std::string> vec = { " ", "B", " ", "D", "E", " ", " ", " " };

    bool notStop = true;
    auto removeSpaceFromLast = [&](const std::string& element)-> bool
    {
        if(element != " " ) notStop = false;
        return ( (element == " ") && (notStop) );
    };

    vec.erase(
        std::remove_if(vec.rbegin(), vec.rend(), removeSpaceFromLast),
            vec.rend() );

    std::copy(vec.begin(), vec.end(), std::ostream_iterator<std::string>(std::cout,","));

    return 0;
}

This gave me an error:

no matching function for call to  std::vector<std::__cxx11::basic_string<char> >::erase(std::reverse_iterator<__gnu_cxx::__normal_iterator<std::__cxx11::basic_string<char>*, std::vector<std::__cxx11::basic_string<char> > > >, std::vector<std::__cxx11::basic_string<char> >::reverse_iterator)'|

Then I read about working of std::vector::erase() here: Does vector::erase not work with reverse iterators?

And changed the code:

vec.erase(
    std::remove_if(vec.rbegin().base(), vec.rend().base(), removeSpaceFromLast),
        vec.rend().base() );

This time it compiled, but gave me the output = original vector.

Can anybody explanine:

1. Why this happend ?
2. If its possible, how can we fix it?

Capello

The answer to the other question says that .rbegin().base() == .end(). So what happens when you start at the end, going forward? – Valenciavalenciennes

@BoPersson Yes now I got it. My doubt was mainly weather the idea of base() method exist for the std::remove_if() and how to apply it, and everything else I followed as in conventional erase-removal idiom. – Capello

I don't really know any good use for base(). :-) Note that because of complicated rules for half-open ranges *rbegin() and *(rbegin().base()) don't even refer to the same element! (And *rbegin() is valid but *end() is not). – Valenciavalenciennes

Answer 1

You miss-placed the calls to base(). remove_if will move all spaces it found starting from the end to the beginning part of the vector (as it would move spaces found starting from the beginning move towards the end if forward iterators were used) and returns the iterator pointing to the end position of the to-be-erased sequence (i.e. the begin of the space to be kept, as we reversed the iterator meanings), i.e.:

" ", " ", " ", "B", " ", "D", "E"

Then, you have to erase from the beginning, i.e. rend().base().

vec.erase(vec.rend().base(), 
          std::remove_if(vec.rbegin(), vec.rend(), removeSpaceFromLast).base()
);

Butanol

I got a better understanding of this by writing it as: auto erase_to = std::remove_if(vec.rbegin(), vec.rend(), removeSpaceFromLast).base(); vec.erase(vec.begin(), erase_to); – Sanborne