Similar to the second approach, you can have better ergonomics and performance by using a memory arena library like slotmap. A doubly linked list implemented using slotmap: https://github.com/orlp/slotmap/blob/ce6e1e02bb2c2074d8d581e...
Slotmap is essentially the Vec + indices solution, while allowing memory to be reused. It is still completely safe, as it automatically versions each slot, and checks the version contained in the key when indexing.
For iteration however, there can be holes that need to be ignored, if the current number of elements in the slotmap is significantly lower than the the maximum capacity. If iteration needs to be very fast (for e.g. game engines) I do have a solution for that, which is the DenseSlotMap. It uses one extra layer of indirection for random access, but stores the actual data values contiguously in a vector, thus iteration is always fast.
E.g. to benchmark removals they used `container.remove(index)` for data structures that support indices but for slotmap they used `slotmap.remove(keys[index])` which unfairly adds another layer of indirection.
DenseSlotMap sort of can. It still can't reclaim the memory used by empty slots for the same reason (at a cost of 8 bytes per slot), but can reclaim the memory used by the actual elements stored.
So if you store 1 million items at one point in a DenseSlotMap, and then clear them all and then shrink to fit (which is actually missing from the API, but I'll fix that soon) you will waste 7.6 megabytes on the empty slots but nothing on the actual data that used to be stored.
1. The name isn't particularly catchy or descriptive. It is the correct name for the data structure, but not too many people know the data structure.
2. People don't even know what they're missing. It's not a very Google-able problem to begin with. Slotmap provides an interesting solution to (circular) ownership and safe allocator / weak pointer design problems, but people don't recognize that they're having them or that slotmap could help.
As an example of this, the doubly linked list example (https://github.com/orlp/slotmap/blob/master/examples/doubly_...) can safely remove nodes from the linked list given their handle, in O(1), even from the middle, completely safely and correctly, even in the presence of double deletions or ABA memory re-use. You can't replicate this with just pointers, without introducing heavy refcounting solutions.
My goal in the post was to avoid "just use this crate" approaches, because clearly there are dozens of crates that could help with this... even crates that implement BSTs :-) The goal was to look at the underlying implementation of such crates, and as the other comment pointed out it seemed like slotmap and others used approaches that mapped to one of the three I outlined in the post.
I very much appreciate this sentiment and it inspires me to actually think about blogging again. Thank you.