If I use std::unordered_map::reserve with the argument n, will inserting into the map be guaranteed to not cause a heap allocation so long as there are fewer than n elements inserted into the map?
1 Answers
No such guarantee appears to be in the standard.
Moreover if you look at an implementation - quoting the headers that come with gcc (<bits/hashtable.h>):
In terms of Standard containers the hashtable is like the aggregation of:
std::forward_list<_Node>containing the elementsstd::vector<std::forward_list<_Node>::iterator>representing the buckets
reserve makes sure that you have the appropriate number of buckets, it sizes that vector appropriately. So there will be no more allocations for new buckets at least. But the buckets are internally linked lists and inserting an element into one has to allocate a new _Node.
So overall: no, even after reserve with the appropriate capacity an unordered map may (and in the case of gcc will) allocate heap memory.
Related