柒葉灬 的博客

柒葉灬 的博客

c++ STL 之 map

posted on 2018-08-22 20:02:09 | under STL |

map的使用方法(蒟蒻的总结

  • 1、map所需要的空间需要注意一下,是普通数组空间的好几倍,访问时间复杂度是log级别的。

  • 2、map很强大,可以在里面放几乎所有东西,什么string,结构体(要重载小于号)都可以存map里面,比如说pos["abc"]=233。

  • 3、虽然说map的访问是log级别的,但是如果存太长的string,访问速度也超级慢,(当初写“文件查询”直接存所有父亲目录,T的不要不要的,而且还不知道为什么T)。


    要使用map必须加上头文件 #include<map> 和 using namespace std
    #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;
    但一般我们会这么写 :

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里面存结构体。

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也又迭代器,下面是演示方法。

#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