map类的介绍
map的声明如下，Key是map底层关键字的类型，T是map底层value的类型。set默认要求Key支持小于比较，如果不支持或者需要的情况下我们可以自行传入仿函数，map底层存储数据的内存是从空间申请来的。一般情况下，我们是不需要传后两个参数的。map的底层是由红黑树实现的，增删改查的效率是logN，迭代器遍历走的是中序，所以Key是有序排列的
红黑树是平衡二叉搜索树
template < class Key, // map::key_type
class T, // map::mapped_type
class Compare = less<Key>, // map::key_compare
class Alloc = allocator<pair<const Key,T> > // map::allocator_typepair类型介绍
红黑树的节点类型是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）,可以看作将两个元素直接转化为pair
m.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冗余，[]就只能⽀ 持插⼊了，不能⽀持修改。
