Rust's standard library contains common collection types, such as sequences, sets, and maps. These live in the
no_std environments, they can be accessed under
Sequences[edit | edit source]
Sequences can contain an arbitrary number of items of the same type. The standard library contains three sequence types:
Vec[edit | edit source]
is the most ubiquitous collection type. It is backed by a heap-allocated array. When items are added or removed from the
Vec, the array grows or shrinks dynamically. Even though pushing items to a
Vec sometimes requires copying the array, the amortized time to push an item is constant.
Vec is the most performant sequence type in the standard library for many purposes, and the only one that can be sliced as it is stored contiguously in memory.
Length and capacity[edit | edit source]
Vec manages to achieve a constant amortized push complexity by allocating space for more elements than it contains. Since most of the time the underlying storage is in fact larger than the required storage, the push operation is simply a matter of copying one item to the end and incrementing the length.
When writing performance-critical code, reallocating can be costly. It is therefore advised to manually control the capacity of your
Vec using methods such as
VecDeque[edit | edit source]
is a circular buffer. It works similar to
Vec, except that inserting or removing items at the start of the sequence is more efficient.
LinkedList[edit | edit source]
is a doubly-linked list. It allows adding and removing items at both ends in constant time, but doesn't allow indexing items in constant time.
LinkedList is less memory efficient and less cache friendly than
VecDeque, which very often leads to worse performance.
Maps[edit | edit source]
Maps are data structures that map keys to values. The standard library contains two map types:
HashMap[edit | edit source]
is an efficient implementation of a hash map. It internally uses the
BTreeMap[edit | edit source]
Sets[edit | edit source]
Sets are unordered collections that can't contain the same item more than once. The standard library contains the
types, which internally use the same implementation as
BTreeMap (the items are stored in the keys, and the values are empty).
BinaryHeap[edit | edit source]
is a priority queue implemented with a binary heap.