Dynamic lists - ArrayList
In this example, we have used the ArrayList type from the standard library to create a dynamic list:
|
const ArrayList = std.ArrayList; // initialize the towers as an empty ArrayList var a_towers: std.ArrayList(HydroTower) = .empty; defer a_towers.deinit(o_alloc); // freed at the end of the scope |
This data structure makes our lives easier when we need our arrays to grow dynamically at runtime.
The way to declare a dynamic list is as follows:
// list initialized empty
var name: std.ArrayList(T) = .empty;
// or reserving an initial capacity
var name: std.ArrayList(T) = try .initCapacity(...);
// or using an external backing array
var name: std.ArrayList(T) = try .initBuffer(&a_buff);
It is a flexible alternative to the static arrays we have used so far. Regular arrays, as you know, always have a fixed number of elements.
ArrayList provides several methods to operate on it:
|
append |
Append and its variants add an element to the list. |
|
pop |
Removes the last element from the list and returns it. If there is nothing, it returns null. |
|
orderedRemove |
Removes the first element from the list and returns it |
|
clone |
Clones the list |
To initialize an ArrayList, we need an explicit allocator:
|
var gpa = std.heap.GeneralPurposeAllocator(.{}){}; const o_alloc = gpa.allocator(); |
In the example we use, .empty to initialize a_towers, the variable that will store the towers built to carry the water up to the castle:
|
// initialize the towers as an empty ArrayList(HydroTower) var a_towers: std.ArrayList(HydroTower) = .empty; |
You are probably wondering: where does that .empty come from?
As you have already learned, we can access the files where these and other structures of the standard library are defined. In this case, ArrayList is located in the directory where we downloaded Zig. We can look for it in the std subdirectory, in the array_list.zig file.
From the previous section on libraries, we know that, for an element declared in a library to be accessible from outside, it must be preceded by the pub keyword. Therefore, the same must apply to empty: we access it from outside, so it has to be public. We can look for its definition using an IDE, a text editor, or directly with grep from the terminal:
|
grep -n "pub.*empty" ~/bin/zig-x86_64-linux-0.15.2/lib/std/array_list.zig 621: pub const empty: Self = .{ |
We see that empty is defined on line 621:
|
/// An ArrayList containing no elements. pub const empty: Self = .{ .items = &.{}, .capacity = 0, }; |
Obviously, .empty is the same as ArrayList(HydroTower).empty. We see that initializing our ArrayList this way means that .items points to an empty array and that .capacity is set to 0.
In the previous example, we added the instances of the HydroTower struct one by one. We do this using .append as we build the towers and reach the required height:
|
// when we add a tower to the list const o_tower = HydroTower{.n_height = n_tower_height}; // we use the allocator try a_towers.append(o_alloc, o_tower); |
Instead of initializing the ArrayList to an empty list, we can use .initCapacity(allocator, N). This is very useful if we can anticipate how many elements we will have. In this way, we increase the efficiency of the program because we avoid requesting memory one by one - remember that this is a costly and slow operation:
|
// initialize the towers with reserved capacity var a_towers: ArrayList(HydroTower) = try .initCapacity(o_alloc, 21); |
If we exceed the initial capacity, the list will be automatically expanded as needed. It is better to keep that expansion minimal to maintain process efficiency.
We have assumed that we can build those towers freely, without limits: all the terrain from the river to the castle is suitable for placing one.
We can build 20, 23, or as many as needed, and our allocator - which in this case acts like a construction foreman - will occupy space on the heap according to what we require.
To free the memory allocated at the end of the current scope, as we saw with allocators in chapter 5, we use defer together with .deinit:
|
// we initialize the towers with reserved capacity var a_towers: ArrayList(HydroTower) = ... defer a_towers.deinit(o_alloc); // frees the memory at the end of the scope |
When the scope is main, and the program is as linear as in this case, freeing the memory manually is not necessary: the operating system reclaims it automatically when the program ends.
What if the a_towers list could grow but only up to a limit? In that case, we can use this variant:
|
// available places to build the towers var a_places: [14]HydroTower = undefined; // initialize the towers with a fixed number of slots var a_towers: ArrayList(HydroTower) = ArrayList(HydroTower) .initBuffer(&a_places); // add a tower to the list a_towers.appendBounded(o_tower) catch |err_x| { print( \\ Impossible to build more towers, sir! \\ We do not have enough places \\ {} \\ , .{err_x}); break; }; |
|
~~~~~ Impossible to build more towers, sir! We do not have enough places error.OutOfMemory Built towers: 14 ... 14: 0L at 57.74m |
When initializing a list in this way, the behavior is very similar to working with a slice over a fixed array, but with explicit control over length and capacity. If you look up the definition of this function, you will find it in the array_list.zig file at line 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, }; } |
As you can see, items is an empty slice pointing to the external buffer, and capacity is set to the buffer's total length. The heap is not used for memory allocation, and if we exceed the list's capacity, we will get an error.
In the example, we catch the error when the 14 available slots for the towers are not enough to reach the castle.
How would you fix it?
I will give you a hint - the workers could create more places on the slope to install new towers… or the towers could be taller.
If you modify the N_EFFICIENCY_PER_METER constant of the towers, you will see how a minimal drop in efficiency can make almost no water reach the castle. And that is how the inventor’s system was: very difficult to calibrate and maintain, since any deviation is amplified from tower to tower.
Maintaining all those towers was constant work. That is why the inventor created an assistant who, in the city of Toledo - adjacent to the castle - the crowd called “the Man of Wood” - since many of his parts were, in fact, made of wood. Although the inventor, Juanelo, preferred to call him Manitas.