elemento Erase nel vettore, mentre l'iterazione lo stesso vettore

Question

Eventuali duplicati:
Erasing from a std::vector while doing a for each?

Sto cercando di implementare vertice colorazione secondo questo 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 
*/ 

Non capisco "aggiungi v a currentColor". linea, ma suppongo, significa assegnare currentColor a V. Quindi, qual è il "set"? Ad ogni modo il problema è cancellare l'elemento nel vettore mentre lo itera. Questo è il codice.

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

Penso it2 = uc.erase(it2); linea è già uso generale ma dà l'errore in fase di esecuzione.

Answer 1

Nella linea:

it2 = uc.erase(it2); 

un elemento puntato dal iteratore it2 viene rimosso dal vettore, elementi vengono spostati nella memoria per colmare questa lacuna che invalida it2. it2 ottiene un nuovo valore e ora punta al primo elemento dopo quello rimosso o alla fine del vettore (se l'elemento rimosso era l'ultimo). Ciò significa che dopo aver cancellato un elemento non si dovrebbe avanzare it2. Un'alternativa alla proposta remove-erase idiom è un semplice trucco:

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

Si può leggere di più su questo here.

Edit: quanto riguarda il tuo commento, è possibile utilizzare una bandiera per passare le informazioni se un elemento è stato cancellato o meno, e si può controllare quando si esce dal ciclo 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; 
} 

Dopo aver cancellato un elemento da uc è necessario interrompere il ciclo interno. Nella prossima iterazione del ciclo esterno sarete in grado di accedere all'elemento successivo nel uc attraverso un iteratore valido.

Answer 2

vector::erase() può invalidate iterators indicando il vettore.

Invalida tutti iteratore e riferimenti a posizione (o prima) e ai suoi elementi successivi.

È necessario aggiungere il risultato del erase al iteratore (si punterà l'elemento subito dopo quella cancellata) e l'uso che di conseguenza. Si noti che in

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

L'iteratore it non è valido dopo uc.erase, quindi il successivo ++ e l'uso potrebbero causare errore di runtime.

Analogamente, anche se si assegna il risultato di cancellazione a it2, la chiamata può invalidare it, che non viene modificata.

La cosa migliore è sia per riavviare il vostro algoritmo dall'inizio dopo ogni erase(), o se è possibile modificare in modo che esso possa continuare dal iteratore restituito da erase, fare questo a guadagnare una certa efficienza.

Answer 3

Invece di lavorare con i tipi iterator, memorizzare un indice nello vector. Quando hai bisogno di un iteratore - forse per passare a erase - puoi dire begin() + myIndex per generare un iteratore.

Ciò rende anche il ciclo più familiare, ad es.

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

Answer 4

Hai l'errore di runtime perché it2 = uc.erase(it2); restituisce l'iteratore dopo l'ultimo elemento rimosso, in modo che il it2++ in for(it2=uc.begin();it2<uc.end();it2++) va oltre l'ultimo elemento.

Provare a cambiare il vostro caso in: quale errore

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