std containers iterator invalidation during erase

Question

Possible Duplicates:
vector erase iterator
Problem with std::map::iterator after calling erase()

I am having a concern about a piece of my code that I have. I have components and an object which stores the components. The problem is during an update the component can tell to remove a component from a the object. But its called from another function.

void Object::update() { //using std::map here
   for(ComponentMap::iterator i = components.begin(); i != components.end(); ++i) {
      (*i).second->update();
   }
}

void HealthComponent::update() {
   if(health <= 0) object->removeComponent("AliveComponent"); //this is wrong logic. but its just an example :D
}

void Object::removeComponent(string component) {

  ComponentMap::iterator i = components.find(component);
  if(i == components.end()) return;

  components.erase(i);

}

and suppose I have lots of components - Health, Alive, Graphics, Physics, Input etc.

I tried something like this (with some test components) and no errors during during update. But I am really concerned. Can it pop me an error in the future? If yes, how to fix it?

Thanks in advance,
Gasim

In your example code, it looks as though you'll be erasing an element which is not necessarily the element that `Object::update()` is currently acting on. That's a much more difficult problem, and probably warrants a rethinking of your design if that is in fact what you want to do. — Michael Burr, Jun 26 '11 at 22:02
@karlphillip: it's not a dup of "vector erase iterator", but it's likely a dup of the other question. As I've just discovered, `erase` on sequences works differently than `erase` on associative containers. — Ken Bloom, Jun 26 '11 at 23:18

score 7 · Answer 1 · edited Jun 26 '11 at 23:16

7

You cannot loop through your container and say ++i when i is potentially no longer valid (because you erased it). A typical erase loop goes like this:

for (it = x.begin(); it != x.end(); /* nothing here! */)
{
  if (must_erase(*it))
  {
    x.erase(it++); // advance it while still valid, return previous and erase
  }
  else
  {
    ++it;
  }
}

Rewrite your code in this spirit.

To spell out your problem: In Object::update(), you call HealthComponent::update() which invalidates the iterator i, and then you call ++i, which is undefined behaviour.

edited Jun 26 '11 at 23:16

Ken Bloom

57,498
14
111
168

answered Jun 26 '11 at 21:46

Kerrek SB

464,522
92
875
1,084

@Ken: Do all versions of `erase` return the iterator to the next element? Pretty sure `set` doesn't do it, hence my less-than-elegant syntax. (Though I guess the OP's use of member-`find` implies it's a `std::list`.) – Kerrek SB Jun 26 '11 at 21:59
Sorry you're right. The sequences support this syntax (and actually require it), but the associative containers don't support it. The associative containers support `find`, but the sequence containers don't. For those, one is expected to use the free function `std::find`. – Ken Bloom Jun 26 '11 at 23:16
@Ken: No worries. I also got confused about `find`, I confused it with `sort` (for which `list` has a special member). As written, the OP appears to be using an associative container. Glad we sorted that out :-) – Kerrek SB Jun 26 '11 at 23:19
I actually like that idea. I am going to kind of send a state that, its erased or something alike. – Gasim Jun 27 '11 at 09:07
std::find is linear complexity because it goes over all the elements. But sets and maps are sorted and balanced binary trees, so the search complexity is logarithmic. Thats why it has its own find function. I don't actually remember where I saw this thing but i have read that for associative trees never use std::find because it has a better function for that. – Gasim Jun 27 '11 at 09:13
@Gasim: Yes, sure, that's the whole point of the associative containers: Fast lookup by value. The difference between associative and sequence containers that we were referring to is whether `erase` returns an iterator (sequence container) or not (ass. container). – Kerrek SB Jun 27 '11 at 10:00
Ohh. Got it. I have a question. Would that be a good idea to keep the iterator inside my class since the update function is called all the time?? If yes, I have an idea to store the iterator and then in the removeComponent `if((i = components.find(name)) == iterator) iterator++;`. What do you think? – Gasim Jun 27 '11 at 10:19
@Gasim: Wait, your condition is very redundant. Why not just `if (name == *iterator)`? Otherwise, are you asking whether `HealthComponent` should keep a copy of the iterator inside `Object`'s container that points to itself? That depends on the container type. You would have to guarantee that the iterator remains valid throughout object's lifetime. – Kerrek SB Jun 27 '11 at 10:25
Because i first thought its better to then perform `components.erase(i)` but no i realized that you can actually do `components.erase(iterator++)` right? Yes. [link](http://codepad.org/E2MoL85O). is that a good idea to store the iterator as a member variable because just right now, i have seen that iterators can be but shouldn't be used as a non-temporary variable... – Gasim Jun 27 '11 at 10:46

score 1 · Answer 2 · answered Jun 26 '11 at 22:26

In MSVC erase will return the next valid iterator however in GCC it returns void so the only portable way to deal with this issue is keeping the previous iterator, erasing the current element then incrementing the previous iterator for next iteration.

http://www.cplusplus.com/reference/stl/map/erase/

  void Object::removeComponent(string component, ComponentMap::iterator& _prev ) 
  {
     ComponentMap::iterator i = components.find(component);
     if(i == components.end()) 
        return;
     _prev = i;
     --_prev;
     components.erase(i);
     ++prev;
   }

Hello. The funny thing is I am using GCC and i get a right output. :/ I'll see what I can do. Thanks. — Gasim, Jun 27 '11 at 09:04

std containers iterator invalidation during erase

2 Answers2