Perché push_back o push_front invalidano gli iteratori di un deque?

Question

Come chiede il titolo.

La mia comprensione di un deque era che assegnava "blocchi". Non vedo come allocare più spazio invalida gli iteratori e, se mai, si potrebbe pensare che gli iteratori di un deque avrebbero più garanzie di quelle di un vettore, non di meno.

Answer 1

Lo standard C++ non specifica come viene implementato il deque. Non è necessario allocare nuovo spazio allocando un nuovo blocco e concatenandolo a quelli precedenti, tutto ciò che è richiesto è che l'inserimento a ciascuna estremità sia ammortizzato a tempo costante.

Quindi, mentre è facile vedere come implementare la deque in modo tale da dare la garanzia che si desidera [*], non è l'unico modo per farlo.

[*] Gli iteratori hanno un riferimento a un elemento, più un riferimento al blocco in cui si trova in modo che possano continuare avanti/indietro alle estremità del blocco quando li raggiungono. Inoltre suppongo un riferimento al deque stesso, in modo che operator+ possa essere costante come previsto per gli iteratori ad accesso casuale - seguire una catena di collegamenti da blocco a blocco non è abbastanza buono.

Answer 2

Anche quando si assegna in blocchi, un inserto farà riallocare quel particolare pezzo se non c'è spazio sufficiente (come nel caso dei vettori).

Answer 3

La cosa fondamentale è non fare alcuna ipotesi, basta considerare l'iteratore come se fosse invalidato.

Anche se ora funziona correttamente, una versione successiva del compilatore o del compilatore per una piattaforma diversa potrebbe venire avanti e interrompere il codice. In alternativa, un collega potrebbe venire e decidere di trasformare la tua deque in un vettore o una lista collegata.

Answer 4

Cosa c'è di più interessante è che push_back e push_front sarà non invalidare eventuali riferimenti agli elementi di una deque. Solo gli iteratori devono essere considerati non validi.

Lo standard, a mia conoscenza, non indica il perché. Tuttavia, se è stato implementato un iteratore che era a conoscenza dei suoi vicini immediati - come è una lista - l'iteratore diventerebbe non valido se indicasse un elemento che era al limite della deque e del bordo di un blocco.

Answer 5

Perché lo standard dice che può. Non impone che deque sia implementato come una lista di blocchi. Implica una particolare interfaccia con particolari condizioni pre e post e particolari minimi di complessità algoritmica.

Gli implementatori sono liberi di implementare la cosa in qualsiasi modo scelgano, purché soddisfino tutti questi requisiti. Un'implementazione ragionevole potrebbe utilizzare liste di blocchi, o potrebbe usare qualche altra tecnica con diversi compromessi.

Probabilmente è impossibile dire che una tecnica è strettamente migliore di un'altra per tutti gli utenti in tutte le situazioni. Questo è il motivo per cui lo standard offre agli implementatori una certa libertà di scelta.

Answer 6

La mia ipotesi. push_back/push_front può allocare un nuovo blocco di memoria. Un iteratore deque deve sapere quando l'operatore di incremento/decremento deve saltare nel blocco successivo. L'implementazione può memorizzare tali informazioni in iteratore stesso. L'incremento/decremento di un vecchio iteratore dopo push_back/push_front potrebbe non funzionare come previsto.

Questo codice potrebbe non avere esito negativo con errore di runtime. Sul mio Visual Studio non è riuscito in modalità di debug, ma corro alla conclusione nella modalità di rilascio. Su Linux ha causato un errore di segmentazione.

#include <iostream> 
#include <deque> 

int main() { 
    std::deque<int> x(1), y(1); 
    std::deque<int>::iterator iterx = x.begin(); 
    std::deque<int>::iterator itery = y.begin(); 

    for (int i=1; i<1000000; ++i) { 
     x.push_back(i); 
     y.push_back(i); 
     ++iterx; 
     ++itery; 
     if(*iterx != *itery) { 
      std::cout << "increment failed at " << i << '\n'; 
      break; 
     } 
    } 
} 

Answer 7

Un iteratore non è solo un riferimento ai dati. Deve sapere come incrementare, ecc.

Per supportare l'accesso casuale, le implementazioni avranno una serie dinamica di puntatori ai blocchi. L'iteratore deque punterà in questo array dinamico. Quando il deque cresce, potrebbe essere necessario assegnare un nuovo chunk. La matrice dinamica crescerà, invalidando i suoi iteratori e, di conseguenza, gli iteratori della deque.

Quindi non è che i blocchi vengono riallocati, ma l'array di puntatori a questi blocchi può essere. Infatti, come ha notato Johannes Schaub, i riferimenti non sono invalidati.

Si noti inoltre che le garanzie di iteratore della deque non sono inferiori a quelle del vettore, che vengono invalidate anche quando il contenitore cresce.