Skip to content
Tutorials Center
My learning

Topics

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.

Rust
use std::collections::{BTreeMap, HashMap, HashSet, VecDeque, BinaryHeap};

Try it

Rust One of each

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.

Rust Ranges and a priority queue

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 need Ord. Floats satisfy neither Eq nor Ord, so wrap them or use an integer key.
  • HashMap and HashSet iterate in unspecified, varying order. Sort the output or use a BTree* when output must be stable.
  • BinaryHeap is a max-heap. Wrap items in std::cmp::Reverse for a min-heap. Iterating a heap does not give sorted order; use into_sorted_vec.
  • VecDeque replaces most uses of LinkedList. 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, Extend and IntoIterator, so collect() and for loops work everywhere. All of them are generic over the allocator only on nightly.
  • Capacity: HashMap, HashSet, VecDeque and BinaryHeap offer with_capacity and reserve; B-trees and LinkedList do not.
  • Vec, slices and String are not in this module; see the type pages.