Best way to in situ delete an element

Question

I have a set of objects which I iterate through, however I may decide during the iteration that one (or more) of those objects now need to be deleted.

My code goes as follows:

if( ! m_Container.empty() )
    {
        for(  typedefedcontainer::iterator it = m_Container.begin();
              it != m_Container.end(); 
              ++it  )
        {
            if( ! ( SomeFunction( (*it), "test", "TEST!", false ))  )
            {
            // If function returns false, delete object.
                m_Container.erase( it );
                AsyncResponseStore::iterator it = m_asyncResponses.begin();
            }

        }


    }

But of course, when I erase an object I get an error : "Map / set iterator not incrementable". Can someone suggest a better way of doing this?

See: What happens if you call erase() on a map element while iterating from begin to end?

Why are you testing the emptiness of your container? If empty, the for loop will never be entered. — Luc Touraille, Dec 09 '08 at 16:56

score 6 · Accepted Answer · answered Dec 09 '08 at 16:18

It depends on the container. The list container supports deletion during enumeration by returning a new iterator from the erase method that represents the next item in the list. map doesn't support this.

A simple method for map is to accumulate the items you want to erase in a separate list, and then iterate over that list when you have finished processing the map to erase the items from the map. This assumes that you can defer the deletion until the iteration has completed. If not then you have no choice but the restart the iteration for each deletion.

Steve Jessop · Answer 2 · 2008-12-10T11:56:52.317

If the container supports it (which I suspect yours doesn't, but the question title is generic so this may be useful to others if not you):

struct SomePredicate {
    bool operator()(typedefedcontainer::value_type thing) {
        return ! SomeFunction(thing, "test", "TEST", false);
    }
};

typedefedcontainer::iterator it;
it = std::remove_if(m_Container.begin(), m_Container.end(), SomePredicate());
m_Container.erase(it, m_Container.end());

m_Container must have an erase range method, which includes any Sequence or Associative Container. It does have to have a mutable iterator, though, and I just noticed that I originally misread the error message: it says "map / set iterator not incrementable". So I guess your container is a map or a set.

Note that the last three could be a truly marvellous one-liner, but this margin is too narrow to contain it.

Also that SomePredicate could have a constructor with parameters to store the additional parameters to SomeFunction, since in real life I guess they're non-constant.

You could actually get rid of SomePredicate entirely if you use boost:bind to construct the functor. Your one-liner would then be truly massive.

[Edit: Rob Walker correctly notes in his answer an assumption that I make here and that the question doesn't state, which is that all erasing can be deferred until after the iterate-and-test is done. If SomeFunction accesses m_Container by a hidden route (e.g. a global, or because SomeFunction is actually a member function of this), and its results depend on the contents of the container, then my code may not be equivalent to the questioner's code. But I think my code is the "unless there's a reason not to" default.]

score 0 · Answer 3 · answered Dec 09 '08 at 16:30

0

Fixed by the following:

for(  typedefedcontainer::iterator it = m_Container.begin();
      it != m_Container.end(); 
        )
{
    if( ! ( SomeFunction( (*it), "test", "TEST!", false ))  )
    {
    // If function returns false, delete object.
        m_Container.erase( it++ );
    }
    else
    { 
        ++i;
    } 

}

When an element is deleted, all pointers to it become invalidated. Therefore by using it++ we get around it. Thanks to those who posted suggestions.

answered Dec 09 '08 at 16:30

Konrad

39,751
32
78
114

Just because you advance to the next iterator safely, **does not** mean that that iterator is valid. onebyone has the best solution. – Frank Krueger Dec 09 '08 at 16:55
Although for some container types, it does mean that. As Rob Walker says, what you can get away with depends on the container type. That's why std::remove_if exists, since together with erase it works on anything having mutable iterators. – Steve Jessop Dec 09 '08 at 17:43

Best way to in situ delete an element

3 Answers3