Experimental handle container in C++

Overview

For an overview of this library and the techniques used, check out the article Handle Lookup Container (Sparse Set).

Following on from c-handle-container, this library builds on the same ideas but supports a dynamic number of elements without a fixed capacity and is templated so arbitrary types can stored.

Note: This is an early draft, proof-of-concept experiment. There's probably bugs, oversights and problems I haven't yet thought of/ran into. Please treat as a reference implementation. YMMV 🙂

Excellent resources on the subject:

• Managing Decoupling Part 4 -- The ID Lookup Table - Niklas Gray (Twitter, GitHub)
• Managing Data Relationships - Noel Llopis (Twitter, GitHub)
• Handles are the better pointers - Andre Weissflog (FlohOfWoe, Floooh) (Twitter, GitHub)

More useful resources:

• Adventures in data-oriented design – Part 3b: Internal References
• Adventures in data-oriented design – Part 3c: External References
  • Stefan Reinalter (Twitter, GitHub)
• Using Uninitialized Memory for Fun and Profit - Russ Cox

Building

To build tests and benchmarks pass -DTHH_HANDLE_ENABLE_TEST and -DTHH_HANDLE_ENABLE_BENCH to CMake.

cmake -B build -DTHH_HANDLE_ENABLE_TEST=ON -DTHH_HANDLE_ENABLE_BENCH=ON

Note: Depending on the generator, use -DCMAKE_BUILD_TYPE=Release for the benchmarks (or build with --config Release if using a multi-config generator).

Note: -DBENCHMARK_ENABLE_TESTING=OFF is passed to CMake at configure time to ensure the Google Test dependency on Google Benchmark is not required (already set inside CMakeLists.txt).

Gotchas

The resolve function (added in the initial version of the library) was easy to use incorrectly due to the fact that if the internal vector had to grow and reallocate, any existing pointers would be invalidated (dangling).

This was unfortunately quite easy to do by mistake. A much better interface which makes this harder to do is provided by call. This accepts a handle and a callable object (a lambda taking an element as its only parameter) which is resolved internally and called. This makes it much harder to accidentally hold onto a pointer for too long (see the tests for examples).

Usage

Either drop the thh-handle-vector folder inside include/ into your project (and then just #include "thh-handle-vector/handle-vector.hpp") or use CMake's FetchContent command.

e.g.

# CMakeLists.txt
include(FetchContent)
FetchContent_Declare(
  thh-handle-vector
  GIT_REPOSITORY https://github.com/pr0g/cpp-handle-container.git
  GIT_TAG        <latest-commit>)
FetchContent_MakeAvailable(thh-handle-vector)
...
target_link_libraries(<your-project> <PRIVATE/PUBLIC> thh-handle-vector)

// .h/cpp file
#include "thh-handle-vector/handle-vector.hpp"