多重集合，地图和哈希映射的复杂性
我想知道在STL multiset，map和hash map类的Big O符号中的复杂性：
- 插入条目
- 访问条目
- 检索条目
- 比较条目
地图，集合，multimap和multiset
这些实现使用红黑树 ，一种平衡二叉search树 。 他们有以下渐近运行时间：
插入：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）最坏的情况
如果使用正确的散列函数，则几乎不会看到最坏的情况，但请记住这一点 – 以本文为例。
cppreference.com是我去我的c + +参考问题。 他们做了一个很好的工作，概述了大部分上面提到的function的大O符号。
您可以在SGI STL文档中find这些信息： http : //www.sgi.com/tech/stl/
基本上，multiset和maps都是二叉树，因此插入/查找N个条目中的1个需要O（logN）。 请参见Sorted Assoc。 容器中的文档。
显然，Hashmap的最大优点是O（1）用于插入和查找条目。
find后访问它是所有结构的O（1）。 比较，你是什么意思？ 听起来像O（1），毕竟我find了。
