Consider STL's unordered_map. The same template class is used for both hashtables that are generated at runtime, and hashtables comprised of compile-time constant values. While recent versions of C++ add constexpr support it does not extend to more complex operations involving the free-store, consequently building a hashtable from compile-time constants must still happen at runtime, making it just as expensive as building any other hashtable at runtime.
Ideally, a perfect compiler would see this and pre-evaluate the hashtable construction at compile-time and embed it directly within the program.
It got me thinking about retrocomputing and microcontrollers which would conceivably have their software written in C or C++ given the development cost of assembly: these environments often have limited RAM but plenty of ROM, and those in-memory data structures (such as an unordered_map) certainly could be pre-generated and persisted to ROM all at compile-time.
As mentioned, the C++ language does not support this for non-trivial constexpr. I understand you could hack this together assuming you can base your complex data-structure on an array-type or reduce it down to a constexpr - or write it all in assembly and manually setting each byte of the structure in a hex-editor and hope it matches the compiler's representation of your struct types (for example).
How is it done today then? And how was it done in the days of 16-bit and 32-bit games consoles where RAM and CPU cycles were at a premium? I'm especially keen to learn about ROM cartridge-based games where the structures are immediately accessible as raw memory.
In C++ microcontroller systems, all constructors of objects with static storage duration are called during boot-up, around the point where .data and .bss etc segments are initialized, before main() is called. This is one of several reasons why C++ tend to be unsuitable for such systems - it actually executes application code during the start-up phase.
The kind of applications you mention, like old video games, most likely had tables pre-calculated and written in ROM. I doubt that C++ was used much for such games, or if it was, they used a restricted sub-set of the language.