前几天写一道双向bfs的题用了一下map来判重被坑了, 更新一下万年未更的博客来记录一下…
首先map的主要功能是维护某种类型的某个key与某种类型的某个value一一对应的映射关系.
顺便提一下, map的内部实现是一颗红黑树.
通俗的讲, map让数组的下标可以取任何类型的变量.
比如:
[code]map<int,int> mp;//普通的int数组[/code]
[code]map<string,int> mp;//下标为字符串的int数组[/code]
例子:像操作数组一样操作map
- #include<cstdio>
- #include<map>
- using namespace std;
- map<string,string> wife;
- int main()
- {
- wife[“zhangsan”]=”lisi”;
- wife[“aaa”]=”bbb”;
- //上面实际上新建了两个map元素(赋初值)
- printf(“%s\n”,wife[“aaa”]);//引用一个map中的元素
- return 0;
- }
这里要注意的点:
map实际上重载了'[‘ , ‘]’ 运算符, 重载为map的查找操作.
mp[key]会返回Key(键值)为key的元素的value(值).(line 10)
数组越界会RE, 那么map的key值越界呢?
如果不存在键值为key的元素, 则会自动新建一个, 值是随机的, 返回指向这个新元素的迭代器.(line 7,8给新建的元素赋了值)
所以这样就引出了一个问题(巨大的误区):怎样判断mp[key]存不存在:
例子:错误写法
- #include<cstdio>
- #include<map>
- using namespace std;
- map<string,string> wife;
- int main()
- {
- wife[“zhangsan”]=”lisi”;
- wife[“aaa”]=”bbb”;
- if(wife[“aaa”]!=””) printf(“aaa has a wife”);
- if(wife[“ccc”]!=””) printf(“ccc has a wife”);
- return 0;
- }
在执行line 9时并不会发生什么, 因为wife[“aaa”]是存在的.
然而在line 10就会出bug, 因为找不到wife[“ccc”], 它返回了一个迭代器, 然后就炸了.
例子:正确写法
- #include<cstdio>
- #include<map>
- using namespace std;
- map<string,string> wife;
- int main()
- {
- wife[“zhangsan”]=”lisi”;
- wife[“aaa”]=”bbb”;
- if(mp.count(“aaa”)==1) printf(“aaa has a wife”);
- if(mp.find(“ccc”)!=mp.end()) printf(“ccc has a wife”);
- return 0;
- }
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中删除操作应该用得比较少…
最新评论