multiset,map和hash map复杂性

Question

在以下情况下,我想知道STL multiset,map和hash map类的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

您可以在SGI STL文档中找到此信息:http: //www.sgi.com/tech/stl/

基本上,multiset和maps都是排序的二叉树,因此在N个条目中插入/查找1需要O(log N).请参阅Sorted Assoc.文档中的容器.

显然,Hashmap的最大优点是O(1)用于插入和查找条目.

找到后访问它是所有结构的O(1).比较,你是什么意思？毕竟发现后听起来像O(1).