# 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
```cpp=
unordered_map<int, int> mp; // key -> value
// 加入新的 key-value:
mp[key] = value;
```
#### unordered map 清空 & 是否為空
```cpp=
mp.clear();
mp.empty();
```
---
#### unordered map 操作
```cpp=
// 檢查 key 是否存在 map 中:
mp.count(key);
// 刪除 key:
mp.erase(key);
// 取得 value
cout << mp[key] << '\n';
```
---
https://vjudge.net/problem/Kattis-grandpabernie
```cpp=
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
```cpp=
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() // 回傳零
```
---
```cpp=
// default
multiset<int> st;
multiset<int, less<int> > st;
// 由大至小
multiset<int, greater<int> > st;
st.erase(val); // 會刪除所有值為 val 的元素。
st.erase(st.find(val)); // 只刪除第一個值為 val 的元素。
```
---
---
```cpp=
// 迭代整個 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 << ' ';
```
{"title":"set/map/hash","description":"| | set | map | unordered_map || –––– | –––– | –––– || Text | Text | Text |","contributors":"[{\"id\":\"616555cd-54b9-4bba-98c9-ddf2c0a6bbc6\",\"add\":4065,\"del\":1835}]"}