超详细介绍map（multimap）的使用

map类的介绍

        map的声明如下，Key是map底层关键字的类型，T是map底层value的类型。set默认要求Key支持小于比较，如果不支持或者需要的情况下我们可以自行传入仿函数，map底层存储数据的内存是从空间申请来的。一般情况下，我们是不需要传后两个参数的。map的底层是由红黑树实现的，增删改查的效率是logN，迭代器遍历走的是中序，所以Key是有序排列的

        红黑树是平衡二叉搜索树

template < class Key,                                     // map::key_typeclass T,                                       // map::mapped_typeclass Compare = less<Key>,                     // map::key_compareclass Alloc = allocator<pair<const Key,T> >    // map::allocator_type

pair类型介绍

        红黑树的节点类型是pair类型，使用pair<Key,T>存储数据

typedef pair<const Key, T> value_type;
template <class T1, class T2>
struct pair 
{typedef T1 first_type;typedef T2 second_type;T1 first;T2 second;pair(): first(T1()), second(T2 ()){}pair(const T1& a, const T2& b): first(a), second(b){}template<class U, class V> pair (const pair<U,V>& pr): first(pr.first), second(pr.second){}
};
template <class T1,class T2>
inline pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}

map的增删查

#include<iostream>
#include<map>
using namespace std;int main()
{map<string, string> m;//插入有名pair（方式一）pair<string, string> s("first", "第一个");m.insert(s);//插入无名piar（方式二）m.insert(pair<string, string>("second", "第二个"));//调用make_pair函数m.insert(make_pair("third", "第三个"));//make_pair函数，其功能为，将两个参数构造成一个pair并返回//隐式类型转化（c++11）,可以看作将两个元素直接转化为pairm.insert({ "auto", "自动的" });// initializer_list构造map<string, string> dict = { {"left", "左边"}, {"right", "右边"},
{"insert", "插⼊"},{ "string", "字符串" } };//map的遍历//pair并没有重载流插入与流提取，故而下面的输出我们只能通过输出成员变量cout << "遍历一：" << endl;for (auto& e : m){cout << e.first << "," << e.second << " ";}cout << endl;cout << "遍历二：" << endl;auto it = m.begin();while (it != m.end()){cout << it->first << "," <<it->second<< " ";it++;}cout << endl;//map的查找string str;cin >> str;auto pos = m.find(str);if (pos != m.end()){cout << "找到了：" << pos->first << "," << pos->second << endl;}else{cout << "不存在！"<<endl;}//map的删除cout << "删除一：" << endl;cin >> str;m.erase(str);for (auto& e : m){cout << e.first << "," << e.second << " ";}cout << endl;cout << "删除二：" << endl;cin >> str;auto pos0 = m.find(str);m.erase(pos0);for (auto& e : m){cout << e.first << "," << e.second << " ";}cout << endl;cout << "删除三：" << endl;//iterator  erase (const_iterator first, const_iterator last);//删除一段区间，给出左边迭代器和右边迭代器，函数将会删除这段区间，//一般搭配 lower_bound  upper_bound 使用
}

        

map的迭代器和[]功能

·        

        operator[]的功能：传入Key值会返回value值（传入pair的first，会返回pair的second）operator[]具有：插入、查找、修改的功能。需要注意的是，如果当传入的Key值本来就不存在map中时，这个值将会被插入map

        而operator[]之所以拥有这些功能与其底层（insert）的实现有关

        下面我们来仔细看看insert函数 

        insert的返回值为一个pair：

        当map中没有这个元素，insert插入成功并返回 pair<成功插入位置的迭代器，true>

        反之当map中有这个元素，insert插入失败并返回  pair<已经存在的值的迭代器，false>

具体实例：

#include<iostream>
#include<map>
using namespace std;int main()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };  // 使用正确汉字 map<string, int> countMap;//普通统计水果数量的方式for (auto& e : arr){auto pos=countMap.find(e);if (pos != countMap.end()){pos->second++;}else{countMap.insert({ e,1 });}}for (auto& e : countMap){cout << e.first << "," << e.second<<" ";}cout << endl;//使用operator[]for (auto& e : arr){countMap[e]++;}//若e存在则插入失败，operator[]返回value，再让其+1//若e不存在则插入成功{e，0}，operator[]返回value，再让其+1 》{e,1}for (auto& e : countMap){cout << e.first << "," << e.second << " ";}cout << endl;}

#include<iostream>
#include<map>
using namespace std;int main()
{map<string, string> dict;dict.insert(make_pair("sort", "排序"));// key不存在-> 插⼊ {"insert", string()} dict["insert"];// key不存在-> 插⼊+修改 dict["left"] = "左边";// key已经存在-> 修改 dict["left"] = "左边、剩余";// key存在->查找 cout << dict["left"] << endl;return 0;
}

multimap和map的差异

        multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如 find时，有多个key，返回中序第⼀个。其次就是multimap不⽀持[]，因为⽀持key冗余，[]就只能⽀ 持插⼊了，不能⽀持修改。