Perché std :: vector :: insert invalidate tutti gli iteratori dopo il punto di inserimento

Question

Quando insert -ing in uno std::vector lo standard C++ assicura che tutti gli iteratori prima del punto di inserimento restino validi fino a quando lo capacity non è esaurito (si veda [ 23.2.4.3/1] o std::vector iterator invalidation).

Qual è la logica alla base del non consentire agli iteratori dopo il punto di inserimento di rimanere valido (se la capacità non è esaurita)? Ovviamente, indicheranno quindi un elemento diverso ma (dalla presunta implementazione di std::vector) dovrebbe essere ancora possibile utilizzare tale iteratore (ad esempio dereferenziarlo o incrementarlo).

Answer 1

Che gli iteratori possano fare riferimento a un elemento diverso è sufficiente per essere invalidati. Si suppone che un iteratore faccia riferimento allo stesso elemento per la durata della sua durata valida.

Hai ragione che, in pratica, potresti non provare nessun demone schiantato o nasale se dovessi dereferire un simile iteratore, ma questo non lo rende valido.

Answer 2

Il vettore non sa quali iteratori esistono. Eppure la posizione di memoria degli elementi dopo l'elemento inserito è cambiata. Ciò significa che gli iteratori devono essere aggiornati per riflettere tale cambiamento nel caso rimangano validi. Ma il vettore non può fare questo aggiornamento, perché non sa quali sono gli iteratori.

Answer 3

Un vettore cresce dinamicamente, quindi quando si preme su un vettore, se non c'è spazio per l'articolo, la memoria deve essere allocata per esso. Lo standard impone che vector memorizzi i suoi elementi nella memoria contigua, quindi quando la memoria è allocata, deve essere sufficiente per memorizzare TUTTI gli elementi esistenti, più il nuovo.

Il vettore non conosce alcun iteratore per se stesso, quindi non può aggiornarli nella nuova memoria di elementi. Gli iteratori sono quindi non validi dopo che la memoria è stata riallocata.

Answer 4

Sembra che tu stia pensando a un iteratore "non valido" come solo uno che provocherebbe un arresto anomalo se utilizzato, ma la definizione dello standard è più ampia. Include la possibilità che l'iteratore possa ancora essere tranquillamente dereferenziato, ma non punta più all'elemento a cui ci si aspetta che punti. (Questo è un caso speciale dell'osservazione che "comportamento indefinito" non corrisponde a significa "il tuo programma si blocca immediatamente", ma può anche significare "il tuo programma calcola silenziosamente il risultato sbagliato" o anche "non si verifica nulla di questo implementazione ")

E 'più facile dimostrare perché questo è un problema con erase:.

#include <vector> 
#include <iostream> 
int main(void) 
{ 
    std::vector<int> a { 0, 1, 2, 3, 4, 4, 6 }; 

    for (auto p = a.begin(); p != a.end(); p++) // THIS IS WRONG 
     if (*p == 4) 
      a.erase(p); 

    for (auto p = a.begin(); p != a.end(); p++) 
     std::cout << ' ' << *p; 

    std::cout << '\n'; 
} 

su implementazioni tipiche del C++ questo programma non andrà in crash, ma stamperà 0 1 2 3 4 6, piuttosto che 0 1 2 3 6 come probabilmente inteso, perché cancellando il f irst 4invalidatop - avanzandolo sopra il secondo 4.

L'implementazione di C++ potrebbe avere una speciale modalità di "debug" in cui questo programma si arresta in modo anomalo durante l'esecuzione.. Ad esempio, con GCC 4.8:

$ g++ -std=c++11 -W -Wall test.cc && ./a.out 
0 1 2 3 4 6 

ma

$ g++ -std=c++11 -W -Wall -D_GLIBCXX_DEBUG test.cc && ./a.out 
/usr/include/c++/4.8/debug/safe_iterator.h:307:error: attempt to increment 
    a singular iterator. 

Objects involved in the operation: 
iterator "this" @ 0x0x7fff5d659470 { 
type = N11__gnu_debug14_Safe_iteratorIN9__gnu_cxx17__normal_iteratorIPiNSt9__cxx19986vectorIiSaIiEEEEENSt7__debug6vectorIiS6_EEEE (mutable iterator); 
    state = singular; 
    references sequence with type `NSt7__debug6vectorIiSaIiEEE' @ 0x0x7fff5d659470 
} 
Aborted 

capiscono che il programma provoca un comportamento indefinito in entrambi i casi. È solo che le conseguenze del comportamento indefinito sono più drammatiche nella modalità di debug.