当为unordered_set / unordered_map调用reserve（new_size）时 - 是否会导致分配新的桶数组？

Question

AFAIU（也许我错了），unordered_set/unordered_map 使用底层数组或向量作为存储桶，每个存储桶中有一个键（或键值）列表。 那么当我们想要更多的桶时，需要分配更大的数组并将桶移入其中吗？ IE。它的工作原理与 vector::reserve 类似吗？

（除了向量元素是使用移动构造函数移动的，这里指针是按照桶内列表的方式移动的）。

Answer 1

对于任何无序关联容器（如

std::unordered_set

）

a

，

a.reserve(n)

相当于：

a.rehash(ceil(n / a.max_load_factor()))

...这确保一旦重新哈希完成，

a.bucket_count() >= ceil(n / a.max_load_factor())

就是

true

。

换句话说，桶计数（可能）会增加，因此无需重新哈希，直到容器中存在超过

n

的唯一元素。

相比之下，

std::vector::reserve(n)

确保在向量的大小超过

n

之前，不会调整向量的大小。