std.collections' other types

What you’ll build

The parts of a small text editor’s back end: an undo history, a queue of files to save, a list of jobs by urgency, an index of words in order, a word counter, and a list of recent files. Each is a collection from std.collections made for that job. They all go in a For ... In, and they share names: Add, Count, Contains, Clear, and Clone mean the same in each.

Stack: last in, first out

A Stack gives back the value added last first, which is what an undo history needs. Push adds a value on top, Pop takes the top one off, and Peek reads it without taking it. Popping an empty Stack panics; TryPop gives Null instead.

Import std.core
Import std.collections

Local undo = Stack<String>()
undo.Push("type 'hello'")
undo.Push("make bold")
undo.Push("delete line")

Print("next undo: {undo.Peek()}")
Print(undo.Pop())
Print(undo.Pop())
Print(undo.ToArray())
Print(undo.TryPop() ?? "-", undo.TryPop() ?? "nothing to undo")

next undo: delete line
delete line
make bold
[type 'hello']
type 'hello' nothing to undo

Queue: first in, first out

A Queue gives values back in the order they came, like people in a line. Enqueue adds at the back, and Dequeue takes from the front.

Import std.core
Import std.collections

Local saves = Queue<String>()
saves.Enqueue("notes.txt")
saves.Enqueue("todo.md")
saves.Enqueue("draft.txt")
While saves.Count > 0
    Print("saving {saves.Dequeue()}")
End While

saving notes.txt
saving todo.md
saving draft.txt

A Deque adds and removes at both ends, with AddFirst, AddLast, RemoveFirst, and RemoveLast.

PriorityQueue: smallest first

A PriorityQueue always gives back its smallest value first, whatever order they were added in. Given a function that says which of two values comes first, it orders values by that instead. Here each job is a tuple of its urgency and its name, and the lower urgency goes first.

Import std.core
Import std.collections

Local jobs = PriorityQueue<(Int, String)>(Function(a, b) => a.0 < b.0)
jobs.Add((3, "check spelling"))
jobs.Add((1, "autosave"))
jobs.Add((2, "rebuild index"))
While jobs.Count > 0
    Local urgency, name = jobs.Pop()
    Print("{urgency}: {name}")
End While

1: autosave
2: rebuild index
3: check spelling

SortedMap: keys in order

A Map keeps keys in the order they were added. A SortedMap keeps them sorted, and can find the nearest key at or below one with Floor, or at or above it with Ceiling, as an entry that can be Null. Here the first key at or after “lemon” is “mango”.

Import std.core
Import std.collections

Local index = SortedMap<String, Int>()
index["zebra"] = 41
index["apple"] = 3
index["mango"] = 17
Print(index)
Print(index.Keys())
Print(index.First() ?? ("", 0))
Print(index.Ceiling("lemon") ?? ("", 0))

{apple: 3, mango: 17, zebra: 41}
[apple, mango, zebra]
(apple, 3)
(mango, 17)

Counter: how many of each

A Counter counts how many times each value was added. Reading a value it hasn’t seen gives 0, and MostCommon lists the values with the highest counts.

Import std.core
Import std.collections
Import std.text

Local words = Counter<String>()
words.AddAll("to be or not to be that is the question".Split(" "))
Print(words["be"], words["question"], words["maybe"])
Print(words.MostCommon(2))

2 1 0
[(to, 2), (be, 2)]

RingBuffer: the last few

A RingBuffer holds a fixed number of values. Once it’s full, adding one drops the oldest, so it always holds the most recent, as a list of recent files does.

Import std.core
Import std.collections

Local recent = RingBuffer<String>(3)
For file In ["a.txt", "b.txt", "c.txt", "d.txt", "e.txt"]
    recent.Add(file)
End For
Print(recent, recent.IsFull)

[c.txt, d.txt, e.txt] True

std.collections has more: Grid for a fixed grid of cells, Trie for String keys by prefix, LinkedList, BitSet, LruCache, MultiMap, IntervalTree, and immutable collections that threads can share. The standard library’s reference lists them all.

What you learned

• A Stack gives back the newest value first, and a Queue the oldest.
• A PriorityQueue gives back the smallest value, or the first by a function you give it.
• A SortedMap keeps its keys in order, with Floor and Ceiling to find the nearest.
• A Counter counts values, and a RingBuffer keeps the last few.
• std’s collections share Method names, so what you learn for one carries over.