map是STL中非常有用的一个容器 和函数类似，map是通过键值key查询对应value 对于数组而言，其下标必须非负整数的数值，且数值不能过大，而map就不同了，map的键值可以是任意类型，包括最常用的string类型，map的value也同样可以为任意类型
map的内部是红黑树实现，其具有自动排序的功能 通过键值排序，以递增的方式排序 若键值为整形，以数值递增排序 若键值为string，以字符串升序排序
先附上一个函数用法表格
用法作用m.begin(), m.end()返回 m的首、尾迭代器m.insert()(1)可以 m[‘a’] = 1进行赋值；(2)m.insert({‘b’, 2});m.erase(迭代器) / m.erase(键) / m.erase(迭代器范围)(1)m.erase(it); (2) m.erase(‘b’); (3) m.erase(it, m.end())it->first / it->second用于map的遍历：it->first获取key值，it->second获取value值m.find(k);返回的键值为k的元素的迭代器m.empty()判断m是否为空，是空返回true，否则返回falsem.clear()清除m中的元素插入
map的插入方式主要是用以下两种，两种方式的区别在于 若存在键值key，则第一种方式insert不能再执行，而第三种可以执行，并且将value覆盖
#include<bits/stdc++.h> using namespace std; map<string,string>m; int main() { m.insert("cwj","scj"); m["wyy"]="yyds"; return 0; }第一种insert是有返回值的，成功插入返回1，插入失败返回0
查找
如何去查找是否存在键值key？ m.find(key)：返回键值key的迭代器，若没有找到则返回m.end() 【注意】 m.end()并不是m的最后一个元素的迭代器，而是最后一个元素的下一个元素的迭代器
#include<bits/stdc++.h> using namespace std; map<string,string>m; int main() { string key; cin>>key; if(m.find(key)!=m.end())cout<<"找到了"; else cout<<"map里没有"; map<string,string>::iterator it; it=m.find(key); if(it==m.end())cout<<"map里没有"; else cout<<"找到了"; return 0; }删除与清空
如何删除键值key？ 有三种方式，一是通过键值删除，二是通过单个元素的迭代器删除，三是通过迭代器的范围 如何清空map容器？ clear即可
#include<bits/stdc++.h> using namespace std; map<string,string>m; int main() { string key; cin>>key; m.erase(key); map<string,string>::iterator it; it=m.find(key); m.erase(it); m.erase(m.begin(),m.end()); map<string,string>::iterator itl; map<string,string>::iterator itr; itl=m.find("123"); itr=m.find("456"); m.erase(itl,itr); m.clear(); return 0; }map的大小
如何知道map中已经有多少个元素了
#include<bits/stdc++.h> using namespace std; map<string,string> m; int main() { int msize=m.size(); return 0; }map的遍历
如何去遍历map中的每一个元素？ 有时我们需要去遍历map去寻找一个max_value之类的，map的遍历通过迭代器实现，迭代器++就可以实现去找下一个元素 迭代器的first返回其键值 迭代器的second返回其value
#include<bits/stdc++.h> using namespace std; map<string,int>m; int main() { string ans; int maxx=-1e9; map<string,int>::iterator it; for(it=m.begin();i!=m.end();i++){ if(it->second>maxx){ maxx=it->second; ans=it->first; } } cout<<"最大的是 "<<ans<<" 其value是 "<<ans; return 0; }map的初始值
string的初始值为：空串"" 整型的初始值为：0
例题1：map标记 例题2：string并查集 例题3：string并查集 例题4：求逆序对
map用来查找字符串非常方便，但不意味着map只使用在字符串查找上。 事实上做了很多题后发现，使用map降复杂度的操作无处不在
快上车
