The solution to that is to either: 1) If you're gonna return pointers, don't use an allocation scheme that invalidates pointers in the implementation of map_t.

The solution to that is to either: 1) If you're gonna return pointers, don't use an allocation scheme that invalidates pointers in the implementation of map_t. 2) If you want to reallocate and move memory, don't return pointers, return abstracted handles/indices. Both of those are completely possible and not particularly unergonomic to do in C. If you need to enforce invariants, then enforce them, C does have enough abstraction level for that.