Che cosa fa realmente l'abilitazione del debug di iteratore STL?

Question

ho attivato il debug iteratore in un'applicazione definendo

_HAS_ITERATOR_DEBUGGING = 1 

mi aspettavo questo per verificare in realtà solo limiti vettore, ma ho la sensazione che sta facendo molto di più di quello. Quali controlli, ecc. Vengono effettivamente eseguiti?

Dinkumware STL, a proposito.

Answer 1

C'è un certo numero di operazioni con iteratori che portano ad un comportamento indefinito, l'obiettivo di questo trigger è di attivare i controlli di runtime per evitare che si verificano (usando afferma).

Il problema

L'operazione ovvia è di usare un iteratore valido, ma questo invalidità può derivare da varie ragioni:

• inizializzate iterator_traits
• Iterator ad un elemento che è stato cancellato
• Iteratore di un elemento la cui ubicazione fisica è stata modificata (riallocazione per un vector)
• Iterator fuori di [begin, end)

La norma precisa in dettaglio straziante per ogni contenitore operazione invalida che iteratore.

C'è una ragione in qualche modo meno evidente che le persone tendono a dimenticare: la miscelazione iteratori a diversi contenitori:

std::vector<Animal> cats, dogs; 

for_each(cats.begin(), dogs.end(), /**/); // obvious bug 

Questo riferiscono a un problema più generale: la validità di intervalli passati agli algoritmi.

• [cats.begin(), dogs.end()) è valido (se non si è un alias per l'altro)
• [cats.end(), cats.begin()) è valido (salvo cats è vuota ??)

La soluzione

La soluzione consiste nell'aggiungere informazioni agli iteratori in modo che la loro validità e validità degli intervalli definiti possano essere asseriti durante l'esecuzione impedendo così indefiniti comportamento da verificarsi.

Il simbolo _HAS_ITERATOR_DEBUGGING funge da trigger per questa funzionalità, poiché purtroppo rallenta il programma. In teoria è abbastanza semplice: ogni iteratore viene creato con il Observer del contenitore da cui è stato emesso e viene quindi notificato della modifica.

In Dinkumware questo si ottiene con due aggiunte:

• Ogni iteratore porta un puntatore al suo contenitore correlato
• Ogni contenitore contiene un elenco collegato di iteratori è creata

E questo risolve perfettamente i nostri problemi:

• Un iteratore unitializzato non ha un contenitore padre, la maggior parte delle operazioni (a parte l'assegnazione e distruzione) attiveranno un'affermazione
• Un iteratore ad un elemento cancellato o spostato è stato notificato (grazie alla lista) e sapere della sua invalidità
• Su incremento e il decremento un iteratore può controllare che rimanga entro i limiti
• Controllare che 2 iteratori appartengano allo stesso contenitore è semplice come confrontare i loro indicatori principali
• Controllare la validità di un intervallo è semplice come controllare che raggiungiamo la fine dell'intervallo. prima che raggiungiamo la fine del container (operazione lineare per quei contenitori che non sono accessibili a caso, quindi la maggior parte di essi)

Il costo

Il costo è pesante, ma non correttezza ha un prezzo? Siamo in grado di abbattere i costi però:

• allocazione di memoria in più (l'elenco supplementare di iteratori mantenuto): processo di notifica O(NbIterators)
• sulle operazioni mutanti: O(NbIterators) (Si noti che push_back o insert non lo fanno invalida necessariamente iteratori, ma erase fa)
• gamma controllo di validità: O(min(last-first, container.end()-first))

la maggior parte degli algoritmi della libreria sono ovviamente state attuate f o massima efficienza, in genere il controllo viene eseguito una volta per tutte all'inizio dell'algoritmo, quindi viene eseguita una versione non controllata.Eppure, la velocità potrebbe gravemente rallentare, in particolare con i cicli scritte a mano:

for (iterator_t it = vec.begin(); 
    it != vec.end();    // Oups 
    ++it) 
// body 

Sappiamo che il Oups linea è di cattivo gusto, ma qui è ancora peggio: ad ogni esecuzione del ciclo, creiamo una nuova iterator quindi lo distrugge che significa allocare e deallocare un nodo per l'elenco degli iteratori di vec ... Devo sottolineare il costo di allocazione/deallocazione della memoria in un ciclo stretto?

Ovviamente, un for_each non riscontra un problema di questo tipo, che rappresenta un altro caso convincente per l'utilizzo di algoritmi STL invece di versioni codificate a mano.

Answer 2

Per quanto ho capito:

_HAS_ITERATOR_DEBUGGING verrà visualizzata una finestra di dialogo in fase di esecuzione per far valere qualsiasi uso iteratore errato tra cui:

1) iteratori utilizzati in un contenitore dopo un elemento viene cancellato

funzione

2) iteratori utilizzati nei vettori dopo un .push() o .Insert() viene chiamato

Answer 3

Secondo http://msdn.microsoft.com/en-us/library/aa985982%28v=VS.80%29.aspx

Lo standard C++ descrive quali funzioni membro fanno sì che gli iteratori di un contenitore non siano più validi. Due esempi sono:

• La cancellazione di un elemento da un contenitore fa sì che gli iteratori dell'elemento non siano più validi.
• L'aumento delle dimensioni di un vettore (push o insert) fa sì che gli iteratori nel contenitore vettoriale non siano più validi.