[C] L'erase della lista mi provoca crash

[themagiciant95]

Ciao a tutti , il codice sotto riportato dovrebbe aggiungere gli elementi di un array a una lista e poi eliminare da quest'ultima tutti i valori dispari . Non capisco perchè crasha.

int main()
{
    int ia[] ={0,1,1,2,3,5,8,13,21,55,89};

    list<int> b ;

    for(auto c :ia)           // /* Aggiungo gli interi dell'array ia
    {                        //  * alla lista b */
           b.push_back(c);   
    }

auto iter=b.begin();

while(iter!=b.end())        // /* Imposto l'iteratore iter , esso passa in rassegna
{                           //  * ogni elemento della lista . Se l'elemento è dispari
    if((*iter)%2!=0)        //  * viene eliminato. */
        b.erase(iter);
    else
        ++iter;
}

}

[MItaly]

Quando cancelli un elemento da una std::list l'iteratore che hai usato non è più valido (se pensi a come è implementata una lista linkata la cosa dovrebbe essere ovvia). In ogni caso, proprio per gestire casi di questo tipo, std::list::erase restituisce un iteratore all'elemento successivo a quello che hai appena cancellato, per cui puoi fare:

while(iter!=b.end())        // /* Imposto l'iteratore iter , esso passa in rassegna
{                           //  * ogni elemento della lista . Se l'elemento è dispari
    if((*iter)%2!=0)        //  * viene eliminato. */
        iter = b.erase(iter);
    else
        ++iter;
}

[themagiciant95]

Quando cancelli un elemento da una std::list l'iteratore che hai usato non è più valido (se pensi a come è implementata una lista linkata la cosa dovrebbe essere ovvia). In ogni caso, proprio per gestire casi di questo tipo, std::list::erase restituisce un iteratore all'elemento successivo a quello che hai appena cancellato, per cui puoi fare:

while(iter!=b.end())        // /* Imposto l'iteratore iter , esso passa in rassegna
{                           //  * ogni elemento della lista . Se l'elemento è dispari
    if((*iter)%2!=0)        //  * viene eliminato. */
        iter = b.erase(iter);
    else
        ++iter;
}

Il mio libro purtroppo non spiega bene questo concetto..

[MItaly]

Il mio libro purtroppo non spiega bene questo concetto..

Una lista linkata è una struttura in cui ciascun elemento è qualcosa di simile a questo:

struct Elem
{
    Elem *next;
    Elem *prev;
    T payload;
}

dove "next" punta all'elemento successivo, "prev" al precedente e payload contiene il dato che effettivamente hai memorizzato. Un iteratore relativo ad una std::list sostanzialmente è un puntatore a questa struttura. Quando tu chiami la erase, concettualmente quello che succede è:

Elem *erase(Elem *pos)
{
    // Aggiusta i puntatori dell'elemento precedente e successivo
    pos->prev->next = pos->next;
    pos->next->prev = pos->prev;
    Elem *ret = pos->next;
    delete pos;
    return ret;    
}

(ci sono un po' più di check e qualche corner case da gestire, a seconda della convenzione scelta per la gestione della "fine lista", ma il concetto è questo)
Come vedi, l'iteratore che hai passato (pos) non è più valido al termine della funzione, dato che punta ad un elemento che è stato deallocato. Accedervi nuovamente risulterà in crash, corruzione di dati o "apparente funzionamento" in maniera più o meno casuale.