set/map/hash

Time Complexity Compare

set map unordered_map
插入 \(O(logn)\) \(O(logn)\) \(O(1)\)
刪除 \(O(logn)\) \(O(logn)\) \(O(1)\)
查詢 \(O(logn)\) \(O(logn)\) \(O(1)\)
底層 紅黑樹 紅黑樹 hash

PE

給定一個列表描述爺爺伯尼去過的所有旅行，以及一些查詢，問他第幾次去了某個國家是在哪一年。

unordered map 支援的操作

unordered map initialize




unordered_map<int, int> mp; // key -> value
// 加入新的 key-value：
mp[key] = value;

unordered map 清空 & 是否為空



mp.clear();
mp.empty();

unordered map 操作









// 檢查 key 是否存在 map 中：
mp.count(key);

// 刪除 key：
mp.erase(key);

// 取得 value
cout << mp[key] << '\n';

https://vjudge.net/problem/Kattis-grandpabernie




























unordered_map<string, vector<int> > mp;
cin >> n;
vector<string> vec;
for(int i = 0;i < n;i++){
    string str;
    int tmp;
    cin >> str >> tmp;
    if(mp.count(str)) mp[str].push_back(tmp);
    else{
        vec.push_back(str);
        mp.insert({str, vector<int>()});
        mp[str].push_back(tmp);
    }
}
int query;
cin >> query;
for(vector<int>::iterator i : vec){
    sort(mp[i].begin(), mp[i].end());
}
for(int i = 0;i < vec.size();i++) 
    sort(mp[vec[i]].begin(), mp[vec[i]].end())
while(query--){
    string str;
    int tmp;
    cin >> str >> tmp;
    cout << mp[str][tmp - 1] << '\n';
}

使用 hash 可以 \(O(1)\) 快速插入以及搜尋，記得要對年份做 sort 。
最後針對各個 query 使用 mp[str][tmp - 1] 就可以快速拿到答案

set & multiset














set <int> st;
// 把元素 x 加進 set：
st.insert(x);
// 檢查元素 x 是否存在 set 中：
st.count(x);
//刪除元素 x：
st.erase(x); // 可傳入值或iterator
// 清空集合中的所有元素：
st.clear();

// 判斷是否為空的 set ：
st.empty() // 回傳 true
st.size() // 回傳零










// default 
multiset<int> st;
multiset<int, less<int> > st;

// 由大至小
multiset<int, greater<int> > st;
    
st.erase(val); // 會刪除所有值為 val 的元素。
st.erase(st.find(val)); // 只刪除第一個值為 val 的元素。













// 迭代整個 multiset
multiset<int, greater<int> > st;
st.insert(1);
st.insert(1);
st.insert(9);
st.insert(8);
st.insert(6);
for(multiset<int>::iterator i = st.begin();i != st.end();i++)
    cout << *i << ' ';
// for C++ 11
for(auto i = st.begin();i != st.end();i++)
    cout << *i << ' ';
Select a repo