#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
Listmethodsviewandchunks, and the access and building methods such asget,take, andextend; - the
ListView[T]type returned byview,chunks, andwindows; - the borrowed
Span[T, 'a]type returned byspanandslice; - the uniquely owned
UniqList[T], which may hold non-copyable elements; - the uniquely owned
UniqMap[K, V], which may hold non-copyable values; - the
Listhelpers, such assorted_by_key,group_by, andwindows, and the functioncounts; - the
Mapmethodsget_or_insert,contains_key,keys, andvalues; - the set
Set[T], the double-ended queueDeque[T], and the max-heapHeap[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 })
socketsIts 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 |
-
std-collections.uniq-list.type
std.collectionsdeclaresUniqList[T < ?Copy]with two private fields, aBuffer[T]and its length, andimpl[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. -
std-collections.uniq-list.new
new()returns an empty list.with_capacity(capacity)returns an empty list whose firstcapacitypushes need no growth. -
std-collections.uniq-list.len
len()returns the number of elements, andis_empty()is true exactly when that number is zero. -
std-collections.uniq-list.push
push(value)movesvalueafter the former last element.pop()moves the last element out and returns it in.Some, or returns.Nonewhen the list is empty. -
std-collections.uniq-list.insert
insert(index, value)movesvaluetoindexand moves each element formerly at or afterindexone place toward the end.indexmay equallen(); a greater index panics. Panic:index-out-of-bounds. -
std-collections.uniq-list.remove-at
remove_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. -
std-collections.uniq-list.swap
swap(left, right)exchanges the two elements without copying either one. An index outside the list panics. Panic:index-out-of-bounds. -
std-collections.uniq-list.truncate
truncate(len)drops every element atlenand after. Alenat least the current length has no effect.clear()istruncate(0). -
std-collections.uniq-list.getFor
T < Copy,get(index)returns.Someof a copy of the indexed element, or.Noneoutside the list. -
std-collections.uniq-list.first-lastFor
T < Copy,first()andlast()return.Someof a copy of the first or last element, or.Nonewhen the list is empty. -
std-collections.uniq-list.bulk-movesGrowth moves the buffer's room into a larger one with
Buffer.grow, onememory.copy.insertandremove_atshift a contiguous byte range with one overlappingmemory.copy. Each source range then counts as empty. No operation tests uniqueness or makes a copy-on-write clone. -
std-collections.uniq-list.get-ref
get_ref(index)returns a shared reference to the indexed element in.Some, or.Noneoutside the list.first_ref()andlast_ref()return the first or last element by shared reference, or.Nonewhen 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). -
std-collections.uniq-list.get-mut
get_mut(index)returns a mutable reference to the indexed element in.Some, or.Noneoutside the list.first_mut()andlast_mut()return the first or last element by mutable reference, or.Nonewhen the list is empty. Each reference lives for the mutable receiver borrow. -
std-collections.uniq-list.index-places
UniqList[T]implementsIndex[usize],IndexMut[usize], andIndexSet[usize, T]for everyT, withOut = T; an index outside the list panics. Panic:index-out-of-bounds. -
std-collections.uniq-list.iter
iter()borrows the list and yields shared references to its elements in order. Its cursor isUniqListIter[T, 'a], with private fields. The cursor and each yielded reference live for the list borrow. -
std-collections.uniq-list.find-ref
find_ref(test)returns a shared reference to the first element for whichtestis true in.Some, or.Nonewhen there is none. -
std-collections.uniq-list.any-all
any(test)andall(test)have the behavior ofstd-collections.helper.any-allandstd-collections.helper.short-circuit, withfn(&T)callbacks. -
std-collections.uniq-list.retain
retain(keep)drops each rejected element in place and preserves the order of those accepted. -
std-collections.uniq-list.sort
sort,sort_by, andsort_by_keysort in place and are stable. They order asstd-collections.helper.sort,std-collections.helper.sort-by, andstd-collections.helper.sort-by-keydo. -
std-collections.uniq-list.sort-complexityEach
UniqListsort uses at most O(n log n) comparisons in the worst case. -
std-collections.uniq-list.into-iter
UniqList[T]implementsIterable[T]. Its privateUniqListIntoIter[T]cursor owns the list and moves its elements out in order. Aforloop over aUniqListtherefore consumes the list and each item. -
std-collections.uniq-list.collect
UniqList[T]implementsFromIterator[T]for everyT < ?Copy, preserving item order. An explicitly targetedcollect, includinglet items: UniqList[_] = cursor.collect(), may therefore collect non-copyable items. -
std-collections.uniq-list.conversionFor
T < Copy,from_list(items)copies the list's elements in order into a newUniqList, andto_list()copies aUniqList's elements in order into a newList. -
std-collections.uniq-list.eqFor
T < ?Copy & Eq, twoUniqList[T]values are equal exactly when they have the same length and equal elements at every position. -
std-collections.uniq-list.debugFor
T < ?Copy & Debug,UniqList[T]implementsDebugwith the same bracketed, comma-separated form as aList[T]. -
std-collections.uniq-list.hashFor
T < ?Copy & Hash,UniqList[T]hashes its length as au64, then each element in order, asList[T]does. -
std-collections.uniq-list.drop
UniqList[T]implementsstd.rt.Drop: dropping a list drops its elements in order, then its buffer frees the room. -
std-collections.uniq-list.capacity
capacity()returns the number of element slots reserved by the list's current buffer, including for zero-sized elements. -
std-collections.uniq-list.reserve
reserve(additional)preserves the length and elements and reserves room for at leastlen() + additionalelements without further growth. -
std-collections.uniq-list.extend
extend[I < ?Copy & Iterable[T]](other: I)consumesother, moving its elements onto the list in iteration order. -
std-collections.uniq-list.containsFor
T < ?Copy & Eq,contains(value: &T)is true exactly when an element equalsvalue. -
std-collections.uniq-list.index-ofFor
T < ?Copy & Eq,index_of(value: &T)returns the first equal element's index in.Some, or.Nonewhen absent. -
std-collections.uniq-list.reverse
reverse()reverses the elements in place without copying them or changing the length or capacity. -
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. -
std-collections.uniq-list.split-off
split_off(at)moves the suffix starting atatinto a new list, preserving both parts' order and the original capacity;at > len()panics. Panic:index-out-of-bounds. -
std-collections.uniq-list.append
append(other: &mut UniqList[T])moves every element ofotherafter the receiver's elements, leavingotherempty with its capacity unchanged. -
std-collections.uniq-list.drain
drain(range: Range[usize])returns a non-copyableUniqListDrain[T, 'a]that holds the mutable receiver borrow and moves selected elements out in order. -
std-collections.uniq-list.drain-boundsThe drain range selects its half-open bounds, or includes its upper bound when
inclusiveis true; reversed or out-of-bounds ranges panic. Panic:index-out-of-bounds. -
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.
-
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. -
std-collections.uniq-list.reserve-overflowA
reservewhose length sum exceeds the address space panics in every build profile. Panic:heap-exhausted. -
std-collections.uniq-list.into-iter.release-restReleasing the consuming cursor drops every element it has not yielded.
-
std-collections.uniq-list.into-iter.linearConsuming a
UniqListtakes O(n) time, excluding element cleanup; eachnext()moves one element without shifting the rest. -
std-collections.uniq-list.pinned-moves
append,drain,extend,insert,reserve, andpushcan move the list's elements, so each holds the whole list, byref.excl.alias.conflict;appendalso holdsother. 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 indrain(1..=3). As withSpan.slice, open bounds are written explicitly:drain(0..items.len())drains the whole list. Unlike Rust's zero-sizedVeccapacity sentinel, capacity reports the existingBuffer's reserved slot count.Ordkeeps 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, '_] |
-
std-collections.uniq-map.type
std.collectionsdeclaresUniqMap[K < Eq & Hash, V < ?Copy]with private fields andimpl[K < Eq & Hash, V < ?Copy] !Copy for UniqMap[K, V]. It is not a prelude name, so code that names it imports it. -
std-collections.uniq-map.new
new()returns an empty map. -
std-collections.uniq-map.len
len()returns the number of entries, andis_empty()is true exactly when that number is zero. -
std-collections.uniq-map.contains-key
contains_key(key)is true exactly when the map has an entry whose key is equal tokey. -
std-collections.uniq-map.insert
insert(key, value)movesvalueinto the entry forkey. It returns the former value in.Somewhen an equal key was present, or.Nonewhen the entry is new. Replacing a value does not changelen(). -
std-collections.uniq-map.remove
remove(key)removes the entry whose key equalskeyand moves its value out in.Some, or returns.Nonewhen there is no such entry. -
std-collections.uniq-map.clear
clear()removes every entry and drops every value. -
std-collections.uniq-map.getFor
V < Copy,get(key)returns.Someof a copy of the value whose key equalskey, or.Nonewhen absent. -
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 onememory.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, throughstd.rt.Drop, then its buffer frees the room. -
std-collections.uniq-map.get-ref
get_ref(key)returns a shared reference to the value whose key equalskeyin.Some, or.Nonewhen absent. The reference lives for the receiver borrow. -
std-collections.uniq-map.get-mut
get_mut(key)returns a mutable reference to the value whose key equalskeyin.Some, or.Nonewhen absent. The reference lives for the mutable receiver borrow. -
std-collections.uniq-map.get-or-insert
get_or_insert(key, default)returns a mutable reference to the value whose key equalskey. When the key is absent, it first insertsdefault; when the key is present, it dropsdefaultwithout replacing the value. The reference lives for the mutable receiver borrow. -
std-collections.uniq-map.iter
iter()borrows the map and yields(K, &V)pairs in table order. Its cursor isUniqMapIter[K, V, 'a], with private fields. The cursor and each yielded value reference live for the map borrow. -
std-collections.uniq-map.keys
keys()borrows the map and yields copies of its keys in the same order asiter(). Its cursor isUniqMapKeys[K, V, 'a], with private fields, and lives for the map borrow. -
std-collections.uniq-map.into-iter
UniqMap[K, V]implementsIterable[(K, V)]. Its privateUniqMapIntoIter[K, V]cursor owns the map and moves each key and value out in table order. Aforloop over aUniqMaptherefore consumes the map and each value. -
std-collections.uniq-map.collect
UniqMap[K, V]implementsFromIterator[(K, V)]. When equal keys occur more than once, the last value replaces and drops the former value. An explicitly targetedcollect, includinglet items: UniqMap[_, _] = cursor.collect(), may therefore collect non-copyable values. -
std-collections.uniq-map.with-capacity
with_capacity(capacity)returns an empty map whose firstcapacitynew entries need no growth; zero capacity allocates no room. -
std-collections.uniq-map.reserve
reserve(additional)preserves every entry and reserves room for at leastadditionalnew entries without growth, including after removals. -
std-collections.uniq-map.retain
retain(keep: fn(&K, &mut V) -> bool)callskeeponce per entry in table order, permits value changes, and drops rejected entries. -
std-collections.uniq-map.values
values()returnsUniqMapValues[K, V, 'a], borrowing the map and yielding shared value references in the same order asiter(). -
std-collections.uniq-map.extend
extend[I < ?Copy & Iterable[(K, V)]](other: I)consumes and inserts each pair in iteration order, replacing and dropping former values for equal keys. -
std-collections.uniq-map.drain
drain()returns a non-copyableUniqMapDrain[K, V, 'a]that holds the mutable receiver borrow and moves every entry out in table order. -
std-collections.uniq-map.drain-dropDropping the drain cursor drops every unvisited entry and leaves the map empty with its allocation available for reuse.
-
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. -
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 consumeIterablesources;flow.for.iterator.iterable-not-impliedkeeps cursors distinct from iterables.
This surface has no literal construction.
- std-collections.uniq-map.index-places
UniqMap[K, V]implementsIndex[K]andIndexMut[K]for every supportedV, withOut = V; a missing key panics. Panic:index-out-of-bounds. - std-collections.uniq-map.index-setIts
IndexSet[K, V]implementation inserts or replaces the key's value, movingVand dropping any previous value. - std-collections.uniq-map.pinned-bulk
drain,retain, andreservehold the whole map, byref.excl.alias.conflict. Called through an alias while a reference into an entry is live, each panics. Panic:borrow-conflict. - std-collections.uniq-map.pinned-insert
insert,get_or_insert,extend, and theIndexSetimplementation (map[key] = value) can rehash the map's buffer, so each holds the whole map, byref.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- std-collections.value.receiverA
stdmethod that changes a list or a map, asextenddoes, needs its receiver in a writable place, as a language-tier changing method does (types.coll.writable). - std-collections.value.own-copySuch a change reaches only the receiver's own value. Another copy of the list or the map is unchanged.
- std-collections.value.resultsA method that returns a list or a map, as
keys,filter, andchunksdo, returns a new value, which the caller may bind withlet mutand change. - std-collections.value.ref-receiverEach such method takes
&mut self. On a map value or a list element, as ingroups[key].extend(more), it changes the collection where it is stored, astypes.coll.nestedstates 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]] |
- std-collections.list.chunks.views
chunks(size)returns consecutive read-onlyListView[T]values in order; only the last view may be shorter thansize. - std-collections.list.chunks.sizeA
sizebelow 1 panics. Panic:explicit-panic. - std-collections.list.window-snapshot
chunkstakes&self, andwindowstakesself; every returned view holds a copy of that list value. - 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] |
- std-collections.list.with-capacity
with_capacity(capacity)returns an empty list whose firstcapacitypushes need no growth. - std-collections.list.reserve
reserve(additional)leaves the elements unchanged and reserves room for at leastadditionalmore elements without growth. - std-collections.list.reserve-zeroReserving zero has no effect.
- std-collections.list.truncate
truncate(len)removes every element at an index at leastlen, and has no effect whenlenis at least the current length. - std-collections.list.split-off
split_off(at)removes the suffix beginning atatand returns it as a new list in the original order. - std-collections.list.split-off-boundsA split index greater than the length panics. Panic:
index-out-of-bounds. - std-collections.list.append
append(other)appends the elements ofotherin order and emptiesother. - std-collections.list.resize
resize(len, value)shortens the list by truncation or appends copies ofvalueuntil its length islen. - std-collections.list.fill
fill(value)replaces each element with a copy ofvalue, without changing the length. - std-collections.list.reverse
reverse()reverses the elements in place, without changing the length. - 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. - std-collections.list.binary-search-duplicatesWhen several elements compare equal, any matching index may be returned.
- std-collections.list.drain
drain(range)returns a non-copyableListDrain[T, 'a]holding the mutable receiver borrow and yielding the selected elements in order. - std-collections.list.drain-boundsThe range selects half-open bounds, or includes its upper bound when
inclusiveis true; reversed or out-of-bounds ranges panic. Panic:index-out-of-bounds. - std-collections.list.drain-dropDropping the cursor discards unvisited selected elements and restores the unselected tail after the prefix in its original order.
- 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 takesRange[usize], including inclusive bounds; write0..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;appendreads 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] |
- std-collections.list.slice.elementsThe result contains the elements from
startup to, but not including,end, in order. - std-collections.list.slice.valueIt is a new list value; changing either list leaves the other unchanged.
- std-collections.list.slice.boundsAn offset greater than the list length, or
start > end, panics. Panic:index-out-of-bounds. - std-collections.list.slice.emptyEqual start and end offsets return an empty list, including at the list's length.
- 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 isview.
#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] |
- std-collections.view
view(start, end)returns aListView[T]of the list's elements at indicesstartup to, not including,end. - std-collections.view.type
std.collectionsdeclaresListView[T]with private fields and the surface in the table above, and no other method or trait implementation. - std-collections.view.snapshot
viewtakes&selfand stores a copy of that list value in the returned view. - std-collections.view.value-copyA
ListView[T]is a struct value. A copy of a view is an equal view. - std-collections.view.import
ListViewis not a prelude name, so code that names it imports it, as inuse std.collections.ListView. - std-collections.view.no-copyCreating a view copies no element.
- std-collections.view.rangeA
startorendthat is greater than the list's length is a checked runtime panic. Panic:index-out-of-bounds. - std-collections.view.reversedA
startgreater thanendis a checked runtime panic. Panic:index-out-of-bounds. - std-collections.view.len
lenreturns the number of elements in the view,end - start. - std-collections.view.index
view[i]reads the list's element at indexstart + i. - std-collections.view.index.rangeA view index that is not less than the view's
lenis a checked runtime panic, even when the list has an element there. Panic:index-out-of-bounds. - std-collections.view.iterIterating a view yields its elements in order, each as
T. - std-collections.view.cursorA view's cursor type is
ListViewIter[T], whichstd.collectionsdeclares with private fields. - std-collections.view.to-list-value
to_listreturns a new list value that holds the view's elements in order, as the sliceitems[start..end]does, solet mut copy = view.to_list()may grow the copy. - std-collections.view.read-onlyA view has no
IndexSetimplementation, so assigning toview[i]is an error. Error:invalid-assignment-target. - std-collections.view.snapshot-writesAn element write or a length change to the list after the view was taken, as
items[i] = voritems.push(v), does not show through the view.
use std.collections.ListView
fn invalid(mut view: ListView[i32]) -> void:
view[0] = 7 # error: invalid-assignment-targetfn 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 fromNote. 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
ArraySliceis, 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 |
- std-collections.span.type
std.collectionsdeclaresSpan[T, 'a]with private fields and the surface above. - std-collections.span.list
list.span()borrows the list for'aand returns a span covering every element. - std-collections.span.no-copyCreating a span copies no element.
- std-collections.span.import
Spanis not a prelude name, so code that names it importsstd.collections.Span. - std-collections.span.len
lenreturns the number of elements in the span. - std-collections.span.get
get(index)returns the indexed element as&'a Tin.Some, or.Nonewhen the index is outside the span. - std-collections.span.index-copy
span[index]copies the indexed element;&span[index]borrows its place. - 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. - std-collections.span.slice
slice(start..end)returns the elements at relative indicesstartup to, not including,end. - std-collections.span.slice-inclusive
slice(start..=end)includes the element at relative indexend. - 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. - std-collections.span.slice-borrowSlicing copies no element and returns another span that borrows the same list for
'a. - std-collections.span.lifetimeA span cannot outlive its list; returning a span of a local list is an error. Error:
local-reference-escapes. - std-collections.span.read-onlyA span has no
IndexSetimplementation, so assigning throughspan[index]is an error. Error:invalid-assignment-target. - std-collections.span.iter
iter()returns a cursor that yields each element in span order as&'a T. - std-collections.span.cursorA span's cursor type is
SpanIter[T, 'a], whichstd.collectionsdeclares with private fields. - 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. - std-collections.span.index-of-span
index_of_span(needle)returns.Someof the smallest relative index at which the span's elements equalneedle's, element by element withEq, and.Nonewhen there is none. The span may hold any bytes, valid UTF-8 or not. - std-collections.span.index-of-span.emptyAn empty needle is at
.Some(0), as instring.find, even in an empty span. - std-collections.span.index-of-span.longerA needle longer than the span gives
.None. - 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.
Spansupports 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 |
- std-collections.span-mut.type
std.collectionsdeclaresSpanMut[T, 'a]with private fields and the surface above. - std-collections.span-mut.list
list.span_mut()borrows the list mutably for'aand returns a mutable span covering every element. - std-collections.span-mut.no-copyCreating or slicing a mutable span copies no element.
- std-collections.span-mut.import
SpanMutis not a prelude name, so code that names it importsstd.collections.SpanMut. - std-collections.span-mut.len
lenreturns the number of elements in the mutable span. - std-collections.span-mut.get
get(index)returns the indexed element as&'b Tin.Some, or.Noneoutside the span. It borrows the span for'b, so the span stays usable after the last use of the result. - std-collections.span-mut.get-mut
get_mut(index)returns the indexed element as&'b mut Tin.Some, or.Noneoutside the span. It borrows the span mutably for'b. - std-collections.span-mut.index
span[index]returns a copy of the indexed element, as a list'sitems[i]does. The read borrows the span only for the call, so the span stays usable;getgives a reference. - std-collections.span-mut.index-set
span[index] = valuereplaces the indexed element without changing the list's length. - std-collections.span-mut.index-rangeAn index read or write outside the span is a checked runtime panic. Panic:
index-out-of-bounds. - std-collections.span-mut.slice
slice_mut(start..end)returns the elements at relative indicesstartup to, not including,end. - std-collections.span-mut.slice-inclusive
slice_mut(start..=end)includes the element at relative indexend. - std-collections.span-mut.slice-rangeAn invalid mutable slice range is a checked runtime panic. Panic:
index-out-of-bounds. - std-collections.span-mut.slice-borrowMutable slicing reborrows the span for
'band returns another span over the same list, so the original span is unusable while the slice is live. Error:conflicting-access. - std-collections.span-mut.swap
swap(left, right)exchanges two indexed elements without changing the list's length. - std-collections.span-mut.swap-rangeAn out-of-range
swapindex is a checked runtime panic. Panic:index-out-of-bounds. - std-collections.span-mut.fill
fill(value)replaces every element in the mutable span withvalue. - std-collections.span-mut.lifetimeA mutable span cannot outlive its list. Error:
local-reference-escapes. - std-collections.span-mut.receivers
len,get,get_mut,slice_mut,swapandfillborrow the span, with&selfor&mut selfas the table shows, so one span serves any number of calls in a row. - std-collections.span-mut.exclusiveWhile a mutable span is live, its source list may be used only through that span. Error:
conflicting-access. - std-collections.span-mut.index-mut
SpanMutimplementsIndexMut[usize]and lends the indexed element mutably, with the same bounds check.
Why.
SpanMutexposes 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 |
- std-collections.helper.unchangedEach helper but
retain,sort,sort_by,sort_by_key, andswapleaves its receiver unchanged, and each one that returns a list returns a new list. - std-collections.helper.callback-orderA helper calls its callback on the elements in list order, at most once each.
- std-collections.helper.callback-rowEach callback has the empty row, as
Iterator.filter'skeepdoes. A function value whose row lists a requirement key does not fit it. Error:type-mismatch. - std-collections.helper.sorted-by-key
sorted_by_key(key)returns the elements in ascending order ofkey(element)byOrd, and callskeyonce per element. - std-collections.helper.sorted
sortedreturns the elements in ascending order byOrd. - std-collections.helper.stableBoth sorts are stable: elements that compare equal keep their order.
- std-collections.helper.group-by
group_by(key)maps each key thatkeyreturns to the list of the elements that gave it, in list order. - std-collections.helper.partition
partition(keep)returns the elements for whichkeepis true, then the rest, each in list order. - std-collections.helper.any-all
any(test)is true whentestis true for some element, andall(test)when it is true for every element. So on an empty listanyis false andallis true. - std-collections.helper.find-copy
find(test)returns a copy of the first element for whichtestis true in.Some, or.Nonewhen there is none. - std-collections.helper.short-circuit
any,all, andfindcallteston no element after the first one that decides the result. - std-collections.helper.flat-map.iterable-owned
flat_map(transform)appends every item from each returnedIterableinto one result list, in source order. - std-collections.helper.windows.views
windows(size)returns overlappingListView[T]values ofsizeelements, in starting-index order. - std-collections.helper.windows.shortA list with fewer than
sizeelements gives[]. - std-collections.helper.windows.sizeA
sizebelow 1 panics, as it does forchunks. Panic:explicit-panic. - std-collections.helper.contains
contains(value)is true when an element equalsvaluebyEq.index_of(value)returns the index of the first such element in.Some, or.None. - std-collections.helper.min-max.copy-first
minreturns a copy of the first smallest element andmaxone to the first largest byOrd, each in.Some. An empty list gives.None. - std-collections.helper.sum
sumreturns the total of the elements, added with+in list order from 0 of typeT, so an empty list gives 0. - std-collections.helper.sum.overflowAn integer total that leaves the range of
Tpanics, as+does. Panic:integer-overflow. - std-collections.helper.sum.iterator
items.sum()returns whatitems.iter().sum()returns. - std-collections.helper.by-key.copy-first
min_by_key(key)returns a copy of the first element whosekeyis smallest byOrd.max_by_key(key)returns a copy of the first whosekeyis largest. Each returns.Some, so equal keys give the earlier element, asminandmaxdo. An empty list gives.None. - std-collections.helper.dedup
dedupreturns the list without each element that equals the element just before it in the receiver, as Rust'sVec::dedupdoes, so only adjacent duplicates go and[1, 2, 1]is unchanged. - std-collections.helper.unique
uniquereturns the list without each element that equals an earlier element, so every distinct element stays once, at its first position. - std-collections.helper.callback-refEach callback looks at an element by reference:
fn(&T), andfn(&T, &T)forsorted_byandsort_by. Each receiver is&self, or&mut selffor a method that changes the list. - std-collections.helper.retain
retain(keep)keeps the elements for whichkeepis true, in list order, and drops the rest, in place. - std-collections.helper.sort
sortputs the elements in ascending order byOrd, in place. - std-collections.helper.sort-by
sort_by(compare)puts the elements in ascending order bycompare, in place. - std-collections.helper.sort-by-key
sort_by_key(key)puts the elements in ascending order ofkey(element)byOrd, in place, and callskeyonce per element. - std-collections.helper.sort.stable
sort,sort_by, andsort_by_keyare stable, assorted_byis: elements that compare equal keep their order. - std-collections.helper.swap
swap(a, b)exchanges the elements ataandb. An index that is not less thanlen()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-panicWhy. The names are Rust's (
sort_by_key,partition,windows,any,all,find,flat_map,contains,min,max), Kotlin'sgroupBy, and Python'slist.index. A sort copies, assorted_bydoes, since hd has no consuming methods.minandmaxboth pick the first of equal elements, as Python'sminandmaxdo, so one rule covers both.sumis Python'ssumand Rust'sIterator::sum; a list has it as a method besideminandmax, since a list is not an iterator.
dedupisVec::dedup, which removes every duplicate only from a sorted list;uniqueis what Python'sdict.fromkeysgives 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"]- std-collections.counts.decl
std.collectionsdeclarespub fn counts[T < Eq & Hash](items: List[T]) -> Map[T, usize]. Code imports it, as inuse std.collections.counts. - 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. - std-collections.counts.emptyAn empty list gives an empty map.
Why.
countsis Python'scollections.Counteras a plain map, so theMapmethods 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,valuesandentriesreturn 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- std-collections.map.get
get(key)is the built-in copying lookup (expr.index.map.get): it returns.Someof a copy of the stored value, or.Nonewhen the map has no equal key. - std-collections.map.get-or-insert
get_or_insert(key, default)returns a mutable reference to the stored value when the map has an equal key. - std-collections.map.get-or-insert.missingWhen the map has no equal key,
get_or_insertinserts(key, default)and returns a mutable reference to the inserted value. - std-collections.map.get-or-insert.referenceThe reference that
get_or_insertreturns is dependent on its receiver byref.dep.elide. - std-collections.map.get-or-insert.probe-onceEach
get_or_insertcall invokes the key'sHashimplementation once and performs one map search, reusing a missing search position for insertion. - std-collections.map.contains-key
contains_key(key)is true exactly when the map has an entry whose key equalskey. - std-collections.map.keys.order
keysreturns the map's keys in its iteration order. - std-collections.map.values
valuesreturns the map's values in the same order. - std-collections.map.snapshotEach returned list is a snapshot: a later change to the map does not change it.
- std-collections.map.is-empty
is_emptyis true exactly whenlen()is 0. - std-collections.map.entries
entriesreturns the map's(key, value)pairs in its iteration order, which is the order ofkeysandvalues, as a snapshot like theirs. - std-collections.map.most-common
most_common(n)returns thenpairs of the map with the largest values, largest first, or every pair whennis at leastlen(). Annof 0 gives[]. - std-collections.map.most-common.tie-orderPairs with equal values keep the map's iteration order, which is the same in every run.
Why.
entriesis a list snapshot likekeysandvalues, since a loop that sorts or indexes the pairs needs a list.most_commonis Python'sCounter.most_common; a stable sort over the map's order gives its tie rule with no extra bookkeeping.get_or_insertis Rust'sHashMap::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] |
- std-collections.map.retain
retain(keep)visits each entry once in iteration order, letskeepchange its value, and removes entries for which it returns false. - std-collections.map.extend
extend(other)inserts each yielded pair in order, replacing the value of an equal key as indexed assignment does. - std-collections.map.extend-last-winsWhen
otheryields equal keys more than once, the value of the last such pair stays. - std-collections.map.drain
drain()empties the map and returns a non-copyableMapDrain[K, V, 'a]that borrows its receiver mutably and yields entries in iteration order. - std-collections.map.drain-dropDropping the drain discards every unvisited entry and leaves the map empty.
- 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- std-collections.struct.value
Set[T],Deque[T], andHeap[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. - 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). - std-collections.struct.receiver-mutMethods that change a collection, such as
push_back,insert, andpop, take&mut self. - 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, asbox(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 |
- std-collections.set.decl
std.collectionsdeclaresSet[T < Eq & Hash]with private fields, the surface in the table above, and no other method or trait implementation. Code imports it, as inuse std.collections.Set. - std-collections.set.distinctA set holds elements no two of which are equal by
Eq.newreturns an empty set. - std-collections.set.len
lenreturns the number of elements, andis_emptyis true exactly when that number is 0. - std-collections.set.contains
contains(value)is true exactly when the set has an element equal tovalue. - std-collections.set.insert
insert(value)addsvalueand returnstruewhen the set has no element equal to it. Otherwise it changes nothing and returnsfalse. - std-collections.set.remove
remove(value)removes the element equal tovalueand returnstrue. When there is none, it changes nothing and returnsfalse. - 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. - std-collections.set.cursorA set's cursor type is
SetIter[T], whichstd.collectionsdeclares with private fields. - std-collections.set.snapshotIterating a set walks the set as it was when
iterwas called. Aninsertor aremovewhile the loop runs changes the set but not the loop, and never panics, asflow.for.snapshotstates for a map. - std-collections.set.eqTwo sets are equal when each element of one equals an element of the other, in any order.
- 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/stdbuilds a set over aMapwhose values carry no meaning, soinsert,remove, andcontainstake expected constant time, bymodule.map.complexity.
Why.
insertandremovereport whether they changed the set, as Rust'sHashSetmethods do, so a loop that skips duplicates needs no second lookup. A set iterates in a map's deterministic order, so its iteration andDebugtext 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] |
- std-collections.deque.collect-surface
std.collectionsdeclaresDeque[T]with private fields, the surface in the table above, and no other method or trait implementation. Code imports it, as inuse std.collections.Deque. - std-collections.deque.orderA deque holds a sequence of elements from its front to its back.
newreturns an empty deque. - std-collections.deque.len
lenreturns the number of elements, andis_emptyis true exactly when that number is 0. - std-collections.deque.push
push_front(value)addsvaluebefore the front, andpush_back(value)adds it after the back. - std-collections.deque.pop
pop_frontremoves the front element and returns it in.Some, andpop_backdoes the same at the back. On an empty deque, each returns.Noneand changes nothing. - std-collections.deque.ends-copy
frontandbackreturn a copy of the front and the back element without removing it, or.Nonewhen the deque is empty. - std-collections.deque.get-copy
get(i)returns a copy of the elementiplaces from the front in.Some, soget(0)is the front. Anithat is not less thanlengives.None. - std-collections.deque.iterIterating a deque yields its elements from front to back, each as
T. - std-collections.deque.cursorA deque's cursor type is
DequeIter[T], whichstd.collectionsdeclares with private fields. - std-collections.deque.snapshotIterating a deque walks the deque as it was when
iterwas called. A push or a pop while the loop runs changes the deque but not the loop, and never panics, asflow.for.snapshotstates for a list. - 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.
- 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 panicsNote.
lib/stdbuilds a deque as a ring buffer over aList[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, andgettakes constant time.
Why.
getreturns an optional, as Rust'sVecDeque::getdoes: 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] |
- std-collections.heap.collect-surface
std.collectionsdeclaresHeap[T < Ord]with private fields, the surface in the table above, and no other method or trait implementation. Code imports it, as inuse std.collections.Heap. - std-collections.heap.len
newreturns an empty heap.lenreturns the number of elements, andis_emptyis true exactly when that number is 0. - std-collections.heap.push
push(value)addsvalueto the heap. - std-collections.heap.pop
popremoves a largest element byOrdand returns it in.Some. On an empty heap, it returns.None. - std-collections.heap.peek-copy
peekreturns a copy of a largest element without removing it, or.Nonewhen the heap is empty. - std-collections.heap.tiesWhen several elements are equal by
cmp, which of thempopandpeekreturn is not specified. - std-collections.heap.sorted
to_sorted_listreturns a new list of every element in ascending order byOrd, and leaves the heap unchanged. - std-collections.heap.min
stdhas no separate min-heap: aHeap[Reverse[T]]pops the smallestTfirst, bystd-cmp.reverse.order. - std-collections.heap.collectA heap implements
FromIterator[T], collecting every element into a max-heap. - std-collections.heap.collect.linearHeapification of
ncollected elements performs O(n) comparisons, by sifting non-leaves from the bottom up.
Note.
lib/stdkeeps the elements in aList[T?]in heap order, sopushandpoptake logarithmic time andpeekconstant time.
Why.
to_sorted_listcopies, assorted_bydoes, because hd has no consuming methods; its ascending order is that of Rust'sinto_sorted_vec. A heap has noEqand 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 |
- std-collections.access.get-copy
get(index)returns.Someof a copy of the element atindex, or.Nonewhenindexis not less thanlen(). It never panics. - std-collections.access.is-empty
is_emptyis true exactly whenlen()is 0. - std-collections.access.first-last-copy
firstreturns a copy of the element at index 0 andlastone of the element at indexlen() - 1, each in.Some. An empty list gives.None. - std-collections.access.take
take(count)returns a new list of the firstcountelements, or of every element whencountis at leastlen(). - std-collections.access.filter
filter(keep)returns a new list of the elements for whichkeepis true, in list order. - std-collections.access.reversed
reversedreturns a new list of the elements in reverse order. - std-collections.access.sorted-by
sorted_by(compare)returns a new list in ascending order bycompare. The sort is stable. - std-collections.access.zip
zip(other)returns a new list of pairs(self[i], other[i])for each indexiof both lists, so it stops at the shorter one. - std-collections.access.extend
extend(other)appends each element ofotherto the receiver, in order, aspushdoes. - std-collections.access.extend.self
items.extend(items)appends a copy of the elementsitemsheld before the call, so it doubles the list. - std-collections.access.helper-rulesThe callbacks of
filterandsorted_byfollowstd-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.
getis the checked, copying read besideitems[i].takeis Kotlin'sList.take: likeList.map, the list method is eager and returns a list, whileIterator.takestays lazy.extendis Rust'sVec::extend, and replacesitems = items + more.
See also: Built-In Methods, Iterator Adapters.