C++ iterador de deque invalidado después de push_front()

Question

Justo ahora, estoy leyendo el libro de AWL de Josuttis.

Por lo que yo sé, el vector C++ es una matriz c que se puede reasignar. Entonces, entiendo, ¿por qué después de push_back() todos los iteradores y referencias pueden dejar de ser válidos?

Pero mi pregunta es sobre std :: deque. Como sé, es una matriz de bloques grandes (c-array de c-arrays). Así que push_front() inserta un elemento al principio y si no hay espacio, deque asigna un nuevo bloque y coloca el elemento al final del bloque asignado.

Después de insertar() en el medio, todas las referencias e iteradores se vuelven inválidos y entiendo por qué: se mueven todos los elementos. Pero realmente malinterpreto la frase "... después de push_back() y push_front() todas las referencias siguen siendo válidas, pero los iteradores no" (la misma frase se puede encontrar @ estándar: 23.2.2.3)

¿Qué hace? ¡¿media?! Si las referencias son válidas, deque deque no podría reasignar (== mover) sus elementos. Entonces, ¿por qué los iteradores se vuelven inválidos? ¿Por qué no puedo usarlos después de la inserción de elementos no móviles? ¿O significa la frase, que no puedo estar seguro acerca de la igualdad de los iteradores para comenzar() o terminar() y desbordar?

Además, quiero mencionar, que después de borrar() todos los iteradores y referencias permanecen válidos (excepto el borrado :-)).

PD: por favor, no responda en forma "estándar": "no se puede usar porque EL ESTÁNDAR lo dice". Quiero entender por qué, qué puede pasar.

Answer 1

Creo que los iteradores de la razón se invalidan pero las referencias no pueden ser debido a la posible implementación deque de una matriz de punteros a las páginas del deque que almacenan los elementos. Una referencia a un elemento en un deque se referirá directamente al elemento en una 'página'. Sin embargo, un iterador en el deque podría depender del vector de punteros que apuntan a las distintas páginas.

Inserción de un nuevo elemento en una cola de doble extremo en uno u otro extremo nunca se requerirá la reasignación y moviendo exsting páginas de datos, pero podría requerir la adición a (y por lo tanto la reasignación de & copiar) la matriz de punteros de página, dejar sin iteradores que dependían en la matriz anterior de punteros de página.

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

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