c++ STL 之 map

# map的使用方法（蒟蒻的总结 - #### 1、map所需要的空间需要注意一下，是普通数组空间的好几倍，访问时间复杂度是log级别的。 - #### 2、map很强大，可以在里面放几乎所有东西，什么string，结构体（要重载小于号）都可以存map里面，比如说pos["abc"]=233。 - #### 3、虽然说map的访问是log级别的，但是如果存太长的string，访问速度也超级慢，（当初写“文件查询”直接存所有父亲目录，T的不要不要的，而且还不知道为什么T）。 ------- ##### 要使用map必须加上头文件 #include<map> 和 using namespace std ```cpp #include<bits/stdc++.h> //真香. using namespace std; map<string,int>pos; int main(){ string a="abc",b="efg"; pos[a]=1,pos[b]=2; cout<<pos[a]<<" "<<pos[b]<<endl; return 0; } ``` ----- ### 以下是map常用的自带函数。 - **1，map的清空：** pos.clear(); - ** 2，map的添加：**pos["abc"]=++id; **但一般我们会这么写 :** ```cpp int read(string a){ if(pos.find(a)==pos.end()) pos[a]=++id; return pos[a]; } ``` ----- #### map是个很好用的东西，比如说有些恶心的题目，明明是个最短路的题目，读入的时候非要给你读入地方的名字，这时候就可以用map轻轻松松解决。 #### map还可以用来hash标记，比如说一块图形的形状，用一个string每次加上dfs的方向，然后pos[a]=1进行标记，问题就可以解决了（不要忘记多加几个字符防止hash冲突）。 ----- 接下来就是更高级的用法了，map里面存结构体。 ```cpp struct node{ string a; int fa; bool operator <(const node &b)const{ if(a!=b.a)return a<b.a; return fa<b.fa; } }; map<node,int>pos; ``` 值得注意的是，map存结构体重载小于号，一定要完全重载，比如说上面的代码中如果直接写 **return fa<b.fa** 就会出错。 ----- 如果map中存了string，map内部会按照字典序排序，那么怎么按照顺序访问呢？按照惯例，map也又迭代器，下面是演示方法。 ```cpp #include<bits/stdc++.h> using namespace std; map<string,int>pos; map<string,int>::iterator it; string a; int main(){ a="zryabc"; pos[a]=1; a="rkj"; pos[a]=2; a="czjxyz"; pos[a]=3; a="wangZY"; pos[a]=4; for(it=pos.begin();it!=pos.end();it++){ cout<< it->first ; putchar(' '); cout<< it->second ; putchar('\n'); } return 0; } ``` ----- _ 写的比较乱=w= ，应该还能勉强看看QuQ