Is there a modern C++ alternative to flexible array members for variable-length struct tails?
Building a cache-optimized skip list where nodes have a variable number of forward pointers depending on their level (determined probabilistically at insertion). My naive approach was `std::array<Node*, MAX_LEVEL>` but that wastes memory since a level-1 node still allocates 16 pointer slots, most of which are nullptr. At scale this killed cache density significantly.
Currently using a C flexible array member:
struct Node {
K key;
V value;
int level;
Node* forward[]; // flexible array member
};
// allocate with extra space for forward pointers
void* mem = pool.allocate(sizeof(Node) + lvl * sizeof(Node*));
Node* n = new (mem) Node(k, v, lvl);
This works great. one contiguous allocation, forward pointers live immediately after the struct, no extra cache misses during traversal. my benchmarks show meaningful wins over std::map at 250K+ elements largely due to this cache density improvement by around 30%-40% or so.
This seems sort of messy though, and I was looking for a modern C++ alternative
I looked at std::span but it still needs a separate allocation for the pointer slots and adds 16 bytes of metadata per node. std::array requires compile-time size. std::inplace_vector (C++23) also needs a compile-time max.
Is the flexible array member still the only real tool for this pattern in modern C++? Is there something cleaner I'm missing, or is this just a gap in the language?
Using C++23, GCC, single-threaded for now.