Indices as handles: the generational arena

Build the data structure real Rust codebases use instead of Rc<RefCell<_>>.

pub fn simulate(ops: Vec<String>) -> Vec<i64>

An Arena owns slots: Vec<Option<i64>>, generations: Vec<u32> and a free: Vec<usize> list of reusable slot indices. A Handle is { slot: usize, generation: u32 } — two plain integers, Copy, no pointer anywhere.

Interpret the script. <n> always means the n-th handle ever issued, counting from zero.

The case that decides everything: insert, remove, insert, then get on the first handle. The second insert reuses the slot. The first handle still points at that slot. It must return -1.

Why not Rc<RefCell<Node>>

You have now built two graphs with shared ownership, watched one leak, fixed it with Weak, and paid for all of it with runtime borrow checks. Here is what compilers, ECS game engines, IDE backends and most serious Rust codebases actually do instead:

Put every node in one Vec and refer to nodes by index.

Everything the borrow checker was fighting you about disappears, because there are no references between nodes at all. A node “pointing at” another node is an integer. Integers are Copy, Send, 'static, serialisable, and free to duplicate. The arena owns everything and drops everything at once. There are no cycles in the ownership graph — the data can be as cyclic as you like, because the cycles are made of numbers.

It is also faster, and not marginally: nodes are contiguous, so traversal is cache-friendly and prefetchable, and there is one allocation instead of one per node.

The cost, stated honestly

This is not free, and pretending otherwise is how people get burned.

An index is not checked for validity. You have re-created dangling pointers as logic bugs.

Nothing stops you using an index after the thing it named was removed. Nothing stops you using an index from arena A on arena B. The compiler that spent ten items protecting you from exactly this class of mistake has no idea these numbers mean anything. And the failure is worse than a dangling pointer in one respect: a freed slot gets reused, so a stale index silently reads somebody else’s data rather than crashing.

The generation counter

The fix is one extra integer, and it is genuinely elegant.

Give every slot a generation counter, starting at zero. Every time a slot is freed, bump it. Make a handle carry the generation it was issued under. Then a lookup checks two things:

if handle.slot >= self.slots.len() || self.generations[handle.slot] != handle.generation {
    return None;      // stale
}

One integer compare, and use-after-free detection is back. A handle to a slot that has since been recycled no longer matches, so it reads as invalid rather than as somebody else’s data. That is the entire idea behind the slotmap crate and behind the entity IDs in every ECS engine you have heard of, and you can implement it in twenty lines of pure std.

Build it in two passes if it helps. First make a plain-index arena and watch the stale-handle case fail — that is what the starter is. Then add the generation check and watch it pass. Without that one test case, this problem grades a plain Vec.

Generation overflow is a real design question — a u32 wraps after four billion removals of one slot, and then a very old handle becomes valid again. Real implementations use a u64, or a NonZeroU32 so that “generation zero” can mean “never issued”. Worth knowing about; not worth testing.

Two Rust details in the starter

Handle must be Copy. It is two integers; passing one should not move it. The starter derives only Clone, and the first thing that breaks is a closure that binds by value:

error[E0507]: cannot move out of a shared reference

Ask why it should be Copy before you add the derive. A handle is a value like an integer, not a resource like a Box — no ownership, no destructor, nothing to be careful with. That is precisely the signal Copy sends, and a handle that was Clone-only would make every call site noisy for no reason.

gen is a reserved keyword in edition 2024. You will see it in older arena code, and it will not compile here — the identifier is reserved for generator blocks. Call the field generation (or write r#gen, which nobody should).

And the lint that is not helping you

Clippy’s indexing_slicing flags self.slots[i] and asks for .get(i), because indexing panics on an out-of-range index. It is allow-by-default, so it will not fire here and the gate will pass code full of arena[id].

Given that bounds-safety is the entire theme of this problem, that is worth sitting with. The gate is a floor. The generation check is not something a linter can ask you for, because it is a property of your design, and this is the level at which correctness stops being mechanical.