【筆記】常用C++ STL:map & unordered_map

【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: 美麗的彩帶題解
分享本文 Share with friends