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 用法與範例