A simplified, educational C++ reimplementation of the high-performance Colony (also known as plf::hive) data structure.
Colony is an unordered, block-based container designed for high-performance scenarios where elements are frequently inserted and removed. Unlike std::vector or std::list, it provides O(1) insertion, O(1) erasure, and iterator stability simultaneously.
- Iterator Stability: Iterators and pointers to elements remain valid for the entire lifetime of the element, regardless of insertions or erasures in the container.
- O(1) Performance: Both insertion and erasure are constant time operations.
- Cache Friendly: Elements are stored in contiguous memory blocks (Groups), offering better cache performance than a standard linked list.
- Zero Reallocations: The container grows by adding new blocks rather than reallocating existing ones, preventing "spikes" in memory usage/latency.
The container manages a linked list of Groups. Each Group contains:
- Slots: A union of the data and a doubly-linked free list pointers of freed space.
- Skipfield: An array used to track which slots are active, allowing iterators to "jump" over erased memory locations in O(1) or near-O(1) time.
#include "my_colony.hpp"
my_lib::Colony<int> colony;
// O(1) Insertion
auto it1 = colony.insert(10);
auto it2 = colony.insert(20);
// Iterators remain valid even after erasing other elements
colony.erase(it1);
// Iteration jumps over "holes" automatically
for (auto it = colony.begin(); it != colony.end(); ++it) {
std::cout << *it << std::endl; // Prints 20
}I benchmarked this implementation against std::vector and std::list with 1,000,000 elements (running on Ubuntu 24.04, GCC 13.3 -O3).
Exact compilation used: g++ -O3 -DNDEBUG benchmark.cpp -o benchmark
Because this involves manual ::operator new calls and placement-new, I verified the implementation with Valgrind to ensure no leaks or buffer overflows occur during the lifecycle of the container.
Exact command used: valgrind --leak-check=full \ --show-leak-kinds=all \ --track-origins=yes \ --verbose \ --log-file=valgrind-out.txt \ ./benchmark
All credit for the original logic, architecture, and the "Hive/Colony" concept is due to Matthew Bentley.
This repository is a simplified educational version based on the research and implementation found at:
- Original Source: plf_colony on GitHub
- Technical Documentation: plflib.org/colony.htm
This project acknowledges the authorship of Matthew Bentley. As a derivative/reimplementation of a work regulated under the zlib License, this software is provided 'as-is', without any express or implied warranty. See the original source for full license details.