std::hive

Overview

std::hive solves a problem that std::vector and std::list each solve only halfway: it delivers cache-friendly block allocation without paying the iterator-invalidation cost of contiguous containers, and it avoids the per-node allocation overhead of std::list.

Internally, a hive partitions its storage into a series of element blocks. Each block holds a contiguous array of element slots and a parallel skipfield — a compact bitfield that marks which slots are occupied. When an element is erased, its slot is marked free in the skipfield but the block is not immediately released; future insertions can reuse that slot. Iteration traverses occupied slots by consulting the skipfield, skipping over gaps in O(1) per step.

Block capacity grows by an implementation-defined factor (approximately 1.69×) up to a configurable maximum. Empty active blocks either return to a reserved pool or are deallocated. Calling reserve(n) pre-populates the reserved pool for n elements.

Because elements are never moved after insertion, all of the following hold regardless of other insertions or erasures:

• pointers to elements remain valid,
• references to elements remain valid,
• iterators to surviving elements remain valid.

This makes std::hive suitable for observer lists, entity-component stores, event queues, and any workload that mixes pointer-stable storage with high-frequency insert/erase.

std::hive satisfies Container, ReversibleContainer, and AllocatorAwareContainer. It deliberately omits operator== and operator!= (two elements in different orders are not meaningfully comparable since insertion order is unspecified).

A PMR alias is also provided:

// C++26
namespace pmr {
    template<class T>
    using hive = std::hive<T, std::pmr::polymorphic_allocator<T>>;
}

Feature-test macro: __cpp_lib_hive equals 202502L when the library support is present.

Syntax

#include <hive>  // C++26

template<
    class T,
    class Allocator = std::allocator<T>
> class hive;

Construction mirrors other sequence containers, with an additional hive_limits parameter for controlling element-block sizing:

// C++26
struct hive_limits {
    std::size_t min;
    std::size_t max;
};

Selected member functions unique to std::hive:

Examples

Basic insert/erase with stable iterators

#include <hive>   // C++26
#include <print>  // C++23

int main() {
    std::hive<int> h;

    auto it_42 = h.insert(42);  // returns iterator to inserted element
    auto it_7  = h.insert(7);
    auto it_99 = h.insert(99);

    // Pointer stability: take a raw pointer before erasing something else.
    int* p = &*it_42;

    h.erase(it_7);  // it_42 and it_99 remain valid; p still points to 42

    std::print("{}\n", *p);   // 42 — C++23

    for (int v : h)
        std::print("{} ", v);  // 42 99 (order unspecified, but stable)
}

get_iterator: pointer-to-iterator conversion

std::hive is the only standard container that supports converting a raw pointer back to a valid iterator. This enables O(1) erasure when the container is accessed via a pointer (e.g., from an ECS or an observer list):

#include <hive>  // C++26

struct Widget { int id; /* ... */ };

void remove_by_pointer(std::hive<Widget>& h, Widget* w) {
    // No linear search needed — hive validates and converts in O(1).
    h.erase(h.get_iterator(w));
}

Passing a pointer to an element that was already erased, or that belongs to a different container, is undefined behaviour.

splice for O(1) bulk transfer

#include <hive>  // C++26

std::hive<int> a, b;
for (int i = 0; i < 1000; ++i) a.insert(i);
for (int i = 1000; i < 2000; ++i) b.insert(i);

// When block limits are compatible, splice transfers ownership of
// b's blocks into a without touching individual elements.
a.splice(std::move(b));
// b is now empty; all iterators into b's former elements now refer into a.

reshape and reserve for known workloads

#include <hive>  // C++26

// Entity pool: expect ~10 000 entities; keep blocks between 512 and 4096.
std::hive<Entity> pool{std::hive_limits{512, 4096}};
pool.reserve(10'000);  // pre-allocate; no allocations during steady state

// Later, after a wave of deletions, release the empty reserved blocks.
pool.trim_capacity();

Best Practices

Prefer hive::insert() over positional insert. Unlike std::list, std::hive does not support inserting at a specific position. Insertion returns an iterator to the newly created element; save it if you need to erase that element later.

Tune block limits up front. The default limits are implementation-defined. If your element type is large or your working set size is predictable, pass hive_limits to the constructor and call reserve() to eliminate allocation jitter during the hot path.

Use get_iterator instead of std::find. When your architecture already passes raw pointers (e.g., observers, ECS component tables), get_iterator converts a pointer to an iterator in O(1) and then erasure is also O(1). A linear std::find over a hive wastes the skipfield advantage.

Call trim_capacity() after bulk deletion. Reserved blocks hold physical memory even when empty. In long-running processes where deletion waves are followed by quiet periods, trim_capacity() recovers that memory without disrupting remaining elements.

Validate custom limits before reshaping. Query block_capacity_hard_limits() or call is_within_hard_limits() before passing user-supplied limits to reshape; exceeding the hard limits results in erroneous, implementation-defined behaviour — not a thrown exception.

Common Pitfalls

Assuming iteration order equals insertion order. std::hive makes no such guarantee. If order matters, sort explicitly with hive::sort() or transfer elements to a std::vector first.

Using operator== to compare two hives. It is not defined; the container intentionally omits it. Two hives with the same elements in different slot arrangements are not meaningfully comparable without a sorted projection.

Calling get_iterator on an erased element. The result is undefined behaviour. The skipfield records that the slot is free, but the API cannot safely detect the misuse. If you hold a raw pointer and the element may have been erased, you need an out-of-band liveness flag.

Expecting splice to always be O(1). Splice is O(1) when the source hive's block limits fall within the destination's limits. If limits are incompatible, individual elements must be moved across blocks, making splice O(n). Standardise block limits across cooperating hives in performance- sensitive code.

Confusing shrink_to_fit with trim_capacity. shrink_to_fit is a non-binding hint that may consolidate fragmented blocks by reallocating and moving elements — it can invalidate iterators. trim_capacity only releases empty reserved blocks and never moves live elements, so iterators remain valid.

See Also

• std::list — doubly-linked list; stable iterators but no pointer-to-iterator conversion and higher per-element overhead
• std::deque — block-based but supports positional insert and provides random-access iterators at the cost of iterator invalidation on push_front/push_back
• std::pmr::hive — PMR alias for using std::hive with a polymorphic allocator
• hive_limits — helper struct controlling minimum and maximum element-block capacity