CODEWITHSUNDEEP
c++c++11
Grapes
Grapes

Reputation: 2583

Iterating through STL containers and removing/adding multiple items

One of the most frequent errors that occur in my code is that STL containers are modified during a loop.

Elements are removed or added during a loop execution so I usually run into out of bounds exceptions.

My for loops usually looks like this:

for (auto& Item : Items) { // Will not work when Items container is modified
    //... loop logic
}

When multiple items can be removed, I use this monstrosity:

for (int Index=Items.size()-1;Index<=0;Index--) {
    if (Index<Items.size()) { //Because multiple items can be removed in a single loop
        //... loop logic
    }
}

This looks bad and it makes me feel bad using that second option. The reason multiple items can be removed is due to events, where a single event can remove any number of elements.

Here is some pseudo code to illustrate when this occurs:

// for each button in vector<button> {
// process button events
// event adds more buttons to vector<button>
// *ERROR* vector<button> is modified during loop.
// }

In another example, imagine a vector with following items:

// 0 1 2 3 4 5 6 7 8 9

We start our loop at 0 and go element by element. At 4, I want to remove elements 1,4 and 9 so we can't use a normal loop here.

Upvotes: 2

Views: 1365

Answers (4)

rectummelancolique
rectummelancolique

Reputation: 2247

Use std::remove_if with a predicate that decide if a button needs to be removed:

bool needsRemoved(const Button& button);

vec.erase(std::remove_if(vec.begin(), vec.end(), &needsRemoved), vec.end());

EDIT: For your last example, the quadratic (i.e. bad for performance) algorithm is:

std::vector<int> vec = {0,1,2,3,4,5,6,7,8,9};
auto end = vec.end();
for (auto it = vec.begin(); it < end; ++it)
{
    std::set<int> bad = {1, 4, 9};
    end = std::remove_if
        (vec.begin(), end,
         [bad](int x) { return (bad.find(x) != bad.end()); });
}
vec.erase(end, vec.end());

You will probably be better off using a container with fast lookup though (like a set, or a map).

Upvotes: 6

James Kanze
James Kanze

Reputation: 154047

Since you're talking about buttons and button events: the simplest solution is simply to reset the loop to the start when you process an event: 

for ( auto current = items.begin(); current != items.end(); ++ current ) {
    if ( current->hasEventWhichNeedsProcessing() ) {
        current->processEvent();    //  possibly invalidates current
        current = items.begin();    //  revalidates current
    }
}

If we're talking about button events (which occur due to a human user action), this should be safe, since you should normally be able to process all of the events before a new event occurs. (For very rapidly occuring events, you may never reach the final entry.)

I'm still not sure that it's the best solution, however. Regardless of how you iterator, it means that you may treat events in a different order than they arrive. A better solution would be to push the events themselves onto a list, and then process this list in order (as a queue).

Upvotes: 0

JohannesD
JohannesD

Reputation: 14471

There are pretty much two ways to do this reliably:

  1. Iterate over a copy of the original container and manipulate the original. This may not be feasible unless your container stores pointers, not the actual elements directly.

  2. Don't allow direct manipulation of the container, but instead mark the to-be-deleted elements somehow and sweep them after iterating. You can also support adding new elements by inserting them into a separate temporary container and appending to the original after the loop is done - you can also do this with the removed elements, obviating the need to store a "removed" flag in the elements themselves. This can of course be abstracted out with suitable add and remove functions.

Edit: The removal part of solution #2 can be nicely done with the erase-remove idiom shown by rectummelancolique.

Upvotes: 3

Ralph Tandetzky
Ralph Tandetzky

Reputation: 23660

Since there are buttons (and I hope there are not too many) you might want to add a flag to each button, which tells, if it has been processed completely or something like that. Then you look for the first item in the array which has not been processed and process it. You repeat this until all items have been processed. 

for (;;) // breaks, when all items have been processed.
{
    auto it = std::find( std::begin(Items), std::end(Items), 
        [](const Item & item){ return item.hasBeenProcessed(); }
    if ( it == std::end(Items) )
        break;
    process( *it );
}

This should be safe. Note that this can have quadratic time complexity with respect to the number of items. As I said, there will hopefully not be too many items. If this is an issue, you might want to optimize this loop a little, for example starting the search where you left the last time. But do this only when it becomes an issue.

Upvotes: 0

Related Questions