stn::hive

Introduction

This is an implementation of the hive container which is part of C++26. The hive container in simple terms is a linked list of arrays ("blocks"). Arbitrary elements can be erased without moving other elements while their freed positions in memory can be reused through later insertions.

For more details and a complete description see here.

Implementation

I used a common free-list for all blocks that can be accessed from within the blocks through an additional array of pointers corresponding to the starting position of the free-list elements. This entails a relatively large memory overhead, but allows for deletion at constant time. My implementation uses the low-complexity-jump-counting-pattern as described in the linked document.

This means that insertion, deletion and iteration all work in (amortized) constant time!

My implementation differs from the description of std::hive. It does not allow any moving of elements and requires the user to manually delete empty blocks by calling discard_emtpy().

I recommend using the for_each() and erase_if() methods instead of iterating with the provided iterators for improved performance achieved by using fewer branches.

Requirements

• C++17 compiler
• new, delete, std::swap and std::forward
• CMake (only for the tests)
• Google Test (only for the tests)
• Doxygen (only for the reference)

Usage

The entire library is contained within hive.hpp. Including it anywhere is sufficient.

Example:

// example.cpp
#include "hive.hpp"

#include <iostream>

struct S
{
    int a, b;

    S(int a, int b)
    : a(a)
    , b(b)
    {}
};

int
main()
{
    stn::hive<S> h;

    h.emplace(1, 2);

    auto del = h.emplace(3, 4);

    h.emplace(5, 6);

    h.erase(del);

    int sum = 0;

    h.for_each([&sum](const S& s)
    {
        sum += s.a + s.b;
    });

    std::cerr << sum << std::endl; // prints "14"
}

Testing

Compiling the tests:

$ mkdir build
$ cd build
$ cmake ..
$ make

Running them:

$ ./test/test

Reference

A complete reference can be generated using doxygen:

$ doxygen Doxyfile

The reference can now be accessed starting at html/index.html.

License

See COPYING.txt

---

(c)2025 Steffen Neumann