C++STL map的使用注意事项

前几天写一道双向bfs的题用了一下map来判重被坑了, 更新一下万年未更的博客来记录一下…

首先map的主要功能是维护某种类型的某个key与某种类型的某个value一一对应的映射关系.

顺便提一下, map的内部实现是一颗红黑树.

通俗的讲, map让数组的下标可以取任何类型的变量.

比如:

[code]map<int,int> mp;//普通的int数组[/code]

[code]map<string,int> mp;//下标为字符串的int数组[/code]

例子:像操作数组一样操作map

1. #include<cstdio>
2. #include<map>
3. using namespace std;
4. map<string,string> wife;
5. int main()
6. {
7.     wife[“zhangsan”]=”lisi”;
8.     wife[“aaa”]=”bbb”;
9.     //上面实际上新建了两个map元素(赋初值)
10.     printf(“%s\n”,wife[“aaa”]);//引用一个map中的元素
11.     return 0;
12. }

这里要注意的点:

map实际上重载了'[‘ , ‘]’ 运算符, 重载为map的查找操作.

mp[key]会返回Key(键值)为key的元素的value(值).(line 10)

数组越界会RE, 那么map的key值越界呢?

如果不存在键值为key的元素, 则会自动新建一个, 值是随机的, 返回指向这个新元素的迭代器.(line 7,8给新建的元素赋了值)

所以这样就引出了一个问题(巨大的误区):怎样判断mp[key]存不存在:

例子:错误写法

1. #include<cstdio>
2. #include<map>
3. using namespace std;
4. map<string,string> wife;
5. int main()
6. {
7.     wife[“zhangsan”]=”lisi”;
8.     wife[“aaa”]=”bbb”;
9.     if(wife[“aaa”]!=””) printf(“aaa has a wife”);
10.     if(wife[“ccc”]!=””) printf(“ccc has a wife”);
11.     return 0;
12. }

在执行line 9时并不会发生什么, 因为wife[“aaa”]是存在的.

然而在line 10就会出bug, 因为找不到wife[“ccc”], 它返回了一个迭代器, 然后就炸了.

例子:正确写法

1. #include<cstdio>
2. #include<map>
3. using namespace std;
4. map<string,string> wife;
5. int main()
6. {
7.     wife[“zhangsan”]=”lisi”;
8.     wife[“aaa”]=”bbb”;
9.     if(mp.count(“aaa”)==1) printf(“aaa has a wife”);
10.     if(mp.find(“ccc”)!=mp.end()) printf(“ccc has a wife”);
11.     return 0;
12. }

mp.count(key)会返回mp中键值为key的元素个数, 由于map是一一对应的, 返回值只可能为0/1, 可据此判断mp[key]的存在与否

mp.find(key)会返回指向mp[key]的迭代器, 若不存在则返回mp.end()(一个空的迭代器)

你问我迭代器是啥?就是一个类似于指针的玩意.

另外一个要注意地方:如何删除map中的元素

直接map[key]=0肯定是不行的.

正确的方法

erase(iterator it);(删掉迭代器it指向的元素)

erase(const Key &key);(删掉mp[key])

mp.clear();(清空mp)

不过OI中删除操作应该用得比较少…