L'itérateur de C++ deque invalidé après push_front()

Question

Tout à l'heure, je lis le livre STL de Josuttis. Pour autant que je sache, le vecteur C++ est un tableau qui peut être réattribué. Donc, je comprends, pourquoi après push_back() tous les itérateurs et les références peuvent devenir invalides.

Mais ma question concerne std :: deque. Comme je sais, c'est un tableau de gros blocs (c-array de c-arrays). Donc, push_front() insère l'élément au début et s'il n'y a pas d'espace, deque alloue un nouveau bloc et place l'élément à la fin du bloc alloué.

Après insertion() au milieu toutes les références et les itérateurs deviennent invalides et je comprends pourquoi - tous les éléments sont déplacés. Mais je ne comprends vraiment pas la phrase "... après push_back() et push_front() toutes les références restent valides, mais pas les itérateurs" (la même phrase peut être trouvée @ standard: 23.2.2.3)

Qu'est-ce que c'est? signifier?! Si les références sont valides, alors deque ne peut pas réaffecter (== move) ses éléments. Alors pourquoi les itérateurs deviennent-ils invalides? Pourquoi ne puis-je pas les utiliser après l'insertion d'éléments non mobiles? Ou la phrase signifie-t-elle que je ne peux pas être sûr de l'égalité des itérateurs pour begin() ou end() et pour déborder?

Aussi, je tiens à mentionner, qu'après effacement() tous les itérateurs et références restent valides (sauf l'effacé :-)). PS: ne répondez pas sous forme "standard": "il ne peut pas être utilisé car LE STANDARD le dit". Je veux comprendre pourquoi, ce qui peut arriver.

Answer 1

Je pense que la raison pour laquelle les itérateurs sont invalidés mais les références ne sont peut-être pas dues à l'implémentation de deque possible d'un tableau de pointeurs sur les pages du deque qui stockent les éléments. Une référence à un élément dans une deque se référera directement à l'élément dans une «page». Cependant, un itérateur dans le fichier peut être dépendant du vecteur de pointeurs qui pointent vers les différentes pages. L'insertion d'un nouvel élément dans une table à une fin ou à une autre ne nécessitera jamais de réaffecter et de déplacer les pages de données existantes, mais il faudra peut-être ajouter (et donc réattribuer & copie) le tableau des pointeurs de page, invalidant tous les itérateurs dépendants. sur le tableau précédent de pointeurs de page.

Array of pointers   
(if this grows     Data Pages 
and gets copied,   (these never move 
iterators are invalid)  due to insert at ends) 
-----------------   -------------------- 

+----------+    +----------+ 
|   -+-------------->|   | 
+----------+    +----------+ 
|   -+---------+  |   | 
+----------+   |  +----------+ 
|   -+---+  |  |   | 
+----------+ |  |  +----------+ 
       |  | 
       |  | 
       |  | 
       |  |  +----------+ 
       |  +---->|   | 
       |   +----------+ 
       |   |   | 
       |   +----------+ 
       |   |   | 
       |   +----------+ 
       |   
       |   +----------+ 
       +---------->|   | 
          +----------+ 
          |   | 
          +----------+ 
          |   | 
          +----------+