pop_back() invalida davvero *tutti* gli iteratori su un std::vettore?

Question

std::vector<int> ints;

// ... fill ints with random values

for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
    if(*it < 10)
    {
        *it = ints.back();
        ints.pop_back();
        continue;
    }
    it++;
}

Questo codice non funziona perché quando pop_back() è chiamato, it è invalidato.Ma non trovo alcun documento che parli dell'invalidazione degli iteratori in std::vector::pop_back().

Hai qualche link a riguardo?

Answer 1

La chiamata a pop_back() rimuove l'ultimo elemento nel vettore e quindi l'iteratore di quell'elemento viene invalidato.IL pop_back() la chiamata lo fa non invalidare gli iteratori agli elementi prima dell'ultimo elemento, solo la riallocazione lo farà.Dal "Riferimento della libreria standard C++" di Josuttis:

L'inserimento o la rimozione di elementi invalida riferimenti, puntatori e iteratori che si riferiscono al seguente elemento.Se un inserimento provoca riallocazione, invalida tutti i riferimenti, iteratori e i puntatori.

Answer 2

Ecco la tua risposta, direttamente da The Holy Standard:

23.2.4.2 Un vettore soddisfa tutti i requisiti di un contenitore e di un contenitore reversibile (dati in due tabelle in 23.1) e di una sequenza, inclusa la maggior parte dei requisiti di sequenza opzionali (23.1.1).

23.1.1.12 Tabella 68 ExpressionA.Pop_Back () restituire la semantica operativaa.erase(--a.end())contenitorevettore, elenco, deque

Si noti che a.pop_back è equivalente a a.erase(--a.end()).Osservando le specifiche del vettore sulla cancellazione:

23.2.4.3.3 - cancellazione dell'iteratore(posizione dell'iteratore) - effetti - Invalida tutti gli iteratori e i riferimenti dopo il punto di cancellazione

Pertanto, una volta chiamato pop_back, tutti gli iteratori dell'elemento precedentemente finale (che ora non esiste più) vengono invalidati.

Osservando il tuo codice, il problema è che quando rimuovi l'elemento finale e l'elenco diventa vuoto, lo incrementi comunque e esci dalla fine dell'elenco.

Answer 3

(Utilizzo lo schema di numerazione utilizzato nella bozza di lavoro C++0x, ottenibile qui

La Tabella 94 a pagina 732 dice che pop_back (se esiste in un contenitore di sequenza) ha il seguente effetto:

{ iterator tmp = a.end(); 
--tmp; 
a.erase(tmp); } 

23.1.1, punto 12 recita che:

Salvo diversa specifica (esplicitamente o definendo una funzione in termini di altre funzioni), invocando una funzione del membro del contenitore o passando un contenitore come argomento a una funzione di biblioteca non deve invalidare iteratori o modificare i valori di, oggetti all'interno di quel contenitore .

Entrambi gli accessi a end() come applicazione del prefisso non hanno tale effetto, tuttavia erase():

23.2.6.4 (riguardo a vector.erase() punto 4):

Effetti:Invalida gli iteratori e i riferimenti in corrispondenza o dopo il punto di cancellazione.

Quindi in conclusione:pop_back() invaliderà un iteratore solo fino all'ultimo elemento, secondo lo standard.

Answer 4

Ecco una citazione dalla documentazione STL di SGI (http://www.sgi.com/tech/stl/Vector.html):

[5] Gli iteratori di un vettore vengono invalidati quando la sua memoria viene riallocata.Inoltre, l'inserimento o l'eliminazione di un elemento nel mezzo di un vettore invalida tutti gli iteratori che puntano agli elementi successivi al punto di inserimento o eliminazione.Ne consegue che è possibile impedire che gli iteratori di un vettore vengano invalidati se si utilizza Reserve() per preallocare tutta la memoria che il vettore utilizzerà mai e se tutti gli inserimenti e le eliminazioni avvengono alla fine del vettore.

Penso che ne consegua pop_back invalida solo l'iteratore che punta all'ultimo elemento e l'iteratore end().Abbiamo davvero bisogno di vedere i dati per i quali il codice fallisce, così come il modo in cui non riesce a decidere cosa sta succedendo.Per quanto ne so, il codice dovrebbe funzionare: il solito problema in tale codice è che la rimozione dell'elemento e ++ sull'iteratore avviene nella stessa iterazione, come sottolinea @mikhaild.Tuttavia, in questo codice non è il caso:it++ non accade quando viene chiamato pop_back.

Potrebbe comunque accadere qualcosa di brutto quando punta all'ultimo elemento e l'ultimo elemento è inferiore a 10.Stiamo ora confrontando un invalidato it e fine().Potrebbe ancora funzionare, ma non è possibile fornire alcuna garanzia.

Answer 5

Gli iteratori vengono invalidati solo in caso di riallocazione dello spazio di archiviazione.Google è tuo amico: vedere la nota 5.

Il tuo codice non funziona per altri motivi.

Answer 6

pop_back() invalida solo gli iteratori che puntano all'ultimo elemento.Dal riferimento alla libreria standard C++:

L'inserimento o la rimozione di elementi invalida riferimenti, puntatori e iteratori che si riferiscono al seguente elemento.Se un inserimento provoca riallocazione, invalida tutti i riferimenti, iteratori e i puntatori.

Quindi, per rispondere alla tua domanda, no, non invalida Tutto iteratori.

Tuttavia, nel tuo esempio di codice, può invalidare it quando punta all'ultimo elemento e il valore è inferiore a 10.In tal caso, il file STL di debug di Visual Studio contrassegnerà l'iteratore come invalidato e un ulteriore controllo per verificare che non sia uguale a end() mostrerà un'asserzione.

Se gli iteratori sono implementati come puntatori puri (come probabilmente farebbero in tutti i casi di vettori STL non di debug), il codice dovrebbe funzionare.Se gli iteratori sono più che puntatori, il codice non gestisce correttamente questo caso di rimozione dell'ultimo elemento.

Answer 7

L'errore è che quando "it" punta all'ultimo elemento del vettore e se questo elemento è inferiore a 10, quest'ultimo elemento viene rimosso.E ora "it" punta a ints.end(), successivamente "it++" sposta il puntatore a ints.end()+1, quindi ora "it" scappa da ints.end() e ottieni un ciclo infinito che scansiona tutti i tuoi memoria :).

Answer 8

La "specifica ufficiale" è lo standard C++.Se non hai accesso a una copia di C++03, puoi ottenere l'ultima bozza di C++0x dal sito web del Comitato: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2008/n2723.pdf

La sezione "Semantica operativa" dei requisiti del contenitore specifica che pop_back() è equivalente a { iterator i = end();--io;cancella(i);}.la sezione [vettoriale.modificatori] per la cancellazione dice "Effetti:Invalida gli iteratori e i riferimenti in corrispondenza o dopo il punto di cancellazione."

Se vuoi l'argomento intuitivo, pop_back è no-fail (poiché la distruzione di value_types nei contenitori standard non è autorizzata a generare eccezioni), quindi non può eseguire alcuna copia o allocazione (poiché possono lanciare), il che significa che puoi indovinarlo l'iteratore dell'elemento cancellato e l'iteratore finale vengono invalidati, ma il resto no.

Answer 9

pop_back() invaliderà solo Esso Se Esso puntava all'ultimo elemento del vettore.Il tuo codice quindi fallirà ogni volta che l'ultimo int nel vettore è inferiore a 10, come segue:

*it = ints.back();// Imposta *it sul valore che ha già
ints.pop_back();// Invalida l'iteratore
Continua;// Esegue il ciclo e accede all'iteratore non valido

Answer 10

Potresti prendere in considerazione l'utilizzo del valore restituito di erase invece di scambiare l'elemento back nella posizione eliminata e tornare indietro.Per le sequenze, la cancellazione restituisce un iteratore che punta l'elemento oltre l'elemento da eliminare.Tieni presente che questo metodo potrebbe causare più copie rispetto all'algoritmo originale.

for(std::vector<int>::iterator it = ints.begin(); it != ints.end(); )
{
    if(*it < 10)
        it = ints.erase( it );
    else
        ++it;
}

std::remove_if potrebbe anche essere una soluzione alternativa.

struct LessThanTen { bool operator()( int n ) { return n < 10; } };

ints.erase( std::remove_if( ints.begin(), ints.end(), LessThanTen() ), ints.end() );

std::remove_if è (come il mio primo algoritmo) stabile, quindi potrebbe non essere il modo più efficiente per farlo, ma è conciso.

Answer 11

Controlla le informazioni qui (cplusplus.com):

Elimina l'ultimo elemento

Rimuove l'ultimo elemento nel vettore, riducendo di fatto la dimensione del vettore di uno e invalidando tutti gli iteratori e i riferimenti ad esso.