$ show mattreecebentley/plf_colony
This repository contains `plf::colony`, a high-performance, single-header C++ container library that provides an unordered data structure with fast iteration, insertion, and erasure while maintaining pointer/iterator/reference validity to non-erased elements. It is implemented as a template class in `plf_colony.h`, supported by `plf_tools.h` which provides compiler feature detection macros, utility functions, and allocator-aware helpers. The container uses a novel skipfield-based memory management technique (low-complexity jump-counting pattern) to achieve O(1) amortized insertion and erasure, and O(n) iteration with minimal overhead. It supports C++98 through C++23, with extensive compile-time feature detection and conditional compilation. The codebase is exceptionally well-crafted, demonstrating advanced template metaprogramming, low-level memory optimization, and careful handling of allocator traits, exception safety, and trivial type optimizations. The test suite (`plf_colony_test_suite.cpp`) is comprehensive, covering correctness, edge cases, fuzz testing, and exception recovery. The repository is a standalone library intended for reuse in any C++ project requiring a flexible, high-performance container with stable iterators.
The LLM identified 3 files worth highlighting for reuse:
The core header defining the `plf::colony` template class. It implements an unordered container using a linked list of memory groups, each with a skipfield for fast iteration over non-erased elements and a free list for reusing erased element slots. The design ensures pointer/iterator/reference validity to non-erased elements after insertions and erasures. The implementation is highly optimized, using compile-time feature detection to adapt to different C++ standards, allocator-aware memory management, and trivial type optimizations. This component is the primary reusable asset of the repository.
A utility header providing compiler feature detection macros (e.g., PLF_MOVE_SEMANTICS_SUPPORT, PLF_CPP20_SUPPORT), custom implementations of standard library utilities for pre-C++11 compatibility (e.g., `enable_if`, `conditional`, `less`, `equal_to`), allocator-aware construction/destruction/allocation macros, and helper functions like `pointer_cast`, `void_cast`, and `make_move_iterator`. It also includes optional bit manipulation tools (`popcount`, `countr_zero`, etc.) and uninitialized memory operations. This header is designed to be reusable across multiple PLF library components and can be extracted for use in other projects requiring portable C++ feature detection and allocator support.
The `colony_data` struct and `data()` member function provide a mechanism to export the internal memory layout of the colony for external iteration or serialization. The struct contains arrays of pointers to element memory blocks, bitfields indicating active elements, and block capacities. This pattern is reusable for any container that wants to expose its raw memory layout in a structured way, enabling efficient bulk operations or integration with other libraries.