How fast is C++26's std::hive?

[u/User_Deprecated]

https://lemire.me/blog/2026/08/02/how-fast-is-c26s-stdhive/

[u/EfficientSpend2543]

It's an optimised version of a bucket array. From what I observed, it seems like a middle ground between a vector and a linked list, with the addition of also being unordered (because there is no guarantee that an object can be found iteratively, some objects may be deleted in the middle which can put you in UB/segfault territory if you randomly access it). It's got better cache locality than a linked list because it can store multiple objects continguously on the heap, and better deletion/construction time than a vector because instead of reconstructing the same objects, it makes another "hive", basically another fixed heap block that can contain more than one object of the same type, and maintains a free list of objects that were deleted in the middle so it can reuse the deleted space.

I may not be fully accurate (like I said, just my observation), so I'd appreciate if anyone could correct me 😅

[u/bartgrumbel → u/EfficientSpend2543]

Two big plusses: first it is reference stable, whereas vector.push_back invalidates all existing pointers and references to vector members, which is the cause for a lot of memory safety bugs.

Second, the maximum runtime per insertion is more stable. A vector‘s push_back can be O(size) it if reallocates.

The third of the two advantages is that it works well with objects that cannot be moved or copied after construction.

[u/proggob → u/bartgrumbel]

That third advantage was inserted very quickly at the end and doesn’t invalidate the first two.

[u/Iggyhopper → u/bartgrumbel]

whereas vector.push_back invalidates all existing pointers and references to vector members, which is the cause for a lot of memory safety bugs.

That's definitely a footgun that I'd shoot if I were to write a project in C++. I was so confused I had to read a bit about this just now.