2

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.

Improve this question
4
  • You can simply modify the iterator when removing or adding elements - as long as you know, how many items are modified and where. Commented Jun 21, 2013 at 8:36
  • @Spook I usually don't know what and where, an event can remove any number of elements at any time during a for loop. Commented Jun 21, 2013 at 8:38
  • Well, if you really don't know when and where elements might be removed (and how many), your only option is to make a copy of the container and modify that... Otherwise there's no way to get this working. Commented Jun 21, 2013 at 8:46
  • This begs a question though, if pressing button 4 removes button 9, and you actually remove it, and then pressing button 5 should remove button 9... it is the same "9" or does it remove what was formerly the 10th element ? In other words, are your elements identified by a key or by their position in the container ? Commented Jun 21, 2013 at 9:16

4 Answers 4

Reset to default
6

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).

Improve this answer
Sign up to request clarification or add additional context in comments.

10 Comments

How does this solve his problem. His problem is that something in button 4 might remove buttons 1, 4 and 9. Invalidating the iterator in his loop.
@James Kanze, I omitted the last part, see edited answer, thanks for pointing it out.
@rectummelancolique I still doubt that your solution can be made to work. If the "buttons" are GUI components, they are probably not copyable, and they are probably polymorphic. In which case, the actual elements in the container are pointers, which means that remove_if cannot be used.
@James Kanze, I'm only reusing the exemple the OP provides. In any case, I don't see why you couldn't use remove_if. If they are not copyable then they cannot reasonnably be put in a vector in the first place. If they are pointers, in the above, Iterating from end to vec.end() to delete the objects before calling erase is simple enough. Not to mention the use of smart pointers instead of regular ones.
@rectummelancolique I realize that. But if the example doesn't make sense with regards to the text? (And the example clearly doesn't explain everything.) WRT pointers: there's too much we don't know to answer (Formally, deleting a pointer from a container before it has been removed from the container is undefined behavior. But it will work in practice, unless other code tries to use it.)
|
3

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.

Improve this answer

4 Comments

The second solution is the canonical solution, but I'm not sure it applies here (or at least, it requires a bit of extra work). In his example, processing button 4 may remove button 9, so he shouldn't process button 9 later in the loop.
@JamesKanze: Well, you could skip those elements that are marked while iterating. I'm not sure, however, that in his use case it actually is a good idea to do that - it creates an asymmetry where, for example, processing element 2 causes the removal of elements 1 and 3, only #3 can be skipped as #1 was already processed.
@JohannesD I don't know. In fact, supposing that the buttons are buttons in a GUI interface, I have my doubts about the approach of iterating over the buttons in general. In most cases, you will want to process the events in the order they arrive: you should queue the events, using a classical FIFO queue.
@JohannesD Re your edit: if the "buttons" in question are GUI components, they probably aren't copyable and probably are polymorphic. In which case, the objects in the container are pointers, and you can't use remove_if on the container.
0

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.

Improve this answer

1 Comment

This is more or less what I suggest as well (although I'd write it cleanly, without a break). I don't think quadratic time is an issue, if the objects really are buttons; how many buttons can a human user press in the time it takes to process them?
0

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).

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.