您的位置:

unordered_map使用详解

一、unordered_map排序

unordered_map是C++11新增的容器之一,它不像map有排序功能。但是我们仍然可以通过一些方法对unordered_map进行排序:

1. 使用pair对unordered_map进行排序

    
// 使用pair对unordered_map进行排序
#include 
   
#include 
    
#include 
     
using namespace std;

int main(){
    unordered_map
       umap = {{2, 3}, {1, 4}, {7, 6}, {4, 1}, {3, 2}};
    auto cmp = [](const pair
       
        &a, const pair
        
         &b) { return a.second < b.second; }; vector
         
          
           > vec(umap.begin(), umap.end()); sort(vec.begin(), vec.end(), cmp); for(auto &it : vec){ cout << it.first << ": " << it.second << endl; } return 0; }
          
         
        
       
      
     
    
   

2. 使用结构体对unordered_map进行排序

    
// 使用结构体对unordered_map进行排序
#include 
   
#include 
    
#include 
     
using namespace std;

struct compare{
    bool operator()(const pair
       &a, const pair
       
        &b) { return a.second < b.second; } }; int main(){ unordered_map
        
         umap = {{2, 3}, {1, 4}, {7, 6}, {4, 1}, {3, 2}}; set
         
          
           , compare> sorted_set(umap.begin(), umap.end()); for(auto &it : sorted_set){ cout << it.first << ": " << it.second << endl; } return 0; }
          
         
        
       
      
     
    
   

二、unordered_map自定义类型

unordered_map不仅可以对基本类型进行使用,也可以使用自定义类型。自定义类型作为key时,需要重载hash函数和==运算符。

    
// unordered_map自定义类型
#include 
   
#include 
    
using namespace std;

struct Book {
    string name;
    int price;
};

struct HashFunc {
    size_t operator() (const Book &book) const {
        return hash
     () (book.name) ^ hash
      () (book.price);
    }
};

struct EqualKey {
    bool operator() (const Book &a, const Book &b) const {
        return a.name == b.name && a.price == b.price;
    }
};

int main() {
    unordered_map
       
        myMap; myMap[{"C++ Primer", 88}] = 100; myMap[{"Computer Network", 59}] = 50; for(auto &bookPrice : myMap) { cout << bookPrice.first.name << " " << bookPrice.first.price << " " << bookPrice.second << endl; } return 0; }
       
      
     
    
   

三、unordered_map用法

1. unordered_map基本操作

unordered_map和其他STL容器使用方法类似,包括插入,访问,删除,迭代等等

    
#include 
   
#include 
    
using namespace std;

int main(){
    unordered_map
      myMap; // 定义unordered_map
    myMap.insert({1, 2}); // 插入{1, 2}
    myMap.emplace(2, 3); // 插入{2, 3}
    myMap[3] = 4; // 插入{3, 4}

    // 判断key是否存在
    if(myMap.count(1))
        cout << "Key 1 exists" << endl;

    // 删除一个键值对
    myMap.erase(2);

    // 迭代输出
    for(auto &it: myMap)
        cout << it.first << ": " << it.second << endl;

    return 0;
}
    
     
    
   

2. unordered_map查找

unordered_map提供了一些方法查找元素。其中find()和count()方法比较常用。find()返回一个迭代器,count()返回一个bool类型的值,表示key是否存在。

    
// unordered_map查找
#include 
   
#include 
    
using namespace std;

int main() {
    unordered_map
      myMap = {{1, 2}, {2, 4}, {3, 6}};

    // find()方法
    if(myMap.find(2) != myMap.end())
        cout << "The value of key 2 is " << myMap.find(2)->second << endl;

    // count()方法
    if(myMap.count(3))
        cout << "Key 3 exists." << endl;

    return 0;
}
    
     
    
   

四、unordered_map性能

unordered_map在插入、查找、删除元素的时间复杂度都是O(1)的,与元素数量无关,因此性能非常高。

以插入为例,下面是一个比较unordered_map和map插入速度的例子:

    
#include 
   
#include 
    
#include 
     
#include 
      
using namespace std;
using namespace chrono;

int main(){
    unordered_map
       
        umap; auto start = high_resolution_clock::now(); for(int i = 0; i < 100000; i++) umap[i] = i; auto stop = high_resolution_clock::now(); auto duration = duration_cast
        
         (stop - start); cout << "unordered_map insert time: " << duration.count() << endl; map
         
          mmap; start = high_resolution_clock::now(); for(int i = 0; i < 100000; i++) mmap[i] = i; stop = high_resolution_clock::now(); duration = duration_cast
          
           (stop - start); cout << "map insert time: " << duration.count() << endl; return 0; }
          
         
        
       
      
     
   

五、map和unordered_map的区别

二者最主要的区别在于内部实现的数据结构不同。map使用红黑树实现,因此元素按照key的大小排列,而unordered_map使用哈希表实现,因此元素的顺序是无序的。

二者在性能方面也有所不同。在查找、插入、删除元素时,unordered_map的时间复杂度都是O(1),而map的时间复杂度是O(logN)。

六、unordered_map底层实现

unordered_map的底层实现使用了哈希表。哈希表包含一个数组和一个哈希函数,哈希函数将元素映射到数组中的一个索引位置。如果两个元素的哈希值相同,那么它们会被映射到数组中同一个索引位置,因此哈希表需要解决冲突的问题。

解决冲突的方式有很多种,其中最常见的是链表法。如果一个索引位置上已经有元素了,那么新元素会被插入到这个元素的链表中。如果链表过长,会影响unordered_map的性能,因此C++11引入了基于哈希表的高质量实现——robin hood hashing。

七、unordered_map和map

unordered_map和map提供了类似的功能,二者都可以插入、查找、删除元素。unordered_map在元素数量较大时性能比map更高,而map保证元素按照key的大小排序。

除了性能和元素排序方式的不同之外,二者的使用方法几乎一样,因此可以根据实际需要选择使用哪一个容器。

八、unordered_map输出

unordered_map可以通过迭代器输出全部元素。如果需要将unordered_map转换为vector,可以使用vector的初始化器列表(initializer list):vector > vec(umap.begin(), umap.end());

    
// unordered_map输出
#include 
   
#include 
    
#include 
      // make_pair()
using namespace std;

int main(){
    unordered_map
       myMap = {{1, 2}, {2, 4}, {3, 6}};
    for(auto & it : myMap){
        cout << it.first << ": " << it.second << endl;
    }

    // 转换为vector
    vector
       
        
         > vec(myMap.begin(), myMap.end()); for(auto & it : vec){ cout << it.first << ": " << it.second << endl; } return 0; }
        
       
      
     
    
   

九、c++ unordered_map

C++11引入了unordered_map,是一种基于哈希表的关联容器,可以对数据进行快速查找。

unordered_map的使用方法与STL中的其他容器类似,但由于其底层实现的差异,一些特性也有所不同。通过深入研究unordered_map的使用,可以让你更好地应用这个容器,从而更加高效地解决相关问题。