maintain O(1) lookups, the array of buckets also needs to be resized as the table size grows, requiring a 3x temporary memory requirement for moving the old bucket array (1x) to the newly allocated, larger (2x) array. In between the bucket array resizes, the default STL implementation memory usage grows at a constant rate as new values are added to the linked lists.</p>
<blockquote>
<p>Instead of having a separate linked list for each bucket, <em>std::unordered_map</em> implementations often use a single li