CODEWITHSUNDEEP
c++stdvectorradixstl-algorithmerase-remove-idiom
JeJo
JeJo

Reputation: 32942

Why erase-remove idiom not working for reverse iterator

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?

Upvotes: 6

Views: 969

Answers (1)

Jodocus
Jodocus

Reputation: 7601

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()
);

Upvotes: 6

Related Questions