据我所知,调整数组大小(例如需要调整数组大小的向量上的push_back)的复杂度为O(n)。如果是这种情况,这是否适用于在 unordered_set 中插入?调整内部数组的大小是否会使插入操作复杂度为 O(n)?在插入元素之前调整大小是否会降低时间复杂度,因为不需要复制任何数据?最后,我相信调整大小不需要重新调整。它是否正确?如果是的话,怎么办?
根据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())
强调我的
当您有疑问时,请务必参考适当的文档,它通常会提供我们需要的答案。