Algorithm20.1 STL map
[TOC]
STL - map
【注意，此处的map是指的c++STL的map，c++STL的map的底层时红黑树，而Java的map的底层是哈希，类似于unordered_map，本质不同】
map底层：红黑树（一种非严格意义上的平衡二叉树）【利用二叉树来进行查询、插入、删除=>O(logn)】map内部所有的数据都是无重复+有序的
map有序性：map的key需要定义operator <。一般的数据类型系统已经确定了（如果是结构体做key的话，需要重载小于号。）
unordered_map底层：hash_value【利用哈希来进行查询、插入、删除=>O(1)】unordered_map内部的数据只保证无重复 （不能保证有序）
unordered_map无重复性：unordered_map需要重载 == ，因为他判断重复就是看 ==。一般的数据类型系统已经确定了（如果是结构体做key的话，需要重载==。）
vector+pair实现：
map与unordered_map VS set与multiset:
map有序，而unordered_map的无序性，但是两者都保持的是key唯一。
set唯一，而multiset不唯一，可重复，但是两者都保持的是有序。
查看是否已经映射
https://www.luogu.com.cn/problem/P1918
#include <iostream>
using namespace std;
#include <map>
map<int, int> mp;
int n, m, t;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {scanf("%d", &t);mp[t] = i;}
scanf("%d", &m);
while (m--) {
scanf("%d", &t);
if (mp.count(t)) printf("%d\n", mp[t]);
else printf("0\n");
}
return 0;
}
管理系统映射
https://www.luogu.com.cn/problem/P5266
#include <iostream>
using namespace std;
#include <map>
typedef unsigned long long ull;
map<string, ull> mp;
ull t, tp, score;
string name;
int main() {
scanf("%lld", &t);
while (t--) {
scanf("%lld", &tp);
if (tp == 1) {
cin>>name>>score;mp[name] = score;printf("OK\n");
} else if (tp == 2) {
cin>>name;
if (mp.count(name)) printf("%lld\n", mp[name]);
else printf("Not found\n");
} else if (tp == 3) {
cin>>name;
if (mp.count(name)) {mp.erase(name);printf("Deleted successfully\n");}
else printf("Not found\n");
} else printf("%d\n", mp.size());
}
return 0;
}
计数映射，直接销毁
https://www.luogu.com.cn/problem/P1684
题目大意：找一个字串中满足移除一定数量之后，满足AABB ABAB ABBA AAAA最多的数量。
思路：能不删就不删，然后只要满足有两种凑够了两个或者有一种凑够了4个，就可以立马将答案+1，然后重置（也就是前面的都不管了）
因而可以利用map进行计数。
#include <iostream>
using namespace std;
#include <map>
int n, t, cnt, ans;
map<int, int> mp;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &t);
mp[t]++;
if (mp[t] == 2) cnt++;
if (cnt == 2) cnt = 0, ans++, mp.clear();
if (mp[t] == 4) cnt = 0, ans++, mp.clear();
}
printf("%d\n", ans);
return 0;
}
利用map的key有序性 - (find函数logn复杂度)
https://www.luogu.com.cn/problem/P5250
题目大意：一堆木头（无重复）有放有拿。拿的时候，如果有刚好对应的长度就拿，没有对应的长度，就拿离他最近长度的，如果比他长和比他短的长度一样，那就拿比他短的那个长度的那根。
思路：
1、利用map的key的有序性，来直接用logn的复杂度来找。
2、想快速查到合适的位置，利用map的key的有序性进行（或者利用lowerbound二分来查找合适的位置然后添加进去）
3、如果没有映射到的，那就可以先创建一个映射，找到这个位置的iterator，然后再通过iterator来上下找。
4、注意erase的时候，如果通过迭代器iterator来进行erase(iterator)的话，很容易发生runtime error，也就是数组越界。所以一般通过erase(key)来进行移除。
#include <iostream>
using namespace std;
#include <map>
map<int, int> mp;
int t, tp, ta;
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &tp, &ta);
if (tp == 1) {
if (mp.count(ta)) printf("Already Exist\n");
else mp[ta] = 1;
} else {
if (mp.size() == 0) {printf("Empty\n");}
else if (mp.count(ta)) {printf("%d\n", ta);mp.erase(ta);}
else {
mp[ta] = 1;
auto iter = mp.find(ta);
auto iter2 = iter;
iter++;
if (iter2 == mp.begin()) {printf("%d\n", iter->first);mp.erase(iter);}
else if (iter == mp.end()) {printf("%d\n", (--iter2)->first);mp.erase(iter2);}
else if (ta-(--iter2)->first > iter->first-ta) {printf("%d\n", iter->first);mp.erase(iter);}
else {printf("%d\n", iter2->first);mp.erase(iter2);}
mp.erase(ta);
}
}
}
return 0;
}
unordered_map - 查看是否重复
题意：输出去重之后的
思路：用unordered_map直接判断是否重复。如果重复就不输出。
（注意：对于unordered_map迭代器iterator无法自减，只能自增。然后也不能reverse。如果按照遍历顺序输出map的话，此时得到的是反向的，也就是说他是先进先出的顺序。虽然unordered_map内部是无序的。
#include <iostream>
using namespace std;
int t, n, ta;
#include <unordered_map>
unordered_map<int, int> mp;
int main() {
scanf("%d", &t);
while (t--) {
mp.clear();
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &ta);
if (mp.count(ta) == 0) printf("%d ", ta);
}
// auto iter = mp.begin();
// while (iter != mp.end()) {
// printf("%d ", iter->first);
// iter++;
// }
printf("\n");
}
return 0;
}