2 ms·
Sort of. For std::unordered_map there are two types of memory allocation, there's a table, of pointers, and then there are nodes, which themselves have a pointe
by tialaramex 3y ago
Sort of. For std::unordered_map there are two types of memory allocation, there's a table, of pointers, and then there are nodes, which themselves have a pointer to a next node if any, forming a "chain".
The table is indeed grown exponentially as you describe. If you tell std::unordered_map that you expect 10000 entries using reserve, it will calculate how big it would expect to grow a table for 10000 entries and make it that size immediately.
The nodes however are created when you insert data. Even though you called reserve, it is an allocation each time you insert to make space for the new node.
If you used a Swiss table (e.g. from Abseil) the reserve behaves more as a person might expect, it will allocate a data structure big enough to insert at least 10 000 entries successfully, and no further allocations are needed unless you keep going.