STL容器 map与unordered_map的区别（3508）

yuanbao

map 和 unordered_map 都是 C++ STL 中的关联容器，用于存储键值对。二者的底层实现不同，导致它们的特性也有所不同。

map 是基于红黑树的实现，因此它的元素是按照键值的大小有序排列的。map 的查找、删除、插入操作都是 $\log n$ 的时间复杂度，其中 $n$ 是元素数量。由于 map 的元素是有序的，因此我们可以使用 lower_bound、upper_bound 等 STL 算法。

unordered_map 是基于哈希表的实现，它的元素是无序的。哈希表的查询、删除、插入操作的时间复杂度都是常数级别的，因此 unordered_map 在元素数量较多时更加高效。但是，由于哈希表需要进行哈希函数的计算，因此 unordered_map 的空间使用上会比 map 大一些。

使用时，如果需要对元素进行排序，或者需要使用 lower_bound、upper_bound 等 STL 算法，就可以使用 map。如果需要快速定位元素并且不需要排序，就可以使用 unordered_map。

需要注意的是，由于哈希表的原理，它的元素在内存中是离散的，因此在访问内存时可能会出现较多的缓存不命中，从而影响程序的性能。另外，由于哈希表的元素数量通常会超过预期，因此需要根据实际情况调整哈希表的初始大小和负载因子，以避免过多的哈希冲突和重新哈希操作。

下面是使用 unordered_map 计算每个树种出现次数的代码：

1. #include <iostream>
   
2. #include <unordered_map>
   
3. #include <string>
   
4. using namespace std;
   
5. 
   
6. int main() {
   
7.     unordered_map<string, int> mp;
   
8.     string st;
   
9.     while (getline(cin, st)) {
   
10.         mp[st]++;
    
11.     }
    
12.     for (auto it = mp.begin(); it != mp.end(); it++) {
    
13.         cout << it -> first << " " << it -> second << endl;
    
14.     }
    
15.     return 0;
    
16. }
    

复制代码

在上述代码中，unordered_map 的 [] 操作符可以直接访问元素，并且如果该元素不存在则会被自动添加到哈希表中。因此，我们可以直接使用 mp[st]++ 来计算每个树种出现次数，无需判断该树种是否已经存在于 mp 中。
终于理解了map容器对key进行排序的了。

1. #include <iostream>
   
2. #include <map>
   
3. #include <iomanip>
   
4. #include <string>
   
5. using namespace std;
   
6. 
   
7. map<string, int> mp;
   
8. string st;
   
9. int cnt;
   
10. double ans;
    
11. 
    
12. int main(){
    
13.         while (getline(cin, st)){
    
14.                 mp[st]++;
    
15.                 cnt++;
    
16.         }
    
17.         for (auto it = mp.begin(); it != mp.end(); it++){
    
18.                 ans = (it -> second) * 1.0 / cnt * 100;
    
19.                 cout << it -> first << ' ' << fixed << setprecision(4) << ans << '\n';
    
20.         }
    
21.         return 0;
    
22. }

复制代码

oliver

实现原理决定了性能的不能，不错

tiger

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. int main(){
   
4.     map<string,int>m1;
   
5.     int c=0;
   
6.     string s;
   
7.     while(getline(cin,s)){
   
8.         m1[s]++;
   
9.         c++;
   
10.     }
    
11.     map<string,int >::iterator i;
    
12.     for(i=m1.begin();i!=m1.end();i++) cout<<setiosflags(ios::fixed)<<setprecision(4)<<i->first<<" "<<100.0*(i->second)/c<<'\n';
    
13.            return 0;
    
14. }

复制代码

map大神

tiger

3508