Regole per Iterator Invalidation

Question

Quali sono le solite regole per l'invalidazione di Iterator quando si opera su classi di container STL (Vector, Dequeue, elenco, mappa, multimap, set, multiset). È possibile classificare e sommare alcune regole/linee guida generali che un programmatore C++ STL deve conoscere mentre lavora con i contenitori e i loro Iterator?

Answer 1

Queste regole sono specifiche del contenitore. In realtà, questi sono criteri importanti per decidere quale contenitore utilizzare.

Ad esempio, gli iteratori di un std::vector possono essere invalidati quando viene inserito un oggetto (dipende da dove viene inserito l'oggetto e se avviene la riallocazione) e vengono invalidati quando un oggetto viene rimosso prima dell'iteratore. Un std::list non ha questo problema. L'inserimento e la rimozione di oggetti (ad eccezione dell'oggetto a cui punta l'iteratore) non invalida l'iteratore.

SGI fornisce il buono documentation su questo.

Answer 2

Le regole di invalidazione si ispirano alle fondamentali strutture Strutture dati e algoritmi utilizzati per implementare questi contenitori. Se non si prevede di apprendere i fondamenti, sarà necessario ricordare a memoria la documentazione iteratore.

Lo standard C++ definisce i comportamenti di iterator in modo che consenta l'implementazione di con semplici puntatori C. Non richiede che la libreria usi effettivamente dei puntatori; rende semplicemente possibile farlo.

Fondamentalmente, un iteratore viene invalidata se un'operazione provoca un elemento sottostante memorizzazione (una matrice mucchio utilizzato in un vector, un nodo lista concatenata utilizzata in un list, o un nodo della struttura utilizzata in una map o set) di essere deallocato o spostato in una diversa posizione di memoria.

A vector viene in genere implementato allocando una matrice dalla memoria dinamica (heap). Per ridurre il numero di riallocazioni, l'array viene sempre allocato con un po 'di spazio, cioè lo spazio inizialmente non utilizzato. Man mano che gli elementi vengono aggiunti all'array, lo spazio allentato viene esaurito. Quando tutto lo spazio è stato occupato e un nuovo elemento deve essere inserito, verrà assegnato un nuovo array con una dimensione più grande. Ciò causerà l'invalidazione di tutti gli iteratori che puntano al vecchio array.

Allo stesso modo, quando un elemento viene cancellato da un vector, questo farà sì che tutti gli elementi successivi vengano copiati in avanti. Un iteratore che punta agli elementi spostati farà ancora riferimento allo stesso indice dell'array, ma quell'indice ora contiene un elemento diverso. Questo è anche un esempio di invalidazione.

Per list, map e set, l'albero-nodo o elenco nodi rimane valido finché l'elemento che contiene viene cancellata. Si noti che un iteratore che punta a un nodo invalidato non può essere utilizzato per nulla; nemmeno per incrementi/decrementi di iteratore. Questo perché in una lista collegata o in una struttura ad albero, l'iteratore dipende dai puntatori figli che sono memorizzati nel nodo stesso.

Al fine di garantire sempre il corretto funzionamento, lo standard è formulato in un modo più restrittivo rispetto all'utilizzo di strutture dati semplici (che paradossalmente offre maggiore libertà agli implementatori di librerie di utilizzare strutture dati più avanzate). Ad esempio, vedere http://c2.com/cgi/wiki?IteratorInvalidationProblem e http://www.threadingbuildingblocks.org/codesamples.php.