I'm writing a shared library in C++ and have the (mostly educational) goal to have every bit of heap allocation done by the library to live in a single, contiguous block, allocated at initialization of a specific part of the library. I achieve this with a single malloc at the start, which implements two stacks (one large and non-poppable for persistent memory, and one with extra machinery as a secondary runtime stack) and a binary buddy system for semi-persistent data.
Given this self-imposed constraint, before this turns too much into an XY situation, I'll describe the problem I'm trying to solve. My library has these items that can have some properties, structs, say A and B. Instead of an OO approach with individual inheritance, I have more of an ECS-like flattening of the data. Items are just id's, and I bookkeep who has each property in separate arrays. So, if I have 5 items, maybe {1, 3, 4, 5} have property A and {2, 3, 4} have property B, the code might look something like:
struct A;
struct B;
int whoHasA[] = {1, 3, 4, 5, 0};
A propertyA[] = {A1, A3, A4, A5, A::null()};
int whoHasB[] = {2, 3, 4, 0};
B propertyB[] = {B2, B3, B4, B::null()};
These arrays can all be allocated following my constraints, by giving them a fixed size and "dynamically" changing the program-relevant size by null-termination, as exemplified in the arrays (I realize this is just an ad-hoc implementation of a sparse array. I like it because I know the sizes at the time of writing the program). Now, the functionality my library needs is as follows. I want my user to be able to create instances of items (up to some maximum number), and add/remove properties after the fact.
To that end, I want my user to refer to items by name instead of cumbersome id's. I then need to expose in my API the following functions
void CreateItem(const char* name); //Store item name in a registry
void GiveProperty(const char* name, A property); //Append item's id to whoHasA and property to propertyA
void GiveProperty(const char* name, B property); //Append item's id to whoHasB and property to propertyB
I need the names to be stored in memory since I want to expose similar functionality to scripting (currently Lua). The solution that comes to mind is some sort of associative map, with the strings as keys and item id's as values. I've been avoiding std::unordered_map due to its dynamic allocations on the map itself and with std::string as keys. Currently all I'm doing is defining a const char** itemNames that CreateItem writes to, and doing a basic linear search through them, comparing char by char on every entry. I haven't benchmarked it, and don't think it would be particularly troublesome, but I'm asking this question hoping for a more elegant solution that fits better and is (theoretically) more efficient.
A place to look (as a model) are file-based hashmaps. For one, putting everything in a file implies a single linear block (albeit on disk), and handling serialization of structures into that block. An implementation that uses mmap() will be yet closer to what I'm guessing you want to build.
You might want to look at Litwin's linear hash tables, which grow (a single hash block) incrementally.