C++26: std::hive

In a recent article on std::inplace_vector, I mentioned that C++26 is generous with new containers. Here’s the other one: std::hive.

Consider a game engine managing thousands of entities. Each entity is stored in a container, and other subsystems hold pointers to those entities. When an entity is destroyed, you erase it from the container. With std::vector, every element after the erased one shifts, invalidating every pointer. With std::list, pointers survive but cache performance suffers.

std::hive gives you both: stable pointers and iterators that survive insertions and erasures, O(1) amortized insertion and erasure, and good cache locality thanks to contiguous memory blocks. It’s available in the new <hive> header, introduced by P0447R28. If the name sounds unfamiliar but the concept doesn’t, you may know it as plf::colony — the library it grew out of, renamed after 28 revisions and eight years of committee work.

Core aspects

The proposal (§V) defines three core aspects that together make a hive what it is:

1. Multiple memory blocks instead of one. Unlike std::vector, which stores everything in a single contiguous allocation, hive uses a collection of independently allocated blocks. This means insertions into a full container don’t trigger reallocation — existing pointers and iterators stay valid.

2. A skipfield for O(1) iteration past erased elements. Instead of shifting elements when you erase (like vector), hive marks slots as erased and uses a run-length-encoded skipfield to jump over them efficiently during iteration.

3. Erased-slot reuse for subsequent insertions. Freed slots are tracked and reused for new elements, which improves cache locality and reduces the number of block allocations over time.

Everything else — pointer stability, O(1) amortized insert/erase, unspecified insertion order, bidirectional (not random-access) iterators — follows from these three design choices.

The basics

1
2
3
4
5
6
7
8
9
10
11
12

#include <hive>

std::hive<int> h;
auto it1 = h.insert(10);
auto it2 = h.insert(20);
auto it3 = h.insert(30);

h.erase(it2);  // erases 20; it1 and it3 remain valid

// iteration skips the erased slot automatically
for (int x : h)
    std::cout << x << ' ';  // prints 10 30 (order may vary)

A few things to note right away:

• Insertion position is unspecified. hive may place a new element in any available slot — including one previously freed by an erasure. There is no push_back or push_front. (Remember design principle #3!)
• No random access. There is no operator[] or at(). Iterators are bidirectional.
• No container-level comparison. There is no operator== or <=> for the container itself, because element-wise comparison would be meaningless when insertion order is unspecified.

How it works

Following design principle #1, internally a hive is a linked list of independently allocated memory blocks. Each block contains a contiguous array of element slots and a parallel skipfield — a metadata array that tracks which slots are active and which are erased.

When you erase an element, its slot is marked in the skipfield and added to a free list. When you insert, the container reuses an erased slot if one is available, or appends to the end of the last block (allocating a new block if needed). Because blocks are never reallocated when the container grows, pointers and iterators to existing elements stay valid.

The skipfield is the clever part. It doesn’t store a boolean per slot — it stores the run length of consecutive erased slots. When an iterator advances, it reads the skipfield value and jumps over the entire erased run in one step. This gives O(1) amortized iteration without the branch misprediction problems that a boolean “is-alive” flag would cause.

Pointer and iterator stability

This is the headline feature. Surviving elements never move in memory after insertion or erasure of other elements:

1
2
3
4
5
6

std::hive<Entity> entities;
auto it = entities.insert(Entity{"player"});
Entity* ptr = &*it;

// thousands of insertions and erasures later...
assert(ptr == &*it);  // still valid, still points to the same Entity

This is what makes hive suitable for systems where multiple subsystems hold cross-references — game entities, event subscribers, connection pools, particle systems.

Block capacity limits

You can control the minimum and maximum number of elements per block:

1

std::hive<int> h(std::hive_limits(64, 4096));

Blocks start at the minimum size and grow (typically by doubling) up to the maximum. This lets you tune the trade-off between memory overhead per block and the number of blocks in the linked list. You can query and change these at runtime with block_capacity_limits() and reshape().

Hive-specific operations

Beyond the usual container operations, hive provides a few extras:

• sort() — sorts elements in-place (not required to be stable).
• unique() — removes consecutive duplicates (like std::unique but modifying the container directly).
• splice(hive&) — transfers all blocks from another hive in O(1). Pointers and iterators from the source remain valid and now refer to *this.
• get_iterator(const_pointer) — converts a pointer to an element back into an iterator.

How it compares

The simplest summary comes from Daniel Lemire’s benchmarks: “The std::hive data structure is not a faster vector. But it is a much better std::list”

Conclusion

std::hive fills a niche that game developers and systems programmers have been filling with custom containers for decades. If your problem involves frequent insertions and erasures with cross-references that must survive, and you don’t need random access or preserved insertion order, hive is the standard answer. It won’t replace std::vector for most use cases — but for the use cases it is designed for, nothing in the standard library has come close before.

Connect deeper

If you liked this article, please

• hit on the like button,
• subscribe to my newsletter
• and let's connect on Twitter!
• if you're preparing for a C++ quant/trading interview, check out GetCracked