implement a version with stable iterators

[martinus]

robin_hood map has an option for stable iterators, that's currently not possible with unordered_dense.

One way to implement this might be be to be able to replace the underlying container with some kind of slotmap.

Slot map design

• a member for size

• one index array (same capacity as data array)

• one data array with stable references on insert (e.g. std::deque)

• index is split into two parts: first part until size(), contains indices into the data with actual content. second part after size contains unused indices

• data is not densely stored, there are empty unconstructed cells in it.

Insert: O(1) amortized.

Take the index after size, construct element in that location in data. Increase size by 1. When capacity is reached we know data is completely full. push back a new index with size and construct there.

Erase at location x: O(1)

1. Lookup in index[x] and destroy that element.
2. std::swap(index[x], index.back())
3. decrease size by one. Now we have one more entry in our free section (past the size)

Iterate

Needs a custom iterator that goes over the index and dereferences from there.

Open questions

• How to support both slotmap and std::vector?
• I probably can't use deque because I have to destroy the elements. I could use std::optional<Data> but that is huge unnecessary overhead.

[Philippe91]

To further dismiss the std::deque option: the performance is very dependent on the stl implementation (and probably the underlying chunk size). I found that with MSVC, the performance is surprisingly bad.

[martinus]

More thoughts:

• I don't need a full slotmap, the index is already in unordered_dense.
• I'd need to keep a freelist somewhere though. This could be done inline in the data array, using the memory of the destroyed objects. Then I only need one additional pointer to the start of the list.
• data can be somehing like the stable_vector (probably stripped down) which has quite fast access: https://gist.github.com/martinus/a5d1c5114cfd1930eec9b620a7803f7a

[Philippe91]

Yes, I made a similar container, precisely because std::deque was found to be slow. My primary interest was to prevent reallocation, in the context of acquiring random batches of data in real-time.

[Philippe91]

This is not too clear from your doc, but with segmented_map, we get stable buckets; that is, once inserted in the map, a key/value pair will never be moved, whatever mutation happens to the map (right?). In which case do we not have iterator stability, given this fact?

[martinus]

With segmented_map you'll get stable iterators & references on insert, but not on erase.

[Philippe91]

Thank you for your answer; it would be worth clarifying this in your documentation about segment_map.

[martinus]

Closing the issue as I won't have time to work on this