This is embarrassing. I read "well known" and for some reason I misfired
and Googled the wrong implementation. Very sorry.

The code you actually linked me to is written at a high level of
abstraction and I just sent you the lowest level of abstraction I could
write. But you are right, it is the same algorithm.

I am using a power of 2 sized array for the handle table. That means the
index into the table can be found with (handle & mask). Where mask is
(capacity - 1). This allows me to just mask off the index and check the
handle found at that index. That allowed me to write a template
specialization where the mask can be a compile time constant for a
statically sized array. And a bitwise operation on a small constant makes
for cheap compact assembly. On 32-bit hardware I break even with the
reference implementation due to 64-bit emulation, but on 64-bit hardware it
looks like a compare gets shaved off, and I get a larger generation counter
out of the deal. The trade off is the size constraint.

As for the reverse mapping, I went and folded my reverse map into the
handle array. Once I decided to have more generation bits than 32 (again, I
am using all the bits in the 64-bit handle except the masked off index
bits) it made sense to have the additional free list index outside the
handle. (In hindsight, having seen your code, I could have packed the free
list in the index bits obviously, but that isn't what I shared with you.)
That left an alignment hole and I decided to put the backwards reference in
the hole. In an ideal world (one the reference code appears to check for)
the backwards reference would be in the same slot as the handle to the
value being erased (because it never moved) maintaining cache coherence.

What can I say, I just independently invented it. At least I ended up in
the right neighborhood.

> sg14::slot_map supports arbitrary (user-defined) `key_type`. There are unit
tests
<https://github.com/Quuxplusone/SG14/blob/master/test/slot_map_test.cpp#L17-L36>
 for that scenario (for values of "40–50" equal to 5).

Fair enough.

I think I have a slightly more optimal implementation, but I'd want
encouragement about moving forward before getting into a bake-off.

> (Merged to where? Whose GitHub?)

How unpopular do you want me to make myself on this list.

Can I unpack your view though. It sort of sounds like you are saying you
are happy to provide sloppy tools to sloppy programmers, because they don't
know better anyway. Meanwhile the elite can go read the white papers for
their CPU architectures and write bespoke solutions for them. Hmm. That
actually does sound like the C++ ecosystem.

I have been working on normal looking containers and algorithms that try
not to be able to do anything sloppy. In theory that would make sloppy
programmers (and sloppy AI) smarter. "You can't get there from here."

Regards,
Adrian


On Mon, Jul 13, 2026 at 8:05 PM Arthur O'Dwyer <arthur.j.odwyer_at_[hidden]>
wrote:

> On Mon, Jul 13, 2026 at 10:12 PM A Johnston <ajohnston54637_at_[hidden]>
> wrote:
>
>>
>> The details of that implementation are the opposite of what I was trying
>> to advocate for. slot_map uses sparse paged allocation with stable pointers
>> the same way std::hive does. My arguments about high frequency iteration
>> over std::hive apply the same w.r.t. slot_map. I would like a dense
>> non-paged array of values
>>
>
> That's what template parameter `Container` is for, and it defaults to
> `std::vector`, which *is* a dense (in fact, contiguous) array of values.
> The innards of sg14::slot_map
> <https://github.com/Quuxplusone/SG14/blob/master/include/sg14/slot_map.h#L410-L414>
> are just three std::vectors.
> `this->reverse_map_` and `this->values_` both obey the invariant that
> their `size()` is always equal to `this->size()` (i.e., they contain no
> irrelevant elements).
> Your `m_values_` is my `values_`; your `m_slots_` is my `slots_` +
> `reverse_map_` AoS <https://en.wikipedia.org/wiki/AoS_and_SoA>'ed
> together. Your `m_mask_` is the part I don't understand at the moment.
>
>
>> and the ability for references held by other languages to be broken
>> without RAII.
>>
>
> That's what the template parameter `Key` is for, right? (In
> sg14::slot_map, `Key` defaults to `pair<unsigned, unsigned>`, where the
> first element of the pair is the index and the second element is the
> generation counter.) The fact that `insert` returns a `key_type` (your
> `hxhandle_t`), rather than an `iterator`, is what makes the thing a
> slot-map instead of an ordinary std::map or std::flat_map.
>
>
>> I also proposed a 40-50 bit "generation" counter (even on 32-bits as
>> compared to 10) before the handle id wraps. That is far larger than slot_map
>> as I didn't want to be responsible for causing data corruption at scale.
>>
>
> sg14::slot_map supports arbitrary (user-defined) `key_type`. There are unit
> tests
> <https://github.com/Quuxplusone/SG14/blob/master/test/slot_map_test.cpp#L17-L36>
> for that scenario (for values of "40–50" equal to 5).
>
>
>> In my mind the question is as much about the kind of language C++ is
>> trying to be. I have been "writing the world from scratch" in C++ for 20
>> years. And maybe we like it that way. Other languages offer you a soup to
>> nuts experience and all I would be doing right now is submitting a pull
>> request on GitHub to get this merged.
>>
>
> (Merged to where? Whose GitHub?)
>
> In this case I am talking about 400 LOC so far
>>
>
> Coincidentally, <sg14/slot_map.h> is also about 400 LOC. :) The unit tests
> are longer than the facility itself.
>
> –Arthur
>
>>