关联容器unordered_map详解

太过爱你忘了你带给我的痛 2022-01-29 23:39 346阅读 0赞

### 文章目录 ###

*   *   *  unordered\_map
         *  unordered\_map vs unordered\_set
         *  unordered\_map vs map
         *  methods on unordered\_map
         *  Methods of unordered\_map

### unordered\_map ###

`unordered_map`是一个存储由`key`和`value`映射值组成的关联容器。该`key`值用于唯一表示该元素，而映射值是该`key`值关联的内容。`key`和`value`都可以被预定义或用户定义为任何类型。

在内部，`unordered_map`是用`HashTable`来实现，该`key`提供的映射被哈希为哈希表的索引，这也就是为什么数据结构的性能很大程度上依赖于哈希后函数。而从哈希表中`search,insert,delete`操作，平均复杂度为`O(1)`.

下面是`C++`程序演示`unordered_map`功能的例子。

#include<iostream>
    #include<unordered_map>
    using namespace std;
    int main(int argc, char const *argv[]) { 
      //声明一个<string,int>类型的umap
      unordered_map<string,int> umap;
    
      //使用[]操作符插入值
      umap["GeeksforGeeks"]=10;
      umap["FEEL"]=1999;
      umap["Contribute"]=30;
      
      for(auto x:umap){ 
        cout<<x.first<<" "<<x.second<<endl;
      }
      return 0;
    }

输出结果：

> GeeksforGeeks 10  
> Contribute 30  
> FEEL 1999

### unordered\_map vs unordered\_set ###

在`unordered_set`中,只有`key`，没有`value`,主要用于查看在一个集合中是否存在。例如，考虑单个单词的频率计数问题，我们不能使用`unordered_set(或set)`,因为无法存储计数个数.

### unordered\_map vs map ###

`map(与set类似)`是一个有唯一值的有序序列，在`unordered_map`中`key`可以存储任何顺序：有序和无序。`Map`是作为一个平衡树的实现，这也是它为什么可以维护元素之间的顺序（通过特定的树遍历）.`Map`操作的时间复杂度为`O(Log n)`，对于`unordered_set`平均复杂度为`O(1)`.

### methods on unordered\_map ###

`unordered_map`中有相当多函数，其中最有用的有`operator=,operator[],empty，size,capacity，begin，end，iterator,find,和count，insert,earse`等方法。

我们可以使用`iterator`遍历`unordered_map`所有元素。下面是一个初始化，索引，迭代的例子：

#include<iostream>
    #include<unordered_map>
    using namespace std;
    int main() { 
      //声明一个<string,int>类型的umap
      unordered_map<string,int> umap;
    
      umap["PI"]=3.14;
      umap["root2"] = 1.414;
      umap["root3"] = 1.732;
      umap["log10"] = 2.302;
      umap["loge"] = 1.0;
    
      //通过insert函数插入值
      umap.insert(make_pair("e",2.112));
      string key="PI";
    
      if(umap.find(key)==umap.end()){ 
        cout<<key<<" not exit!"<<endl;
      }
      else{ 
        cout<<"Found "<<key<<endl;
      }
    
      //遍历umap中的所有值
      // unordered_map<string,double>::iterator it;
      cout<<endl<<"All Elements:"<<endl;
      for(auto it=umap.begin();it!=umap.end();it++){ 
        cout<<it->first<<" "<<it->second<<endl;
      }
      for(auto x:umap){ 
        cout<<x.first<<" "<<x.second<<endl;
      }
      return 0;
    }

输出结果：

> Found PI
> 
> All Elements:  
> loge 1  
> e 2  
> log10 2  
> root3 1  
> PI 3  
> root2 1  
> loge 1  
> e 2  
> log10 2  
> root3 1  
> PI 3  
> root2 1

*  下面是一个基于`unordered_map`的实际问题——给定串单词，找出每个单词出现的次数。
    
    > Input : str = “geeks for geeks geeks quiz practice qa for”;
    > 
    > Output : Frequencies of individual words are
    > 
    > (practice, 1)
    > 
    > (for, 2)
    > 
    > (qa, 1)
    > 
    > (quiz, 1)
    > 
    > (geeks, 3)
    
    关于这个问题，采用`unordered_map`来解决代码如下：

#include<bits/stdc++.h>
     using namespace std;
     
     void printS(const string &s){ 
       unordered_map<string,int> umap;
     
       stringstream ss(s);
       string word;
       while(ss>>word){ 
         umap[word]++;
       }
       for(auto it=umap.begin();it!=umap.end();it++){ 
         cout<<"("<<it->first<<","<<it->second<<")"<<endl;
       }
     }
     
     int main() { 
       string s="geeks for geeks geeks quiz practice qa for";
       printS(s);
       return 0;
     }

### Methods of unordered\_map ###

*  `at()：` 返回指定`key`的值的引用
 *  `begin():`返回指向`unordered_map`的第一个元素的迭代器
 *  `end():`返回指向`unordered_map`的最后一个元素的迭代器
 *  `bucket():`返回`map`中`key`为指定值的`bucket`值,即索引
 *  `bucket_count：`得到`bucket`的个数
 *  `bucket_size：` 返回`bucket`的大小
 *  `count()：`使用给定`key`获取在`unordered_map`中出现的次数
 *  `equal_range：` 使用一个等于`k`的`key`键来返回包含容器中所有元素的范围的边界，
 *  `equal_range`示例：

#include<bits/stdc++.h>
    using namespace std;
    typedef unordered_map<char,char> gfg;
    
    int main() {
      gfg g;
    
      g.insert(gfg::value_type('a','b'));
      g.insert(gfg::value_type('b','d'));
      g.insert(gfg::value_type('e','f'));
    
      //’f'作为‘key’,
      pair<gfg::iterator,gfg::iterator> p1=g.equal_range('f');
    
      //不存在'f'
      cout<<"nsearch for f:";
      for(;p1.first!=p1.second;++p1.first){
        cout<<p1.first->first<<","<<p1.first->second<<endl;
      }
    
      p1=g.equal_range('a');
    
      cout << "\nsearch for 'a' : [";
        for (; p1.first != p1.second; ++p1.first) {
            cout << p1.first->first << ", " << p1.first->second << "]"<<endl;
        }
    
      return 0;
    }

输出：

> nsearch for f:  
> search for ‘a’ : \[a, b\]