Como el título pregunta.¿Por qué push_back o push_front invalida los iteradores de un deque?
Mi comprensión de una deque fue que asignó "bloques". No veo cómo asignar más espacio invalida los iteradores, y en todo caso, uno pensaría que los iteradores de un deque tendrían más garantías que un vector, no menos.
El estándar C++ no especifica cómo se implementa deque. No es necesario asignar espacio nuevo asignando un nuevo fragmento y encadenándolo a los anteriores, todo lo que se requiere es que la inserción en cada extremo se amortice a tiempo constante.
Por lo tanto, si bien es fácil ver cómo implementar deque de manera que ofrezca la garantía que desea [*], esa no es la única forma de hacerlo.
[*] Los iteradores tienen una referencia a un elemento, más una referencia al bloque en el que se encuentra para que puedan continuar hacia adelante/hacia atrás en los extremos del bloque cuando los alcanzan. Además, supongo que se hace referencia al propio deque, de modo que operator+ puede ser de tiempo constante como se espera para los iteradores de acceso aleatorio: seguir una cadena de enlaces de bloque a bloque no es lo suficientemente buena.
deque no es una lista, ¡los bloques no están encadenados! – curiousguy
Incluso cuando está asignando en trozos, un inserto hará que ese trozo en particular se reasigne si no hay suficiente espacio (como es el caso de los vectores).
La reasignación es la clave aquí. – curiousguy
La clave está en no hacer ninguna suposición simplemente tratar el iterador como si fuera invalidado.
Incluso si funciona bien ahora, una versión posterior del compilador o el compilador de una plataforma diferente podría aparecer y romper su código. Alternativamente, un colega puede aparecer y decidir convertir su deque en un vector o lista vinculada.
Lo que es más interesante es que push_back y push_front se no dejar sin efecto las referencias a los elementos de un deque. Solo se supone que los iteradores son inválidos.
La norma, que yo sepa, no indica por qué. Sin embargo, si se implementara un iterador que conociera sus vecinos inmediatos, como lo es una lista, ese iterador se volvería inválido si apuntaba a un elemento que estaba al borde del deque y al borde de un bloque.
Otra razón, creo, es que el iterador podría implementarse manteniendo un índice de un elemento. Si se inserta algo al principio/final de la deque, ese índice ya no es válido (uno por uno), aunque cualquier apuntador/referencia a ese elemento al que apuntaba sigue siendo válido, ya que no se realizó ninguna reasignación, de curso). Lo mismo cuando mantenemos el índice en una matriz de indicadores de bloque (como lo adiviné en mi comentario sobre la pregunta). –
Consulte mi [respuesta] (http://stackoverflow.com/a/39420347/3903076) para obtener una explicación de esto basada en una implementación directa. – filipos
Porque el estándar dice que sí. No exige que deque se implemente como una lista de fragmentos. Requiere una interfaz particular con condiciones previas y posteriores particulares y mínimos de complejidad algorítmicos particulares.
Los implementadores son libres de implementar la cosa de la manera que elijan, siempre que cumpla con todos esos requisitos. Una implementación sensata podría usar listas de fragmentos, o podría usar alguna otra técnica con diferentes intercambios.
Probablemente sea imposible decir que una técnica es estrictamente mejor que otra para todos los usuarios en todas las situaciones. Por eso, el estándar otorga libertad a los implementadores para elegir.
No creo que se refiera a una lista (por ejemplo, std :: list) de fragmentos, ya que los iteradores de acceso aleatorio no podrían ser O (1). –
Un vistazo rápido a una implementación sugiere que un deque es más parecido a un std :: vector
Mi conjetura. push_back/push_front puede asignar un nuevo bloque de memoria. Un iterador deque debe saber cuándo el operador de incremento/decremento debe saltar al siguiente bloque. La implementación puede almacenar esa información en el propio iterador. Incrementando/disminuyendo un viejo iterador después de push_back/push_front puede no funcionar como se esperaba.
Este código puede fallar o no con el error de tiempo de ejecución. En mi Visual Studio falló en el modo de depuración pero se ejecuta hasta la conclusión en el modo de lanzamiento. En Linux causó un error de segmentación.
#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;
}
}
}
Un iterador no es solo una referencia a los datos. Debe saber cómo incrementar, etc.
Para admitir el acceso aleatorio, las implementaciones tendrán una matriz dinámica de punteros a los fragmentos. El iterador deque apuntará a esta matriz dinámica. Cuando el deque crece, es posible que sea necesario asignar un nuevo fragmento. La matriz dinámica crecerá, invalidando sus iteradores y, en consecuencia, los iteradores de deque.
No es que los trozos se reasignen, pero la matriz de punteros a estos trozos puede ser. De hecho, como señaló Johannes Schaub, las referencias no se invalidan.
También tenga en cuenta que las garantías del iterador de deque no son menores que las del vector, que también se invalidan cuando el contenedor crece.
iirc, la implementación de deque de gcc mantiene una serie de punteros a esos bloques ... Si la matriz necesita ser reasignada, los iteradores pueden volverse inválidos. Tal vez esa es la razón? No estoy seguro ... Eso al menos explica por qué las inserciones en cualquiera de los extremos invalidan los iteradores, pero no las referencias/punteros a los elementos. –