c++ map

• map 的特性是可以用 key 去查詢 value，也就是用 key-value 來儲存資料。
• map 底層通常以紅黑樹實作，key 會自動排序，因此搜尋、插入、刪除的時間複雜度都是 O(log n)。
• 另一種是 unordered_map，底層以 hash table 實作，key 不會排序，平均搜尋、插入、刪除的時間複雜度是 O(1)，最差情況是 O(n)。

建立 map

• #include <map> : 引入 map
• map<keyType, valueType> m : 宣告
• map<keyType, valueType> m={{key1, val1}, {key2, val2}} : 宣告 + 初始化

使用範例：

#include <iostream>
#include <map>
using namespace std;

int main(){
    
    map<int, string> m1;                          // m1 = {}
    map<int, string> m2={{1, "cat"}, {3, "dog"}}; // m2 = {{1, "cat"}, {3, "dog"}}

    return 0;
}

新增、修改及刪除元素

• m[key]=val : 插入或修改 key 對應的 value
• m.insert({key, val}) : 插入 key-value，若 key 已存在則不會覆蓋
• m.erase(key) : 刪除 key 對應的元素，回傳刪除的元素數量（0 或 1）
• m.clear() : 清空所有元素

使用範例：

#include <iostream>
#include <map>
using namespace std;

int main(){
    
    map<int, string> m;

    m[1]="cat";   // m = {{1, "cat"}}
    m[3]="dog";   // m = {{1, "cat"}, {3, "dog"}}
    m[1]="bird";  // m = {{1, "bird"}, {3, "dog"}}
    
    m.insert({2, "fish"});    // m = {{1, "bird"}, {2, "fish"}, {3, "dog"}}
    m.insert({2, "rabbit"});  // m = {{1, "bird"}, {2, "fish"}, {3, "dog"}}
    
    m.erase(1);   // m = {{2, "fish"}, {3, "dog"}}
    m.clear();    // m = {}

    return 0;
}

用 key 存取 value

• m[key] : 取得 key 對應的 value，若 key 不存在會自動建立一個預設值
• m.at(key) : 取得 key 對應的 value，若 key 不存在會丟出例外

使用範例：

#include <iostream>
#include <map>
using namespace std;

int main(){

    map<int, string> m={{1, "cat"}, {2, "dog"}};

    cout << m[1] << endl;    // "cat" 
    cout << m.at(2) << endl; // "dog"
    cout << m[3] << endl;    // ""    (m={{1, "cat"}, {2, "dog"}, {3, ""}})
    cout << m.at(4) << endl; // error message: terminating due to uncaught exception of type std::out_of_range: map::at:  key not found

    return 0;
}

查詢 key 是否存在

• m.count(key) : 查詢 key 是否存在，回傳 0 或 1
• m.find(key) : 回傳 key 對應元素的 iterator（找不到則回傳 m.end()）

使用範例：

#include <iostream>
#include <map>
using namespace std;

int main(){

    map<int, string> m={{1, "cat"}, {2, "dog"}, {3, "bird"}};
    
    cout << m.count(1) << endl; // 1
    cout << m.count(5) << endl; // 0
    
    cout << (m.find(1) != m.end()) << endl; // 1
    cout << (m.find(5) != m.end()) << endl; // 0

    return 0;
}

走訪 map

map 走訪時，元素會依照 key 由小到大排序

#include <iostream>
#include <map>
using namespace std;

int main(){
    
    map<int, string> m={{3, "dog"}, {1, "cat"}, {2, "bird"}};
    
    // method 1
    for(auto [key, val] : m){
        cout << key << ":" << val << " "; // 1:cat 2:bird 3:dog (key 有排序)
    }
    cout << endl;
    
    // method 2
    for(auto iter=m.begin(); iter!=m.end(); iter++){
        cout << iter->first << ":" << iter->second << " "; // 需要 dereference
    }
    cout << endl;

    return 0;
}

其他

• m.size() : map 的大小
• m.empty() : 判斷 map 是不是空的

使用範例：

#include <iostream>
#include <map>
using namespace std;

int main(){

    map<int, string> m={{1, "cat"}, {2, "dog"}, {3, "bird"}};

    cout << m.size() << endl;  // 3
    cout << m.empty() << endl; // 0 (false)

    return 0;
}

unordered_map

使用上基本和 map 類似，把 map 改成 unordered_map 即可。

unordered_map 與 map 差異：

• map：有序（紅黑樹），查找、插入、刪除 O(log n)
• unordered_map：無序（hash table），平均查找、插入、刪除 O(1)

使用範例：

#include <iostream>
#include <unordered_map>
using namespace std;

int main(){
    
    unordered_map<int, string> m={{3, "dog"}, {1, "cat"}, {2, "bird"}};
    
    for(auto [key, val] : m){
        cout << key << ":" << val << " "; // 2:bird 1:cat 3:dog (key 無排序)
    }
    cout << endl;

    return 0;
}