[devbug]

A similar data-structure that is also very useful uses sparse-dense arrays but encodes a free-list in the unused memory. It's an ideal data structure if your access patterns are sporadic reads/writes bookmarked by frequent complete iterations of the dense array. You can insert and remove (swap 'n' pop) in O(1) and iterate in O(n) without polluting your cache and skipping over empty slots.

It's frequently used in Entity-Component Systems (ECS) which introduce safety by associating a counter with each entry in the sparse array (usually called a "generation") and incrementing them on deletion. You can also verify cross-linkage between the sparse and dense arrays like the data structure described in the article, but that comes at the cost of another indirection and fetch from memory.

[gpderetta]

Is this related to std::hive [1] as proposed for next C++ standard?

[1] https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2023/p04...

[devbug]

At a quick glance, this is very close. However, the proposal goes through several contortions to maintain pointer stability. If you preallocate sufficient storage for your worst case (which can be unmapped virtual memory) then it makes implementation a lot simpler.

Neat that the committee is looking to introduce it. Too bad we eschew the STL (and even CRT) in games.

[mandarax8]

This sounds like just what I need for a project, any idea where I could find more info on this or how its called?

[orlp]

In Rust there's my crate slotmap, the above described design matches the DenseSlotMap type. It's also often called a generational arena.

[devbug]

There’s some articles floating around that touch on the idea. Bitsquid comes to mind. [1]

To give a slightly more detailed description, you allocate two arrays of the extents. One is the dense array of whatever type, say T, and the other is the sparse array of 32 bit or 64 bit integers. The sparse array stores indices into the dense array for extant objects. However, for extinct objects, the indices instead point to the sparse array itself to encode a free-list.

To insert, in O(1), you check the free-list for an unused slot. If there is none, then you grow the sparse array (increment a counter) and use the newly introduced slot. Then you insert (or construct in place) your object at the end of the dense array. Finally, you map that slot in the sparse array to the end of the dense array.

To delete, in O(1), you swap the object you wish to delete with the last in the dense array and decrement the counter (swap and pop). Then you add the index in the sparse array to the free-list. You’ll need to know the index assigned to the object you swapped with to do this, which can either be stored on the object itself or by introducing another array the maintains an inverse mapping.

To iterate, you can treat the dense array like any other array.

This scheme poses some challenges:

- You lose pointer stability because you are relocating your objects. You must access them through indices. If you can defer your deletions, say to a frame boundary, you assume your pointers are stable.

- Indices, without further work, are not safe. They are just as safe as pointers. Usually you don’t expect more than N objects, so you can use log2(N) bits for the forward and reverse mappings between sparse and dense arrays and then use the leftover bits to identify stale indices. You can, and should, encapsulate this in a type-safe handle system. [2][3]

- High churn can cause index invalidation to fail (if you wrap a counter) and performs worse than other data structures.

- “Swap and pop” requires T to be trivially copyable, or ideally, trivially relocatable.

It’s also worth mentioning that you can reorder the dense array to maintain custom invariants. This is really useful if you have dependencies between objects and want to iterate in order.[4]

[1]: http://bitsquid.blogspot.com/2014/08/building-data-oriented-...

[2]: https://floooh.github.io/2018/06/17/handles-vs-pointers.html

[3]: You usually can use 24 bits for index and 8 bits for a discriminator (counter) in games. Handles (that you pass around) can be wider to exploit register widths and increase safety, since you have 32 bits for further runtime checks.

[4]: By doing more work at insertion and deletion, a constant factor on O(1), you can save work on iteration or updates, a constant factor on O(n). A great example of this being a worthwhile optimization is for scene graphs or transform hierarchies. If you partially order by depth in the hierarchy, you can guarantee correct computation without chasing indexes or pointers. If you maintain additional information about boundaries, you can trivially parallelize computation of transforms or reduce redundant work.