Pick the advanced Rust data structure that makes ownership trivial instead of fighting the borrow checker. Covers arena allocation & generational indices (slotmap, generational-arena, id-arena, typed-arena) as the idiomatic alternative to Rc<RefCell> for graphs/trees; petgraph for real graph algorithms; small/inline vectors (smallvec, tinyvec, arrayvec); Rc/Arc + Weak for breaking cycles; lock-free & concurrent (crossbeam channels/epoch/queue, flume, dashmap, atomics, the ABA problem); intrusive collections; copy-on-write (Cow, im/rpds persistent structures); ECS / struct-of-arrays for cache locality; string/symbol interning; bitsets (roaring); and choosing among BTreeMap / HashMap / hashbrown / fxhash / ahash / indexmap. Use when a Rust ownership problem is really a data-structure choice, when Rc<RefCell> or lifetimes are spiraling, or when a hot path needs a cache-friendlier or concurrent container. NOT for beginner Rust syntax, generic borrow-checker tutoring unrelated to structure choice, async runtime se
Instrucciones de origen · Vista previa de solo lectura
name
rust-data-structures-advanced
version
0.1.0
description
Pick the advanced Rust data structure that makes ownership trivial instead of fighting the borrow checker. Covers arena allocation & generational indices (slotmap, generational-arena, id-arena, typed-arena) as the idiomatic alternative to Rc<RefCell> for graphs/trees; petgraph for real graph algorithms; small/inline vectors (smallvec, tinyvec, arrayvec); Rc/Arc + Weak for breaking cycles; lock-free & concurrent (crossbeam channels/epoch/queue, flume, dashmap, atomics, the ABA problem); intrusive collections; copy-on-write (Cow, im/rpds persistent structures); ECS / struct-of-arrays for cache locality; string/symbol interning; bitsets (roaring); and choosing among BTreeMap / HashMap / hashbrown / fxhash / ahash / indexmap. Use when a Rust ownership problem is really a data-structure choice, when Rc<RefCell> or lifetimes are spiraling, or when a hot path needs a cache-friendlier or concurrent container. NOT for beginner Rust syntax, generic borrow-checker tutoring unrelated to structure choice, async runtime selection, or non-Rust data-structure theory.
license
Apache-2.0
allowed-tools
Read,Write,Edit,Bash,Glob,Grep,WebSearch,WebFetch
metadata
{"category":"Code Architecture & Performance","tags":["rust","data-structures","arena","generational-index","slotmap","petgraph","lock-free","crossbeam","cache-locality","ecs","performance"],"pairs-with":[{"skill":"advanced-rust-patterns","reason":"Trait/generic design and structure choice are the two halves of \"idiomatic ownership\" in Rust"},{"skill":"rust-performance-and-idioms","reason":"A structure swap (arena, smallvec, dashmap) is only a win if the idiom and the benchmark agree"},{"skill":"rust-debugging-mastery","reason":"Diagnosing a hand-rolled lock-free bug (ABA, use-after-free) or a Miri/Loom failure hands off to this skill's debugging depth"},{"skill":"rust-with-claude-code","reason":"Shares the toolchain/testing workflow this skill's worked examples and quality gates plug into when pairing with an agent"}],"provenance":{"kind":"first-party","owners":["port-daddy"]},"authorship":{"maintainers":["port-daddy"]},"io-contract":{"kind":"deliverable","consumes":["[Truncated]","[Truncated]"],"produces":["[Truncated]","[Truncated]"]}}
rust-data-structures-advanced
The skill for when a Rust ownership problem is actually a data-structure problem.
The throughline: choose the structure that makes ownership trivial. Most "fighting the
borrow checker" pain on graphs, trees, caches, and shared state is self-inflicted by
reaching for Rc<RefCell<T>> (or worse, Arc<Mutex<T>>) to model relationships that an
arena + indices models with zero runtime borrow checking, zero cycles-as-leaks, and
better cache behavior. The borrow checker is not the obstacle; the wrong container is.
When to Use
✅ Use for:
Modeling a graph, tree, DAG, AST, or doubly-linked structure in Rust
Rc<RefCell<T>> / Arc<Mutex<T>> is multiplying and ownership is spiraling
A hot path needs cache locality (struct-of-arrays, inline vectors) or a faster map/hasher
Concurrent producers/consumers: which channel, which concurrent map, lock-free vs lock
Cheap-to-clone shared state (copy-on-write, persistent/immutable structures)
Interning strings/symbols, dense ID sets (bitsets), or stable handles into a pool
❌ NOT for:
Beginner Rust syntax or generic borrow-checker tutoring with no structural decision
Choosing an async runtime (tokio vs smol) — orthogonal to container choice
Algorithm design or complexity theory divorced from a concrete Rust crate
Non-Rust languages (GC languages make most of this moot)
The One Decision That Drives Everything
flowchart TD
A["I need to store related items"] --> B{"Shape of relationship?"}
B -->|"Graph / tree / cyclic / cross-links"| C{"Need graph algorithms<br/>(BFS, Dijkstra, SCC, topo)?"}
C -->|Yes| D["petgraph (StableGraph if you delete nodes)"]
C -->|No| E["Arena + generational index<br/>slotmap / generational-arena"]
B -->|"Pool of objects, stable handles, deletes"| E
B -->|"Build-once, same-type, never delete (AST/IR)"| F["typed-arena / id-arena<br/>(&'arena T or u32 ids)"]
B -->|"Sequence, small & bounded"| G{"Spills past N ever?"}
G -->|"Never (hard cap)"| H["arrayvec (fixed, panics over cap)"]
G -->|"Rarely, want safety net"| I["smallvec / tinyvec (inline → heap)"]
B -->|"Key → value lookup"| J["see references/04-choosing-a-map.md"]
B -->|"Shared, mostly-read, cheap clone"| K["Cow / im / rpds (persistent)"]
B -->|"Shared across threads, mutated"| L["see references/02-concurrent-and-lockfree.md"]
E --> M["Ownership is now trivial:<br/>the arena owns everything,<br/>indices are Copy, cycles are fine"]
D --> M
F --> M
Read the diagram as one claim: the moment relationships are modeled as indices into a
single owner (an arena) instead of pointers between owners (Rc), the borrow checker
stops fighting you. Indices are Copy, cycles are just usizes, and deletion is safe
because a generational index detects a stale handle instead of dangling. Depth lives in
references/01-arenas-and-graphs.md.
Core Capabilities
Structure / crate
Wins for the access pattern
Replaces (the naive thing)
Intuition / benchmark
slotmap
Pool with stable Copy keys, fast iteration over holes
Generation check is one ==; secondary maps give ECS-style columns. Unsafe inside but safe API.
generational-arena
Same, zero-unsafe, simpler
hand-rolled free list
Slightly slower iteration than slotmap; pick when you want no unsafe in the dep
id-arena / typed-arena
Build-once same-type allocation (AST/IR)
Box-per-node with lifetime soup
typed-arena hands back &'arena T (no indices); id-arena hands back CopyId<T>
petgraph
Real graph algorithms on a built graph
rolling your own adjacency + BFS
Graph is dense+fast but indices shift on delete; StableGraph keeps indices stable across removals
smallvec/tinyvec
Sequences that are usually tiny
Vec that allocates for 0–4 elements
Inline N on stack, spill to heap past N. tinyvec is 100% safe but needs T: Default
arrayvec
Hard-capped sequence, no heap ever
Vec with a known max
Fixed capacity; push past cap panics (or try_push). no_std friendly
Rc/Arc + Weak
Tree with child→parent backrefs
Rc↔Rc cycle that leaks
Weak for the up/back edge breaks the refcount cycle; arenas usually beat this anyway
crossbeam-channel / flume
MPMC pipelines, select!
std::sync::mpsc (SPMC-limited, slower)
Both MPMC, both clone Sender+Receiver, both beat std mpsc; flume is leaner, crossbeam has select!
dashmap
Concurrent map, many threads R/W
Arc<Mutex<HashMap>> (one big lock)
Sharded locks → contention drops; but a held Ref guards a shard (deadlock risk)
crossbeam-epoch / -queue
Lock-free structures, safe reclamation
raw atomics + "when do I free?"
Epoch GC solves use-after-free / ABA without hazard-pointer bookkeeping
Cow<'a, T>
Mostly-borrow, occasionally-own
always .to_owned() / .clone()
Clone-on-write: borrow until the first mutation, then own
im / rpds
Cheap-clone shared snapshots, undo
deep clone() of a big Vec/HashMap
Structural sharing: clone is pointer+refcount; edits copy only the touched path
struct-of-arrays / ECS (hecs/slotmap)
Iterate one field over millions
Vec<BigStruct> (cache-thrash)
Columns are contiguous → SIMD-friendly, no padding waste
string/symbol interner (string-interner/lasso)
Compare/copy strings by u32
String clones, HashMap<String,_> keys
Intern once → Copy symbol; equality is integer compare
roaring
Dense/sparse integer sets, set algebra
HashSet<u32> for millions of ids
Compressed bitmap; AND/OR/cardinality are blazing and memory-tiny
Full per-structure tradeoffs, gotchas, and sourced benchmarks live in the four references.
Failure Modes (Novice vs Expert)
Reaching for Rc<RefCell<T>> to model a graph
Novice: "Nodes point at each other, so every node is Rc<RefCell<Node>> and edges are
Vec<Rc<RefCell<Node>>>." Then cycles leak, borrow_mut() panics at runtime, and threading
it means Arc<Mutex<_>> everywhere.
Expert: Put every node in one arena; edges are Copy keys (NodeKey). The arena owns
everything, so there is one owner and the borrow checker is satisfied trivially. Cycles are
just keys — no leak. A deleted node's stale key fails a generation check instead of dangling.
The Rust standard reference ("Too Many Linked Lists") reaches the same conclusion: safe
linked/graph structures want indices, not pointer webs.Detection: Rc<RefCell< or Arc<Mutex< appearing on a node type; .borrow_mut() in
graph traversal; Weak sprinkled to "fix" leaks.
Using plain petgraph::Graph and then deleting nodes
Novice: Stores NodeIndex values in their own structs, then calls remove_node — and
every index past the removed one silently shifts, corrupting all stored references.
Expert: If you delete, use StableGraph: it invalidates only the removed node's index,
never unrelated ones (it keeps a free list and tolerates gaps). Use plain Graph only when
the graph is build-once / append-only.
Detection: stored NodeIndex + any remove_node/remove_edge on a non-stable Graph.
Arc<Mutex<HashMap>> as the default concurrent map
Novice: One global mutex around a HashMap; every thread serializes on it.
Expert: Reach for dashmap (sharded locks) or, for read-mostly, arc-swap / an
RwLock. But know dashmap's gotcha: holding a Ref/RefMut locks that shard — taking a
second guard for a key on the same shard deadlocks. Keep guard lifetimes short.
Detection: Arc<Mutex<HashMap in a hot multi-thread path; long-lived dashmap guards.
SmallVec/ArrayVec as a reflex "optimization"
Novice: Swaps every Vec for SmallVec "for speed," adding unsafe deps and bloating
struct sizes (inline capacity is always in the struct, even when spilled).
Expert: Inline vectors win only where the collection is usually below the inline cap
and lives in a hot path or in a Vec<SmallVec<…>> (cache locality). Otherwise it is
premature optimization that grows the type. Measure first.
Detection: SmallVec in cold/startup code; huge inline N; no benchmark justifying it.
Lock-free by hand with raw atomics (and the ABA problem)
Novice: Builds a lock-free stack with AtomicPtr + CAS, frees popped nodes immediately.
A node freed and reallocated at the same address makes a stale CAS succeed (ABA), and
freeing while another thread holds the pointer is use-after-free.
Expert: Don't free immediately. Use crossbeam-epoch (epoch-based reclamation defers
frees until no thread can observe the pointer) or crossbeam-queue which already solved it.
Hand-rolled lock-free is a last resort, proven with Loom and Miri.
Detection: AtomicPtr + manual Box::from_raw/drop in a concurrent structure; no
epoch/hazard-pointer scheme; no Loom test.
String keys and clones where a symbol would do
Novice: HashMap<String, T> keyed by identifiers, cloning Strings to compare/store.
Expert: Intern once (lasso/string-interner) → a Copyu32 symbol. Equality becomes
an integer compare; storage drops from N copies to one. Pairs with arenas: nodes hold symbols.
Detection: repeated .to_string()/.clone() of the same identifiers; HashMap<String,_>
in a hot lookup.
Quality Gates
□ No Rc<RefCell<…>> / Arc<Mutex<…>> on a NODE type — relationships are arena keys/indices
□ Deletable graph uses StableGraph (or an arena), never plain Graph with stored indices
□ Generational index (slotmap/generational-arena) used wherever slots are reused — no bare usize
□ Hasher choice is deliberate: SipHash default kept ONLY if untrusted keys; else fxhash/ahash with a note
□ Map choice justified: HashMap vs BTreeMap (ordered/range) vs IndexMap (insertion order) — see ref 04
□ smallvec/arrayvec presence is backed by a benchmark and a "usually < N" claim, not reflex
□ Concurrent map is dashmap/RwLock/arc-swap with short guard lifetimes — not one global Mutex
□ Any hand-rolled lock-free code has epoch/hazard reclamation + Loom + Miri; otherwise use crossbeam
□ Cheap-clone snapshots use Cow / im / rpds (structural sharing), not deep clone()
□ examples/ compile: `cargo build` in examples/ is green (slotmap graph + crossbeam pipeline)
□ Every structural claim cites a real crate doc / benchmark (see References)
□ python3 scripts/validate_skill.py → 0 errors
□ node scripts/structure_choice_audit.mjs --input <plan>.json → pass:true (see Structure-Choice Audit)
Worked Example: a Mutable Graph Without Rc<RefCell>
Problem. A dependency graph where nodes carry data, edges are added/removed at runtime,
and we traverse it. The reflex is Rc<RefCell<Node>> with Vec<Rc<…>> edges — which leaks
on cycles and panics on overlapping borrows.
Structure choice. A slotmap keyed by NodeKey. The slotmap owns every node; edges
are Vec<NodeKey> (just Copy keys). Ownership is trivial — one owner, the map. Deletion is
safe: a stale NodeKey fails the generation check and returns None instead of dangling.
use slotmap::{SlotMap, new_key_type};
new_key_type! { structNodeKey; }
structNode { name: String, edges: Vec<NodeKey> }
fnmain() {
letmut g: SlotMap<NodeKey, Node> = SlotMap::with_key();
leta = g.insert(Node { name: "build".into(), edges: vec![] });
letb = g.insert(Node { name: "test".into(), edges: vec![] });
g[a].edges.push(b); // edge a -> b, no Rc, no RefCell// Delete a node; b's key is unaffected, a's key now reads as None.
g.remove(a);
assert!(g.get(a).is_none()); // stale key detected by generation, not a crashassert!(g.get(b).is_some());
}
No Rc, no RefCell, no Weak, no unsafe in your code, no borrow panics, no cycle
leak. The full runnable version (with traversal and a secondary map for per-node metadata)
is examples/slotmap_graph.rs; a lock-free producer/consumer pipeline is
examples/crossbeam_pipeline.rs. Both compile under examples/Cargo.toml.
When this choice is wrong: if you actually need Dijkstra / SCC / topological sort, don't
re-implement them on the slotmap — hand the graph to petgraph (StableGraph if you delete).
If the graph is build-once and never mutated (an AST), typed-arena (&'arena Node) or
id-arena is even simpler. See references/01-arenas-and-graphs.md.
Structure-Choice Audit
scripts/validate_skill.py self-checks this skill's own files (frontmatter, references,
examples). It does not check whether a user's structure choice actually follows the thesis
above. For that, run scripts/structure_choice_audit.mjs against a structure-choice-plan
matching schemas/structure-plan.schema.json. It encodes this skill's Quality Gates as
deterministic checks over each modeled relationship — no keyword matching, only structured
fields (shape, usesRcRefCellOnNode, deletableGraphUsesStableGraph, generationalIndex,
smallvecJustifiedByBench, concurrentMap, handRolledLockFree, cheapCloneUsesPersistent,
hasherDeliberate):
examples/sample-input.json is a plan where every relationship already follows the thesis
(arena keys, StableGraph, generational indices, dashmap, a benchmarked smallvec, a
persistent shared snapshot, a deliberate hasher) and returns pass: true. A plan that models a
graph as Rc<RefCell<Node>> with a global-Mutex-guarded map returns pass: false with
critical/high findings pointing at rc-refcell-on-node and arc-mutex-hashmap-default.
References
File
Consult when
references/01-arenas-and-graphs.md
Arena/generational-index deep dive, slotmap vs generational-arena vs id-arena vs typed-arena, petgraph & StableGraph, Rc/Arc + Weak, intrusive-collections, the "Too Many Linked Lists" lesson
references/02-concurrent-and-lockfree.md
crossbeam (channel/epoch/queue) vs flume vs std mpsc, dashmap, atomics & memory ordering, the ABA problem, epoch reclamation, Loom/Miri verification
BTreeMap vs HashMap vs hashbrown vs fxhash/ahash vs IndexMap, hasher security (SipHash/HashDoS), when ordered/range/insertion-order matters
Examples
File
Walks through
examples/slotmap_graph.rs
A mutable, deletable graph with slotmap + a secondary map — the no-Rc<RefCell> pattern, with traversal
examples/crossbeam_pipeline.rs
A bounded multi-stage crossbeam-channel pipeline (MPMC), scoped threads, graceful shutdown
examples/Cargo.toml
Pins the exact crate versions both examples compile against
examples/sample-input.json
A structure-choice-plan where every relationship follows the thesis — scripts/structure_choice_audit.mjs --input examples/sample-input.json returns pass: true
Self-check: frontmatter, required references/examples, mermaid present, SKILL.md line budget, example Cargo.toml sanity. Run python3 scripts/validate_skill.py from the skill directory.
Domain auditor: checks a user's structure-choice-plan JSON against this skill's Quality Gates (arena vs Rc<RefCell>, StableGraph, generational indices, concurrent map, hand-rolled lock-free reclamation/Loom, persistent snapshots, deliberate hashers). Run node scripts/structure_choice_audit.mjs --input <plan>.json.
Interface
UI/catalog metadata for this first-party skill lives in agents/openai.yaml (display name,
short description, recommended context, and quality_gates). Update it alongside the skill
purpose so chips and skill lists stay accurate.
Skill Bundle Index
Every file in this skill, and when to open it. Auto-generated; run scripts/index_references.py --fix.
references/01-arenas-and-graphs.md — 01 — Arenas, Generational Indices & Graphs — > The idiomatic Rust answer to "how do I model a graph/tree without fighting the borrow > checker" is almost never Rc<RefCell<T>>.
references/02-concurrent-and-lockfree.md — 02 — Concurrent & Lock-Free Structures — > The throughline holds across threads too: the right structure makes sharing trivial.
references/03-small-and-cache-friendly.md — 03 — Small, Inline & Cache-Friendly Structures — > These structures win by respecting the memory hierarchy: keep small things on the stack / > inline, keep iterated things contiguous, and m
references/04-choosing-a-map.md — 04 — Choosing a Map: HashMap vs BTreeMap vs hashbrown vs fxhash/ahash vs IndexMap — > Two independent axes: container (hash table vs ordered tree vs insertion-ordered) and > hasher (security vs speed).
references/INDEX.md — References — rust-data-structures-advanced — SKILL.md points here; read only the file the decision in front of you needs.
