目錄
【map】搜尋紅黑樹,O(log(N))
- map:存放 key-value pairs 的映射資料結構,會按 key 由小到大排序。
- 宣告:
- map <int, int> mp; // key和value都是整數
- 加入新的key-value pair:
- mp[key] = value;
- 檢查 key 是否存在 map 中:
- mp.count(key);
- 刪除 key:
- mp.erase(key);
- 清空 map 中的所有元素:
- mp.clear();
- 利用 key 取值:
- value = mp[key];
- 判斷是否為空的map:
- mp.empty() 回傳true
- mp.size() 回傳零
- 【範例】ZeroJudge a135: 12250 – Language Detection 【題解】
- 遍歷整個map時,利用iterator操作:
- 取key:it->first 或 (*it).first
- 取value:it->second 或 (*it).second
for (auto it = mp.begin(); it != mp.end(); ++it){
cout << it->first << " => " << it->second << '\n';
}
for (auto it = mp.begin(); it != mp.end(); ++it){
cout << (*it).first << " => " << (*it).second << '\n';
}
【unordered_map】搜尋Hash Table,O(1)
- unordered_map:存放 key-value pairs 的「無序」映射資料結構。
- 宣告:
- unordered_map <string, int> mp;
- 其它用法與 map 相同。
- 【範例】ZeroJudge e289: 美麗的彩帶 【題解】