【C++】map和multimap的常用接口详解

map和multimap的文档：<map> - C++ Reference

1.map类的介绍

map 有两个模板参数，是 key/value的场景。

这里的Key就是key，T就是value，命名不同而已。
map默认要求Key⽀持⼩于⽐较（升序），如果不⽀持或者需要的话可以⾃⾏实现仿函数传给第⼆个模版参数，map底层存储数据的内存是从空间配置器申请的。⼀般情况下，我们都不需要传后两个模版参数。
map底层是⽤红⿊树实现，增删查改效率是 O(logN) ，迭代器遍历是⾛的中序，所以是按key有序顺序遍历的，不是按value。

我们打开map的文档介绍会发现和set的一些接口大差不差，但值得注意的是，map的value_type不同于set了。

所以在介绍map的接口之前我们先说一下这个value_type。

2.pair类型介绍

从文档我们可以看到，这里的value_type是一个叫pair的东西。

和set对比一下。

set的 key_type 和 value_type是一样的，就是key，map的key_type是key，value_type是pair。

map底层的红⿊树节点中的数据，使⽤pair<Key, T>存储键值对数据。我们来看一下这个pair。在文档就能查到。

pair是函数模板，有两个模板参数，里面有两个成员，first和second。

first就是T1，second就是T2。pair的底层实现这里有一份，感兴趣可以看一下。

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));
}

简单来说就是我们的key传过去就是pair里的first，传的value就是这里的second。

在【C++】二叉搜索树（搜索二叉树）这篇博客中，我们自己实现key/value场景的时候，要分别传key和value，两个模板参数是分开的。拿insert来举例。

有了pair就可以理解为，原本分开的key和value“捆绑”在一起了，多封了一层。

3.map增删查改

前面提到了insert那就从insert开始介绍吧。

3.1 insert增和改

这就是插入一个pair，插入pair有三种方法。

map<string, string> m;//插入有名对象
pair<string, string> word1("hello", "你好");
m.insert(word1);

//插入匿名对象
m.insert(pair<string, string>("eat", "吃"));

//调用make_pair
m.insert(make_pair("bad", "坏的"));

前两种都比较好理解，来看第三个，调用make_pair函数模板，这个函数在文档里可以找到。

make_pair这个函数模板大概就长这样，就是因为pair写起来要写模板参数，像前面两种写法，比较多比较长，就有了这个函数模板。传两个值给make_pair，然后这个模板推导对应的类型，返回一个pair对象。

还有就是用大括号括起来，这里走的是隐式类型转换，C++11之后支持多参数的转换，如下。

m.insert( { "cat", "猫" } );

这4种方式都可以，用的最多的还是花括号的写法。

insert的返回值

insert的返回值也是pair，这里就出现两个pair，一个是前面说过的，pair存的是key/value，insert的返回值的pair存的是一个迭代器和bool值，因为insert可能插入成功，也可能失败。

并且注意这句话，这个first这个迭代器要么指向新插入的元素，要么是指向和key相等的元素。

总结一下就是:

插入成功，就返回 pair<新插入值所在迭代器，true> ，
插入失败，就返回pair<已经存在的和key相等的值所在迭代器，false>。

这也意味着，insert不仅可以插入数据，还能查找数据。这是为了operator[]做准备。

列表插⼊，已经在容器中存在的值不会插⼊ 。

如果要同时插入多组值，也是可以用花括号，插入列表值。

m.insert({{"hello", "你好"},  {"eat", "吃"}, {"bad", "坏的"}, {"cat", "猫"}});

我们可以把插入的这些值打印出来。但是这里的迭代器不同以前。

C++不支持两个值同时返回，并且pair没有支持流插入和流提取，所以下面的写法是错误的。

auto it = m.begin();
while (it != m.end())
{cout << *it << endl; //错误写法it++;
}
cout << endl;

最简单的写法如下。

cout << it->first << ":" << it->second << endl;

顺序是按key比较的，字符串就是按ASCII码比。

我们也可以通过 . 来取pair里的数据,但是->用的还是最多的。

cout << (*it).first << ":" << (*it).second << endl;

假如说我现在要插入key相同但是value不同的值，如下。

m.insert({"cat", "猫"}); //原来的
m.insert({ "cat", "猫科动物"}); //新插入的

key相等但是value不相等，会不会更新这个value？

是不会把旧的覆盖掉的。插入的时候只看key是否相等，不看value，而map不允许冗余，multimap才允许冗余，这里相当于插入失败了。

虽然key不支持修改，但是这里的value是支持修改的。

auto it = m.begin();
while (it != m.end())
{//it->first += 'z'; //不可修改it->second += 'z';//可修改cout << it->first << ":" << it->second << endl;it++;
}
cout << endl;

3.2 erase

删除有三个版本：删除⼀个迭代器位置的值；删除k，k存在返回0，存在返回1；删除⼀段迭代器区间的值。删除和插入一样，只与key有关，和value没关系。

map<string, string> m = { {"hello", "你好"},  {"eat", "吃"},{"bad", "坏的"}, {"cat", "猫"} };
auto it = m.begin();
while (it != m.end())
{cout << it->first << ":" << it->second << endl;it++;
}
cout << endl;

给值删除

m.erase("cat"); 
it = m.begin();
while (it != m.end())
{cout << it->first << ":" << it->second << endl;it++;
}

给迭代器删除。

m.erase(m.begin()); 
it = m.begin();
while (it != m.end())
{cout << it->first << ":" << it->second << endl;it++;
}

3.3 其他常用接口

以下四个接口，在set详细介绍过，且与set的这些接口用法差不多，不了解的可移步至：【C++】set和multiset的常用接口详解

查找k，返回k所在的迭代器，没有找到返回end() 。

查找k，返回k的个数。

返回⼤于等于k位置的迭代器。

返回⼤于k位置的迭代器。

equal_range这个接口在set中没做介绍，因为它的返回值是pair。

就是把与k相等的的左闭右开区间返回，这主要是用在multimap的，因为multimap存在多个相同的key。

4.map的迭代器和[]功能

先把我们在搜索二叉树的一个统计水果出现次数的例子拿过来。

int main()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜","苹果", "香蕉", "苹果", "香蕉" };map<string, int> countMap;for (const auto& str : arr){auto ret = countMap.find(str);if (ret == countMap.end()){countMap.insert({ str, 1 });}else{ret->second++;}}for (const auto& e : countMap){cout << e.first << ":" << e.second << endl;}return 0;
}

利⽤find和iterator修改功能，统计水果出现的次数。

先查找⽔果在不在map中：

不在，说明⽔果第⼀次出现，则插⼊{⽔果, 1}
在，则查找到的节点中⽔果对应的次数，然后++

但是有了[ ]，就只需要一句话搞定。

for (const auto& str : arr)
{countMap[str]++; //用[]
}

来看这个operator[]。

简单来说，就是给一个map的first，也就是key，返回他的second，也就是value。这个operator[]同时具有插入，查找，修改的功能。在文档里写了这个operator[]的底层。

可以理解为[]就是调用上面这个东西，也能说明operator[]底层是用insert实现的。仔细看前面说到的insert的返回值，insert插⼊失败时充当了查找的功能，正是因为这⼀点，insert可以⽤来实现operator[]。

上面的那句代码比较复杂，这里展开后，如下。

// operator的内部实现
mapped_type& operator[] (const key_type& k)
{pair<iterator, bool> ret = insert({ k, mapped_type() });iterator it = ret.first;return it->second;
}

如果k不在map中，insert会插⼊k和mapped_type默认值（可以是相应类型的默认构造），同时[]返回结点中存mapped_type值的引⽤，那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊+修改功能。
如果k在map中，insert会插⼊失败，但是insert返回pair对象的first是指向key结点的迭代器，返回值同时[]返回结点中存储mapped_type值的引⽤，所以[]具备了查找+修改的功能。

结合上面的代码，接可以理解operator[]是怎么用的了。

比如说第一次插入西瓜，西瓜没出现过，会插入成功。此时insert会插⼊k和mapped_type默认值，mapped_type是int，int默认值是0。

插入成功，就返回 pair<新插入值所在迭代器，true> 。

ret的first是西瓜的迭代器，ret的second是这个bool值，所以这句话是把西瓜的迭代器取出来。

此时 it 就是西瓜的迭代器，it的first是string，就是这个“西瓜”，就是key，it的second是int，就是value。返回的就是这个it的second。返回的这个second再++。

countMap[str]++;

再举一个插入失败的例子。

比如说第2次插入苹果的时候，会插入失败，因为苹果已经存在过了，此时的mapped_type是1。

插入失败时，返回的就是 pair<已经存在的和key相等的值所在迭代器，false> ，所以这里会返回苹果的迭代器，false。

ret的first是苹果的迭代器，ret的second是这个bool值，所以这句话是把苹果的迭代器取出来。

返回值是it的second，it就是苹果的迭代器，苹果的first是string，就是这个“苹果”，就是key，苹果的second是int，就是value。返回的这个second再++。

countMap[str]++;

所以这句话就是当str不存在时，充当插入+修改的功能，当str存在时，充当查找+修改的功能。

方括号的几个功能我们再说一下。

map<string, string> mymap;
mymap.insert({ "hello", "你好" });//key不存在 -> 插入
mymap["cat"];

当key不存在的时候，并且不进行修改动作，只是插入，用[]的话会直接插入。

并且新插入的这个key所对应的value是空串，因为string的默认构造就是空串。

map<string, string> mymap;
mymap.insert({ "hello", "你好" });//key不存在 -> 插入
mymap["cat"]; //key不存在 -> 插入+修改
mymap["right"] = "右边";

当key不存在的时候，并且进行修改动作，这个[]的功能就是插入+修改。

新插入的这个key所对应的value就是修改的那个值。

map<string, string> mymap;
mymap.insert({ "hello", "你好" });//key不存在 -> 插入
mymap["cat"]; //key不存在 -> 插入+修改
mymap["right"] = "右边";//key存在 -> 修改
mymap["right"] = "正确的";

当key存在的时候，并且进行修改动作，这个[]的功能就是修改。

此时的key所对应的value就是修改后的那个值。

[]可以用来查找。

//查找不存在的key
cout << mymap["left"] << endl;
//查找存在的key
cout << mymap["right"] << endl;

当我们查找存在的key时，打印相应的value，但是查找不存咋的key时，打印的是空串。因为这个key不存在，就会把key插入。

所以用[]来查找的话要谨慎，一不小心就误操作了，一般不建议用[]来查找。

5. map和multimap的区别

multimap和map的使⽤基本完全类似，主要区别点在于multimap⽀持关键值key冗余，那么

insert/find/count/erase都围绕着⽀持关键值key冗余有所差异，这⾥跟set和multiset完全⼀样，⽐如insert的时候，重复的值 都能插入； find时，有多个key，返回 中序第⼀个； 删除key的话是 删除所有的key； 其次就是multimap 不⽀持[] ，因为⽀持key冗余，[]就只能⽀持插⼊了，不能⽀持修改。

equal_range这个接口在multimap里就比较好用了。

int main()
{multimap<char, int> mymm;mymm.insert(pair<char, int>('a', 10));mymm.insert(pair<char, int>('b', 20));mymm.insert(pair<char, int>('b', 30));mymm.insert(pair<char, int>('b', 40));mymm.insert(pair<char, int>('c', 50));mymm.insert(pair<char, int>('c', 60));mymm.insert(pair<char, int>('d', 60));cout << "mymm contains:" << endl;for (char ch = 'a'; ch <= 'd'; ch++){pair <multimap<char, int>::iterator, multimap<char, int>::iterator> ret;ret = mymm.equal_range(ch);cout << ch << " =>";for (multimap<char, int>::iterator it = ret.first; it != ret.second; ++it)cout << ' ' << it->second;cout << endl;}return 0;
}

给equal_range传一个key过去，equal_range返回与key相等的左开右闭迭代器区间。