STL map 的总结

STL map在算法竞赛中总是用于hash，将两个有大小关系的数据结构关联起来。基本上相当于set< pair<> >。
我们以字符串到int的map为例

map<string, int> mp;

插入时

string str;
int key;
cin>>str>>key;
mp.insert(make_pair(str, key));
mp[str] = key;

就以上来说这两种插入方式的结果是没有区别的，但是后者更慢。可是如果要重复插入，那么前者是无效的。
map的三种删除方式和set基本相同(详见上一篇博文)

mp.erase(key);
mp.erase(mp.find(key));
mp.erase(mp.lower_bound(key1), mp.lower_bound(key2));

map的查找也是set 的哪几种方式

S.find(key);        //返回迭代器
S.count(key);       //返回1或0，表示是存在x.first == key
S.lower_bound(key); //返回第一个first关键字大于等于key的迭代器
S.upper_bound(key); //返回第一个first关键字大于key的迭代器
S.equal_range(key); //返回一个pair<set::iterator, set::iterator> 分别是S.lower_bound(key)和S.upper_bound(key)的返回值。

mp仅仅作为hash方法来使用的话是很容易的，可以大量简化我们的代码
但是要考虑时间复杂度的问题。