Complejidad de STL deque :: insert()

Question

que aprendió la complejidad de deque::insert() del C++ estándar de 2003 (capítulo 23.2.1.3) de la siguiente manera:

En el peor de los casos, la inserción de un solo elemento en una deque lleva tiempo lineal en el mínimo de la distancia desde el punto de inserción hasta el comienzo del deque y la distancia desde el punto de inserción hasta el final del deque.

Siempre entiendo la implementación de stl deque como una colección de fragmentos de memoria. Por lo tanto, una inserción solo afectará a los elementos en la misma porción de memoria que la posición de inserción. Mi pregunta es, ¿qué significa el estándar por "lineal en el mínimo de la distancia desde el punto de inserción hasta el comienzo del deque y la distancia desde el punto de inserción hasta el final del deque"?

Mi comprensión es porque el estándar C++ no impone una determinada implementación de deque. La complejidad es solo en general para el peor de los casos. Sin embargo, en la implementación real en los compiladores, es lineal a la cantidad de elementos en un fragmento de memoria, que puede variar según el tamaño de los diferentes elementos.

Otra suposición podría ser que, como insert() invalidará todos los iteradores, deque necesita actualizar todos los iteradores. Por lo tanto, es lineal.

Answer 1

std :: deque es normalmente (siempre?) Implementado como una colección de fragmentos de memoria, pero que normalmente no le insertará un trozo nuevo sólo para que inserte un nuevo elemento en el medio de la colección . Como tal, encontrará si el punto de inserción está más cerca del principio o del final, y mezcla los elementos existentes para dejar espacio para el nuevo elemento en un fragmento existente. Solo agregará un nuevo fragmento de memoria al principio o al final de la colección.

Answer 2

Lineal en el número de elementos insertados (copia de la construcción). Además, dependiendo de la implementación de la biblioteca en particular, el tiempo lineal adicional en el número de elementos entre la posición y uno de los extremos de la deque. Reference...

Answer 3

Tu conjetura es ... 99.9% cierto. Todo depende de la implementación real. Lo que el estándar especifica es el requisito mínimo tanto para los implementadores (que no pueden pretender ser estándar si no se ajustan a las especificaciones) como para los usuarios (que no deben esperar "mejores desempeños" si escriben código independiente de implementación).

La idea detrás de la especificación, es un fragmento (a == uno) de la memoria no inicializada donde los elementos se asignan alrededor del centro ... hasta que haya espacio para ellos. Insertar en el medio significa cambio. Insertar en el frente o en el extremo significa simplemente construir en su lugar. (cuando no hay espacio, se realiza una reasignación) No se puede confiar en los índices y los iteradores después de una modificación, ya que no podemos asumir qué se ha desplazado y en qué dirección.

Implementación más eficiente no use un solo fragmento, sino un bloque múltiple para redistribuir el problema de "desplazamiento" y asignar memoria en tamaño constante desde el sistema subyacente (limitando así la reasignación y la fragmentación). Si se dirige a uno de ellos, puede esperar mejores resultados; de lo contrario, es mejor no asumir ninguna optimización de la estructura.

Answer 4

Creo que sería mejor ser atendido por un diagrama ... ¡juguemos con arte ASCII!

Una deque es generalmente una matriz de fragmentos de memoria, pero aparte de los trozos de memoria frontal y posterior están llenos.Esto es necesario porque un deque es un RandomAccessContainer, y para obtener O (1) el acceso a cualquier recipiente, no se puede tener un número ilimitado de contenedores desde el que se lee el tamaño:

bool size() const { return first.size + (buckets.size()- 2) * SIZE + last.size; } 

T& operator[](size_t i) { 
    if (i < first.size) { return first[SIZE - i]; } 

    size_t const correctedIndex = i - first.size; 
    return buckets[correctedIndex/SIZE][correctedIndex % SIZE]; 
} 

Esas operaciones son O (1) debido a la multiplicación/división!

En mi ejemplo, supongo que un trozo de memoria está lleno cuando contiene 8 elementos. En la práctica, nadie dijo que el tamaño debería ser fijo, solo que todos los cubos internos deben tener el mismo tamaño.

// Deque 
0:  ++ 
1: ++++++++ 
2: ++++++++ 
3: ++++++++ 
4: +++++ 

Ahora dicen que queremos insertar en el índice 13. Se sitúa en algún lugar en el cubo de la etiqueta 2. Hay varias estrategias que podemos pensar:

• extender cubeta 2 (sólo)
• introducir un nuevo cubo, ya sea antes o después de 2 y orden aleatorio sólo unos pocos elementos

Pero esas dos estrategias violaría el invariante que todos los cubos "internos" tienen el mismo num ber de elementos.

Por lo tanto nos quedamos con barajar los elementos alrededor, ya sea hacia el principio o el final (el que sea más barato), en nuestro caso:

// Deque 
0:  +++ 
1: ++++++++ 
2: +O++++++ 
3: ++++++++ 
4: +++++ 

Nota cómo cubo de 0 creció.

Esta combinación implica que, en el peor de los casos, moverá la mitad de los elementos: O (N/2).

deque tiene O (1) inserte al comienzo o al final, porque allí solo se trata de agregar el elemento en el lugar correcto o (si el recipiente está lleno) creando un nuevo cubo.

Existen otros contenedores que tienen un mejor comportamiento de inserción/borrado en índices aleatorios, basados ​​en B+ Trees. En un árbol B + indexado puede, en lugar de una "clave" (o en paralelo) mantener internamente un recuento de los elementos antes de una posición determinada. Hay varias técnicas para hacer esto de manera eficiente. Al final se obtiene un recipiente con:

• O (1): vacío, tamaño
• O (log N): a, insertar, borrar

puede comprobar el módulo de blist en Python que implementa un elemento similar a una lista de Python respaldado por dicha estructura.