Lo spostamento di un vettore annulla gli iteratori?

Se ho un iteratore nel vettore a , quindi mi muovo, costruisco o sposto, assegno il vettore b da a , l’iteratore punta ancora allo stesso elemento (ora nel vettore b )? Ecco cosa intendo nel codice:

 #include  #include  int main(int argc, char *argv[]) { std::vector::iterator a_iter; std::vector b; { std::vector a{1, 2, 3, 4, 5}; a_iter = a.begin() + 2; b = std::move(a); } std::cout << *a_iter << std::endl; // Is a_iter valid here? return 0; } 

a_iter è ancora valido poiché a è stato spostato in b , o l’iteratore è invalidato dallo spostamento? Per riferimento, std::vector::swap non invalida gli iteratori .

Mentre potrebbe essere ragionevole presumere che gli iterator siano ancora validi dopo una move , non penso che lo Standard in realtà lo garantisca. Pertanto, gli iteratori si trovano in uno stato indefinito dopo lo move .


Non vi è alcun riferimento che possa trovare nello Standard che specifichi in modo specifico che gli iteratori esistenti prima di una move siano ancora validi dopo lo move .

Sulla superficie, sembrerebbe perfettamente ragionevole presumere che un iterator sia tipicamente implementato come puntatori nella sequenza controllata. Se questo è il caso, gli iteratori sarebbero comunque validi dopo lo move .

Ma l’implementazione di un iterator è definita dall’implementazione. Significa che, purché l’ iterator su una determinata piattaforma soddisfi i requisiti stabiliti dallo Standard, può essere implementato in qualsiasi modo. In teoria, potrebbe essere implementato come combinazione di un puntatore alla class vector insieme a un indice. In questo caso, gli iteratori diventerebbero non validi dopo lo move .

Indipendentemente dal fatto che un iterator sia effettivamente implementato in questo modo è irrilevante. Potrebbe essere implementato in questo modo, quindi senza una specifica garanzia dello standard che gli iteratori post- move sono ancora validi, non si può presumere che lo siano. Tenete a mente anche che esiste una tale garanzia per gli iteratori dopo uno swap . Questo è stato specificamente chiarito dal precedente Standard. Forse è stata semplicemente una supervisione del comitato di Std a non fare un chiarimento simile per gli iteratori dopo una move , ma in ogni caso non esiste una tale garanzia.

Pertanto, il lungo e il breve è che non puoi supporre che i tuoi iteratori siano ancora buoni dopo una move .

MODIFICARE:

23.2.1 / 11 in Draft n3242 afferma che:

Se non diversamente specificato (esplicitamente o definendo una funzione in termini di altre funzioni), invocare una funzione membro contenitore o passare un contenitore come argomento a una funzione di libreria non deve invalidare gli iteratori o modificare i valori di oggetti all’interno di tale contenitore .

Questo potrebbe portare a concludere che gli iteratori sono validi dopo una move , ma non sono d’accordo. Nel tuo codice di esempio, a_iter era un iteratore del vector a . Dopo la move , quel container, a è stato sicuramente cambiato. La mia conclusione è che la clausola di cui sopra non si applica in questo caso.

Penso che la modifica che ha cambiato la costruzione della mossa per spostare l’incarico cambia la risposta.

Almeno se sto leggendo correttamente la tabella 96, la complessità per la costruzione del movimento è data come “nota B”, che è una complessità costante per qualsiasi cosa eccetto std::array . La complessità per l’ assegnazione del movimento, tuttavia, è data come lineare.

In quanto tale, la costruzione del movimento non ha sostanzialmente altra scelta che copiare il puntatore dalla sorgente, nel qual caso è difficile vedere come gli iteratori potrebbero diventare non validi.

Per l’assegnazione del movimento, tuttavia, la complessità lineare significa che potrebbe scegliere di spostare singoli elementi dall’origine alla destinazione, nel qual caso gli iteratori diventeranno quasi certamente non validi.

La possibilità di spostare l’assegnazione degli elementi è rafforzata dalla descrizione: “Tutti gli elementi esistenti di a sono mossi assegnati o distrutti”. La parte “distrutta” corrisponderebbe alla distruzione dei contenuti esistenti e al “furto” del puntatore dalla sorgente, ma la “mossa assegnata a” indicherebbe invece il trasferimento di singoli elementi dall’origine alla destinazione.

Poiché non c’è nulla che impedisca a un iteratore di mantenere un riferimento o un puntatore al contenitore originale, direi che non si può fare affidamento sugli iteratori che rimangono validi a meno che non si trovi una garanzia esplicita nello standard.

tl; dr: Sì, lo spostamento di std::vector può invalidare gli iteratori

Il caso comune (con std::allocator in atto) è che l’invalidazione non avviene ma non ci sono garanzie e cambiando i compilatori o anche il prossimo aggiornamento del compilatore potrebbe rendere il tuo comportamento scorretto se ti affidi al fatto che la tua implementazione al momento non invalidare gli iteratori.


Assegnazione delle mosse :

La domanda se std::vector iterators può effettivamente rimanere valida dopo l’assegnazione del movimento è connessa con la consapevolezza dell’archittore del template vettoriale e dipende dal tipo di allocatore (e possibilmente dalle relative istanze).

In ogni implementazione che ho visto, l’assegnazione del movimento di std::vector> 1 non invaliderà effettivamente iteratori o puntatori. C’è un problema, tuttavia, quando si tratta di fare uso di questo, poiché lo standard non può garantire che gli iteratori rimangano validi per qualsiasi spostamento-assegnazione di un’istanza di std::vector in generale, perché il contenitore è consapevole dell’allocatore.

Gli allocatori personalizzati possono avere uno stato e se non si propagano sull’assegnazione dello spostamento e non sono uguali, il vettore deve allocare lo spazio per gli elementi spostati utilizzando il proprio allocatore.

Permettere:

 std::vector a{/*...*/}; std::vector b; b = std::move(a); 

Ora se

  1. std::allocator_traits::propagate_on_container_move_assignment::value == false &&
  2. std::allocator_traits::is_always_equal::value == false && ( possibilmente come in c ++ 17 )
  3. a.get_allocator() != b.get_allocator()

quindi b assegnerà una nuova memoria e trasferirà gli elementi di uno a uno in quella memoria, invalidando quindi tutti gli iteratori, i puntatori e i riferimenti.

La ragione è che l’adempimento della condizione di cui sopra 1. divieto di spostare l’assegnazione dell’allocatore sul movimento del contenitore. Pertanto, dobbiamo fare i conti con due diverse istanze dell’allocatore. Se questi due oggetti allocatori ora non confrontano mai uguali ( 2. ) né effettivamente uguali, allora entrambi gli allocatori hanno uno stato diverso. Un allocatore x potrebbe non essere in grado di deallocare la memoria di un altro allocatore y avere uno stato diverso e quindi un contenitore con allocatore x non può semplicemente rubare memoria da un contenitore che ha assegnato la memoria tramite y .

Se l’allocatore si propaga sull’assegnazione dello spostamento o se entrambi gli allocatori sono uguali, un’implementazione molto probabilmente sceglierà semplicemente di rendere b propri dati perché può essere sicuro di poter deallocare correttamente lo spazio di archiviazione.

1 : std::allocator_traits>::propagate_on_container_move_assignment e std::allocator_traits>::is_always_equal entrambi sono typdefs per std::true_type (per qualsiasi std::allocator non specializzato std::allocator ).


Sulla costruzione del movimento :

 std::vector a{/*...*/}; std::vector b(std::move(a)); 

Il costruttore di movimento di un contenitore che riconosce gli allocatori si sposterà: costruirà la sua istanza allocator dall’istanza allocator del contenitore da cui si sta muovendo l’espressione corrente. Pertanto, viene garantita la capacità di deallocazione appropriata e la memoria può essere rubata (e infatti sarà) perché la costruzione della mossa è (ad eccezione di std::array ) associata a una complessità costante.

Nota: non esiste ancora alcuna garanzia che gli iteratori rimangano validi anche per la costruzione delle mosse.


In swap :

Richiedere agli iteratori di due vettori di rimanere validi dopo uno scambio (ora si punta solo nel rispettivo contenitore scambiato) è facile perché lo swap ha solo un comportamento definito se

  1. std::allocator_traits::propagate_on_container_swap::value == true ||
  2. a.get_allocator() == b.get_allocator()

Quindi, se gli allocatori non si propagano sullo swap e se non sono uguali, scambiare i contenitori è un comportamento indefinito in primo luogo.