hd-lang

#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 borrowed Span[T, 'a] type returned by span and slice;
  • the uniquely owned UniqList[T], which may hold non-copyable elements;
  • the uniquely owned UniqMap[K, V], which may hold non-copyable values;
  • the List helpers, such as sorted_by_key, group_by, and windows, and the function counts;
  • the Map methods get_or_insert, contains_key, keys, and values;
  • 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):

Item Why it stays in the language tier
items[i], len, iter, push, pop, insert, remove_at, clear built-in indexing and intrinsics over the list's representation

#UniqList

UniqList[T] is the uniquely owned counterpart of List[T]. It accepts any element type and moves its elements when it grows or shifts them:

use std.collections.UniqList

struct Socket:
    id: usize

impl !Copy for Socket

fn pool() -> UniqList[Socket]:
    let mut sockets = UniqList::[Socket].new()
    sockets.push(Socket { id: 1 })
    sockets

Its surface is:

Item Signature
construction new() -> UniqList[T]; with_capacity(capacity: usize) -> UniqList[T]
size len(&self) -> usize; is_empty(&self) -> bool
append/remove push(&mut self, value: T) -> void; pop(&mut self) -> T?
indexed change insert(&mut self, index: usize, value: T) -> void; remove_at(&mut self, index: usize) -> T; swap(&mut self, left: usize, right: usize) -> void
shortening truncate(&mut self, len: usize) -> void; clear(&mut self) -> void
copyable access, T < Copy get(&self, index: usize) -> T?; first(&self) -> T?; last(&self) -> T?
element places Index[usize] with Out = T; IndexMut[usize]; IndexSet[usize, T]
shared access get_ref['a](&'a self, index: usize) -> (&'a T)?; first_ref['a](&'a self) -> (&'a T)?; last_ref['a](&'a self) -> (&'a T)?
mutable access get_mut['a](&'a mut self, index: usize) -> (&'a mut T)?; first_mut['a](&'a mut self) -> (&'a mut T)?; last_mut['a](&'a mut self) -> (&'a mut T)?
borrowing cursor iter['a](&'a self) -> UniqListIter[T, 'a], whose item is &'a T
consuming cursor Iterable[T] with UniqListIntoIter[T], whose item is T; FromIterator[T]
copyable conversion, T < Copy from_list(items: List[T]) -> UniqList[T]; to_list(&self) -> List[T]
looking find_ref['a](&'a self, test: fn(&T) -> bool) -> (&'a T)?; any(&self, test: fn(&T) -> bool) -> bool; all(&self, test: fn(&T) -> bool) -> bool
changing retain(&mut self, keep: fn(&T) -> bool) -> void; sort_by(&mut self, compare: fn(&T, &T) -> Ordering) -> void; sort_by_key[K < Ord](&mut self, key: fn(&T) -> K) -> void
capacity capacity(&self) -> usize; reserve(&mut self, additional: usize) -> void
bulk changes extend[I < ?Copy & Iterable[T]](&mut self, other: I) -> void; append(&mut self, other: &mut UniqList[T]) -> void; split_off(&mut self, at: usize) -> UniqList[T]; reverse(&mut self) -> void; drain(&mut self, range: Range[usize]) -> UniqListDrain[T, '_]
equality, T < ?Copy & Eq contains(&self, value: &T) -> bool; index_of(&self, value: &T) -> usize?; dedup(&mut self) -> void
ordered, T < Ord sort(&mut self) -> void; binary_search(&self, value: &T) -> Result[usize, usize]
value-looking traits Eq for T < ?Copy & Eq; Debug for T < ?Copy & Debug; Hash for T < ?Copy & Hash
  1. std-collections.uniq-list.typestd.collections declares UniqList[T < ?Copy] with two private fields, a Buffer[T] and its length, and impl[T < ?Copy] !Copy for UniqList[T]. It is not a prelude name, so code that names it imports it. No count is kept of a list or of its buffer.

  2. std-collections.uniq-list.newnew() returns an empty list. with_capacity(capacity) returns an empty list whose first capacity pushes need no growth.

  3. std-collections.uniq-list.lenlen() returns the number of elements, and is_empty() is true exactly when that number is zero.

  4. std-collections.uniq-list.pushpush(value) moves value after the former last element. pop() moves the last element out and returns it in .Some, or returns .None when the list is empty.

  5. std-collections.uniq-list.insertinsert(index, value) moves value to index and moves each element formerly at or after index one place toward the end. index may equal len(); a greater index panics. Panic: index-out-of-bounds.

  6. std-collections.uniq-list.remove-atremove_at(index) moves the indexed element out, moves each later element one place toward the start, and returns the removed element. An index outside the list panics. Panic: index-out-of-bounds.

  7. std-collections.uniq-list.swapswap(left, right) exchanges the two elements without copying either one. An index outside the list panics. Panic: index-out-of-bounds.

  8. std-collections.uniq-list.truncatetruncate(len) drops every element at len and after. A len at least the current length has no effect. clear() is truncate(0).

  9. std-collections.uniq-list.getFor T < Copy, get(index) returns .Some of a copy of the indexed element, or .None outside the list.

  10. std-collections.uniq-list.first-lastFor T < Copy, first() and last() return .Some of a copy of the first or last element, or .None when the list is empty.

  11. std-collections.uniq-list.bulk-movesGrowth moves the buffer's room into a larger one with Buffer.grow, one memory.copy. insert and remove_at shift a contiguous byte range with one overlapping memory.copy. Each source range then counts as empty. No operation tests uniqueness or makes a copy-on-write clone.

  12. std-collections.uniq-list.get-refget_ref(index) returns a shared reference to the indexed element in .Some, or .None outside the list. first_ref() and last_ref() return the first or last element by shared reference, or .None when the list is empty. Each reference lives for the receiver borrow and is the element's place in the buffer's room (module.rt.ptr.as-ref).

  13. std-collections.uniq-list.get-mutget_mut(index) returns a mutable reference to the indexed element in .Some, or .None outside the list. first_mut() and last_mut() return the first or last element by mutable reference, or .None when the list is empty. Each reference lives for the mutable receiver borrow.

  14. std-collections.uniq-list.index-placesUniqList[T] implements Index[usize], IndexMut[usize], and IndexSet[usize, T] for every T, with Out = T; an index outside the list panics. Panic: index-out-of-bounds.

  15. std-collections.uniq-list.iteriter() borrows the list and yields shared references to its elements in order. Its cursor is UniqListIter[T, 'a], with private fields. The cursor and each yielded reference live for the list borrow.

  16. std-collections.uniq-list.find-reffind_ref(test) returns a shared reference to the first element for which test is true in .Some, or .None when there is none.

  17. std-collections.uniq-list.any-allany(test) and all(test) have the behavior of std-collections.helper.any-all and std-collections.helper.short-circuit, with fn(&T) callbacks.

  18. std-collections.uniq-list.retainretain(keep) drops each rejected element in place and preserves the order of those accepted.

  19. std-collections.uniq-list.sortsort, sort_by, and sort_by_key sort in place and are stable. They order as std-collections.helper.sort, std-collections.helper.sort-by, and std-collections.helper.sort-by-key do.

  20. std-collections.uniq-list.sort-complexityEach UniqList sort uses at most O(n log n) comparisons in the worst case.

  21. std-collections.uniq-list.into-iterUniqList[T] implements Iterable[T]. Its private UniqListIntoIter[T] cursor owns the list and moves its elements out in order. A for loop over a UniqList therefore consumes the list and each item.

  22. std-collections.uniq-list.collectUniqList[T] implements FromIterator[T] for every T < ?Copy, preserving item order. An explicitly targeted collect, including let items: UniqList[_] = cursor.collect(), may therefore collect non-copyable items.

  23. std-collections.uniq-list.conversionFor T < Copy, from_list(items) copies the list's elements in order into a new UniqList, and to_list() copies a UniqList's elements in order into a new List.

  24. std-collections.uniq-list.eqFor T < ?Copy & Eq, two UniqList[T] values are equal exactly when they have the same length and equal elements at every position.

  25. std-collections.uniq-list.debugFor T < ?Copy & Debug, UniqList[T] implements Debug with the same bracketed, comma-separated form as a List[T].

  26. std-collections.uniq-list.hashFor T < ?Copy & Hash, UniqList[T] hashes its length as a u64, then each element in order, as List[T] does.

  27. std-collections.uniq-list.dropUniqList[T] implements std.rt.Drop: dropping a list drops its elements in order, then its buffer frees the room.

  28. std-collections.uniq-list.capacitycapacity() returns the number of element slots reserved by the list's current buffer, including for zero-sized elements.

  29. std-collections.uniq-list.reservereserve(additional) preserves the length and elements and reserves room for at least len() + additional elements without further growth.

  30. std-collections.uniq-list.extendextend[I < ?Copy & Iterable[T]](other: I) consumes other, moving its elements onto the list in iteration order.

  31. std-collections.uniq-list.containsFor T < ?Copy & Eq, contains(value: &T) is true exactly when an element equals value.

  32. std-collections.uniq-list.index-ofFor T < ?Copy & Eq, index_of(value: &T) returns the first equal element's index in .Some, or .None when absent.

  33. std-collections.uniq-list.reversereverse() reverses the elements in place without copying them or changing the length or capacity.

  34. std-collections.uniq-list.dedupFor T < ?Copy & Eq, dedup() drops every element equal to its preceding retained neighbour, keeping each run's first element and the capacity.

  35. std-collections.uniq-list.split-offsplit_off(at) moves the suffix starting at at into a new list, preserving both parts' order and the original capacity; at > len() panics. Panic: index-out-of-bounds.

  36. std-collections.uniq-list.appendappend(other: &mut UniqList[T]) moves every element of other after the receiver's elements, leaving other empty with its capacity unchanged.

  37. std-collections.uniq-list.draindrain(range: Range[usize]) returns a non-copyable UniqListDrain[T, 'a] that holds the mutable receiver borrow and moves selected elements out in order.

  38. std-collections.uniq-list.drain-boundsThe drain range selects its half-open bounds, or includes its upper bound when inclusive is true; reversed or out-of-bounds ranges panic. Panic: index-out-of-bounds.

  39. std-collections.uniq-list.drain-dropDropping the drain cursor drops every unvisited selected element and restores the unselected tail after the prefix, preserving order and capacity.

  40. std-collections.uniq-list.binary-searchFor T < Ord, binary_search(value: &T) searches an ascending list, returning .Ok(index) for any equal element or .Err(index) for its insertion point.

  41. std-collections.uniq-list.reserve-overflowA reserve whose length sum exceeds the address space panics in every build profile. Panic: heap-exhausted.

  42. std-collections.uniq-list.into-iter.release-restReleasing the consuming cursor drops every element it has not yielded.

  43. std-collections.uniq-list.into-iter.linearConsuming a UniqList takes O(n) time, excluding element cleanup; each next() moves one element without shifting the rest.

  44. std-collections.uniq-list.pinned-movesappend, drain, extend, insert, reserve, and push can move the list's elements, so each holds the whole list, by ref.excl.alias.conflict; append also holds other. Called through an alias while a reference into an element of a held list is live, each panics. Panic: borrow-conflict.

Note: hd's Range[usize] also represents inclusive bounds, as in drain(1..=3). As with Span.slice, open bounds are written explicitly: drain(0..items.len()) drains the whole list. Unlike Rust's zero-sized Vec capacity sentinel, capacity reports the existing Buffer's reserved slot count. Ord keeps its existing copyable bound (ref.copy.trait.default); equality queries and deduplication also accept non-copyable elements.

This surface has no literal construction.

#UniqMap

UniqMap[K, V] is the uniquely owned counterpart of Map[K, V]. Keys stay copyable so lookup can take them by value, while values may be non-copyable and move into and out of the table.

use std.collections.UniqMap

fn positive_stock() -> UniqMap[string, i32]:
    let mut stock = UniqMap::[string, i32].with_capacity(3)
    stock.extend([("apples", +2), ("pears", +0)])
    stock.retain(fn(key: &string, value: &mut i32) -> bool: *value > +0)
    stock
Item Signature
construction new() -> UniqMap[K, V]; with_capacity(capacity: usize) -> UniqMap[K, V]
size len(&self) -> usize; is_empty(&self) -> bool
lookup contains_key(&self, key: K) -> bool
change insert(&mut self, key: K, value: V) -> V?; remove(&mut self, key: K) -> V?; clear(&mut self) -> void
copyable access, V < Copy get(&self, key: K) -> V?
element places Index[K] with Out = V; IndexMut[K]; IndexSet[K, V]
reference access get_ref(&self, key: K) -> (&V)?; get_mut(&mut self, key: K) -> (&mut V)?; get_or_insert(&mut self, key: K, default: V) -> &mut V
borrowed iteration iter(&self) -> UniqMapIter[K, V, '_]; keys(&self) -> UniqMapKeys[K, V, '_]; values(&self) -> UniqMapValues[K, V, '_]
bulk changes reserve(&mut self, additional: usize) -> void; retain(&mut self, keep: fn(&K, &mut V) -> bool) -> void; extend[I < ?Copy & Iterable[(K, V)]](&mut self, other: I) -> void; drain(&mut self) -> UniqMapDrain[K, V, '_]
  1. std-collections.uniq-map.typestd.collections declares UniqMap[K < Eq & Hash, V < ?Copy] with private fields and impl[K < Eq & Hash, V < ?Copy] !Copy for UniqMap[K, V]. It is not a prelude name, so code that names it imports it.

  2. std-collections.uniq-map.newnew() returns an empty map.

  3. std-collections.uniq-map.lenlen() returns the number of entries, and is_empty() is true exactly when that number is zero.

  4. std-collections.uniq-map.contains-keycontains_key(key) is true exactly when the map has an entry whose key is equal to key.

  5. std-collections.uniq-map.insertinsert(key, value) moves value into the entry for key. It returns the former value in .Some when an equal key was present, or .None when the entry is new. Replacing a value does not change len().

  6. std-collections.uniq-map.removeremove(key) removes the entry whose key equals key and moves its value out in .Some, or returns .None when there is no such entry.

  7. std-collections.uniq-map.clearclear() removes every entry and drops every value.

  8. std-collections.uniq-map.getFor V < Copy, get(key) returns .Some of a copy of the value whose key equals key, or .None when absent.

  9. std-collections.uniq-map.storage-seeded-bulkThe hash table stores one Buffer, its entry count, and a 64-bit seed. Occupied and removed entries occupy the buffer's start, followed by a compact probe index at twice the entry capacity. Probing borrows entries. Rehashing moves each occupied entry into its new place with one memory.copy; the old buffer then holds none. No operation tests uniqueness or makes a copy-on-write clone. Dropping a map drops each entry in use, through std.rt.Drop, then its buffer frees the room.

  10. std-collections.uniq-map.get-refget_ref(key) returns a shared reference to the value whose key equals key in .Some, or .None when absent. The reference lives for the receiver borrow.

  11. std-collections.uniq-map.get-mutget_mut(key) returns a mutable reference to the value whose key equals key in .Some, or .None when absent. The reference lives for the mutable receiver borrow.

  12. std-collections.uniq-map.get-or-insertget_or_insert(key, default) returns a mutable reference to the value whose key equals key. When the key is absent, it first inserts default; when the key is present, it drops default without replacing the value. The reference lives for the mutable receiver borrow.

  13. std-collections.uniq-map.iteriter() borrows the map and yields (K, &V) pairs in table order. Its cursor is UniqMapIter[K, V, 'a], with private fields. The cursor and each yielded value reference live for the map borrow.

  14. std-collections.uniq-map.keyskeys() borrows the map and yields copies of its keys in the same order as iter(). Its cursor is UniqMapKeys[K, V, 'a], with private fields, and lives for the map borrow.

  15. std-collections.uniq-map.into-iterUniqMap[K, V] implements Iterable[(K, V)]. Its private UniqMapIntoIter[K, V] cursor owns the map and moves each key and value out in table order. A for loop over a UniqMap therefore consumes the map and each value.

  16. std-collections.uniq-map.collectUniqMap[K, V] implements FromIterator[(K, V)]. When equal keys occur more than once, the last value replaces and drops the former value. An explicitly targeted collect, including let items: UniqMap[_, _] = cursor.collect(), may therefore collect non-copyable values.

  17. std-collections.uniq-map.with-capacitywith_capacity(capacity) returns an empty map whose first capacity new entries need no growth; zero capacity allocates no room.

  18. std-collections.uniq-map.reservereserve(additional) preserves every entry and reserves room for at least additional new entries without growth, including after removals.

  19. std-collections.uniq-map.retainretain(keep: fn(&K, &mut V) -> bool) calls keep once per entry in table order, permits value changes, and drops rejected entries.

  20. std-collections.uniq-map.valuesvalues() returns UniqMapValues[K, V, 'a], borrowing the map and yielding shared value references in the same order as iter().

  21. std-collections.uniq-map.extendextend[I < ?Copy & Iterable[(K, V)]](other: I) consumes and inserts each pair in iteration order, replacing and dropping former values for equal keys.

  22. std-collections.uniq-map.draindrain() returns a non-copyable UniqMapDrain[K, V, 'a] that holds the mutable receiver borrow and moves every entry out in table order.

  23. std-collections.uniq-map.drain-dropDropping the drain cursor drops every unvisited entry and leaves the map empty with its allocation available for reuse.

  24. std-collections.uniq-map.reserve-overflowA capacity request that exceeds the address space or cannot fit the table in the heap panics in every build profile. Panic: heap-exhausted.

  25. std-collections.uniq-map.into-iter.release-restReleasing the consuming cursor drops every key and value it has not yielded.

Note: like Rust's HashMap.drain, map draining takes no positional range; map entries have keys rather than list positions. The collection extensions consume Iterable sources; flow.for.iterator.iterable-not-implied keeps cursors distinct from iterables.

This surface has no literal construction.

  1. std-collections.uniq-map.index-placesUniqMap[K, V] implements Index[K] and IndexMut[K] for every supported V, with Out = V; a missing key panics. Panic: index-out-of-bounds.
  2. std-collections.uniq-map.index-setIts IndexSet[K, V] implementation inserts or replaces the key's value, moving V and dropping any previous value.
  3. std-collections.uniq-map.pinned-bulkdrain, retain, and reserve hold the whole map, by ref.excl.alias.conflict. Called through an alias while a reference into an entry is live, each panics. Panic: borrow-conflict.
  4. std-collections.uniq-map.pinned-insertinsert, get_or_insert, extend, and the IndexSet implementation (map[key] = value) can rehash the map's buffer, so each holds the whole map, by ref.excl.alias.conflict. Called through an alias while a reference into an entry is live, each panics. Panic: borrow-conflict.

#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.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:

Receiver Methods
List[T] view(&self, start: usize, end: usize) -> ListView[T]; chunks(&self, size: usize) -> List[ListView[T]]
  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-snapshotchunks takes &self, and windows takes self; every returned view holds a copy of that list value.
  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).

#List Capacity And Bulk Changes

These methods use the existing list primitives and preserve value copying:

Item Signature
construction with_capacity(capacity: usize) -> List[T]
reservation reserve(&mut self, additional: usize) -> void
shortening truncate(&mut self, len: usize) -> void; split_off(&mut self, at: usize) -> List[T]
bulk change append(&mut self, other: &mut List[T]) -> void; resize(&mut self, len: usize, value: T) -> void; fill(&mut self, value: T) -> void; reverse(&mut self) -> void
draining drain['a](&'a mut self, range: Range[usize]) -> ListDrain[T, 'a]
ordered, T < Ord binary_search(&self, value: &T) -> Result[usize, usize]
  1. std-collections.list.with-capacitywith_capacity(capacity) returns an empty list whose first capacity pushes need no growth.
  2. std-collections.list.reservereserve(additional) leaves the elements unchanged and reserves room for at least additional more elements without growth.
  3. std-collections.list.reserve-zeroReserving zero has no effect.
  4. std-collections.list.truncatetruncate(len) removes every element at an index at least len, and has no effect when len is at least the current length.
  5. std-collections.list.split-offsplit_off(at) removes the suffix beginning at at and returns it as a new list in the original order.
  6. std-collections.list.split-off-boundsA split index greater than the length panics. Panic: index-out-of-bounds.
  7. std-collections.list.appendappend(other) appends the elements of other in order and empties other.
  8. std-collections.list.resizeresize(len, value) shortens the list by truncation or appends copies of value until its length is len.
  9. std-collections.list.fillfill(value) replaces each element with a copy of value, without changing the length.
  10. std-collections.list.reversereverse() reverses the elements in place, without changing the length.
  11. std-collections.list.binary-searchOn an ascending sorted list, binary_search(value) returns .Ok(index) for an equal element or .Err(index) for its sorted insertion position.
  12. std-collections.list.binary-search-duplicatesWhen several elements compare equal, any matching index may be returned.
  13. std-collections.list.draindrain(range) returns a non-copyable ListDrain[T, 'a] holding the mutable receiver borrow and yielding the selected elements in order.
  14. std-collections.list.drain-boundsThe range selects half-open bounds, or includes its upper bound when inclusive is true; reversed or out-of-bounds ranges panic. Panic: index-out-of-bounds.
  15. std-collections.list.drain-dropDropping the cursor discards unvisited selected elements and restores the unselected tail after the prefix in its original order.
  16. std-collections.list.bulk-copyEach bulk change leaves other copies of the list unchanged, including copies shared with append's source.

Note. As with UniqList.drain, hd takes Range[usize], including inclusive bounds; write 0..items.len() for the whole list. The copying list drain retains a snapshot until the cursor is dropped. Unlike Rust's exclusive borrow, hd's mutable borrow can have aliases; append reads its source before clearing it, so two box aliases naming the same list leave that list empty.

#List Slices

List.slice builds a new value from explicit element offsets:

Rule Signature
std-collections.list.slice slice(&self, start: usize, end: usize) -> List[T]
  1. std-collections.list.slice.elementsThe result contains the elements from start up to, but not including, end, in order.
  2. std-collections.list.slice.valueIt is a new list value; changing either list leaves the other unchanged.
  3. std-collections.list.slice.boundsAn offset greater than the list length, or start > end, panics. Panic: index-out-of-bounds.
  4. std-collections.list.slice.emptyEqual start and end offsets return an empty list, including at the list's length.
  5. std-collections.list.slice.hdThe method is ordinary hd and copies the selected elements.

Note. A whole-list selection is items.slice(0, items.len()). A read-only window without an element copy is view.

#Views

view gives a read-only window on a run of a list's elements. It takes &self and stores a copy of that list value, as Swift's ArraySlice does. The view shares its storage, so taking it copies no element:

use std.collections.ListView

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

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

ListView[T] has this surface:

Item Signature
len len(&self) -> usize
to_list to_list(&self) -> List[T]
index read Index[usize] with Out = T
iteration Iterable[T]
  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.snapshotview takes &self and stores a copy of that list value in the returned view.
  4. std-collections.view.value-copyA ListView[T] is a struct value. A copy of a view is an equal view.
  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.snapshot-writesAn element write or a length change to the list after the view was taken, as items[i] = v or items.push(v), does not show through the view.
Error example
use std.collections.ListView

fn invalid(mut view: ListView[i32]) -> void:
    view[0] = 7  # error: invalid-assignment-target
fn snapshot() -> i32:
    let mut items = [+1, +2, +3]
    window := items.view(0, 2)
    items[0] = +9
    items.push(+4)
    window[0]  # 1: the view kept the list it was taken from

Note. A view keeps the whole list's storage, not only its run. Copy a run you keep for long with to_list().

Why. A view is a value, as Swift's ArraySlice is, so it can never go stale and no use of it needs a runtime check. A view that referred to the list's place would need a reference that outlives the call.

See also: List Indexing, List And Optional Map.

#Spans

span gives a read-only live view of a list. Unlike ListView, a span borrows the caller's list instead of holding a snapshot value:

use std.collections.Span

fn middle['a](items: &'a List[i32]) -> Span[i32, 'a]:
    items.span().slice(1..3)

Span[T, 'a] has this surface:

Item Signature
construction span['a](&'a self) -> Span[T, 'a] on List[T]
len len(&self) -> usize
get get(self, index: usize) -> (&'a T)?
slice slice(self, range: Range[usize]) -> Span[T, 'a]
index read Index[usize] with Out = T
iter iter(self) -> SpanIter[T, 'a]
index_of_span index_of_span['b](&self, needle: Span[T, 'b]) -> usize? with T < Eq
  1. std-collections.span.typestd.collections declares Span[T, 'a] with private fields and the surface above.
  2. std-collections.span.listlist.span() borrows the list for 'a and returns a span covering every element.
  3. std-collections.span.no-copyCreating a span copies no element.
  4. std-collections.span.importSpan is not a prelude name, so code that names it imports std.collections.Span.
  5. std-collections.span.lenlen returns the number of elements in the span.
  6. std-collections.span.getget(index) returns the indexed element as &'a T in .Some, or .None when the index is outside the span.
  7. std-collections.span.index-copyspan[index] copies the indexed element; &span[index] borrows its place.
  8. std-collections.span.index-rangeAn index outside the span is a checked runtime panic, even when the list has an element there. Panic: index-out-of-bounds.
  9. std-collections.span.sliceslice(start..end) returns the elements at relative indices start up to, not including, end.
  10. std-collections.span.slice-inclusiveslice(start..=end) includes the element at relative index end.
  11. std-collections.span.slice-rangeA slice bound outside the span, or a start after its exclusive end, is a checked runtime panic. Panic: index-out-of-bounds.
  12. std-collections.span.slice-borrowSlicing copies no element and returns another span that borrows the same list for 'a.
  13. std-collections.span.lifetimeA span cannot outlive its list; returning a span of a local list is an error. Error: local-reference-escapes.
  14. std-collections.span.read-onlyA span has no IndexSet implementation, so assigning through span[index] is an error. Error: invalid-assignment-target.
  15. std-collections.span.iteriter() returns a cursor that yields each element in span order as &'a T.
  16. std-collections.span.cursorA span's cursor type is SpanIter[T, 'a], which std.collections declares with private fields.
  17. std-collections.span.iter-lifetimeA span cursor retains the span's borrow for 'a, so it cannot outlive the borrowed list. Error: local-reference-outlives-local.
  18. std-collections.span.index-of-spanindex_of_span(needle) returns .Some of the smallest relative index at which the span's elements equal needle's, element by element with Eq, and .None when there is none. The span may hold any bytes, valid UTF-8 or not.
  19. std-collections.span.index-of-span.emptyAn empty needle is at .Some(0), as in string.find, even in an empty span.
  20. std-collections.span.index-of-span.longerA needle longer than the span gives .None.
  21. std-collections.span.index-of-span.costThe search makes at most a number of comparisons linear in the span's length plus the needle's.

Why. Span supports borrowed reads without a snapshot allocation. Its explicit lifetime makes retention beyond the source list a compile-time error.

#Mutable Spans

span_mut gives an exclusive mutable view of a list. Its indices remain relative to the view, and every mutation preserves the list's length.

Operation Signature or trait
whole-list view span_mut['a](&'a mut self) -> SpanMut[T, 'a]
len len(&self) -> usize
get get['b](&'b self, index: usize) -> (&'b T)?
get_mut get_mut['b](&'b mut self, index: usize) -> (&'b mut T)?
slice_mut slice_mut['b](&'b mut self, range: Range[usize]) -> SpanMut[T, 'b]
index read Index[usize] with Out = T
mutable element place IndexMut[usize]
index write IndexSet[usize, T]
swap swap(&mut self, left: usize, right: usize) -> void
fill fill(&mut self, value: T) -> void
  1. std-collections.span-mut.typestd.collections declares SpanMut[T, 'a] with private fields and the surface above.
  2. std-collections.span-mut.listlist.span_mut() borrows the list mutably for 'a and returns a mutable span covering every element.
  3. std-collections.span-mut.no-copyCreating or slicing a mutable span copies no element.
  4. std-collections.span-mut.importSpanMut is not a prelude name, so code that names it imports std.collections.SpanMut.
  5. std-collections.span-mut.lenlen returns the number of elements in the mutable span.
  6. std-collections.span-mut.getget(index) returns the indexed element as &'b T in .Some, or .None outside the span. It borrows the span for 'b, so the span stays usable after the last use of the result.
  7. std-collections.span-mut.get-mutget_mut(index) returns the indexed element as &'b mut T in .Some, or .None outside the span. It borrows the span mutably for 'b.
  8. std-collections.span-mut.indexspan[index] returns a copy of the indexed element, as a list's items[i] does. The read borrows the span only for the call, so the span stays usable; get gives a reference.
  9. std-collections.span-mut.index-setspan[index] = value replaces the indexed element without changing the list's length.
  10. std-collections.span-mut.index-rangeAn index read or write outside the span is a checked runtime panic. Panic: index-out-of-bounds.
  11. std-collections.span-mut.sliceslice_mut(start..end) returns the elements at relative indices start up to, not including, end.
  12. std-collections.span-mut.slice-inclusiveslice_mut(start..=end) includes the element at relative index end.
  13. std-collections.span-mut.slice-rangeAn invalid mutable slice range is a checked runtime panic. Panic: index-out-of-bounds.
  14. std-collections.span-mut.slice-borrowMutable slicing reborrows the span for 'b and returns another span over the same list, so the original span is unusable while the slice is live. Error: conflicting-access.
  15. std-collections.span-mut.swapswap(left, right) exchanges two indexed elements without changing the list's length.
  16. std-collections.span-mut.swap-rangeAn out-of-range swap index is a checked runtime panic. Panic: index-out-of-bounds.
  17. std-collections.span-mut.fillfill(value) replaces every element in the mutable span with value.
  18. std-collections.span-mut.lifetimeA mutable span cannot outlive its list. Error: local-reference-escapes.
  19. std-collections.span-mut.receiverslen, get, get_mut, slice_mut, swap and fill borrow the span, with &self or &mut self as the table shows, so one span serves any number of calls in a row.
  20. std-collections.span-mut.exclusiveWhile a mutable span is live, its source list may be used only through that span. Error: conflicting-access.
  21. std-collections.span-mut.index-mutSpanMut implements IndexMut[usize] and lends the indexed element mutably, with the same bounds check.

Why. SpanMut exposes in-place element updates while the existing exclusive-borrow rules prevent changing the source list behind the view.

#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
Receiver Methods
List[T] sorted_by_key[K < Ord](&self, key: fn(&T) -> K) -> List[T]; group_by[K < Eq & Hash](&self, key: fn(&T) -> K) -> Map[K, List[T]]; partition(&self, keep: fn(&T) -> bool) -> (List[T], List[T]); any(&self, test: fn(&T) -> bool) -> bool; all(&self, test: fn(&T) -> bool) -> bool; find(&self, test: fn(&T) -> bool) -> T?; flat_map[U, I < Iterable[U]](self, transform: fn(T) -> I) -> List[U]; windows(self, size: usize) -> List[ListView[T]]
List[T] min_by_key[K < Ord](&self, key: fn(&T) -> K) -> T?; max_by_key[K < Ord](&self, key: fn(&T) -> K) -> T?
List[T], when T < Eq contains(&self, value: T) -> bool; index_of(&self, value: T) -> usize?; dedup(self) -> List[T]
List[T], when T < Eq & Hash unique(self) -> List[T]
List[T], when T < Ord sorted(&self) -> List[T]; sort(&mut self) -> void; min(&self) -> T?; max(&self) -> T?
List[T], when T < Num sum(self) -> T
  1. std-collections.helper.unchangedEach helper but retain, sort, sort_by, sort_by_key, and swap 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.find-copyfind(test) returns a copy of 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.copy-firstmin returns a copy of the first smallest element and max one to the first largest 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.copy-firstmin_by_key(key) returns a copy of the first element whose key is smallest by Ord. max_by_key(key) returns a copy of the first whose key is largest. Each returns .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.
  24. std-collections.helper.callback-refEach callback looks at an element by reference: fn(&T), and fn(&T, &T) for sorted_by and sort_by. Each receiver is &self, or &mut self for a method that changes the list.
  25. std-collections.helper.retainretain(keep) keeps the elements for which keep is true, in list order, and drops the rest, in place.
  26. std-collections.helper.sortsort puts the elements in ascending order by Ord, in place.
  27. std-collections.helper.sort-bysort_by(compare) puts the elements in ascending order by compare, in place.
  28. std-collections.helper.sort-by-keysort_by_key(key) puts the elements in ascending order of key(element) by Ord, in place, and calls key once per element.
  29. std-collections.helper.sort.stablesort, sort_by, and sort_by_key are stable, as sorted_by is: elements that compare equal keep their order.
  30. std-collections.helper.swapswap(a, b) exchanges the elements at a and b. An index that is not less than len() panics. Panic: index-out-of-bounds.
Call Result
[3, 1, 2].partition(fn(n: &i32) -> bool: n > 1) ([3, 2], [1])
[1, 2].flat_map(fn(n: i32) -> List[i32]: [n, n]) [1, 1, 2, 2]
[1, 2, 3].windows(2) views of [1, 2] and [2, 3]
[1, 2].windows(3) []
[5, 7, 5].index_of(5) .Some(0)
[2, 9, 4].max() .Some(9)
["bb", "a", "cc"].max_by_key(fn(w: &string) -> usize: w.len()) .Some("bb")
[1, 1, 2, 1].dedup() [1, 2, 1]
[1, 1, 2, 1].unique() [1, 2]
[1, 2, 3].sum() 6
[0.5, 0.25].sum() 0.75
[] of i64, .sum() 0
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:

Receiver Methods
Map[K, V] get_or_insert(&mut self, key: K, default: V) -> &mut V; contains_key(&self, key: K) -> bool; keys(&self) -> List[K]; values(&self) -> List[V]; is_empty(&self) -> bool; entries(&self) -> List[(K, V)]
Map[K, usize] most_common(&self, n: usize) -> List[(K, usize)]

Note. Built-in map loops borrow entry slots: shared loops bind (&K, &V), and mutable loops bind (&K, &mut V) (Element Reference Loops). keys, values and entries return lists of copied values.

use std.collections.counts

fn shelf_count(stock: &Map[string, List[string]], item: string) -> usize:
    match stock.get(item):  # List[string]?: one count of the list buffer
        .Some(shelves) => shelves.len()
        .None => 0

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", 3), ("b", 2)] for ["a", "b", "a", "c", "b", "a"]

fn pairs(stock: Map[string, i32]) -> List[(string, i32)]:
    stock.entries()  # ("tea", 3) and ("milk", 1), in the map's order

fn tally(words: List[string]) -> Map[string, usize]:
    let mut found: Map[string, usize] = {}
    for word in words:
        *found.get_or_insert(word, 0) += 1
    found
  1. std-collections.map.getget(key) is the built-in copying lookup (expr.index.map.get): it returns .Some of a copy of the stored value, or .None when the map has no equal key.
  2. std-collections.map.get-or-insertget_or_insert(key, default) returns a mutable reference to the stored value when the map has an equal key.
  3. std-collections.map.get-or-insert.missingWhen the map has no equal key, get_or_insert inserts (key, default) and returns a mutable reference to the inserted value.
  4. std-collections.map.get-or-insert.referenceThe reference that get_or_insert returns is dependent on its receiver by ref.dep.elide.
  5. std-collections.map.get-or-insert.probe-onceEach get_or_insert call invokes the key's Hash implementation once and performs one map search, reusing a missing search position for insertion.
  6. std-collections.map.contains-keycontains_key(key) is true exactly when the map has an entry whose key equals key.
  7. std-collections.map.keys.orderkeys returns the map's keys in its iteration order.
  8. std-collections.map.valuesvalues returns the map's values in the same order.
  9. std-collections.map.snapshotEach returned list is a snapshot: a later change to the map does not change it.
  10. std-collections.map.is-emptyis_empty is true exactly when len() is 0.
  11. 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.
  12. 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 [].
  13. std-collections.map.most-common.tie-orderPairs with equal values keep the map's iteration order, which is the same in every run.

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. get_or_insert is Rust's HashMap::entry(key).or_insert(default) operation without exposing an entry object that holds a reference.

#Map Bulk Changes

Item Signature
retaining retain(&mut self, keep: fn(&K, &mut V) -> bool) -> void
extending extend[I < ?Copy & Iterable[(K, V)]](&mut self, other: I) -> void
draining drain['a](&'a mut self) -> MapDrain[K, V, 'a]
  1. std-collections.map.retainretain(keep) visits each entry once in iteration order, lets keep change its value, and removes entries for which it returns false.
  2. std-collections.map.extendextend(other) inserts each yielded pair in order, replacing the value of an equal key as indexed assignment does.
  3. std-collections.map.extend-last-winsWhen other yields equal keys more than once, the value of the last such pair stays.
  4. std-collections.map.draindrain() empties the map and returns a non-copyable MapDrain[K, V, 'a] that borrows its receiver mutably and yields entries in iteration order.
  5. std-collections.map.drain-dropDropping the drain discards every unvisited entry and leaves the map empty.
  6. std-collections.map.bulk-copyThese methods leave other copies of the map unchanged.

Note. Map draining takes no positional range, as in Rust. The cursor retains an entry snapshot until it is dropped.

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.lend-or-boxA function that changes the caller's set, deque, or heap takes &mut Set[T], &mut Deque[T], or &mut Heap[T], and a change through it changes the place it refers to. A collection that two holders keep is boxed, as box(queue), which gives a *mut Deque[T].

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:

Item Signature
new Set::new() -> Set[T]
len, is_empty len(&self) -> usize; is_empty(&self) -> bool
contains contains(&self, value: T) -> bool
insert, remove insert(&mut self, value: T) -> bool, and the same for remove
iteration Iterable[T]
collect FromIterator[T]
equality Eq
Debug when T < Debug
  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.collect-distinctA set implements FromIterator[T]. The collected set holds each distinct item once, 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:

Item Signature
new Deque::new() -> Deque[T]
len, is_empty len(&self) -> usize; is_empty(&self) -> bool
push_front, push_back push_front(&mut self, value: T) -> void, and the same for push_back
pop_front, pop_back pop_front(&mut self) -> T?, and the same for pop_back
front, back front(&self) -> T?, and the same for back
get get(&self, index: usize) -> T?
iteration Iterable[T]
equality Eq when T < Eq
Debug when T < Debug
collect FromIterator[T]
  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.ends-copyfront and back return a copy of the front and the back element without removing it, or .None when the deque is empty.
  7. std-collections.deque.get-copyget(i) returns a copy of 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:

Item Signature
new Heap::new() -> Heap[T]
len, is_empty len(&self) -> usize; is_empty(&self) -> bool
push push(&mut self, value: T) -> void
pop pop(&mut self) -> T?
peek peek(&self) -> T?
to_sorted_list to_sorted_list(&self) -> List[T]
Debug when T < Debug
collect FromIterator[T]
  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.peek-copypeek returns a copy of 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))
Receiver Methods
List[T] get(&self, index: usize) -> T?; is_empty(&self) -> bool; first(&self) -> T?; last(&self) -> T?; take(self, count: usize) -> List[T]; filter(&self, keep: fn(&T) -> bool) -> List[T]; reversed(self) -> List[T]; sorted_by(&self, compare: fn(&T, &T) -> Ordering) -> List[T]; zip[U](self, other: List[U]) -> List[(T, U)]
List[T], changing extend(&mut self, other: List[T]) -> void; retain(&mut self, keep: fn(&T) -> bool) -> void; sort_by(&mut self, compare: fn(&T, &T) -> Ordering) -> void; sort_by_key[K < Ord](&mut self, key: fn(&T) -> K) -> void; swap(&mut self, a: usize, b: usize) -> void
  1. std-collections.access.get-copyget(index) returns .Some of a copy 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-last-copyfirst returns a copy of the element at index 0 and last one of 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.
  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.
fn adjust(items: &mut List[i32], stock: &mut Map[string, i32]) -> void:
    items[1] += 10
    *stock.get_or_insert("tea", 0) += 1
Call Result
[4, 5].get(1) .Some(5)
[4, 5].get(2) .None
[1, 2, 3].take(2) [1, 2]
[1, 2].take(5) [1, 2]
[1, 2, 3].zip(["a", "b"]) [(1, "a"), (2, "b")]

Why. get is the checked, copying 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.