Arrays, slices and algorithms

An array that grows

int[] scores = [72, 95, 88]; declares a dynamic array. It has a length, an index for every element, and room to grow: scores ~= 100 appends a value and leaves scores.length one larger. scores[0] is the first element and scores[$ - 1] is the last, with $ standing for the length.

The length is part of the value, not a separate variable. scores.length = 2 keeps the first two elements and forgets the rest; setting it longer fills the new slots with the type default. Appending is the safe way to grow, because it keeps the length and the storage in step.

An array of structs is one list of records rather than several lists of fields, which is the reason arrays and structs are taught together later in the course. Adding a field then means changing one type, not every loop that walked three lists in step.

A slice is a window

scores[1 .. $ - 1] is a slice: every element except the first and the last, sharing the same memory as the original. Nothing is copied, so slicing a long list is cheap. It also means a change made through the slice is visible through the array.

sort sorts in place, so it reorders the array you handed it. When the original order matters, copy first with .dup, which builds a real second array, and sort the copy.

std.algorithm and std.array

sort puts an array in order, canFind answers whether a value is present, and filter! and map! build new sequences: filter keeps the elements that pass a test, map turns each element into something else. The ! introduces the little function, as in scores.filter!(s => s >= 88).

filter and map are lazy: they describe work rather than doing it, so nothing happens until something asks for the values. writeln asks, but the type it receives is a range rather than an array, which is why .array appears at the end — it builds the array and makes the result easy to print and to keep.

A range is the general idea behind filter and map: something that can be asked for its next value until it has none. An array is one kind of range, which is why the same functions work on a file, a string or a generated sequence. .array is the step that turns the description back into storage.

Two words and a window

A dynamic array value is a pointer to its first element plus a length. Passing it to a function copies those two words, not the elements, which is why arrays travel cheaply while structs are copied whole. Indexing checks the length first, so reading one past the end stops the program with a range error instead of returning whatever memory sits there.

A slice is the same pair with a different starting point. scores[1 .. 3] points at the second element and carries a length of two, so it shares storage with the original. Writing through either name is visible through the other, and no allocation happens when the slice is made.

Growth can move the data

Appending with ~= may need more room than the block has. When it does, the runtime allocates a larger block, copies the elements across and leaves the old block where it was. A slice still pointing at the old block now sees frozen values, which is why a slice kept across an append is a bug waiting to happen.

.dup is the explicit copy: a new block with the same elements, safe to sort or modify without touching the original. Assigning to .length resizes when it can, and .capacity reports how much room is already reserved, which is the number to watch when a loop appends a million times.

Sort in place, then slice

import std.stdio;
import std.algorithm;

void main() {
    int[] xs = [4, 1, 3];
    sort(xs);
    writeln(xs);
    writeln(xs[1 .. $]);
}

Try these next

• Change the window to xs[0 .. 2], sort it, and predict the new order before running.
• Print .capacity before and after a series of appends and explain the jumps.
• Take a slice, append to the original, and describe which values the slice can still see.