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;
};

API Reference

The table below covers every commonly used member function. All member functions on iterators into the hive remain valid across unrelated insertions and erasures; exceptions are noted explicitly.

Insertion and construction

Erasure

Iteration and access

Capacity and sizing

Ordered operations

Bulk transfer

Performance Characteristics

The table below compares std::hive against the other three workhorses for common operation categories. "Pointer stable" means that an element's address never changes as long as it is alive (not erased) and no sort/shrink_to_fit is called.

Key takeaway. std::hive sits between std::list (stable, slow iteration) and std::vector (fast iteration, unstable). When you need both iteration speed and pointer stability under frequent erasure — the classic game entity or simulation particle workload — std::hive wins.

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 — pointer still valid after unrelated erase

    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();

Iteration After Erasure

One of std::hive's most important properties is that erasing an element never invalidates iterators to other elements. This is fundamentally different from both std::vector and std::list:

• std::vector: any reallocation (triggered by insert) invalidates all iterators, pointers, and references. Even an insert that does not trigger reallocation invalidates iterators at or after the insertion point.
• std::list: only the iterator to the erased node is invalidated; all others remain valid. But there is no get_iterator from a raw pointer.
• std::hive: erasing element X leaves all iterators to other elements intact. An insertion may allocate a new block but never moves any existing element.

Erasing during iteration — the safe pattern

Because erase returns the next valid iterator, you can erase elements inside a range-for equivalent loop without undefined behaviour:

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

int main() {
    std::hive<int> h;
    for (int i = 0; i < 10; ++i) h.insert(i);

    // Erase all even numbers while iterating — safe with hive.
    auto it = h.begin();
    while (it != h.end()) {
        if (*it % 2 == 0)
            it = h.erase(it);  // erase returns the next valid iterator
        else
            ++it;
    }

    for (int v : h)
        std::print("{} ", v);  // 1 3 5 7 9 (order unspecified but correct)
}

This pattern is identical to the std::list erase-during-iteration idiom and works for std::hive for the same reason: the skipfield records the gap without moving any element.

The range-for loop is NOT safe for erase-during-iteration in any standard container. Always use a manual iterator loop as shown above.

Entity-Component System Example

A common pattern in game engines and simulations is a component store: a container holding one type of component for all active entities. The store must support adding and removing entities mid-frame without disrupting iteration in other systems. std::hive is purpose-built for this.

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

using EntityId = std::uint32_t;

// A component store backed by std::hive.
// Supports insert/erase while other systems iterate over live components.
template<typename Component>
class ComponentStore {
public:
    struct Entry {
        EntityId    entity;
        Component   data;
    };

    // Add a component for an entity; returns a stable pointer to it.
    Component* add(EntityId id, Component c) {
        auto it = store_.emplace(id, std::move(c));  // C++26 — O(1) amortized
        return &it->data;
    }

    // Remove a component via its stable pointer — O(1), no search.
    void remove(Component* ptr) {
        // get_iterator converts the raw pointer back to a hive iterator.
        auto entry_it = store_.get_iterator(
            reinterpret_cast<Entry*>(
                reinterpret_cast<char*>(ptr) - offsetof(Entry, data)));
        store_.erase(entry_it);  // O(1) skipfield mark
    }

    // Iterate over all live components; safe to call remove() for other
    // entities during the same loop without invalidating this iterator.
    void for_each(auto&& fn) {
        for (auto& entry : store_)
            fn(entry.entity, entry.data);
    }

    std::size_t size() const { return store_.size(); }

private:
    std::hive<Entry> store_;
};

// ---------------------------------------------------------------------------
// Simulation tick: physics system adds/removes rigid bodies mid-loop.
// ---------------------------------------------------------------------------
struct RigidBody { float mass; float velocity; };

int main() {
    ComponentStore<RigidBody> bodies;

    auto* a = bodies.add(1, {1.0f, 0.0f});
    auto* b = bodies.add(2, {2.0f, 5.0f});
    auto* c = bodies.add(3, {0.5f, -3.0f});

    // Physics tick: remove bodies that have come to rest.
    // Removing via raw pointer — O(1), no iterator invalidation for others.
    bodies.for_each([&](EntityId id, RigidBody& rb) {
        rb.velocity *= 0.9f;  // damping
        std::print("entity {} vel={:.3f}\n", id, rb.velocity);
    });

    bodies.remove(b);  // entity 2 removed; iterators to entity 1 and 3 intact

    std::print("remaining: {}\n", bodies.size());  // 2
}

The key property here: calling bodies.remove(b) during or between for_each calls does not invalidate any iterator held by any other system iterating over the same ComponentStore.

Skipfield and Block Limits Configuration

The hive_limits struct controls the minimum and maximum number of element slots in each block. Tuning these values trades allocation frequency against memory locality.

// C++26 — hive_limits struct
struct hive_limits {
    std::size_t min;  // minimum slots per block (default: implementation-defined, often 8)
    std::size_t max;  // maximum slots per block (default: implementation-defined, often 2048+)
};

You can supply limits at construction or change them later with reshape():

#include <hive>  // C++26

// Construction with custom limits.
std::hive<float> particles{std::hive_limits{256, 256}};
// Fixed block size of exactly 256 floats — predictable memory footprint.

// Change limits after construction; takes effect on the next block allocation.
particles.reshape(std::hive_limits{128, 512});

// Always validate user-supplied limits before applying them.
std::hive_limits candidate{16, 32};
if (particles.is_within_hard_limits(candidate))
    particles.reshape(candidate);
else
    // handle the error — reshape with out-of-range limits is UB, not an exception
    ;

Why tune block limits?

Predictable memory growth. With a fixed min == max, each block holds exactly that many elements. Memory grows in quantised steps, which simplifies capacity planning and makes memory-usage profiling easier.

NUMA locality. On non-uniform memory access systems, you want related objects allocated together. Setting a large min ensures a single block spans an entire NUMA-local region; the default growing strategy may spread objects across allocations that land on different NUMA nodes.

Reduce TLB pressure. Larger blocks mean fewer distinct virtual pages, reducing TLB thrash when iterating over many elements.

Smaller objects with high churn. If elements are tiny (4–8 bytes) and are erased at high rates, a small max reduces wasted skipfield memory per block and keeps empty blocks cheap to return to the OS.

// Example: particle system with tight block size control
// C++26
std::hive<Particle> particles{std::hive_limits{1024, 1024}};
particles.reserve(65536);  // 64 blocks of 1024 each, all allocated up-front

// After a wave of particle death:
particles.trim_capacity();  // free empty blocks, keep live data intact

sort() and Ordered Operations

std::hive provides an in-place sort() member that behaves like std::list::sort() but operates on block-stored elements. Understanding its iterator invalidation rules is critical.

sort() moves elements and therefore invalidates all pointers and references. Iterators, however, remain valid after sort — they are internally updated to track their elements' new positions.

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

int main() {
    std::hive<int> h;
    h.insert(5); h.insert(1); h.insert(3); h.insert(2); h.insert(4);

    int* raw_ptr = &*h.begin();  // raw pointer to the first element

    h.sort();  // in-place sort — O(n log n)
    // raw_ptr is NOW DANGLING — elements were moved during sort.
    // (Using raw_ptr here is undefined behaviour.)

    for (int v : h)
        std::print("{} ", v);  // 1 2 3 4 5
}

Contrast this with std::list::sort(), which sorts by relinking nodes — pointers remain valid. std::hive::sort() physically moves elements to eliminate skipfield gaps and produce a sorted, tightly-packed layout.

After sorting, calling unique() removes consecutive duplicates:

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

int main() {
    std::hive<int> h;
    for (int v : {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5})
        h.insert(v);

    h.sort();          // {1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9}
    auto removed = h.unique();   // erases consecutive duplicates
    std::print("removed {} duplicates\n", removed);  // 4

    for (int v : h)
        std::print("{} ", v);  // 1 2 3 4 5 6 9
}

Do not hold raw pointers across sort(). If you need stable pointers through a sort, copy elements to a std::vector, sort there, and repopulate.

PMR Allocator Usage

std::pmr::hive<T> uses a polymorphic_allocator backed by any memory_resource. This is especially useful in frame-based simulations where all allocations for a tick are bump-allocated from a monotonic buffer and then discarded as a unit:

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

struct Projectile {
    float x, y, z;
    float speed;
};

// Per-frame arena: 1 MiB of stack storage.
std::array<std::byte, 1024 * 1024> frame_buf;

void simulate_frame() {
    // monotonic_buffer_resource: bump-allocates; cannot free individual blocks.
    std::pmr::monotonic_buffer_resource mbr{
        frame_buf.data(), frame_buf.size()};

    // All hive block allocations come from the arena — zero heap traffic.
    std::pmr::hive<Projectile> projectiles{&mbr};  // C++26

    projectiles.emplace(0.0f, 0.0f, 0.0f, 300.0f);
    projectiles.emplace(5.0f, 0.0f, 0.0f, 280.0f);

    for (auto& p : projectiles) {
        p.x += p.speed * 0.016f;  // advance by ~16 ms
        std::print("proj at ({:.1f}, {:.1f})\n", p.x, p.y);
    }

    // At end of scope: mbr destructor releases the entire 1 MiB in one call.
    // No individual element destructors need to free allocator memory.
}

int main() {
    simulate_frame();
}

PMR hive is ideal for frame-scoped or request-scoped data where you want the allocation efficiency of arena allocation but the ergonomics of a standard container. The monotonic resource eliminates allocator lock contention in multi-threaded renderers that give each thread its own buffer.

For longer-lived objects that must survive beyond a single arena, use std::pmr::unsynchronized_pool_resource or std::pmr::synchronized_pool_resource instead of monotonic_buffer_resource.

Comparison with plf::colony

std::hive is a direct standardisation of the plf::colony library, which has been available since C++11. If you are on C++11 through C++23, use plf::colony from its GitHub repository (https://github.com/mattreecebentley/plf_colony) as a drop-in predecessor.

Key differences

Migration from plf::colony to std::hive

The transition is largely mechanical:

// Before (C++11–23 with plf::colony)
#include "plf_colony.h"

plf::colony<Widget> widgets;
plf::colony<Widget>::iterator it = widgets.insert(Widget{42});
widgets.reshape(64, 512);  // positional min/max

// After (C++26 with std::hive)
#include <hive>  // C++26

std::hive<Widget> widgets;
std::hive<Widget>::iterator it = widgets.insert(Widget{42});
widgets.reshape(std::hive_limits{64, 512});  // named struct

The most common source-level change is wrapping the two reshape integers in a hive_limits struct. All iterator and pointer stability guarantees are identical between the two libraries.

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 undefined behaviour — not a thrown exception.

Do not hold raw pointers across sort(). Sort physically moves elements and invalidates all existing raw pointers and references. Iterators are the only handles that survive a sort call. If you need to keep raw pointers stable through a sort, you must use a different approach (e.g., sort indices or keys).

Standardise block limits across cooperating hives when using splice. If two hives that frequently exchange elements have incompatible block limits, every splice call degrades from O(1) to O(n). Agreeing on a shared hive_limits at design time preserves the O(1) bulk transfer guarantee.

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.

Calling reshape with out-of-hard-limit values. Unlike most standard containers that throw std::length_error, reshape with an invalid hive_limits produces undefined behaviour in most implementations. Always call is_within_hard_limits() first when limits come from user input or configuration.

Using std::hive when ordered access is required frequently. Hive has no operator[] and no random-access iterator. If your workload frequently requires the n-th element by position, std::vector or std::deque is more appropriate. Hive shines when you iterate over all elements and use stable pointers/iterators for individual access.

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
• plf::colony — predecessor library available for C++11–23; nearly identical API