update map value

Question

I have a map like this:

map<prmNode,vector<prmEdge>,prmNodeComparator> nodo2archi;

When I have to update the value (vector), I take the key and his value, I update the vector of values, I erase the old key and value then I insert the key and the new vector. The code is this:

bool prmPlanner::insert_edgemap(int from,int to) {

  prmEdge e;
  e.setFrom(from);
  e.setTo(to);

  map<prmNode,vector<prmEdge> >::iterator it;

  for (it=nodo2archi.begin(); it!=nodo2archi.end(); it++){
      vector<prmEdge> appo;
      prmNode n;
      n=(*it).first;
      int indice=n.getIndex();

      if (indice==f || indice==t){
          appo.clear();
          vector<prmEdge> incArchi;
          incArchi=(*it).second;
          appo=(incArchi);

          appo.push_back(e);

          nodo2archi.erase(it);
          nodo2archi.insert(make_pair(n,appo) );
       }

    }
return true;
}

The problem is that for the first 40-50 iterations everything go weel and the map is updated well, while with more iterations it goes sometimes in segmentation fault, sometimes in an infinite idle. I don't know why. Somebody can help me please?? Thank you very much.

Answer 1

Yo do modify collection while iterating over it.

Answer 2

You are erasing nodes while iterating through your map. This is asking for trouble :)

Answer 3

You are iterating through nodo2archi and at the sametime changing its size by doing nodo2archi.erase(it); and nodo2archi.insert(make_pair(n,appo) );. If you do that your iterator may become invalid and your it++ might crash.

Answer 4

You must not modify a collection itself while iterating over it. C++ will allow it, but it still results in undefined behavior. Other languages like Java have fail-fast iterators that immediately break when the collection has been modified.

Answer 5

The problem is that after erasing the iterator it you are trying to perform operations on it (increment) which is Undefined Behavior. Some of the answers state that modifying the container while you are iterating over it is UB, which is not true, but you must know when your iterators become invalidated.

For sequence containers, the erase operation will return a new valid iterator into the next element in the container, so this would be a correct and idiomatic way of erasing from such a container:

for ( SequenceContainer::iterator it = c.begin(); it != c.end(); ) 
   // note: no iterator increment here
   // note: no caching of the end iterator
{
   if ( condition(*it) ) {
      it = c.erase(it); 
   } else {
      ++it;
   }
}

But sadly enough, in the current standard, associative containers erase does not return an iterator (this is fixed in the new standard draft), so you must manually fake it

for ( AssociativeContainer::iterator it = c.begin(); it != c.end(); )
   // again, no increment in the loop and no caching of the end iterator
{
   if ( condition(*it) ) {
      AssociativeContainer::iterator del = it++; // increment while still valid
      c.erase(del);                              // erase previous position
   } else {
      ++it;
   }
}

And even more sadly, the second approach, correct for associative containers, is not valid for some sequence containers (std::vector in particular), so there is no single solution for the problem and you must know what you are iterating over. At least until the next standard is published and compilers catch up.

Answer 6

Are you simply trying to append data to some of the mapped vectors? In this case you don't need to erase and insert anything:

for (MapType::iterator it = map.begin(); it != map.end(); ++it) {
    if (some_condition) {
        it->second.push_back(some_value);
    }
}