2010-01-14 19 views
50

Esiste un modo per verificare se un iteratore (indipendentemente da un vettore, da un elenco, da un deque ...) è (ancora) dereferenziabile, ovvero non è stato invalidato?Verifica se un iteratore è valido

Sto usando try - catch, ma c'è un modo più diretto per farlo?

Esempio: (che non funziona)

list<int> l; 
for (i = 1; i<10; i++) { 
    l.push_back(i * 10); 
} 

itd = l.begin(); 
itd++; 
if (something) { 
    l.erase(itd); 
} 

/* now, in other place.. check if itd points to somewhere meaningful */ 
if (itd != l.end()) 
{ 
    // blablabla 
} 
+5

In C++, quando si modifica l'iteratore e non si utilizza il valore, si dovrebbe sempre preferire '++ itd' a' itd ++ '. –

+6

Dopo aver visto il nuovo esempio di codice, nota che i metodi di cancellazione STL restituiscono l'iteratore successivo, che è un iteratore valido (sebbene possa essere l'iteratore finale). Pertanto, per mantenerlo valido, è possibile eseguire questa operazione: if (qualcosa) { itd = l.erase (itd); } –

+0

Mmm ... Vedo ... – huff

risposta

53

Suppongo che tu intenda "è un iteratore valido", che non è stato invalidato a causa di modifiche al contenitore (ad esempio, inserimento/cancellazione di/da un vettore). In tal caso, no, non è possibile determinare se un iteratore è (sicuro) dereferenziabile.

+5

Anche se, penso che sia tempo di introdurre 'Checked STL' nella mischia: un obiettivo stl controllato è catturare errori iteratori> uso di iteratori non validi o confronto di iteratori da diversi contenitori, tra gli altri. Un viaggio da un check stl dovrebbe sicuramente far parte della tua suite di test;) –

+0

@ Matthieu M: Non penso che questo succederà nel prossimo futuro, in quanto così facendo costerebbe almeno 1. mantenendo puntatore ad ogni iteratore che rimanda al vector 2. Quando si annulla l'attraversamento di ogni elemento dell'elenco I falchi delle prestazioni spareranno in giù dalle miglia. :( –

+3

@Ajeet: l'STL verificato esiste già, solitamente cotto nel tradizionale STL ma '# ifdef' out. Costa, rallenta il codice, ma MSVC ad esempio ha 2 livelli di controlli, il primo è molto accessibile (il secondo è decisamente lento ...) ** Fai ** ricorda che questo è ovviamente solo per le build ** Test ** –

9

solito si prova verificando se è differente dalla fine(), come

if (it != container.end()) 
{ 
    // then dereference 
} 

Inoltre usando eccezione movimentazione per la sostituzione la logica è cattiva in termini di design e prestazioni. La tua domanda è molto buona e vale la pena sostituirla nel tuo codice. Gestione delle eccezioni come i nomi dice deve essere utilizzato solo per problemi imprevisti rari.

+2

Quindi, quando si distrugge l'elemento a cui punta l'iteratore in un elenco o un elemento situato prima su un vettore, l'iteratore punta alla fine? Non lo faccio, nel mio caso ... (Modificherò la domanda per essere più chiara) – huff

+0

Quando si eliminano e si inseriscono, * tutti * gli iteratori e i riferimenti potrebbero essere distrutti. Quindi è meglio ottenere nuovi iteratori prima di continuare. Questo perché un esempio. a volte un vettore deve riallocare tutta la memoria prima di aggiungere un nuovo oggetto. Questo naturalmente invaliderà tutti i puntatori, i riferimenti e gli iteratori (che nella maggior parte dei casi sono molto simili ai puntatori) – daramarak

+0

@huff Devi leggere la documentazione API di vector :: erase e list :: erase per capire il comportamento. Inoltre ci sono alcune aree grigie dove l'API era (è ancora?) Leggermente diversa per l'implementazione di std :: map :: erase da parte di Microsoft e GCC, se posso ricordare correttamente. –

0
if (iterator != container.end()) { 
    iterator is dereferencable ! 
} 

Se il vostro iteratore doesnt uguale container.end(), e non è dereferencable, stai facendo qualcosa di sbagliato.

3

Cercare e catturare non è sicuro, non lo farai, o almeno lo farai di rado se il tuo iteratore è "fuori limite".

cosa dire, un iteratore può sempre essere dereferenziato. Non importa quale brutta cosa ci sia sotto. È abbastanza possibile iterare in altre aree della memoria e scrivere in altre aree che potrebbero mantenere altri oggetti. Ho osservato il codice, osservando le variabili che cambiano senza una ragione particolare. Questo è un bug che è davvero difficile da rilevare.

Inoltre è opportuno ricordare che l'inserimento e la rimozione di elementi potrebbe potenzialmente invalidare tutti i riferimenti, puntatori ed iteratori.

Il mio miglior consiglio sarebbe quello di mantenere gli iteratori sotto controllo e tenere sempre un iteratore di "fine" a portata di mano per essere in grado di testare se siete alla fine della linea, per così dire.

+2

Con "può essere dereferenziato" probabilmente intenderai: nessuno ti impedirà di farlo. Tuttavia, si verificherà un comportamento indefinito durante il dereferenziazione di iteratori invalidati. – xtofl

+1

Sì, c'è una differenza tra il dereferenziamento e il dereferenziamento sicuro ... – daramarak

21

Come ha detto jdehaan, se l'iteratore non è stato invalidato e punta in un contenitore, è possibile verificarlo confrontandolo con container.end().

Si noti, tuttavia, che se l'iteratore è singolare - perché non è stato inizializzato o è diventata invalida dopo un'operazione di mutazione sul contenitore (iteratori del vettore vengono invalidate quando si aumenta la capacità del vettore, per esempio) - l'unica operazione che è possibile eseguire su di essa è l'assegnazione. In altre parole, non è possibile verificare se un iteratore sia singolare o meno.

std::vector<int>::iterator iter = vec.begin(); 
vec.resize(vec.capacity() + 1); 
// iter is now singular, you may only perform assignment on it, 
// there is no way in general to determine whether it is singular or not 
4

C'è un modo per verificare se un iteratore (se si tratta di un vettore, un elenco, una deque ...) è (ancora) dereferencable, cioè non è stato invalidato?

No, non c'è.Invece è necessario controllare l'accesso al contenitore mentre l'iteratore esiste, ad esempio:

  • tuo thread non dovrebbe modificare il contenitore (invalidando l'iteratore) mentre è ancora utilizzando un iteratore istanziato per quel contenitore

  • Se esiste il rischio che altri thread possano modificare il contenitore mentre il thread sta eseguendo l'iterazione, per rendere questo scenario thread-safe il thread deve acquisire una sorta di blocco sul contenitore (in modo che impedisca ad altri thread di modificare il contenitore mentre sta utilizzando un iteratore)

L'aggiramento come la cattura di un'eccezione non funzionerà.

Questa è un'istanza specifica del problema più generale, "posso verificare/rilevare se un puntatore è valido?", La risposta a cui è in genere "no, non è possibile testarlo: invece è necessario gestire tutte le allocazioni di memoria e le cancellazioni al fine di conoscere se un dato puntatore è ancora valido ".

+0

E in uno scenario multithreading, questo farà schifo, vero ?: l.erase (itd); itd = l.end(); - E il altro thread confronta itd a l.end(). - Sì, lo so che non è perfetto, ma le probabilità che l'altro thread intervenga dopo la cancellazione e prima dell'assegnazione sono così remote ... eheheh: D – huff

9

risposta non-portatile: Sì - in Visual Studio

visivi iteratori STL dello Studio hanno una modalità "debug", che fanno esattamente questo. Non vorrai abilitare questo in build di navi (c'è overhead) ma utile nelle build verificate.

Leggi informazioni su VC10 here (questo sistema può e in effetti cambia ogni versione, quindi cerca i documenti specifici per la tua versione).

Modifica Inoltre, dovrei aggiungere: gli iteratori di debug in Visual Studio sono progettati per esplodere immediatamente quando li usi (comportamento non definito); non consentire "interrogazioni" del loro stato.

+0

Questo è molto utile. – newprint

-1

uso cancellare con minimo:

 
    if (something) l.erase(itd++); 

in modo da poter verificare la validità del iteratore.

0

In alcuni dei contenitori STL, l'iteratore corrente non è più valido quando si cancella il valore corrente dell'iteratore. Ciò si verifica perché l'operazione di cancellazione modifica la struttura della memoria interna del contenitore e incrementa l'operatore sui punti iteratori esistenti in posizioni non definite.

Quando si esegue quanto segue, l'iteratore è integrato prima di passare alla funzione di cancellazione.

if (something) l.erase(itd++);

0

Il tipo di parametri della funzione di cancellazione di qualsiasi contenitore std (come hai elencato nella tua domanda, vale a dire se si tratta di un vettore, un elenco, una deque ...) è sempre iteratore di questo contenitore solo.

Questa funzione utilizza il primo iteratore specificato per escludere dal contenitore l'elemento a cui questo iteratore punta e anche quelli che seguono. Alcuni contenitori cancellano solo un elemento per un iteratore e alcuni altri contenitori cancellano tutti gli elementi seguiti da un iteratore (incluso l'elemento puntato da questo iteratore) fino alla fine del contenitore.Se la funzione di cancellazione riceve due iteratori, i due elementi, puntati da ciascun iteratore, vengono cancellati dal contenitore e tutti gli altri elementi vengono cancellati dal contenitore, ma il punto è che ogni iteratore passato a la funzione di cancellazione di qualsiasi contenitore std non è più valida! anche:

Ogni iteratore che stava indicando qualche elemento che è stato cancellato dal contenitore diventa valido, ma non passa l'estremità del contenitore!

Ciò significa che un iteratore che puntava su un elemento che è stato cancellato dal contenitore non può essere paragonato a container.end(). Questo iteratore non è valido e quindi non è dereferenziabile, ovvero non è possibile utilizzare né gli operatori * né ->, non è neanche incrementabile, ovvero non è possibile utilizzare l'operatore ++ e non è neanche decrementabile, ovvero non è possibile usa l'operatore -.

Non è paragonabile !!! OSSIA non è nemmeno possibile utilizzare né == né! = operatori

In realtà non è possibile utilizzare alcun operatore dichiarato e definito nell'iter iter. Non puoi fare nulla con questo iteratore, come un puntatore nullo.

Fare qualcosa con un iteratore non valido interrompe immediatamente il programma e causa persino l'arresto anomalo del programma e viene visualizzata una finestra di dialogo di asserzione. Non c'è modo di continuare il programma, non importa quali opzioni scegli, quali pulsanti fai clic. È possibile terminare il programma e il processo facendo clic sul pulsante Abort.

Non si fa altro con un iteratore non valido, a meno che non sia possibile impostarlo all'inizio del contenitore o semplicemente ignorarlo.

Ma prima di decidere cosa fare con un iteratore, in primo luogo è necessario sapere se questo iteratore non è valido o meno, se si chiama la funzione di cancellazione del contenitore che si sta utilizzando.

Ho eseguito da solo una funzione che controlla, verifica, conosce e restituisce true se un dato iteratore non è valido o meno. Puoi utilizzare la funzione memcpy per ottenere lo stato di qualsiasi oggetto, elemento, struttura, classe e così via, e ovviamente usiamo sempre la funzione memset per cancellare o svuotare un nuovo buffer, struttura, classe o qualsiasi oggetto o elemento :

bool IsNull(list<int>::iterator& i) //In your example, you have used list<int>, but if your container is not list, then you have to change this parameter to the type of the container you are using, if it is either a vector or deque, and also the type of the element inside the container if necessary. 
{ 
    byte buffer[sizeof(i)]; 
    memset(buffer, 0, sizeof(i)); 
    memcpy(buffer, &i, sizeof(i)); 
    return *buffer == 0; //I found that the size of any iterator is 12 bytes long. I also found that if the first byte of the iterator that I copy to the buffer is zero, then the iterator is invalid. Otherwise it is valid. I like to call invalid iterators also as "null iterators". 
} 

ho già testato questa funzione prima ho postato lì e ho trovato che questa funzione sta lavorando per me.

Spero davvero di aver esaudito pienamente la tua domanda e di averti aiutato moltissimo!

+0

Siamo spiacenti, ma questo è solo un insieme di aneddoti senza senso, completato da idee prive di senso o dannose.(A) 'cancella' non rimuove" i due elementi "ai suoi iteratori di input; # 2 è passato-fine/esclusivo. (B) Questo è ciò che gli iteratori validi fanno sulla tua implementazione in una volta_; il mio potrebbe non andare mai in crash, potrebbe bloccarsi all'uscita, potrebbe lanciare un 'assert' totalmente casuale da GTK +, _etc ._... (B) Non diffondere idee così dannatamente pericolose: che tutti gli iteratori hanno le stesse dimensioni, che tutto -0x00 è _somehow_ un segno di invalidità (e c'è un qualsiasi punto 'memset'ing un buffer prima di' memcpy'ing su tutto questo; _why _?) ... no –

0

C'è un modo per verificare se un iteratore è dereferencable

Sì, con gcc debugging containers disponibili come estensioni GNU. Per std::list puoi invece utilizzare __gnu_debug::list. Il seguente codice si interromperà non appena si tenterà di utilizzare un iteratore non valido. Poiché i contenitori di debug impongono un overhead aggiuntivo, sono destinati solo al debugging.

#include <debug/list> 

int main() { 
    __gnu_debug::list<int> l; 
    for (int i = 1; i < 10; i++) { 
    l.push_back(i * 10); 
    } 

    auto itd = l.begin(); 
    itd++; 
    l.erase(itd); 

    /* now, in other place.. check if itd points to somewhere meaningful */ 
    if (itd != l.end()) { 
    // blablabla 
    } 
} 

$ ./a.out 
/usr/include/c++/7/debug/safe_iterator.h:552: 
Error: attempt to compare a singular iterator to a past-the-end iterator. 

Objects involved in the operation: 
    iterator "lhs" @ 0x0x7ffda4c57fc0 { 
     type = __gnu_debug::_Safe_iterator<std::_List_iterator<int>, std::__debug::list<int, std::allocator<int> > > (mutable iterator); 
     state = singular; 
     references sequence with type 'std::__debug::list<int, std::allocator<int> >' @ 0x0x7ffda4c57ff0 
    } 
    iterator "rhs" @ 0x0x7ffda4c580c0 { 
     type = __gnu_debug::_Safe_iterator<std::_List_iterator<int>, std::__debug::list<int, std::allocator<int> > > (mutable iterator); 
     state = past-the-end; 
     references sequence with type 'std::__debug::list<int, std::allocator<int> >' @ 0x0x7ffda4c57ff0 
    } 
Aborted (core dumped)