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的使用，可以讓你更好地應用這個容器，從而更加高效地解決相關問題。