elemento de borrado en el vector mientras que la iteración el mismo vector

Question

Duplicar posibles:
Erasing from a std::vector while doing a for each?

Estoy tratando de poner en práctica vértice coloración de acuerdo con este algoritmo;

/* 
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 
*/ 

No entiendo "add v to currentColor." línea, pero supongo, significa assing currentColor a v. Por lo tanto, ¿qué es el "conjunto"? De todos modos, el problema es borrar el elemento en el vector al iterarlo. Este es el código.

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; 
    } 

creo it2 = uc.erase(it2); línea ya es de uso general pero da error de tiempo de ejecución.

Answer 1

En el line:

it2 = uc.erase(it2); 

un elemento apuntado por iterador it2 se retira a partir del vector, los elementos se desplazan en la memoria con el fin de llenar este vacío que invalida it2. it2 obtiene un nuevo valor y ahora apunta al primer elemento después del eliminado o al final del vector (si el elemento eliminado fue el último). Esto significa que después de borrar un elemento no debe avanzar it2. Una alternativa a la propuesta remove-erase idiom es un simple truco:

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

Usted puede leer más sobre esto here.

Editar: En cuanto a su comentario, puede usar una bandera para pasar la información de si un elemento ha sido borrado o no, y se puede comprobar que al salir del bucle interno:

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; 
} 

Después de haber borrado un elemento del uc, debe salir del bucle interno. En la siguiente iteración del ciclo externo, podrá acceder al siguiente elemento en el uc a través de un iterador válido.

Answer 2

vector::erase() puede invalidate iterators apuntando al vector.

Esto invalida todo el iterador y las referencias a la posición (o primero) y sus elementos posteriores.

es necesario agregar el resultado de erase para el iterador (apuntará al elemento justo después de la que se ha borrado) y el uso que en consecuencia. Tenga en cuenta que en

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

El iterador it no es válida después uc.erase, ++ y su uso posterior por lo que podría dar lugar a error de ejecución.

Del mismo modo, aunque asigne el resultado de borrar a it2, la llamada puede invalidar it, que no se cambia.

Su mejor opción es reiniciar su algoritmo desde el principio después de cada erase(), o si puede modificarlo para que pueda continuar desde el iterador devuelto por erase, hágalo para obtener cierta eficiencia.

Answer 3

En lugar de trabajar con tipos iterator, guarde un índice en el vector. Cuando necesite un iterador, tal vez para pasar al erase, puede decir begin() + myIndex para generar un iterador.

Esto también hace que el lazo parezca más familiar, p. Ej.

for(ind=0; ind < uc.size(); ind++) { 

Answer 4

Tienes el error de ejecución debido a it2 = uc.erase(it2); devuelve el iterador siguiente al último elemento eliminado, por lo que el it2++ en for(it2=uc.begin();it2<uc.end();it2++) va más allá del último elemento.

Prueba a cambiar si en:

if(adjacencyMatris[(*it2).id][(*it3).id] == 0) { 
    B.id = (*it2).id;  
    uc.erase(it2); 
    B.color = currentColor; 
    c.push_back(B); 
    break; 
}