Standard Library

#Collections

Status: standard library specification draft.

This chapter defines the part of std.collections that lib/std writes in ordinary hd over the language tier:

• the List methods view and chunks, and the access and building methods such as get, take, and extend;
• the ListView[T] type returned by view, chunks, and windows;
• the List helpers, such as sorted_by_key, group_by, and windows, and the function counts;
• the Map methods contains_key, keys, values, and get_or;
• the set Set[T], the double-ended queue Deque[T], and the max-heap Heap[T], which are values as a list is.

The language tier keeps what the compiler knows about a list (List Indexing, Built-In Methods, Iterator Snapshots):

#List And Map Values

A list or a map is a value (Collection Values), and the std methods treat it as one.

fn joined(first: List[i32], second: List[i32]) -> List[i32]:
    let mut all = first
    all.extend(second)  # first is unchanged
    all

1. std-collections.value.receiverA std method that changes a list or a map, as extend does, needs its receiver in a writable place, as a language-tier changing method does (types.coll.writable).
2. std-collections.value.own-copySuch a change reaches only the receiver's own value. Another copy of the list or the map is unchanged.
3. std-collections.value.resultsA method that returns a list or a map, as keys, filter, and chunks do, returns a new value, which the caller may bind with let mut and change.
4. std-collections.value.pinned-lengthA std method that changes the length of a pinned list or map, as extend with a non-empty list does, is a checked runtime panic, as a language-tier change is (ref.elem.pinned, ref.elem.pinned.map). Panic: collection-pinned.
5. std-collections.value.ref-receiverEach such method takes &mut self. On a map value or a list element, as in groups[key].extend(more), it changes the collection where it is stored, as types.coll.nested states for every change through a path.

#List Methods

std gives List[T] these methods, beside the language-tier ones:

1. std-collections.list.chunks.viewschunks(size) returns consecutive read-only ListView[T] values in order; only the last view may be shorter than size.
2. std-collections.list.chunks.sizeA size below 1 panics. Panic: explicit-panic.
3. std-collections.list.window-borrowchunks and windows take &self, so every returned view refers to the receiver's place.
4. std-collections.list.window-costBoth methods create one result list of views and should copy no elements.

use std.collections.ListView

fn pairs(items: *List[i32]) -> List[ListView[i32]]:
    items.chunks(2)  # views of [1, 2] and [3] for [1, 2, 3]

Note. piece.to_list() copies a returned view into a list. A copy of a run of elements is also a slice, items[start..end], a new list (Slicing).

#Views

view gives a read-only window on a run of a list's elements, with no copy. It refers to the list's place, as a &self method does:

use std.collections.ListView

fn window(items: List[i32]) -> ListView[i32]:
    items.view(1, 3)

fn total(view: ListView[i32]) -> i32:
    let sum = 0
    for item in view:
        sum = sum + item
    sum + view[view.len() - 1]

ListView[T] has this surface:

1. std-collections.viewview(start, end) returns a ListView[T] of the list's elements at indices start up to, not including, end.
2. std-collections.view.typestd.collections declares ListView[T] with private fields and the surface in the table above, and no other method or trait implementation.
3. std-collections.view.placeview takes &self, so the view refers to the list's place: a binding, a field, or a value reached through a reference. Called on a list that is no place, such as a call result, it refers to a new object that holds the list.
4. std-collections.view.valueA ListView[T] is a struct value. A copy of a view is another window on the same place.
5. std-collections.view.importListView is not a prelude name, so code that names it imports it, as in use std.collections.ListView.
6. std-collections.view.no-copyCreating a view copies no element.
7. std-collections.view.rangeA start or end that is greater than the list's length is a checked runtime panic. Panic: index-out-of-bounds.
8. std-collections.view.reversedA start greater than end is a checked runtime panic. Panic: index-out-of-bounds.
9. std-collections.view.lenlen returns the number of elements in the view, end - start.
10. std-collections.view.indexview[i] reads the list's element at index start + i.
11. std-collections.view.index.rangeA view index that is not less than the view's len is a checked runtime panic, even when the list has an element there. Panic: index-out-of-bounds.
12. std-collections.view.iterIterating a view yields its elements in order, each as T.
13. std-collections.view.cursorA view's cursor type is ListViewIter[T], which std.collections declares with private fields.
14. std-collections.view.to-list-valueto_list returns a new list value that holds the view's elements in order, as the slice items[start..end] does, so let mut copy = view.to_list() may grow the copy.
15. std-collections.view.read-onlyA view has no IndexSet implementation, so assigning to view[i] is an error. Error: invalid-assignment-target.
16. std-collections.view.writesAn element write to the list's place, as items[i] = v, shows through every view of it, so a later read of the view gives the new value.
17. std-collections.view.invalidateChanging the list's length invalidates every view of it.
18. std-collections.view.invalidate.anywhereA length change invalidates a view wherever it happens, so appending past a view's end invalidates it too.
19. std-collections.view.invalid-useThe next use of an invalidated view is a checked runtime panic. Such a use is a len, index, or to_list call, an iter() call, or the next next call of an iterator taken from it. Panic: iterator-invalidated.

use std.collections.ListView

fn invalid(mut view: ListView[i32]) -> void:
    view[0] = 7  # error: invalid-assignment-target

fn stale(items: *mut List[i32]) -> usize:
    window := items.view(0, 2)
    items.push(4)
    window.len()  # panics with iterator-invalidated

Why. A view fails fast, as Java's subList does: a window whose list changed length would otherwise read the wrong elements without notice.

See also: List Indexing, List And Optional Map.

#List Helpers

std also gives List[T] helpers that sort, group, split, and search a list without a hand-written loop:

use std.collections.ListView

struct Task:
    name: string
    owner: string
    hours: i32

fn plan(tasks: List[Task]) -> List[Task]:
    tasks.sorted_by_key(fn(task: Task) -> i32: task.hours)

fn by_owner(tasks: List[Task]) -> Map[string, List[Task]]:
    tasks.group_by(fn(task: Task) -> string: task.owner)

fn has_long(tasks: List[Task]) -> bool:
    tasks.any(fn(task: Task) -> bool: task.hours > 8)

fn steps(readings: *List[i32]) -> List[ListView[i32]]:
    readings.windows(2)  # views of [1, 4] and [4, 9] for [1, 4, 9]

fn shortest(tasks: List[Task]) -> Task?:
    tasks.min_by_key(fn(task: Task) -> i32: task.hours)  # the first of equal hours

fn owners(tasks: List[Task]) -> List[string]:
    tasks.map(fn(task: Task) -> string: task.owner).unique()  # ["bo", "al"] for bo, al, bo

1. std-collections.helper.unchangedEach helper leaves its receiver unchanged, and each one that returns a list returns a new list.
2. std-collections.helper.callback-orderA helper calls its callback on the elements in list order, at most once each.
3. std-collections.helper.callback-rowEach callback has the empty row, as Iterator.filter's keep does. A function value whose row lists a requirement key does not fit it. Error: type-mismatch.
4. std-collections.helper.sorted-by-keysorted_by_key(key) returns the elements in ascending order of key(element) by Ord, and calls key once per element.
5. std-collections.helper.sortedsorted returns the elements in ascending order by Ord.
6. std-collections.helper.stableBoth sorts are stable: elements that compare equal keep their order.
7. std-collections.helper.group-bygroup_by(key) maps each key that key returns to the list of the elements that gave it, in list order.
8. std-collections.helper.partitionpartition(keep) returns the elements for which keep is true, then the rest, each in list order.
9. std-collections.helper.any-allany(test) is true when test is true for some element, and all(test) when it is true for every element. So on an empty list any is false and all is true.
10. std-collections.helper.findfind(test) returns the first element for which test is true in .Some, or .None when there is none.
11. std-collections.helper.short-circuitany, all, and find call test on no element after the first one that decides the result.
12. std-collections.helper.flat-map.iterable-ownedflat_map(transform) appends every item from each returned Iterable into one result list, in source order.
13. std-collections.helper.windows.viewswindows(size) returns overlapping ListView[T] values of size elements, in starting-index order.
14. std-collections.helper.windows.shortA list with fewer than size elements gives [].
15. std-collections.helper.windows.sizeA size below 1 panics, as it does for chunks. Panic: explicit-panic.
16. std-collections.helper.containscontains(value) is true when an element equals value by Eq. index_of(value) returns the index of the first such element in .Some, or .None.
17. std-collections.helper.min-max.firstmin returns the first smallest element and max the first largest one by Ord, each in .Some. An empty list gives .None.
18. std-collections.helper.sumsum returns the total of the elements, added with + in list order from 0 of type T, so an empty list gives 0.
19. std-collections.helper.sum.overflowAn integer total that leaves the range of T panics, as + does. Panic: integer-overflow.
20. std-collections.helper.sum.iteratoritems.sum() returns what items.iter().sum() returns.
21. std-collections.helper.by-key.firstmin_by_key(key) returns the first element whose key is smallest by Ord, and max_by_key(key) the first whose key is largest, each in .Some, so equal keys give the earlier element, as min and max do. An empty list gives .None.
22. std-collections.helper.dedupdedup returns the list without each element that equals the element just before it in the receiver, as Rust's Vec::dedup does, so only adjacent duplicates go and [1, 2, 1] is unchanged.
23. std-collections.helper.uniqueunique returns the list without each element that equals an earlier element, so every distinct element stays once, at its first position.

fn paged(items: List[i32]) -> List[List[i32]]:
    items.windows(0)  # panics with explicit-panic

Why. The names are Rust's (sort_by_key, partition, windows, any, all, find, flat_map, contains, min, max), Kotlin's groupBy, and Python's list.index. A sort copies, as sorted_by does, since hd has no consuming methods. min and max both pick the first of equal elements, as Python's min and max do, so one rule covers both. sum is Python's sum and Rust's Iterator::sum; a list has it as a method beside min and max, since a list is not an iterator.

dedup is Vec::dedup, which removes every duplicate only from a sorted list; unique is what Python's dict.fromkeys gives for a list that is not sorted. The names differ because the results differ.

#Counts

counts tallies how often each element occurs:

use std.collections.counts

fn tally(words: List[string]) -> Map[string, usize]:
    counts(words)  # {"a": 2, "b": 1} for ["a", "b", "a"]

1. std-collections.counts.declstd.collections declares pub fn counts[T < Eq & Hash](items: List[T]) -> Map[T, usize]. Code imports it, as in use std.collections.counts.
2. std-collections.counts.valueThe map has one entry per distinct element of items, and its value is the number of elements equal to that one.
3. std-collections.counts.emptyAn empty list gives an empty map.

Why. counts is Python's collections.Counter as a plain map, so the Map methods read it.

#Map Methods

std gives Map[K, V] these methods, beside the language-tier ones:

fn summary(stock: Map[string, i32]) -> string:
    if stock.contains_key("tea"):
        return "${stock.keys().len()} items"
    "no tea"

fn top_words(words: List[string]) -> List[(string, usize)]:
    counts(words).most_common(2)  # [("a", 2), ("b", 1)] for ["a", "b", "a", "c"]

fn pairs(stock: Map[string, i32]) -> List[(string, i32)]:
    stock.entries()  # [("tea", 3), ("milk", 1)] for {"tea": 3, "milk": 1}

1. std-collections.map.contains-keycontains_key(key) is true exactly when the map has an entry whose key equals key.
2. std-collections.map.keys.orderkeys returns the map's keys in its iteration order.
3. std-collections.map.valuesvalues returns the map's values in the same order.
4. std-collections.map.snapshotEach returned list is a snapshot: a later change to the map does not change it.
5. std-collections.map.is-emptyis_empty is true exactly when len() is 0.
6. std-collections.map.entriesentries returns the map's (key, value) pairs in its iteration order, which is the order of keys and values, as a snapshot like theirs.
7. std-collections.map.most-commonmost_common(n) returns the n pairs of the map with the largest values, largest first, or every pair when n is at least len(). An n of 0 gives [].
8. std-collections.map.most-common.tiesPairs with equal values keep the map's iteration order, so on a counts result the element that occurred first comes first, as in Python's Counter.most_common.

Why. entries is a list snapshot like keys and values, since a loop that sorts or indexes the pairs needs a list. most_common is Python's Counter.most_common; a stable sort over the map's order gives its tie rule with no extra bookkeeping.

See also: Map Key Types.

#Set, Deque, And Heap Values

Set[T], Deque[T], and Heap[T] are structs over a list or a map, so each one is a value, as a list is:

use std.collections.Deque

fn with_last(queue: Deque[string]) -> Deque[string]:
    let mut own = queue
    own.push_back("last")  # the caller's deque is unchanged
    own

fn enqueue(queue: &mut Deque[string], name: string) -> void:
    queue.push_back(name)  # changes the caller's deque

1. std-collections.struct.valueSet[T], Deque[T], and Heap[T] are structs, so each is a value. Binding, assigning, passing, returning, and storing one copies it, and a change to one copy leaves every other copy unchanged.
2. std-collections.struct.costA copy shares its source's elements until one of the two changes, as a list does (types.coll.copy-on-write).
3. std-collections.struct.receiver-mutMethods that change a collection, such as push_back, insert, and pop, take &mut self.
4. std-collections.struct.sharedA set, deque, or heap that two holders share is written &mut Set[T], &mut Deque[T], or &mut Heap[T]. A change through the reference changes the place it refers to.

Why. These types were shared objects. As values they follow the list they wrap: a copy is cheap until it changes, and sharing is written where it happens.

See also: Reference Receivers for temporary calls and not-writable on read-only places.

#Set

A Set[T] holds distinct elements, in a deterministic order:

use std.collections.Set

fn unique(words: List[string]) -> List[string]:
    let mut seen: Set[string] = Set::new()
    let mut kept: List[string] = []
    for word in words:
        if seen.insert(word):
            kept.push(word)
    kept  # ["b", "a"] for ["b", "a", "b"]

fn distinct(words: List[string]) -> Set[string]:
    words.iter().collect()

Set[T < Eq & Hash] has this surface:

1. std-collections.set.declstd.collections declares Set[T < Eq & Hash] with private fields, the surface in the table above, and no other method or trait implementation. Code imports it, as in use std.collections.Set.
2. std-collections.set.distinctA set holds elements no two of which are equal by Eq. new returns an empty set.
3. std-collections.set.lenlen returns the number of elements, and is_empty is true exactly when that number is 0.
4. std-collections.set.containscontains(value) is true exactly when the set has an element equal to value.
5. std-collections.set.insertinsert(value) adds value and returns true when the set has no element equal to it. Otherwise it changes nothing and returns false.
6. std-collections.set.removeremove(value) removes the element equal to value and returns true. When there is none, it changes nothing and returns false.
7. std-collections.set.iterIterating a set yields its elements in the order that a map's keys would have after the same inserts and removes, by types.map.order.deterministic.
8. std-collections.set.cursorA set's cursor type is SetIter[T], which std.collections declares with private fields.
9. std-collections.set.snapshotIterating a set walks the set as it was when iter was called. An insert or a remove while the loop runs changes the set but not the loop, and never panics, as flow.for.snapshot states for a map.
10. std-collections.set.eqTwo sets are equal when each element of one equals an element of the other, in any order.
11. std-collections.set.collectA set implements FromIterator[T]. Collecting inserts each item in order, so the set holds each distinct item once, in the order of its first occurrence, and an empty iterator gives an empty set.

Note. lib/std builds a set over a Map whose values carry no meaning, so insert, remove, and contains take expected constant time, by module.map.complexity.

Why. insert and remove report whether they changed the set, as Rust's HashSet methods do, so a loop that skips duplicates needs no second lookup. A set iterates in a map's deterministic order, so its iteration and Debug text are the same in every run. A set is a value, so a loop walks a snapshot of it, as a loop over a map does.

#Deque

A Deque[T] is a double-ended queue: a sequence that grows and shrinks at both ends.

use std.collections.Deque

fn rotate(items: List[i32]) -> List[i32]:
    let mut queue: Deque[i32] = Deque::new()
    for item in items:
        queue.push_back(item)
    match queue.pop_front():
        .Some(first) => queue.push_back(first)
        .None => pass
    let mut rotated: List[i32] = []
    for item in queue:
        rotated.push(item)
    rotated  # [2, 3, 1] for [1, 2, 3]

Deque[T] has this surface:

1. std-collections.deque.collect-surfacestd.collections declares Deque[T] with private fields, the surface in the table above, and no other method or trait implementation. Code imports it, as in use std.collections.Deque.
2. std-collections.deque.orderA deque holds a sequence of elements from its front to its back. new returns an empty deque.
3. std-collections.deque.lenlen returns the number of elements, and is_empty is true exactly when that number is 0.
4. std-collections.deque.pushpush_front(value) adds value before the front, and push_back(value) adds it after the back.
5. std-collections.deque.poppop_front removes the front element and returns it in .Some, and pop_back does the same at the back. On an empty deque, each returns .None and changes nothing.
6. std-collections.deque.endsfront and back return the front and the back element without removing it, or .None when the deque is empty.
7. std-collections.deque.getget(i) returns the element i places from the front in .Some, so get(0) is the front. An i that is not less than len gives .None.
8. std-collections.deque.iterIterating a deque yields its elements from front to back, each as T.
9. std-collections.deque.cursorA deque's cursor type is DequeIter[T], which std.collections declares with private fields.
10. std-collections.deque.snapshotIterating a deque walks the deque as it was when iter was called. A push or a pop while the loop runs changes the deque but not the loop, and never panics, as flow.for.snapshot states for a list.
11. std-collections.deque.eqTwo deques are equal when they have the same length and equal elements in the same order from the front, as two lists are.
12. std-collections.deque.collectA deque implements FromIterator[T], collecting every element in source order.

use std.collections.Deque

fn grow(queue: &mut Deque[i32]) -> void:
    for item in *queue:  # the deque as it was here
        queue.push_back(item)  # doubles the deque; the loop never panics

Note. lib/std builds a deque as a ring buffer over a List[T?]. A push into a full buffer first copies the elements into a buffer twice its size. So each push and pop takes amortized constant time, and get takes constant time.

Why. get returns an optional, as Rust's VecDeque::get does: a queue's length changes often, so a missing element is an expected case. A deque is a value, so a loop walks a snapshot of it, as a loop over a list does.

#Heap

A Heap[T] is a binary max-heap, as Rust's BinaryHeap is: pop removes its largest element.

use std.cmp.Reverse
use std.collections.Heap

fn largest(items: List[i32]) -> i32?:
    let mut heap: Heap[i32] = Heap::new()
    for item in items:
        heap.push(item)
    heap.pop()  # .Some(9) for [5, 9, 2]

fn smallest(items: List[i32]) -> i32?:
    let mut heap: Heap[Reverse[i32]] = Heap::new()
    for item in items:
        heap.push(Reverse { value: item })
    heap.pop().map(fn(top: Reverse[i32]) -> i32: top.value)  # .Some(2) for [5, 9, 2]

Heap[T < Ord] has this surface:

1. std-collections.heap.collect-surfacestd.collections declares Heap[T < Ord] with private fields, the surface in the table above, and no other method or trait implementation. Code imports it, as in use std.collections.Heap.
2. std-collections.heap.lennew returns an empty heap. len returns the number of elements, and is_empty is true exactly when that number is 0.
3. std-collections.heap.pushpush(value) adds value to the heap.
4. std-collections.heap.poppop removes a largest element by Ord and returns it in .Some. On an empty heap, it returns .None.
5. std-collections.heap.peekpeek returns a largest element without removing it, or .None when the heap is empty.
6. std-collections.heap.tiesWhen several elements are equal by cmp, which of them pop and peek return is not specified.
7. std-collections.heap.sortedto_sorted_list returns a new list of every element in ascending order by Ord, and leaves the heap unchanged.
8. std-collections.heap.minstd has no separate min-heap: a Heap[Reverse[T]] pops the smallest T first, by std-cmp.reverse.order.
9. std-collections.heap.collectA heap implements FromIterator[T], collecting every element into a max-heap.
10. std-collections.heap.collect.linearHeapification of n collected elements performs O(n) comparisons, by sifting non-leaves from the bottom up.

Note. lib/std keeps the elements in a List[T?] in heap order, so push and pop take logarithmic time and peek constant time.

Why. to_sorted_list copies, as sorted_by does, because hd has no consuming methods; its ascending order is that of Rust's into_sorted_vec. A heap has no Eq and no iteration, as in Rust: two heaps with the same elements may hold them in different orders.

See also: Reverse, Debug For Standard Types.

#List Access And Building

std gives List[T] methods that read one element safely, copy part of a list, and grow one list by another:

fn second(items: List[string]) -> string?:
    items.get(1)

fn preview(lines: List[string]) -> List[string]:
    if lines.is_empty():
        return ["(empty)"]
    lines.take(3)

fn merged(head: List[i32], tail: List[i32]) -> List[i32]:
    let mut all: List[i32] = []
    all.extend(head.filter(fn(n: i32) -> bool: n > 0))
    all.extend(tail)
    all.sorted_by(fn(a: i32, b: i32) -> Ordering: b.cmp(a))

1. std-collections.access.getget(index) returns .Some of the element at index, or .None when index is not less than len(). It never panics.
2. std-collections.access.is-emptyis_empty is true exactly when len() is 0.
3. std-collections.access.first-lastfirst returns the element at index 0 and last the element at index len() - 1, each in .Some. An empty list gives .None.
4. std-collections.access.taketake(count) returns a new list of the first count elements, or of every element when count is at least len().
5. std-collections.access.filterfilter(keep) returns a new list of the elements for which keep is true, in list order.
6. std-collections.access.reversedreversed returns a new list of the elements in reverse order.
7. std-collections.access.sorted-bysorted_by(compare) returns a new list in ascending order by compare. The sort is stable.
8. std-collections.access.zipzip(other) returns a new list of pairs (self[i], other[i]) for each index i of both lists, so it stops at the shorter one.
9. std-collections.access.extendextend(other) appends each element of other to the receiver, in order, as push does. It changes the length, so it invalidates the list's views by std-collections.view.invalidate.
10. std-collections.access.extend.selfitems.extend(items) appends a copy of the elements items held before the call, so it doubles the list.
11. std-collections.access.helper-rulesThe callbacks of filter and sorted_by follow std-collections.helper.callback-row: each has the empty row.

Why. get is Rust's slice::get, the checked read beside items[i]. take is Kotlin's List.take: like List.map, the list method is eager and returns a list, while Iterator.take stays lazy. extend is Rust's Vec::extend, and replaces items = items + more.

See also: Built-In Methods, Iterator Adapters.