map/multimap：由红黑树实现，元素为键值-实值。
一：特点
1.map为单重映射，键值和实值是一对一的关系，不允许重复键值；multimap是多重映射，允许相同键值，一个键值可以对应多个实值。
2.具有自动排序功能，所有map里的数据都是有序的。
3.map提供的[]操作符的重载；multimap未提供。
二：定义与初始化
map<int, int> m1;map<int, int, less<int>> m2; map<int, int, greater<int>> m3;multimap<int, int> m4;multimap<int, int, less<int>> m5;multimap<int, int, greater<int>> m6;三：基本操作
map<int, int> m1;
map<int, int, less<int>> m2;
map<int, int, greater<int>> m3;multimap<int, int> m4;
multimap<int, int, less<int>> m5;
multimap<int, int, greater<int>> m6;//插入
m3.insert(pair<int, int>(1, 1));
m3.insert(make_pair(3, 4));
m3.insert(map<int, int>::value_type(2, 6));
m3[4] = 8;//仅适用于map,不适用于multimap//查询
m3[2];//表示key为2
m3.at(2);//表示key为2
//查找find: 如果找到查找的键值，则返回该值的迭代器位置，否则返回集合最后一个元素后一个位置的迭代器，即end();
map<int, int>::iterator it;
it = m3.find(3);
if (it != m3.end())
{cout << it->first << endl;cout << it->second << endl;
}
else
{cout << "not find" << endl;
}//删除
m3.erase(4);//删除键为4的键值对
m3.erase(m3.begin(), m3.begin()++);//删除区间
m3.erase(m3.begin());//删除位置m3.size();
m3.max_size();
m3.count(3);统计键值的个数，为0或者1，multimap可大于1
m3.clear();四：自定义排序规则
struct myoper
{//自定义排序规则bool operator()(string s1, string s2) const{return s1.length() < s2.length();}
};
int main()
{map<string, int, myoper> m;m.insert(make_pair("jinwang", 99));m.insert(make_pair("zhangsan", 88));m.insert(make_pair("wuliu", 77));map<string, int>::iterator it = m.begin();while (it != m.end()){cout << it->first << ":" << it->second << endl;it++;}return 0;
}/*
*output:
wuliu:77
jinwang:99
zhangsan:88
*/五：总结
1.时间复杂度：查询，插入，删除都为O(log(n))；
2.存储数据字典，并且要求方便地根据 key 找到 value，一对一的情况使用 map，一对多的情况使用 multimap。