多重集，地图和哈希映射复杂性 [英] multiset, map and hash map complexity
问题描述
我想知道STL multiset，map和hash map类在大O表示法中的复杂性：
I would like to know the complexity in Big O notation of the STL multiset, map and hash map classes when:
- 插入条目
- 正在访问条目
- >
- inserting entries
- accessing entries
- retrieving entries
- comparing entries
推荐答案
map，set，multimap和multiset
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:
插入：O（log n）
查找：O（log n）
删除：O（log n）
Insertion: O(log n)
Lookup: O(log n)
Deletion: O(log n)
使用哈希表实现。它们有以下运行时：
These are implemented using hash tables. They have the following runtimes:
插入：O（1）预期，O（n）最坏情况
查找：O ，O（n）最坏情况下
删除：O（1）预期，O（n）最坏情况
Insertion: O(1) expected, O(n) worst case
Lookup: O(1) expected, O(n) worst case
Deletion: O(1) expected, O(n) worst case
函数，你几乎不会看到最坏的情况下的行为，但它是要记住 - 请参阅本文为例。
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 this paper for an example.
这篇关于多重集，地图和哈希映射复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
