multiset,map和hash map复杂性

在以下情况下,我想知道STL multiset,map和hash map类的Big O表示法的复杂性:

插入条目

访问条目

检索条目

比较条目

Adam Rosenfi.. 101

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的算法复杂性攻击中的拒绝服务.

1> Adam Rosenfi..：

---

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的算法复杂性攻击中的拒绝服务.

---

你在`hash_*`上所说的都是指C++ 11无序和Boost.Unordered容器吗？

---

@myWallJSON:是的

---

`hash_*`类模板是[Silicon Graphics STL](https://www.sgi.com/tech/stl/)的一部分.它们被整合到了`unordered_*`名称(unordered_map,unordered_set等)下的C++ 11版本中.此外,它们已被包含在libstdc ++,Visual C++和Boost C++库中.

2> ypnos..：

---

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

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

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

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