Rust Reference ยท Standard Library Modules
The std::collections module
Overview of Rust std::collections: Vec companions HashMap, BTreeMap, HashSet, BTreeSet, VecDeque, BinaryHeap and LinkedList, and how to choose between them.
std::collections holds the standard library's general-purpose collection types other than Vec and arrays (which live in the prelude and in alloc). There are seven: HashMap, BTreeMap, HashSet, BTreeSet, VecDeque, BinaryHeap and LinkedList. Maps and sets come in a hashed and a sorted flavour; the other three are specialised sequences.
Choosing is mostly a question of which operations you need. Start with Vec, HashMap and HashSet; reach for a BTree* when you need sorted iteration or range queries, VecDeque for queues, and BinaryHeap for "give me the largest next". LinkedList is almost never the right answer.
use std::collections::{BTreeMap, HashMap, HashSet, VecDeque, BinaryHeap};
Try it
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.
Press Run (or Ctrl + Enter) to see the result here.
Program input ยท what you'd type while the program runs
Type the answers before you press Run, one per line. Each time the program reads a line (with io::stdin().read_line()), it gets the next line from this box.
Syntax
| Type | Backing structure | Key operations | Cost |
|---|---|---|---|
HashMap<K, V> |
hash table | insert, get, remove, entry | O(1) average |
HashSet<T> |
hash table | insert, contains, remove, set algebra | O(1) average |
BTreeMap<K, V> |
B-tree | the same, plus range, first_key_value, sorted iteration |
O(log n) |
BTreeSet<T> |
B-tree | the same, sorted | O(log n) |
VecDeque<T> |
ring buffer | push_front, push_back, pop_front, pop_back, indexing |
O(1) at both ends |
BinaryHeap<T> |
binary max-heap | push, pop, peek |
O(log n) push/pop, O(1) peek |
LinkedList<T> |
doubly linked list | push/pop at both ends, append, split_off |
O(1) at ends, O(n) to reach the middle |
Usage notes
- Hash keys need
Eq + Hash; B-tree keys needOrd. Floats satisfy neitherEqnorOrd, so wrap them or use an integer key. HashMapandHashSetiterate in unspecified, varying order. Sort the output or use aBTree*when output must be stable.BinaryHeapis a max-heap. Wrap items instd::cmp::Reversefor a min-heap. Iterating a heap does not give sorted order; useinto_sorted_vec.VecDequereplaces most uses ofLinkedList. Contiguous memory is much faster in practice.- Mutating keys is impossible (keys are owned by the collection and exposed as
&K), which keeps the ordering and hash invariants safe. Interior mutability in a key can break them, so do not do that. - Collections implement
FromIterator,ExtendandIntoIterator, socollect()andforloops work everywhere. All of them are generic over the allocator only on nightly. - Capacity:
HashMap,HashSet,VecDequeandBinaryHeapofferwith_capacityandreserve; B-trees andLinkedListdo not. Vec, slices andStringare not in this module; see the type pages.
Related
Vec<T>,HashMap<K, V>,HashSet<T>,LinkedList<T>,std::cmp- Lessons: HashMap, Other collections, Entry API