example - queue c++

¿Por qué push_back o push_front invalidan los iteradores de un deque?

Question

Como lo pide el título.

Mi comprensión de un deque era que asignaba "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.

Answer 1

El estándar de C ++ no especifica cómo se implementa el deque. No es necesario asignar nuevo espacio al asignar un nuevo fragmento y encadenarlo a los anteriores, todo lo que se requiere es que la inserción en cada extremo se amortice a tiempo constante.

Entonces, 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 está, de modo que pueden continuar avanzando / retrocediendo desde los extremos del bloque cuando los alcanzan. Además, supongo que una referencia al propio deque, por lo que el operator+ puede ser de tiempo constante como se espera para los iteradores de acceso aleatorio, no es suficiente seguir una cadena de enlaces de bloque a bloque.

Answer 2

Incluso cuando se está asignando en porciones, una inserción hará que esa porción en particular se reasigne si no hay espacio suficiente (como es el caso de los vectores).

Answer 3

La clave es no hacer suposiciones, simplemente tratar el iterador como si fuera invalidado.

Incluso si funciona bien ahora, una versión posterior del compilador o del compilador para una plataforma diferente podría aparecer y romper su código. Alternativamente, un colega puede venir y decidir convertir tu deque en un vector o una lista enlazada.

Answer 4

Lo que es más interesante es que push_back y push_front no invalidarán ninguna referencia a los elementos de un deque. Solo los iteradores deben ser asumidos como inválidos.

El estándar, que yo sepa, no dice por qué. Sin embargo, si se implementara un iterador que fuera consciente de sus vecinos inmediatos, como lo es una lista, ese iterador se volvería inválido si señalaba un elemento que estaba tanto en el borde del deque como en el borde de un bloque.

Answer 5

Mi conjetura. push_back / push_front puede asignar un nuevo bloque de memoria. Un iterador de 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. Incrementar / disminuir un iterador anterior después de push_back / push_front puede no funcionar como se esperaba .

Este código puede o no fallar con un error de tiempo de ejecución. En mi Visual Studio falló en el modo de depuración pero se ejecutó hasta la conclusión en el modo de lanzamiento. En Linux causó falla 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;
        }
    }
}

Answer 6

Porque la norma dice que puede. No obliga a que el deque se implemente como una lista de fragmentos. Ordena una interfaz particular con condiciones previas y posteriores particulares y mínimos de complejidad algorítmica particular.

Los implementadores son libres de implementar la cosa en la forma que deseen, 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 compromisos.

Probablemente sea imposible decir que una técnica es estrictamente mejor que otra para todos los usuarios en todas las situaciones. Es por eso que el estándar le da a los implementadores cierta libertad para elegir.

Answer 7

Un iterador no es solo una referencia a los datos. Debe saber como 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 deba asignarse un nuevo fragmento. La matriz dinámica crecerá, invalidando sus iteradores y, en consecuencia, los iteradores de deque.

Por lo tanto, no es que los trozos se reasignen, sino que 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.