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.
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.