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<pair> 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<pair, 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 " <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 

五、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<pair> 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<pair> 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的使用，可以让你更好地应用这个容器，从而更加高效地解决相关问题。