c++ - 多重集、映射和哈希映射复杂性

Question

在以下情况下，我想知道 STL 多重集、映射和哈希映射类的 Big O 表示法的复杂性：

• 插入条目
• 访问条目
• 检索条目
• 比较条目

Answer 1

map、set、multimap 和 multiset

这些是使用红黑树（一种平衡二叉搜索树）实现的。它们具有以下渐近运行时间：

插入：O(log n)
查找：O(log n)
删除：O(log n)

hash_map、hash_set、hash_multimap 和 hash_multiset

这些是使用哈希表实现的。它们具有以下运行时：

插入：预期 O(1)，最坏情况 O(n)
查找：预期 O(1)，最坏情况 O(n)
删除：预期 O(1)，最坏情况 O(n)

如果您使用适当的哈希函数，您几乎永远不会看到最坏的情况，但请牢记这一点——请参阅Crosby 和 Wallach 的通过算法复杂性攻击拒绝服务的示例。

Answer 2

对于set、multiset、map、multimap，插入、删除和检索信息的时间复杂度为O(logn)，因为它们遵循平衡二叉树来构造数据。

对于unordered_set和unordered_map，使用散列方法来构造数据。所以这个时间复杂度是O(1)。这是对信息执行任何操作的完美方式，以防您的先决条件是没有按排序顺序排列的数据。