Collections

Joule provides a comprehensive set of collection types in the standard library.

Overview

Vec<T>

See Vec for full documentation.

let mut v: Vec<i32> = Vec::new();
v.push(1);
v.push(2);
let first = v[0];

HashMap<K, V>

See HashMap for full documentation.

let mut map: HashMap<String, i32> = HashMap::new();
map.insert("key", 42);
let val = map.get("key");

HashSet<T>

An unordered set of unique elements.

let mut set: HashSet<i32> = HashSet::new();
set.insert(1);
set.insert(2);
set.insert(1);          // no effect, already present
let has = set.contains(1); // true
let count = set.len();     // 2

BTreeMap<K, V>

A sorted map. Keys are kept in sorted order.

let mut map: BTreeMap<String, i32> = BTreeMap::new();
map.insert("banana", 2);
map.insert("apple", 1);
map.insert("cherry", 3);

// Iterates in key order: apple, banana, cherry
for (key, value) in map {
    println!("{}: {}", key, value);
}

BTreeSet<T>

A sorted set of unique elements.

let mut set: BTreeSet<i32> = BTreeSet::new();
set.insert(3);
set.insert(1);
set.insert(2);

// Iterates in order: 1, 2, 3
for item in set {
    println!("{}", item);
}

VecDeque<T>

A double-ended queue implemented as a ring buffer.

let mut deque: VecDeque<i32> = VecDeque::new();
deque.push_back(1);
deque.push_back(2);
deque.push_front(0);

let front = deque.pop_front();   // Option::Some(0)
let back = deque.pop_back();     // Option::Some(2)

BinaryHeap<T>

A max-heap (priority queue). The largest element is always at the top.

let mut heap: BinaryHeap<i32> = BinaryHeap::new();
heap.push(3);
heap.push(1);
heap.push(4);
heap.push(1);
heap.push(5);

let max = heap.pop();    // Option::Some(5)
let next = heap.pop();   // Option::Some(4)

SmallVec[T; N]

A vector that stores up to N elements inline (on the stack), spilling to the heap only when the capacity is exceeded. Ideal for short, bounded collections where heap allocation is wasteful.

let mut sv: SmallVec[i32; 8] = SmallVec::new();

// First 8 elements are stored inline — no heap allocation
for i in 0..8 {
    sv.push(i);       // 0.5 pJ per push (inline)
}

// 9th element triggers heap spill — 45.0 pJ
sv.push(99);

sv.len();             // 9
sv.capacity();        // 16 (heap capacity after spill)
sv.spilled();         // true
sv.get(0);            // 0
sv.pop();             // 99

sv.clear();
sv.drop();            // free heap if spilled

Energy trade-off: Inline pushes cost 0.5 pJ vs ~45 pJ for heap spill. Size N so that most instances never spill.

Deque<T>

Double-ended queue implemented as a ring buffer. O(1) push/pop at both ends.

let mut dq: Deque<i32> = Deque::new();
dq.push_back(1);
dq.push_back(2);
dq.push_front(0);

let front = dq.pop_front();   // Option::Some(0)
let back = dq.pop_back();     // Option::Some(2)

dq.front();                    // peek at front
dq.back();                     // peek at back
dq.len();                      // 1
dq.rotate_left(1);            // rotate elements

Arena<T>

Bump allocator — allocates by advancing a pointer. Individual elements cannot be freed; call reset() to free everything at once in O(1). Ideal for phase-based allocation (parsers, compilers, frame allocators).

let mut arena: Arena<AstNode> = Arena::new();

// Allocation is a pointer bump — 1.0 pJ
let node1 = arena.alloc(AstNode { kind: "expr", children: Vec::new() });
let node2 = arena.alloc(AstNode { kind: "stmt", children: Vec::new() });

arena.len();            // 2 elements allocated
arena.bytes_used();     // bytes consumed
arena.bytes_capacity(); // total buffer size

// Free everything at once — 0.5 pJ regardless of count
arena.reset();

BitSet

Fixed-capacity bit field stored as u64 words. Space-efficient boolean set with O(1) insert/contains and fast set operations.

let mut bits = BitSet::new();

bits.insert(0);
bits.insert(42);
bits.insert(63);

bits.contains(42);           // true
bits.remove(42);
bits.count_ones();           // number of set bits
bits.count_zeros();          // number of unset bits

// Set operations
let union = bits.union(&other);
let inter = bits.intersection(&other);
let diff = bits.difference(&other);
bits.is_subset(&other);

BitVec

Dynamic-length bit vector. Like BitSet but growable.

let mut bv = BitVec::new();

bv.push(true);
bv.push(false);
bv.push(true);

bv.get(1);              // false
bv.set(1, true);
bv.len();               // 3 (bits)
bv.count_ones();        // 3
bv.pop();               // true

Choosing a Collection

• Need a sequence? Use Vec<T>
• Need a short, bounded sequence? Use SmallVec[T; N] (avoids heap allocation)
• Need fast key lookup? Use HashMap<K,V>
• Need unique elements? Use HashSet<T>
• Need sorted keys? Use BTreeMap<K,V> (12.0 pJ per traversal)
• Need a queue? Use Deque<T> (2.0 pJ push/pop)
• Need a priority queue? Use BinaryHeap<T>
• Need phase-based allocation? Use Arena<T> (1.0 pJ alloc, 0.5 pJ free-all)
• Need a compact boolean set? Use BitSet or BitVec (0.3 pJ per operation)
• Need frequent middle insertion? Use LinkedList<T> (rare)