调整 unordered_set 的大小如何影响性能？

Question

据我所知，调整数组大小（例如需要调整数组大小的向量上的push_back）的复杂度为O(n)。如果是这种情况，这是否适用于在 unordered_set 中插入？调整内部数组的大小是否会使插入操作复杂度为 O(n)？在插入元素之前调整大小是否会降低时间复杂度，因为不需要复制任何数据？最后，我相信调整大小不需要重新调整。它是否正确？如果是的话，怎么办？

Answer 1

根据cppreference关于

std::unordered_set<>::insert()

：

如果操作后新的元素数量大于旧的元素数量

max_load_factor() * bucket_count()

发生重新哈希。
如果发生重新散列（由于插入），所有迭代器和引用都会失效。否则（不重新散列），迭代器和引用不会失效。 如果插入成功，则在节点句柄中获取的元素的指针和引用将失效，而在提取该元素之前获取的指针和引用将变得有效。 （自 C++17 起）

^强调我的

所以是的，当您插入新元素时可能会发生重新哈希。

对于复杂性，文档也回答了这个问题：

复杂性

1-4) 平均情况：O(1)，最坏情况 O(size())
5-6) 平均情况：O(N)，其中 N 是要插入的元素数量。最坏情况：O(N*size()+N)
7-8) 平均情况：O(1)，最坏情况 O(size())

^强调我的

当您有疑问时，请务必参考适当的文档，它通常会提供我们需要的答案。