Saltar al contenido
wandres.dev
Iniciar sesión

Recorrido narrado

Un recorrido completo

  • Estado inicial: bloque A, longitud 4, capacidad 4. Los cuatro valores pertenecen a A.
  • Reserva: aparece B con capacidad 8. A todavía conserva los valores.
  • Traslado: cada valor pasa al mismo índice de B. Durante la operación existen ambas reservas.
  • Publicación: la cabecera pasa a referenciar B; A deja de ser el almacenamiento del vector.
  • Liberación: se devuelve A. Una referencia a su dirección antigua ya no sirve para acceder al elemento.
  • Inserción: se escribe 42 en B y la longitud pasa a 5.

Recorre los seis pasos de la figura y explica cada cambio con estas seis observaciones. Las identidades de los elementos se conservan aunque sus direcciones puedan cambiar. Al terminar, confirma que recorriste el ejemplo.

La mudanza de un vector en seis pasosSeis pasos con dos bloques, A y B. Paso 1: A guarda 12, 23, 31 y 8; ptr apunta a A, len 4, cap 4. Paso 2: se reserva B con capacidad 8, vacío; ptr sigue en A. Paso 3: los cuatro valores se trasladan al mismo índice de B; ptr sigue en A y A aún conserva los valores. Paso 4: ptr pasa a B, con len 4 y cap 8; A queda atenuado. Paso 5: A se libera, con borde punteado. Paso 6: se escribe 42 en la posición 4 de B y len pasa a 5.Paso 1 de 6: inicio. ptr → A, len 4, cap 4AB1223318todavía no existe← ptrPaso 2 de 6: reserva. Aparece B (cap 8); ptr → AAB1223318← ptrPaso 3 de 6: traslado. Los valores pasan a B; ptr → AAB122331812*23*31*8*← ptrPaso 4 de 6: publicación. ptr → B, len 4, cap 8AB12233181223318← ptrPaso 5 de 6: liberación. A se devuelve; ptr → BABliberado1223318← ptrPaso 6 de 6: inserción. 42 en B; ptr → B, len 5, cap 8ABliberado122331842*← ptr
Los mismos seis pasos del ejemplo. Con * se marca lo recién escrito; borde punteado, posiciones sin valor; atenuado, un bloque que ya no es el almacenamiento.

Su fila en la tabla de costos

Crecer añade una condición a insertar al final. En la tabla de costos, la fila del array con capacidad que se agota queda así:

Operación Costo Condición
insertar al final O(1) hay capacidad libre (longitud menor que capacidad)
insertar al final O(n) no hay capacidad: se traslada cada elemento al bloque nuevo

Recorre las 6 observaciones del ejemplo. Al pasar al siguiente momento, este cuenta como leído.

Paso 1 de 6: Bloque A: cuatro valores, longitud 4 y capacidad 4.

Referencia → A · longitud 4 · capacidad 4

A: 12, 23, 31, 8

B: sin reservar