genmap

A Rust crate for a generational map, handle map, whatever you want to call it. Whatever it is, this is a random-access data structure that stores an unordered bag of items and gives you a handle for each specific item you insert. Looking things up by is O(1) -- the backing storage is just a Vec -- and items can be removed as well, which is also O(1). Handles are small (two usize's) and easy to copy, similar to a slice.

This is useful for various things: managing lots of uniform things with shared ownership (such as video game resources), interning strings, that sort of thing. Essentially you get handles to items with runtime-checked memory safety; you can get an item from the map using the handle, since it's basically just an array index. The trick is that you can safely remove items from the map as well, and unlike using array indices, a handle to an item that has been removed is invalid and trying to use it will fail at runtime, even if the storage the item occupied has been reused.

In practice this is not unrelated to Rc, it's just that Rc does the accounting of memory on cloning the Rc, and this does it on "dereferencing" by looking up an object's handle. Referencing counting, threading garbage collection and this sort of map are all different methods of achieving the same thing (checking for memory safety at runtime) with different tradeoffs.

Limitations

Other things like this: