3

I ran into a problem where I wanted to go through my vector and delete the elements which were no longer wanted. The reason for why it failed is obvious, but I didn't see it when I tried my naive approach. Basically the iterator gets invalidated when I erase an element, and the loop can't continue. What I did is the following:

    #define GOOD 1
    #define BAD 0

    struct Element
    {
        Element(int isGood) : good(isGood){}
        bool good;
    };

    int main()
    {
        std::vector<Element> arr;
        arr.push_back(Element(BAD));
        arr.push_back(Element(GOOD));
        arr.push_back(Element(BAD));
        arr.push_back(Element(GOOD));

    //__CLEAN ARRAY__//
        for (auto it = arr.begin(); it != arr.end(); ++it)
        {
            if ((*it).good == false) arr.erase(it);
        }
    }

So it's obvious that this won't work, I was wondering what the correct/best way of doing this is. My next step would be to restart the loop with fresh iterators if there is a no good found, but this also seems like a waste. Ideally the loop would continue where it left off with fresh iterators?

Thanks.

Zebrafish
  • 11,682
  • 3
  • 43
  • 119

1 Answers1

4

You want:

arr.erase( std::remove_if(arr.begin(), arr.end(), [](auto& obj){return obj.good == false;}), arr.end() );

and its called remove-erase idiom:

https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom

But if you want to fix loop then it is possible, erase returns next valid iterator so you should use it:

    for (auto it = arr.begin(); it != arr.end(); )
    {
      if ((*it).good == false) 
        it = arr.erase(it);
      else
        it++;
    }
marcinj
  • 48,511
  • 9
  • 79
  • 100
  • Thanks. I was just going to say remove and remove_if don't adjust the size of the container. So if I have 10 elements, and remove 2, the iterator returns the new end at the end of the 8 elements, but the container.end() iterator is still pointing at one past the end, 10 + 1. This kind of makes the vector container kind of useless after this then, doesn't it? Also, does this affect optimisation opportunity for the loop, as it would then have to recheck arr.end() each loop iteration. – Zebrafish Jan 25 '17 at 22:50
  • std::remove_if returns the new end() for the vector, and arr.erase uses it to remove all the removed elements. So after this statement is executed, arr will have 8 elements. I am not sure if I understand your second question, if you use loop then surely you need to check .end() on each iteration. – marcinj Jan 25 '17 at 23:04
  • Oh I see, you mean to call erase on the range after you do remove_if. What I mean by the second thing I mentioned is that the iterator wouldn't have to be checked each time if the compiler can know it won't change. Isn't that one of the optimisations the compiler does? – Zebrafish Jan 26 '17 at 00:19