Warum macht push_back oder push_front die Iteratoren einer Deque ungültig?

Question

Wie der Titel fragt.

Mein Verständnis eines Deque war, dass es "Blöcke" zugewiesen. Ich sehe nicht, wie die Zuweisung von mehr Speicherplatz Iteratoren ungültig macht, und wenn überhaupt, würde man meinen, dass die Iteratoren einer Deque mehr Garantien haben als die eines Vektors, nicht weniger.

Answer 1

Der C++ - Standard legt nicht fest, wie deque implementiert wird. Es ist nicht erforderlich, neuen Speicherplatz zuzuweisen, indem ein neuer Block zugewiesen und an die vorherigen angekettet wird. Es ist lediglich erforderlich, dass die Einfügung an jedem Ende zu einer konstanten Zeit amortisiert wird.

So, während es ist einfach zu sehen, wie Deque so implementieren, dass es die Garantie gibt, die Sie wollen [*], das ist nicht die einzige Möglichkeit, es zu tun.

[*] Iteratoren haben einen Verweis auf ein Element sowie einen Verweis auf den Block, in dem sie sich befinden, damit sie bei Erreichen der Blöcke weiter vorwärts/rückwärts gehen können. Plus ich nehme einen Verweis auf die Deque selbst, so dass operator+ Konstante Zeit sein kann wie erwartet für Random-Access-Iteratoren - eine Kette von Links von Block zu Block zu folgen ist nicht gut genug.

Answer 2

Auch wenn Sie in Chunks zuweisen, bewirkt ein Einfügen, dass dieser bestimmte Chunk neu zugewiesen wird, wenn nicht genügend Platz vorhanden ist (wie bei Vektoren).

Answer 3

Der Schlüssel ist, keine Annahmen zu machen, sondern den Iterator so zu behandeln, als ob er für ungültig erklärt wird.

Auch wenn es jetzt funktioniert, könnte eine neuere Version des Compilers oder des Compilers für eine andere Plattform kommen und Ihren Code beschädigen. Alternativ könnte ein Kollege kommen und entscheiden, Ihre Deque in einen Vektor oder eine verknüpfte Liste umzuwandeln.

Answer 4

Was interessant ist, dass push_back und push_front wird nicht keine Referenzen ungültig auf Elemente eines Deque. Nur Iteratoren sind als ungültig zu betrachten.

Der Standard, nach meinem Wissen, gibt nicht an warum. Wenn jedoch ein Iterator implementiert wird, der seine unmittelbaren Nachbarn kennt - wie eine Liste -, wird dieser Iterator ungültig, wenn er auf ein Element zeigt, das sich sowohl an der Kante der Deque als auch an der Kante eines Blocks befindet.

Answer 5

Weil der Standard sagt, kann es. Es schreibt nicht vor, dass deque als eine Liste von Blöcken implementiert wird. Sie erfordert eine bestimmte Schnittstelle mit bestimmten Vor- und Nachbedingungen und besonderen algorithmischen Komplexitätsminima.

Implementierer sind frei, das Ding auf jede erdenkliche Weise zu implementieren, solange es alle diese Anforderungen erfüllt. Eine sinnvolle Implementierung könnte Listen von Blöcken verwenden oder eine andere Technik mit unterschiedlichen Kompromissen verwenden.

Es ist wahrscheinlich unmöglich, zu sagen, dass eine Technik, als eine andere streng besser ist für alle Benutzer in allen Situationen. Aus diesem Grund bietet der Standard den Herstellern eine gewisse Entscheidungsfreiheit.

Answer 6

Meine Vermutung. push_back/push_front kann einen neuen Speicherblock zuweisen. Ein Deque-Iterator muss wissen, wann der Inkrement/Dekrement-Operator in den nächsten Block springen soll. Die Implementierung kann diese Information im Iterator selbst speichern. Das Inkrementieren/Dekrementieren eines alten Iterators nach push_back/push_front funktioniert möglicherweise nicht wie vorgesehen.

Dieser Code kann mit einem Laufzeitfehler fehlschlagen oder nicht. In meinem Visual Studio ist es im Debug-Modus fehlgeschlagen, aber im Freigabemodus zum Abschluss gekommen. Unter Linux verursachte es Segmentierungsfehler.

#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

Ein Iterator ist nicht nur eine Referenz auf die Daten. Es muss wissen, wie zu inkrementieren, etc.

Um den wahlfreien Zugriff zu unterstützen, werden Implementierungen eine dynamische Array von Zeigern auf die Chunks haben. Der Deque-Iterator zeigt in dieses dynamische Array. Wenn die Deque wächst, muss möglicherweise ein neuer Chunk zugewiesen werden. Das dynamische Array wird größer und macht seine Iteratoren und folglich die Iteratoren der Deque ungültig.

Es ist also nicht so, dass Chunks neu zugewiesen werden, aber das Array von Zeigern auf diese Chunks kann sein. In der Tat, wie Johannes Schaub bemerkte, werden Referenzen nicht für ungültig erklärt.

Beachten Sie auch, dass die Iteratorgarantien des Deques nicht kleiner als die des Vektors sind, die auch ungültig werden, wenn der Container wächst.