C ++ Iterator lifetime e rilevamento dell'invalidità

8

Basato su ciò che è considerato idiomatico in C ++ 11:

  • se un iteratore in un contenitore personalizzato sopravvive al fatto che il contenitore stesso viene distrutto?
  • dovrebbe essere possibile rilevare quando un iteratore viene invalidato?
  • sono le condizioni sopra condizionali su "build di debug" in pratica?

Dettagli : di recente mi sono occupato del mio C ++ e ho imparato a conoscere C ++ 11. Come parte di ciò, ho scritto un involucro idiomatico attorno alla libreria di uriparser . Parte di questo è il wrapping della rappresentazione della lista collegata dei componenti del percorso analizzati. Sto cercando consigli su ciò che è idiomatico per i contenitori.

Una cosa che mi preoccupa, arrivando più recentemente dai linguaggi raccolti dai rifiuti, è assicurare che gli oggetti casuali non spariscano agli utenti solo se commettono un errore in termini di vite. Per tenere conto di ciò, sia il contenitore PathList che i suoi iteratori mantengono un shared_ptr nell'oggetto stato interno effettivo. Questo garantisce che finché qualsiasi indichi che i dati esistono, così fanno i dati.

Tuttavia, guardando STL (e lotti di ricerca), non sembra che i contenitori C ++ lo garantiscano. Ho questo orribile sospetto che l'aspettativa è quella di lasciare che i contenitori vengano distrutti, invalidando ogni iteratore insieme ad esso. std::vector sembra certamente consentire agli iteratori di essere invalidati e comunque (erroneamente) funzionare.

Quello che voglio sapere è: cosa ci si aspetta da un codice C ++ 11 "buono" / idiomatico? Dati i nuovi e brillanti puntatori intelligenti, sembra strano che STL ti consenta di saltare facilmente le gambe perdendo accidentalmente un iteratore. Sta usando shared_ptr ai dati di supporto un'inefficienza inutile, una buona idea per il debug o qualcosa che ci si aspetta che STL non funzioni?

(Spero che questo approccio a "C ++ 11 idiomatico" eviti le accuse di soggettività ...)

    
posta DK. 27.06.2012 - 10:48
fonte

4 risposte

10

Is using shared_ptr to the backing data an unnecessary inefficiency

Sì: impone un'indirizzamento extra e un'assegnazione extra per elemento, e nei programmi multithread ogni incremento / decremento del conteggio dei riferimenti è costoso molto costoso se un determinato contenitore viene utilizzato solo all'interno di un singolo thread.

Tutte queste cose potrebbero andare bene, e persino desiderabile, in alcune situazioni, ma la regola generale non è di imporre le inutili spese generali che l'utente non può evitare , anche quando sono inutili.

Poiché nessuno di questi overhead è necessario, ma sono piuttosto debug delle sottigliezze (e ricorda, la durata errata di un iteratore è un bug di logica statica, non un comportamento di runtime strano), nessuno ti ringrazierebbe per il rallentamento della corretta codice per catturare i tuoi bug.

Quindi, alla domanda originale:

should an iterator into a custom container survive the container itself being destroyed?

la vera domanda è: se il costo di tenere traccia di tutti gli iteratori dal vivo in un contenitore e di invalidarli quando il contenitore viene distrutto, fallo schiacciare su persone il cui codice è corretto?

Probabilmente no, anche se ci sono casi in cui è veramente difficile gestire correttamente le durate di iteratore e sei disposto a prendere il colpo, un contenitore dedicato (o un adattatore per container) che fornisce questo servizio potrebbe essere aggiunto come opzione .

In alternativa, il passaggio a un'implementazione di debug basata su un flag del compilatore potrebbe essere ragionevole, ma è una modifica molto più grande e più costosa di molti controllati da DEBUG / NDEBUG. È certamente un cambiamento più grande rispetto alla rimozione delle dichiarazioni di asserzione o all'utilizzo di un allocatore di debug.

Ho dimenticato di dirlo, ma la tua soluzione di usare shared_ptr ovunque non risolve necessariamente il tuo bug in ogni caso: può semplicemente cambiarlo per un bug diverso , cioè una perdita di memoria.

    
risposta data 27.06.2012 - 13:38
fonte
7

In C ++, se si lascia che il contenitore venga distrutto, gli iteratori diventano non validi. Perlomeno questo significa che l'iteratore è inutile, e se provi a dereferenziarlo, possono succedere molte cose brutte (esattamente quanto male dipende dall'implementazione, ma di solito è piuttosto brutto).

In una lingua come C ++, è responsabilità del programmatore mantenere tali cose dritte. Questo è uno dei punti di forza del linguaggio, perché puoi praticamente dipendere da quando accadono le cose (hai cancellato un oggetto?) Ciò significa che al momento dell'eliminazione, il distruttore verrà chiamato e la memoria verrà liberata, e tu puoi dipendere su questo), ma significa anche che non puoi andare a tenere gli iteratori in contenitori dappertutto, e quindi eliminare quel container.

Ora, potresti scrivere un contenitore che trattiene i dati fino a quando gli iteratori non saranno scomparsi? Certo, hai chiaramente capito. Questo NON è il solito modo C ++, ma non c'è niente di sbagliato in questo, purché sia correttamente documentato (e, naturalmente, debug). Non è solo il modo in cui funzionano i contenitori STL.

    
risposta data 27.06.2012 - 13:35
fonte
5

Una delle differenze (spesso non dette) tra i linguaggi C ++ e GC è che l'idioma C ++ tradizionale presuppone che tutte le classi siano classi di valore.

Ci sono puntatori e riferimenti, ma sono per lo più relegati nel permettere il dispiegamento polimorfico (tramite la funzione virtuale indiretta) o la gestione dell'oggetto la cui durata deve sopravvivere a quella del blocco che li ha creati.

In quest'ultimo caso, è responsabilità del programmatore definire la politica e la politica su chi crea e chi e quando deve distruggere. I puntatori intelligenti (come shared_ptr o unique_ptr ) sono solo strumenti per aiutare in questo compito nei casi molto particolari (e frequenti) che un oggetto è "condiviso" da diversi proprietari (e vuoi che l'ultimo lo distrugga) o deve essere spostato attraverso i contesti avendo sempre un singolo contesto che lo possiede.

Gli interruttori, in base alla progettazione, hanno senso solo durante ... un'iterazione e, quindi, non devono essere "archiviati per un uso successivo", poiché ciò a cui si riferiscono non è garantito per rimanere uguale o per rimanere lì (un contenitore può trasferire il suo contenuto quando cresce o diminuisce ... invalidando tutto). I contenitori basati su link (come list s) sono un'eccezione a questa regola generale, non la regola stessa.

Nel C ++ idiomatico se A "ha bisogno" B, B deve essere posseduto in un luogo che vive più a lungo del luogo che possiede A, quindi non è richiesto alcun "rilevamento di vita" di B da A.

shared_ptr e weak_ptr aiuto dove questo idioma è troppo restrittivo, consentendo rispettivamente "il non andare via fino a che tutti noi non ti permettiamo" o il "se vai via lascia un messaggio per noi" . Ma hanno un costo, dal momento che - per farlo - devono allocare alcuni dati ausiliari.

Il prossimo passo sono gc_ptr-s (che la libreria standard non offre, ma che puoi implementare se vuoi, usando -per esempio- algoritmi sweep e mark) dove le strutture di tracciamento saranno ancora più complesse e più intensivo del processore è la loro manutenzione.

    
risposta data 27.06.2012 - 16:29
fonte
4

In C ++ è idiota creare qualcosa che

  • può essere prevenuto con un'attenta codifica e
  • potrebbe sostenere costi di runtime per proteggersi da

un Comportamento indefinito .

In particolare per gli iteratori, la documentazione di ciascun contenitore indica quali operazioni invalidano gli iteratori (la distruzione del contenitore è sempre tra di loro) e l'accesso a un iteratore non valido è Comportamento indefinito. In pratica significa che il runtime accederà ciecamente al puntatore non più valido. Di solito si blocca, ma potrebbe corrompere la memoria e causare risultati completamente imprevedibili.

Fornendo controlli facoltativi che possono essere attivati in modalità di debug (con #define che viene impostato automaticamente su on se _DEBUG è definito e disabilitato se NDEBUG è) è una buona pratica.

Tuttavia ricorda che C ++ è progettato per gestire casi in cui uno ha bisogno di un po 'di prestazioni e talvolta i controlli possono essere piuttosto costosi, dal momento che gli iteratori vengono spesso utilizzati in cicli stretti, quindi non attivarli per impostazione predefinita.

Nel nostro progetto di lavoro ho dovuto disabilitare il controllo iteratore nella libreria standard di Microsoft anche in modalità debug, perché alcuni container utilizzano internamente altri contenitori e iteratori e distruggere solo uno enorme impiegava mezz'ora a causa dei controlli!

    
risposta data 28.06.2012 - 08:53
fonte

Leggi altre domande sui tag