std.collections

Provides the growable containers of the standard library.

List: a growing array, indexed from 0.
Map: keys to values by hash, each key once, in no order of its own.
Set: values by hash, each once, in no order of its own.
Deque: a double-ended queue, pushed and popped at either end.
Heap: a binary min-heap.

Each can be built from an array literal and through collect(), and is Clone where its elements are. All but the heap are Iterable, and Equatable, Debug and Display where their elements are; the heap is Debug. The iterator methods that build containers — toList, toSet, toMap, chunks, windows, sorted, sortedBy, partition, groupBy — live here too.

The containers are not safe across threads: share one through a Mutex.

Examples

import std.io { println };
import std.collections { List, Map, Set };

let words = List.of(["fig", "pear", "fig", "plum", "pear", "fig"]);
let counts = Map<string, int>.new();
for (w in words) {
    counts.insert(w, (counts.get(w) ?? 0) + 1);
}
println(counts.get("fig") ?? 0);
let distinct = Set.of(["fig", "pear", "plum", "fig"]);
println(distinct.length());

3
3

Types

List class — A growing array: its elements in order, indexed from 0.

ListIter struct — Iterates over a list's elements, front to back; made by List.iter.

Map class — A hash map from keys to values: each key once, in no order of its own.

MapEntriesIter struct — Iterates over a map's entries, (K, V), slot by slot; made by Map.iter.

MapKeysIter struct — Iterates over a map's keys or a set's values; made by Map.keys and Set.iter.

MapValuesIter struct — Iterates over a map's values; made by Map.values.

Set class — A hash set: values, each once, in no order of its own.

ChunksIter struct — Yields the values of an iterator in lists of n; made by it.chunks(n).

WindowsIter struct — Yields every run of n consecutive values of an iterator in turn, each in a new list; made by it.windows(n).

Deque class — A double-ended queue: values pushed and popped at either end in amortized constant time.

DequeIter struct — Iterates over a deque's values, front to back; made by Deque.iter.

Heap class — A binary min-heap: Heap.peek and Heap.pop give the least value.

Extensions

extend<I :: [Iterator]> I

pub fn toList(): List<I.Item> throws I.Error

Collects the values into a new list, in order.

The list starts with room for the iterator's lower sizeHint.

Errors

Throws what a pull of the iterator throws.

extend<I :: [Iterator]> I

pub fn chunks(n: int): ChunksIter<I>

Returns an iterator over the values in lists of n, the last one possibly shorter.

Panics

When n is less than 1.

pub fn windows(n: int): WindowsIter<I>

Returns an iterator over every run of n consecutive values, each in a new list.

Panics

When n is less than 1.

pub fn sortedBy<E :: [Error]>(
    cmp: fn(I.Item, I.Item) -> Ordering throws E
): List<I.Item> throws Join<I.Error, E>

Returns the values in a new list, sorted by cmp.

The sort is stable: equal values keep their order.

Errors

Throws what a pull of the iterator or cmp throws, as the view's sortBy does.

pub fn partition<E :: [Error]>(
    p: fn(I.Item) -> bool throws E
): (List<I.Item>, List<I.Item>) throws Join<I.Error, E>

Splits the values into two new lists: those for which p holds and the others, each in order.

Errors

Throws what a pull of the iterator or p throws.

pub fn groupBy<K :: [Hashable], E :: [Error]>(
    key: fn(I.Item) -> K throws E
): Map<K, List<I.Item>, DefaultHasher> throws Join<I.Error, E>

Groups the values into a new map from each key to the list of values with that key.

Eager: walks the whole iterator. Each list keeps the values' order.

Errors

Throws what a pull of the iterator or key throws.

extend<I :: [Iterator<Item = T>], T :: [TotalOrder]> I

pub fn sorted(): List<T> throws I.Error

Returns the values in a new list, in ascending order.

The sort is stable: equal values keep their order.

Errors

Throws what a pull of the iterator throws.

extend<I :: [Iterator<Item = (K, V)>], K :: [Hashable], V> I

pub fn toMap(): Map<K, V, DefaultHasher> throws I.Error

Collects the pairs into a new map; a later value of a key replaces the earlier one.

Errors

Throws what a pull of the iterator throws.

extend<I :: [Iterator<Item = T>], T :: [Hashable]> I

pub fn toSet(): Set<T> throws I.Error

Collects the values into a new set, each once.

Errors

Throws what a pull of the iterator throws.

pub extend<T> Slice<T>

pub fn reversed(): T[]

Returns a new array of the elements, the last first.

pub fn partitionPoint<E :: [Error]>(p: fn(T) -> bool throws E): int throws E

Returns the first index whose element fails p, by binary search.

The elements must be partitioned by p: every one it holds for before every one it does not.

Errors

What p throws.

pub extend<T :: [Equatable]> Slice<T>

pub fn find(x: T): ?int

Returns the index of the first element equal to x, or null.

pub extend<T :: [TotalOrder]> Slice<T>

pub fn binarySearch(x: T): ?int

Returns the index of an element equal to x in sorted elements, or null.

The elements must be sorted in their total order.