C++ 多重集、映射和哈希映射复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/222658/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
multiset, map and hash map complexity
提问by Adam Rosenfield
I would like to know the complexity in Big O notation of the STL multiset, map and hash map classes when:
在以下情况下，我想知道 STL 多集、映射和哈希映射类的 Big O 表示法的复杂性：
- inserting entries
- accessing entries
- retrieving entries
- comparing entries
- 插入条目
- 访问条目
- 检索条目
- 比较条目
回答by Adam Rosenfield
map, set, multimap, and multiset
映射、集合、多映射和多集
These are implemented using a red-black tree, a type of balanced binary search tree. They have the following asymptotic run times:
这些是使用红黑树实现的，红黑树是一种平衡二叉搜索树。它们具有以下渐近运行时间：
Insertion: O(log n)
Lookup: O(log n)
Deletion: O(log n)
插入：O(log n)
查找：O(log n)
删除：O(log n)
hash_map, hash_set, hash_multimap, and hash_multiset
hash_map、hash_set、hash_multimap 和 hash_multiset
These are implemented using hash tables. They have the following runtimes:
这些是使用哈希表实现的。它们具有以下运行时：
Insertion: O(1) expected, O(n) worst case
Lookup: O(1) expected, O(n) worst case
Deletion: O(1) expected, O(n) worst case
插入：O(1) 预期，O(n) 最坏情况
查找：O(1) 预期，O(n) 最坏情况
删除：O(1) 预期，O(n) 最坏情况
If you use a proper hash function, you'll almost never see the worst case behavior, but it is something to keep in mind — see Denial of Service via Algorithmic Complexity Attacksby Crosby and Wallach for an example of that.
如果您使用适当的散列函数，您几乎不会看到最坏情况的行为，但要记住这一点——请参阅Crosby 和 Wallach 的通过算法复杂性攻击拒绝服务的示例。
回答by ypnos
You can find this information in the SGI STL documentation: http://www.sgi.com/tech/stl/
您可以在 SGI STL 文档中找到此信息：http: //www.sgi.com/tech/stl/
Basically, both multiset and maps are sorted binary trees, so inserting/finding 1 out of N entries takes O(log N). See Sorted Assoc. Containers in the documentation.
基本上，多重集和映射都是排序的二叉树，因此从 N 个条目中插入/查找 1 个需要 O(log N)。请参阅排序关联。文档中的容器。
Obviously, the big advantage of Hashmap is O(1) for inserting and finding entries.
显然，Hashmap 的一大优势是插入和查找条目的复杂度为 O(1)。
Accessing it after found is O(1) for all structures. Comparison, what do you mean by that? Sounds like O(1) to me, after all were found.
对于所有结构，在找到后访问它是 O(1)。比较，你的意思是什么？毕竟找到了，对我来说听起来像 O(1)。
