C++｜STL map的operator[]的底层实现及其使用

首先我们都知道STL中的map的operator[]可以通过key值找到对应的value值的：

<code>#include <iostream>
#include /<iostream>/<code>

这里我们要了解map模板类operator[]的底层实现，首先要了解一下map模板类的数据成员和成员函数。（参考：http://www.cplusplus.com/reference/map/map/）

如：

<code>key_type： The first template parameter (Key)
mapped_type： The second template parameter (T)
value_type： pair<const> 

operator[]()：Access element (public member function )
insert()：Insert elements (public member function )/<const>/<code>

其中operator[]()的实现原型：

（参考：http://www.cplusplus.com/reference/map/map/operator[]/）

<code>mapped_type& operator[] (const key_type& k)
{
    return (*((this->insert(make_pair(k,mapped_type()))).first)).second;
}/<code>

那我们可以发现其实operator[]底层是用insert()来实现的。

（参考：http://www.cplusplus.com/reference/map/map/operator[]/）

那么inset()的返回值又是什么呢？我们一起来看看insert()的函数原型：

<code>pair<iterator> insert (const value_type& val);/<iterator>/<code>

cplusplus网站对insert的返回值是这样解释的：

The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element with an equivalent key in the map. The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent key already existed.

inset的返回值其实是一个pair，这个pair的key值其实是一个迭代器，这个迭代器是指向新插入这个位置的value_type，value值其实是一个bool值，表示插入成功还是失败，原来没有这个key值插入会成功返回true，已经存在这个key值插入会失败，返回false。

我们再回头看看这个operator[]的底层实现：

make_pair(k,mapped_type())（红色框框）：表示创建了一个pair，这个pair的key值为传参传过来的k，value是一个mapped_type的value，暂时为空待定。

insert(make_pair(k,mapped_type()))（绿色框框）：调用insert插入这个pair。插入这个pair会返回一个pair。pair的第一个值就是这个位置的迭代器，但是因为这个key值已经存在了，因此pair的value为false。

(this->insert(make_pair(k,mapped_type()))).first（粉色框框）：this指针取到这个pair的first，就是我们刚刚看到的insert的返回值pair的key值，也就是插入位置的迭代器。

最后解引用迭代器之后再取到这个位置pair的second值，也就是这个位置的value值。然后函数的返回值为mapped_type的引用，因为是引用，所以可以做为左值而更新其value。

综上所述，operator[]返回的是这个key值所对应的value的引用。因此operator[]可以通过key值找到对应的value值，然后对这个value值进行修改操作。

举个例子：

<code>map<string> dict;
dict.insert({ "left", "左边" });
dict["left"] = "剩余";/<string>/<code>

“left”这个key值已经存在，因此insert返回的是这个位置的迭代器和一个false（false是因为key值存在插入失败），取到这个迭代器，然后解引用取到迭代器的second，也就是value并返回value的引用，因此dict["left"]返回的就是"左边"这个字符串的引用，那么在执行赋值操作，也就是改变了这个“left”所对应的value值，此时“left”的value值就变成了“剩余”。

那么operator[]又可以完成数据的插入，这又是怎么实现的呢？

我们继续分析operator[]的底层实现。

当我们传过来的key值是map里没有的，那么这里创建了一个pair，这个pair的key值就是传过来的key值，但是此时这里的mapped_type的value，暂时为空待定。调用了insert，因为这个key值没有，所以完成了插入，insert的返回值为新插入这个位置的迭代器和true（true表示插入成功），然后取到这个迭代器，解引用之后拿到这个key值的value（此时value值为空），返回的就是这个空的value。

再举个例子：

<code>map<string> dict;
dict["banana"];/<string>/<code>

如上就是插入了一个key为“banana”，value为“\\0”的一个pair。

<code>dict["key"] = "关键字";/<code>

如上，首先经过dict["key"]之后，就成功插入了一个key值为“key”，value为“\\0”的一个pair，返回值是“\\0”的引用，然后再赋值操作，也就是将“\\0”变成了“关键字”，这样就完成了一个pair的插入。

总结一下，operator[]可以查找到对应key值的value，如果key值没有的话，也可以进行插入操作。

实例：统计每种水果出现的次数。

“苹果”, “苹果”, “梨”, “苹果”, “香蕉”, “梨”, “香蕉”, “香蕉”, “苹果”, "西瓜"

有以下三种解决方法：

方法一：

定义一个map，类型为map<string> ，key值就是水果（不允许重复），value值就可以记录出现的次数。/<string>

去寻找字符串在不在这个map中，如果这个水果在，那么直接给这个pair的second++，如果不在，就插入这个水果，把second设置为1。

<code>string str[] = { "苹果", "苹果", "梨", "苹果", "香蕉", "梨", "香蕉", "香蕉", "苹果", "西瓜" };
map<string> count_map;
for (const auto &s : str)
{
\tauto tmp = count_map.find(s);
\tif (tmp != count_map.end())
\t{
\t\ttmp->second++;
\t}
\telse
\t{
\t\tcount_map.insert({ s, 1 });//返回的是pair/<string>/<code>

方法二：

定义一个map，类型为map<string> ，key值就是水果（不允许重复），value值就可以记录出现的次数。/<string>

因为insert的返回值中value是一个bool，表示插入成功还是失败，所以我们直接插入这个水果和1（表示这个水果出现了一次）。我们可以通过这个bool值判断这个水果在不在这个map里。如果在，那么insert的返回值的value是一个false，那么直接利用inset的返回值中的key（对应位置的迭代器）找到对应位置的value，直接++即可。如果不在那么insert的返回值的value是一个true，此时就完后了这个水果和1次的插入。

<code>string str[] = { "苹果", "苹果", "梨", "苹果", "香蕉", "梨", "香蕉", "香蕉", "苹果", "西瓜" };
map<string> count_map;
for (const auto &s : str)
{
  // insert()的返回值是一个pair
\tpair/<string>/<code>

方法三：

定义一个map，类型为map<string> ，key值就是水果（不允许重复），value值就可以记录出现的次数。/<string>

我们可以利用这个operator[]来解决这个问题，代码非常简单。

直接遍历这个水果字符串数组，然后调用operator[]，因为operator[]有就返回value的引用，没有就插入之后返回value的引用，那么当遍历这些水果的时候，如果这个水果在，那么直接给value++，如果这个水果不在，那么返回的是0的引用，直接++就变成了1，表示出现一次，后续在插入同样的水果时，插入失败，直接给value++，逻辑也没有任何问题，因此这个方法最为简单，推荐~

<code>string str[] = { "苹果", "苹果", "梨", "苹果", "香蕉", "梨", "香蕉", "香蕉", "苹果", "西瓜" };
map<string> count_map;
for (auto s : str)
{
\tcount_map[s]++;
}
for (const auto &e : count_map)
{
\tcout << e.first << ":" << e.second << endl;
}/<string>/<code>

三种方法都可以正确运行，结果如下：

<code>梨:2
苹果:4
西瓜:1
香蕉:3/<code>

ref

https://blog.csdn.net/ETalien_/article/details/89442131

-End-

閱讀更多 小智雅匯 的文章

關鍵字: 引用 遍历 水果