20

Possible Duplicate:
Erasing from a std::vector while doing a for each?

I'm trying to implement vertice coloring according to this algorithm;

/*
Given G=(V,E):
Compute Degree(v) for all v in V.
Set uncolored = V sorted in decreasing order of Degree(v).
set currentColor = 0.
while there are uncolored nodes:
   set A=first element of uncolored
   remove A from uncolored
   set Color(A) = currentColor
   set coloredWithCurrent = {A}
   for each v in uncolored:
      if v is not adjacent to anything in coloredWithCurrent:
         set Color(v)=currentColor.
         add v to currentColor.
         remove v from uncolored.
      end if
   end for
   currentColor = currentColor + 1.
end while
*/

I don't understand "add v to currentColor." line but I supposed, it means assing currentColor to v. Therefore what is the "set"? Anyway the problem is erasing element in vector while iterating it. This is the code.

    vector<struct Uncolored> uc;
    vector<struct Colored> c;   

    int currentColor = 0;
    struct Colored A;
    struct Colored B;

    vector<struct Uncolored>::iterator it;
    vector<struct Uncolored>::iterator it2;
    vector<struct Colored>::iterator it3;

    for(it=uc.begin();it<uc.end();it++){

        A.id = (*it).id;        
        uc.erase(uc.begin());
        A.color = currentColor;
        c.push_back(A);

        for(it2=uc.begin();it2<uc.end();it2++) {
            it3=c.begin();
            while(it3 != c.end()) {
                if( adjacencyMatris[(*it2).id][(*it3).id] == 0 ) {
                    B.id = (*it2).id;       
                    it2 = uc.erase(it2);
                    B.color = currentColor;
                    c.push_back(B);
                }
                it3++;
            }
        }
        currentColor = currentColor + 1;
    }

I think it2 = uc.erase(it2); line is already general use but It gives run time error.

Community
  • 1
  • 1
miqbal
  • 2,213
  • 3
  • 27
  • 35

4 Answers4

48

In the line:

it2 = uc.erase(it2);

an element pointed by iterator it2 is removed from the vector, elements are shifted in memory in order to fill that gap which invalidates it2. it2 gets a new value and now points to the first element after the the removed one or the end of the vector (if removed element was the last one). This means that after erasing an element you should not advance it2. An alternative to proposed remove-erase idiom is a simple trick: 

for(it2 = uc.begin(); it2 != uc.end();)
{
   ...   
   if(...)
   {
      it2 = uc.erase(it2); 
   }
   else
   {
      ++it2;
   }
   ...
}

You can read more about this here.

Edit: Regarding your comment, you can use a flag to pass the information whether an element has been erased or not, and you can check it when you get out from the inner loop:

for(it2=uc.begin(); it2 != uc.end();)
{
   bool bErased = false;

   for(it3 = c.begin(); it3 != c.end(); ++it3)
   {
      if(adjacencyMatris[(*it2).id][(*it3).id] == 0 )
      {
         B.id = (*it2).id;
         it2 = uc.erase(it2);
         bErased = true;
         B.color = currentColor;
         c.push_back(B);
         break;
      }
   }

   if(!bErased)
      ++it2;
}

After you've erased an element from uc you need to break from the inner loop. In the next iteration of the outer loop you'll be able to access the next element in the uc through a valid iterator.

Bojan Komazec
  • 9,216
  • 2
  • 41
  • 51
4

Instead of working with iterator types, store an index into the vector. When you need an iterator--perhaps for passing into erase--you can say begin() + myIndex to generate an iterator.

This also makes the loop look more familiar, e.g.

for(ind=0; ind < uc.size(); ind++) {
StilesCrisis
  • 15,972
  • 4
  • 39
  • 62
2

vector::erase() can invalidate iterators pointing to the vector.

This invalidates all iterator and references to position (or first) and its subsequent elements.

You need to add the result of erase to the iterator (it will point to the element just after the one erased) and use that consequently. Note that in

for(it=uc.begin();it<uc.end();++it){ 
  A.id = (*it).id;         
  uc.erase(uc.begin()); 
  ...
}

The iterator it is not valid after uc.erase, so subsequent ++ and use might result in runtime error.

Similarly, even though you assign the result of erase to it2, the call can invalidate it, which is not changed.

Your best bet is either to re-start your algorithm from the beginning after each erase(), or if you can alter it so that it can continue from the iterator returned by erase, do that to gain some efficiency.

Andreas
  • 5,393
  • 9
  • 44
  • 53
Attila
  • 28,265
  • 3
  • 46
  • 55
0

You've got the runtime error because it2 = uc.erase(it2); returns the iterator following the last removed element, so the it2++ in for(it2=uc.begin();it2<uc.end();it2++) goes beyond the last element.

Try changing your if in:

if( adjacencyMatris[(*it2).id][(*it3).id] == 0 ) {
    B.id = (*it2).id;       
    uc.erase(it2);
    B.color = currentColor;
    c.push_back(B);
    break;
}
asclepix
  • 7,971
  • 3
  • 31
  • 41