C/C++教學

C++ std::unordered_map 用法與範例

本篇介紹 C++ 的 std::unordered_map 用法，一開始會先介紹 unordered_map 的概念，再來是 unordered_map 的用法教學，並提供一些範例參考。

std::unordered_map 與 std::map 的區別
C++ STL 中 map 裡面的存放資料是有序(排序)的，map 對應的資料結構是紅黑樹(red-black tree)，紅黑樹是一種自平衡的二元搜尋樹，在紅黑樹上做搜尋的時間複雜度為O(logN)。而 unordered_map 裡面的存放資料是無序的，unordered_map 對應雜湊表(hash table)，雜湊表的特點就是搜尋效率高，利用鍵值與雜湊函數(hash function)計算出雜湊值而快速的查找到對應的元素，時間複雜度為常數級別O(1)， 而額外空間複雜度則要高出許多。unordered_map 與 map 的使用方法基本上一樣，都是 key/value 之間的映射，只是他們內部採用的資料結構不一樣。所以對於需要高效率查詢的情況可以使用 unordered_map 容器。而如果對記憶體消耗比較敏感或者資料存放要求排序的話則可以用 map 容器。

以下 C++ unordered_map 內容將分為這幾部份，

  • unordered_map 初始化
  • unordered_map 容器裡插入元素與存取元素
  • unordered_map 容器裡移除元素
  • 使用迴圈尋訪 unordered_map 容器
  • 清空 unordered_map 容器
  • 判斷 unordered_map 容器是否為空
  • unordered_map 使用範例

要使用 unordered_map 容器的話，需要引入的標頭檔：<unordered_map>

unordered_map 初始化

以下為 unordered_map 初始化容器的寫法，

1
2
3
4
5
std::unordered_map<std::string, int> umap = {
    {"Tom", 1},
    {"Ann", 4},
    {"Jack", 2}
};

unordered_map 容器裡插入元素與存取元素

unordered_map 容器插入元素有兩種寫法，
第一種是使用中括號 [] 的方式來插入元素，很像陣列的寫法，例如：umap[key] = value，範例如下，

1
2
3
std::unordered_map<std::string, int> umap;
...
umap["John"] = 3;

另一種是使用 umap.insert() 成員函式來插入元素，
那這個 umap.insert() 方式跟上面中括號 [] 的方式有什麼不同呢？

差別在於如果 key 值已經存在的話，使用中括號 [] 的方式會將新資料覆蓋舊資料，
而使用 umap.insert() 的方式會回傳插入的結果，該 key 值存在的話會回傳失敗的結果，
檢查 umap.insert() 的插入結果方式如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> umap;
    umap.insert(std::pair<std::string, int>("John", 3));

    std::pair<std::unordered_map<std::string, int>::iterator, bool> retPair;
    retPair = umap.insert(std::pair<std::string, int>("John", 3));  
    
    if (retPair.second == true)
        std::cout << "Insert Successfully\n";
    else
        std::cout << "Insert Failure\n";

    return 0;
}

unordered_map 容器要取得某 key 鍵值元素的話可以這樣寫，

1
std::cout << "id: " << umap["John"] << "\n";

unordered_map 容器裡移除元素

以下為 unordered_map 容器裡移除元素的寫法，移除第一個元素的寫法像這樣，

1
2
3
std::unordered_map<std::string, int> umap;
...
umap.erase(umap.begin());

unordered_map 容器移除指定元素的寫法，

1
2
3
std::unordered_map<std::string, int> umap;
...
umap.erase("Ann");

unordered_map 容器移除某段範圍元素的寫法，下例示範從 John 開始移除到尾部的範圍，

1
2
3
std::unordered_map<std::string, int> umap;
...
umap.erase(umap.find("John"), umap.end());

使用迴圈尋訪 unordered_map 容器

這邊示範用 for 迴圈尋訪 unordered_map 裡面的元素，並且將它們印出來，寫法如下，

1
2
3
for (const auto& n : umap) {
    std::cout << "name: " << n.first << ", id: " << n.second << "\n";
}

另一種迴圈尋訪 unordered_map 的方法是使用迭代器，以下示範使用前向迭代器，改用 auto 的話可以讓 code 更簡潔，

1
2
3
4
5
for (std::unordered_map<std::string, int>::iterator it = umap.begin(); it != umap.end(); it++) {
// or
// for (auto it = umap.begin(); it != umap.end(); it++) {
    std::cout << "name: " << (*it).first << ", id: " << (*it).second << "\n";
}

清空 unordered_map 容器

要清空 unordered_map 容器的的話，要使用 clear()，

1
2
3
std::unordered_map<std::string, int> umap;
...
umap.clear();

判斷 unordered_map 容器是否為空

要判斷 unordered_map 是否為空或是裡面有沒有元素的話，可以用 empty()，寫法如下，

1
2
3
4
5
6
7
8
std::unordered_map<std::string, int> umap;
umap.clear();

if (umap.empty()) {
    std::cout << "empty\n";
} else {
    std::cout << "not empty, size is "<< umap.size() <<"\n";
}

unordered_map 使用範例

std-unordered_map.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// g++ std-unordered_map.cpp -o a.out -std=c++11
#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> umap = {
        {"Tom", 1},
        {"Ann", 4},
        {"Jack", 2}
    };

    for (const auto& n : umap) {
        std::cout << "name: " << n.first << ", id: " << n.second << "\n";
    }

    umap["Tiffany"] = 5;
    umap["John"] = 3;

    std::cout << umap["John"] << "\n";
    std::cout << umap["Tiffany"] << "\n";

    for (std::unordered_map<std::string, int>::iterator it = umap.begin(); it != umap.end(); it++) {
    // or
    // for (auto it = umap.begin(); it != umap.end(); it++) {
        std::cout << "name: " << (*it).first << ", id: " << (*it).second << "\n";
    }
}

輸出如下：

1
2
3
4
5
6
7
8
9
10
name: Jack, id: 2
name: Tom, id: 1
name: Ann, id: 4
3
5
name: John, id: 3
name: Tiffany, id: 5
name: Jack, id: 2
name: Tom, id: 1
name: Ann, id: 4

參考
std::unordered_map - cppreference.com
https://en.cppreference.com/w/cpp/container/unordered_map
unordered_map - C++ Reference
http://www.cplusplus.com/reference/unordered_map/unordered_map/
unordered_map in C++ STL - GeeksforGeeks
https://www.geeksforgeeks.org/unordered_map-in-cpp-stl/
C++ STL 之哈希表 | unordered_map | 「浮生若梦」 - sczyh30’s blog
https://www.sczyh30.com/posts/C-C/cpp-stl-hashmap/
C++ STL unordered_map介紹與使用方法 - Cypress的博客 - CSDN博客
https://blog.csdn.net/Cypress1010/article/details/53669409
雜湊表 - 維基百科，自由的百科全書
https://zh.m.wikipedia.org/zh-tw/%E5%93%88%E5%B8%8C%E8%A1%A8
雜湊函式 - 維基百科，自由的百科全書
https://zh.m.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8

其它相關文章推薦
如果你想學習 C++ 相關技術，可以參考看看下面的文章，
C/C++ 新手入門教學懶人包
std::map 用法與範例
std::multimap 用法與範例
std::vector 用法與範例
std::deque 用法與範例
std::queue 用法與範例