Beyond the Standard Collections

Rust’s standard library collections — Vec, HashMap, BTreeMap, and the rest — solve the vast majority of data storage needs. They are well-optimized, thoroughly tested, and deeply integrated with the ownership system. But they are not the final word. Some problems demand performance characteristics, concurrency guarantees, or memory layouts that the standard types deliberately do not provide. The broader crate ecosystem fills those gaps with data structures that, while not always necessary, make certain classes of programs simpler, faster, or even possible.

This page surveys the most important collection crates outside std, explains the situations that motivate them, and shows how to use each one in practice.

Why Look Beyond std::collections?

The standard collections are built for broad generality. That means they make trade-offs: HashMap uses a cryptographically strong hash function that resists HashDoS attacks but is not the fastest possible hash. Vec always allocates on the heap, even when you only need to store three integers. None of the standard maps or sets remember insertion order, and none are safe to share across threads without external synchronisation.

A crate author can optimise for a narrower slice of the design space. The result is a collection that outperforms the standard one in a specific dimension — speed, memory footprint, concurrency, or access pattern — while giving up something else. The skill lies in recognising when that trade-off is worth making.

When Standard Collections Fall Short

Several concrete signals suggest it is time to look beyond std:

• You need to iterate a map in insertion order. HashMap and BTreeMap iterate in arbitrary hash order or key-sorted order respectively. Neither preserves the order in which entries were added.
• You create many tiny collections. Allocating a Vec with three elements on the heap is wasteful. A collection that stores small numbers of items directly on the stack can eliminate heap traffic entirely.
• Multiple threads need to read and write the same map. Wrapping a HashMap in a Mutex serialises all access. A concurrent map allows far more parallelism.
• You need a lock-free queue for message passing across threads. std provides mpsc channels, but lock-free queues can deliver lower latency under contention.
• You need persistent, immutable data structures that share structure between versions. Functional programming patterns, undo systems, or time-travel debugging become drastically simpler with structural sharing.
• You are targeting no_std or embedded environments and cannot use heap-allocated collections at all, or you need fixed-capacity containers that never allocate.

Each of these scenarios maps directly to a well-established crate.

Common Categories of Third-Party Collections

The Rust ecosystem organises its non-standard collections into a few clear families. Understanding these families helps you navigate the crate landscape without memorising every library.

IndexMap and IndexSet: Order-Preserving Maps

The indexmap crate provides IndexMap<K, V> and IndexSet<T>. They behave like the standard HashMap and HashSet but additionally remember the order in which keys were inserted. Iteration yields entries in that exact order. You can also access entries by positional index, something impossible with a standard hash map.

[dependencies]
indexmap = "2"

use indexmap::IndexMap;
let mut scores = IndexMap::new();
scores.insert("Blue", 10);
scores.insert("Red", 25);
scores.insert("Green", 15);
// Iteration follows insertion order: Blue, Red, Green
for (team, score) in &scores {
    println!("{team}: {score}");
}
// Access by position
if let Some((team, score)) = scores.get_index(1) {
    println!("Second entry: {team} has {score}");
}

Under the hood, IndexMap maintains a hash table for fast key lookup and a Vec that stores the key-value pairs in insertion order. The dual structure means lookups are still O(1) expected, but iteration is slightly faster than HashMap because the items are already laid out contiguously in the internal vector. The price is higher memory overhead — the keys and values are stored twice, once in the hash table and once in the order vector — and slightly slower insertion and removal because both structures must be updated.

SmallVec, TinyVec, and ArrayVec: Stack-Optimised Vectors

A Vec<T> always allocates its buffer on the heap, even if it only holds two elements. The smallvec crate offers SmallVec<[T; N]>, which stores up to N elements directly on the stack inside the struct. When the inline capacity is exceeded, it spills the remaining elements onto the heap, behaving like a normal Vec from that point on.

This can eliminate enormous numbers of heap allocations in code that creates thousands of short-lived, small vectors.

[dependencies]
smallvec = "1"

use smallvec::{smallvec, SmallVec};
// Inline storage for up to 4 elements — no heap allocation
let mut v: SmallVec<[i32; 4]> = smallvec![1, 2, 3];
v.push(4);      // still inline
v.push(5);      // spills to heap — now behaves like Vec<i32>

arrayvec takes a stricter approach: it never allocates. ArrayVec<[T; N]> uses a fixed-size array as its backing store, and any attempt to push beyond that capacity returns an error or panics. This makes arrayvec ideal for no_std contexts or places where allocation is simply forbidden.

[dependencies]
arrayvec = "0.7"

use arrayvec::ArrayVec;
let mut v: ArrayVec<i32, 4> = ArrayVec::new();
v.push(1);
v.push(2);
assert!(v.try_push(3).is_ok());
assert!(v.try_push(4).is_ok());
// v.try_push(5) would return Err(CapacityError { .. })

Concurrent Collections for Multi-Threaded Code

The standard library provides no concurrent collections beyond channels. If multiple threads need to share a mutable map, you must wrap a HashMap in a Mutex or RwLock. That works, but all threads contend for a single lock. Under heavy read traffic, the lock becomes a scalability ceiling.

dashmap is the most popular concurrent map in the Rust ecosystem. It shards the hash table into multiple segments, each protected by its own RwLock. Reads that fall into different shards can proceed in parallel, and writes only block their own shard. The API is deliberately similar to HashMap, with a few extra methods like alter for atomic updates.

[dependencies]
dashmap = "5"

use dashmap::DashMap;
use std::sync::Arc;
use std::thread;
let map = Arc::new(DashMap::new());
map.insert("key", 0);
let mut handles = vec![];
for _ in 0..8 {
    let map = Arc::clone(&map);
    handles.push(thread::spawn(move || {
        // Each thread increments the value atomically
        map.alter("key", |_, v| v + 1);
    }));
}
for h in handles {
    h.join().unwrap();
}
assert_eq!(*map.get("key").unwrap(), 8);

dashmap does not support holding a mutable reference to a value while performing other operations on the same map — the shard lock is not re-entrant. Doing so will deadlock.

// DANGER: deadlock — the shard is already locked by the `get_mut` guard
let map = DashMap::new();
map.insert("a", 1);
let mut guard = map.get_mut("a").unwrap();
map.insert("b", 2); // waits forever for the shard lock

For lock-free queues, the crossbeam crate offers SegQueue and ArrayQueue, and concurrent-queue provides a multi-producer multi-consumer queue that can be used without Arc if you are in a single-task context.

Persistent and Immutable Data Structures

Conventional collections like Vec are ephemeral: when you push an element, the collection mutates in place, and the old state is gone. Persistent data structures, by contrast, preserve the old version while creating a new one. They do this through structural sharing — both versions reference most of the same memory, so cloning is cheap even for large collections.

The im crate (short for "immutable") provides persistent vectors, hash maps, hash sets, and ordered maps designed for use with Rust's ownership model. Every update returns a new collection, leaving the original intact.

[dependencies]
im = "15"

use im::Vector;
let v1 = Vector::new();
let v2 = v1.push_back(1);
let v3 = v2.push_back(2);
// v1 is still empty, v2 contains [1], v3 contains [1, 2]
// They share most of their internal tree structure

Cloning an im::Vector or im::HashMap is an O(1) pointer copy, not an O(n) element copy. This makes patterns like keeping a history of states, implementing undo functionality, or passing snapshots between threads trivial — you just clone the collection.

Specialised and Niche Data Structures

Beyond the broad categories, several crates solve narrower problems:

• heapless — provides Vec, String, and LinearMap that never allocate, backed by fixed-capacity arrays. Essential for no_std firmware or real-time systems.
• bitvec — a Vec<bool> replacement that actually packs bits, supporting bit-level indexing and slicing with a familiar API.
• ndarray — multi-dimensional arrays with slicing, broadcasting, and mathematical operations. Closer to NumPy than to standard collections, but indispensable for numerical computing.
• halfbrown — an alternative hash map implementation designed for smaller keys and faster hashing, sometimes used in performance-sensitive parsers.

Each of these crates follows the same pattern: they solve one specific problem that the standard library chose not to solve, and they do it well.

Choosing the Right Crate

Use this decision sequence when a standard collection isn't enough:

1. Identify the missing capability. Is it insertion-order iteration? Concurrent access? Cheap cloning? Zero allocation?
2. Select the narrowest crate that provides that capability. Don't pull in a full persistent data structure library if all you need is a small-vector optimisation.
3. Verify that the performance profile matches your workload. An IndexMap is faster for iteration but slower for insertion than a HashMap. A DashMap scales across threads but has higher single-thread overhead than a plain Mutex<HashMap> when contention is low.
4. Test with realistic data. Microbenchmarks rarely tell the whole story. The only way to know if a collection improves your program is to measure it in context.

Summary

The standard collections cover the common case brilliantly, but Rust's crate ecosystem fills the gaps with precision. indexmap preserves insertion order. smallvec and arrayvec eliminate heap traffic for tiny collections. dashmap and crossbeam make concurrency practical without hand-rolled locks. im enables the functional patterns that some domains demand.

The thread connecting all these crates is that they solve a specific, named problem — not a vague desire for "better performance," but a concrete requirement like "I need to iterate in insertion order" or "I need multiple threads to read without blocking each other." When you can articulate the problem that clearly, the right crate is usually obvious. When you can't, the standard library is almost certainly the right place to stay.