Collections in the standard library
Sets, deques, stacks, queues, ordered maps and priority queues, all built around a prototype value.
The language gives you List<T> and Map<K, V>. The standard library adds the
data structures those two cannot express.
Every one of these classes takes a prototype value in its constructor, which
is how an empty typed collection is created, the language has no empty literal
and no List<T>() call. See
Standard library overview.
Set<T>
An unordered collection of unique values.
import { Set } from std.collections.set
fn main() {
let s = Set<int>(0)
s.add(3)
s.add(3)
s.add(4)
println(s.size()) // 2
println(s.contains(3)) // true
println(s.remove(3)) // true
println(s.size()) // 1
s.clear()
println(s.size()) // 0
}
| Member | Signature |
|---|---|
add |
add(v: T) |
contains |
contains(v: T) -> bool |
size |
size() -> int |
remove |
remove(v: T) -> bool |
clear |
clear() |
toList |
toList() -> List<T> |
Set operations are free functions, because they take two sets and return a third:
import { Set, union, intersect, difference } from std.collections.set
fn main() {
let a = Set<int>(0)
a.add(1)
a.add(2)
let b = Set<int>(0)
b.add(2)
b.add(3)
let u = union(a, b)
let i = intersect(a, b)
let d = difference(a, b)
println("union {u.size()}") // 3
println("intersect {i.size()}") // 1
println("difference {d.size()}") // 1
}
| Function | Signature |
|---|---|
union |
union<K>(a: Set<K>, b: Set<K>) -> Set<K> |
intersect |
intersect<K>(a: Set<K>, b: Set<K>) -> Set<K> |
difference |
difference<K>(a: Set<K>, b: Set<K>) -> Set<K> |
Stack<T> and Queue<T>
Both have the same shape. Queue is FIFO, Stack is LIFO.
import { Stack } from std.collections.stack
import { Queue } from std.collections.queue
fn main() {
let s = Stack<int>(0)
s.push(1)
s.push(2)
match (s.peek()) {
case some(v) -> { println("stack top {v}") } // 2
case none -> { println("empty") }
}
match (s.pop()) {
case some(v) -> { println("stack pop {v}") } // 2
case none -> { println("empty") }
}
let q = Queue<int>(0)
q.push(1)
q.push(2)
match (q.pop()) {
case some(v) -> { println("queue pop {v}") } // 1
case none -> { println("empty") }
}
}
| Member | Signature |
|---|---|
push |
push(v: T) |
pop |
pop() -> T? |
peek |
peek() -> T? |
size |
size() -> int |
clear |
clear() |
Both pop and peek return T?, which is the important difference from the
builtin List.pop(), which returns the element directly. Prefer these when you
need a safe empty check.
Deque<T>
A double-ended queue, with a separate method per end.
import { Deque } from std.collections.deque
fn main() {
let d = Deque<int>(0)
d.pushBack(2)
d.pushFront(1)
println(d.size()) // 2
match (d.front()) {
case some(v) -> { println("front {v}") } // 1
case none -> { println("empty") }
}
match (d.back()) {
case some(v) -> { println("back {v}") } // 2
case none -> { println("empty") }
}
match (d.popFront()) {
case some(v) -> { println("popFront {v}") } // 1
case none -> { println("empty") }
}
match (d.popBack()) {
case some(v) -> { println("popBack {v}") } // 2
case none -> { println("empty") }
}
}
| Member | Signature |
|---|---|
pushFront / pushBack |
(v: T) |
popFront / popBack |
() -> T? |
front / back |
() -> T? |
size |
size() -> int |
clear |
clear() |
OrderedMap<K, V>
A map that remembers insertion order. Note the naming: it is set, not index
assignment, and keyList / valueList, not keys / values.
import { OrderedMap } from std.collections.orderedmap
fn main() {
let m = OrderedMap<string, int>("", 0)
m.set("a", 1)
m.set("b", 2)
m.set("c", 3)
println(m.size()) // 3
println(m.has("a")) // true
let keys = m.keyList()
for (k in keys) {
print("{k} ")
}
println("") // a b c
match (m.get("a")) {
case some(v) -> { println("a = {v}") }
case none -> { println("missing") }
}
m.remove("a")
println(m.size()) // 2
}
| Member | Signature |
|---|---|
set |
set(k: K, v: V) -> bool |
get |
get(k: K) -> V? |
has |
has(k: K) -> bool |
remove |
remove(k: K) -> bool |
keyList |
keyList() -> List<K> |
valueList |
valueList() -> List<V> |
size |
size() -> int |
clear |
clear() |
Reach for this over the builtin Map when output order matters.
PriorityQueue<T>
A binary heap. The constructor takes a prototype and a comparison function
that returns true when its first argument has the higher priority.
import { PriorityQueue } from std.collections.priorityqueue
fn main() {
let pq = PriorityQueue<int>(0, fn(a: int, b: int) -> bool { return a < b })
pq.push(3)
pq.push(1)
pq.push(2)
match (pq.pop()) {
case some(v) -> { println("first {v}") } // 1
case none -> { println("empty") }
}
match (pq.pop()) {
case some(v) -> { println("second {v}") } // 2
case none -> { println("empty") }
}
println("size {pq.size()}")
}
| Member | Signature |
|---|---|
push |
push(v: T) |
pop |
pop() -> T? |
peek |
peek() -> T? |
size |
size() -> int |
Flip the comparison to get a max-heap: fn(a: int, b: int) -> bool { return a > b }.
std.collections.list: free functions
Helpers for the builtin List<T>:
import { sliceOf, filled, containsElem, indexOfElem } from std.collections.list
fn main() {
let xs = [1, 2, 3, 4]
let mid = sliceOf(xs, 1, 3, 0)
println("slice len {len(mid)}") // 2
let f = filled(7, 3)
println("first {f[0]} len {len(f)}") // 7 3
println(containsElem(xs, 3)) // true
println(indexOfElem(xs, 3)) // 2
}
| Function | Signature |
|---|---|
sliceOf |
sliceOf<T>(xs: List<T>, lo: int, hi: int, proto: T) -> List<T> |
filled |
filled<T>(proto: T, count: int) -> List<T> |
containsElem |
containsElem<T>(xs: List<T>, v: T) -> bool |
indexOfElem |
indexOfElem<T>(xs: List<T>, v: T) -> int |
sliceOf and filled take a prototype for exactly the empty-result case, a
zero-length slice, or filled with a count of zero.
Choosing a structure
| Need | Use |
|---|---|
| Ordered sequence, indexable | List<T> |
| Key lookup | Map<K, V> |
| Key lookup in insertion order | OrderedMap<K, V> |
| Uniqueness | Set<T> |
| Last in, first out | Stack<T> |
| First in, first out | Queue<T> |
| Both ends | Deque<T> |
| Smallest / largest first | PriorityQueue<T> |
Next steps
- Lists and maps: the language-level collections.
- Threads and concurrency
