Listas dinámicas - ArrayList
En este ejemplo, hemos usado el tipo ArrayList de la librería estándar para crear una lista dinámica:
|
const ArrayList = std.ArrayList; // incializamos las torres como un ArrayList vacío var a_towers: std.ArrayList(HydroTower) = .empty; defer a_towers.deinit(o_alloc); // libera al final del scope |
Esta estructura de datos nos hace la vida más fácil cuando necesitamos que nuestros arrays puedan crecer de manera dinámica en tiempo de ejecución.
La forma de declarar una lista dinámica es la siguiente:
// lista iniciada vacía
var nombre: std.ArrayList(T) = .empty;
// o reservando una capacidad inicial
var nombre: std.ArrayList(T) = try .initCapacity(...);
// o usando un array externo de base
var nombre: std.ArrayList(T) = try .initBuffer(&a_buff);
Es una alternativa flexible frente a los arrays estáticos que hemos usado hasta ahora. Los arrays normales como sabes siempre tienen el número de elementos fijo.
ArrayList nos ofrece unos métodos para operar con ellos:
|
append |
Append y sus variantes añade un elemento a la lista |
|
pop |
Saca el último elemento de la lista y lo devuelve, si no hay nada devuelve null |
|
orderedRemove |
Saca el primer elemento de la lista y lo devuelve |
|
clone |
Clona la lista |
Para incializar un ArrayList necesitamos un allocator explícito:
|
var gpa = std.heap.GeneralPurposeAllocator(.{}){}; const o_alloc = gpa.allocator(); |
En el ejemplo usamos .empty para inicializar el a_towers, la variable que almacenará las torres construidas para llevar el agua hasta el castillo:
|
// inicializamos las torres como un ArrayList(HydroTower) vacío var a_towers: std.ArrayList(HydroTower) = .empty; |
Seguro que te preguntas: ¿de dónde viene ese .empty?
Como ya has aprendido, podemos acceder a los archivos dónde se definen estas y otras estructuras de la librería estándar. En este caso, ArrayList está en el directorio dónde hemos descargado Zig, buscaremos en el subdirectorio std en el fichero array_list.zig.
Del apartado anterior sobre las librerías sabemos que, para que un elemento declarado en la librería sea accesible desde fuera, debe llevar delante la palabra clave pub. Por lo tanto, lo mismo tiene que cumplirse con empty: lo accedemos desde fuera así que tiene que ser público. Podemos buscar la definición con un IDE, con un editor de texto o directamente con grep desde la terminal:
|
grep -n "pub.*empty" ~/bin/zig-x86_64-linux-0.15.2/lib/std/array_list.zig 621: pub const empty: Self = .{ |
Vemos que empty está definido en la línea 621:
|
/// An ArrayList containing no elements. pub const empty: Self = .{ .items = &.{}, .capacity = 0, }; |
Obviamente .empty es lo mismo que ArrayList(HydroTower).empty. Vemos que iniciar nuestro ArrayList así significa que .items apunta a un array vacío y que se asigna un 0 a .capacity.
En el ejemplo anterior, vamos añadiendo, una a una, las instancias del struct HydroTower. Esto lo hacemos usando .append, según vamos construyendo las torres y alcanzando la altura necesaria:
|
// cuando añadimos una torre a la lista const o_tower = HydroTower{.n_height = n_tower_height}; // usamos el allocator try a_towers.append(o_alloc, o_tower); |
En lugar de iniciar la lista vacía, podemos usar .initCapacity(allocator, N). Esto es muy útil si podemos prever cuántos elementos tendremos. De ese modo, aumentamos la eficiencia del programa porque no vamos solicitando memoria uno en uno -recuerda que es una operación costosa y lenta:
|
// incializamos las torres con capacidad reservada var a_towers: ArrayList(HydroTower) = try .initCapacity(o_alloc, 21); |
Si superamos la capacidad inicial, la lista será ampliada automáticamente según lo necesitemos. Es mejor que esa ampliación sea mínima para mantener la eficiencia del proceso.
Hemos supuesto que podemos construir esas torres libremente, sin límites: todo el terreno desde el río hasta el castillo es apto para colocar una. Podemos construir 20, 23 o las que haga falta y nuestro allocator -que en este caso actúa como un capataz de obra- irá ocupando espacios en el heap según lo que necesitemos.
Para liberar la memoria asignada al final del scope actual, tal y como vimos con los allocators en el capítulo 5, usamos defer junto con .deinit:
|
// incializamos las torres con capacidad reservada var a_towers: ArrayList(HydroTower) = ... defer a_towers.deinit(o_alloc); // libera la memoria al final del scope |
Cuando el scope coincide con main, y el programa es tan lineal como en este caso, liberar la memoria manualmente no es necesrio: el sistema operativo la recupera al finalizar el programa de manera automática.
¿Y si la lista a_towers pudiera crecer pero solo hasta un límite? En ese caso podemos usar esta variante:
|
// sitios disponibles para hacer las torres var a_places: [14]HydroTower = undefined; // incializamos las torres con un número fijo de espacios var a_towers: ArrayList(HydroTower) = ArrayList(HydroTower) .initBuffer(&a_places); // añadimos una torre a la lista a_towers.appendBounded(o_tower) catch |err_x| { print( \\ ¡Imposible construir más torres, señor! \\ No tenemos suficientes sitios \\ {} \\ , .{err_x}); break; }; |
|
~~~~~ ¡Imposible construir más torres, señor! No tenemos suficientes sitios error.OutOfMemory Se han construido: 14 torres ... 14: 0L a 57.74m |
En el caso de inicializar una lista de esta manera, el comportamiento es muy parecido a trabajar con un slice sobre un array fijo, pero con control explícito de longitud y capacidad. Si buscas la definición de esta función, la encontrarás en el fichero array_list.zig en la línea 646:
|
/// Initialize with externally-managed memory. The buffer determines the /// capacity, and the length is set to zero... pub fn initBuffer(buffer: Slice) Self { return .{ .items = buffer[0..0], .capacity = buffer.len, }; } |
Como puedes ver, items es un slice vacío apuntando sobre el buffer externo y capacity está fijada a la longitud total de ese buffer. No se usa el heap para asignar la memoria y si superamos la capacidad de la lista nos dará un error.
En el ejemplo, capturamos el error cuando los 14 espacios disponibles para las torres no son suficientes para llegar hasta el castillo.
¿Cómo lo arreglarías?
Te doy una pista - los obreros podrían crear más sitios en la cuesta para colocar nuevas torres… o las torres podrían ser más altas.
Si modificas la constante N_EFFICIENCY_PER_METER de las torres. comprobarás como una mínima bajada de eficiencia puede hacer que apenas llegue agua hasta el castillo. Y así era el sistema del inventor: muy difícil de calibrar y mantener ya que cualquier desviación se amplifica torre a torre.
Mantener todas esas torres era un trabajo constante. Por eso el inventor creó un ayudante que, en la ciudad de Toledo -adyacente al castillo-, la muchedumbre llamó “el Hombre de Palo” - ya que muchas de sus partes, de verdad, estaban hechas de madera. Aunque el inventor -Juanelo- prefería llamarle Manitas.