1.1 map 和 multimap 参考文档

官方文档链接：https://legacy.cplusplus.com/reference/map/

1.2 map 类的介绍

先来看 map 的声明：

template < class Key,                                   // map::key_type
           class T,                                      // map::mapped_type
           class Compare = less,                    // map::key_compare
           class Alloc = allocator > // map::allocator_type
           > class map;

这里 Key 是关键字类型，T 是值（value）类型。map 默认要求 Key 支持小于比较运算符，如果不支持或者需要自定义比较规则，可以自行实现仿函数并传给第二个模板参数。至于底层存储数据的内存，则从空间配置器中申请。一般情况下，我们都不需要传递后两个模板参数。

map 底层采用红黑树实现，增删查改的时间复杂度均为 O(logN)。迭代器遍历走的是中序，因此会按照 Key 的升序顺序进行遍历。

1.3 pair 类型介绍

在讲解 map 的使用前，先来认识一下 pair 类型，因为 map 正是用 pair 来存储 key 和 value 的。

pair 是一个类模板，它将一对键值对耦合在一起，包含两个模板参数：

template  struct pair;

它内部有两个成员：first 和 second；first 是 T1 类型，second 是 T2 类型。

pair 的底层实现大致如下：

template 
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
    pair(const pair& pr) : first(pr.first), second(pr.second) {}
};

在 map 中，我们插入数据时传入的都是 pair 对象，其中 Key 是 const Key，T 是 value，即 pair。也就是说，first 代表 key，second 代表 value。

1.4 map 的构造

map 的构造我们关注以下几个接口即可。map 支持正向和反向迭代遍历，遍历默认按 key 的升序顺序，因为底层是二叉搜索树，迭代器遍历走的是中序；支持迭代器就意味着支持范围 for 循环。map 支持修改 value 数据，但不支持修改 key 数据——修改关键字数据会破坏底层搜索树的结构。

// empty (1) 无参默认构造
explicit map(const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

// range (2) 迭代器区间构造
template 
map(InputIterator first, InputIterator last,
    const key_compare& comp = key_compare(),
    const allocator_type & = allocator_type());

// copy (3) 拷贝构造
map(const map& x);

// initializer list (5) initializer 列表构造
map(initializer_list il,
    const key_compare& comp = key_compare(),
    const allocator_type& alloc = allocator_type());

// 迭代器是一个双向迭代器
iterator -> a bidirectional iterator to const value_type

// 正向迭代器
iterator begin();
iterator end();
// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();

1.5 map 的插入

1.5.1 map 的插入方法

map 的插入方式有多种，例如我们创建一个字典：

int main()
{
    map dict;

    // 法一：插入有名 pair 对象
    pair kv1("left", "左边");
    dict.insert(kv1);
        
    // 法二：插入匿名 pair 对象
    dict.insert(pair("right", "右边"));

    // 法三：调用 make_pair 函数
    dict.insert(make_pair("insert", "插入"));
    
    // 法四：C++11 后支持多参数的隐式类型转换
    dict.insert({ "string", "字符串" });

    return 0;
}

很明显，法四是最简洁的写法。

1.5.2 验证

用迭代器遍历一遍：

map::iterator it = dict.begin();
while (it != dict.end())
{
    // pair 不支持流插入和流提取
    cout << (*it).first << ":" << it->second << endl;
    ++it;
}

通过迭代器遍历，我们也能清楚为什么 map 的 insert 返回值是 pair，而不是把 key 和 value 分开返回。因为 C++ 只支持返回一个值。如果将 key 和 value 分开，返回 key 还是 value 呢？都不合适。如何才能同时返回 key 和 value？将它们用一个结构体封装起来，返回一个结构体不就可以了。

如果我们插入：

pair kv1("left", "叶子");

left 的键值对会被修改吗？不会。插入时只会判断 key 是否相等，如果相等则插入失败，与 value 无关。

1.5.3 再探 pair

有细心的小伙伴可能会发现：insert 插入的类型是 value_type，而 value_type 是 pair。

但是上面例子我们插入的都是 pair 类型。模板参数不同，它们就是不同的类型，就像 vector 和 vector，虽然都是同一个模板，但模板参数不同，就不是同一个类型。那为什么 pair 和 pair 是两个完全不同的类型，我们还能插入成功呢？

玄机就在于 pair 的构造函数上。

更准确地说，问题出现在 pair 的拷贝构造函数上。pair 的拷贝构造不是写死的，而是写成了一个模板。前面我们说过：类模板中的函数可以继续是函数模板。

一起来理解一下：insert 需要传递的是 pair 类型，但现在我们传的是 pair。因此我们要用传递的 pair 类型去构造一个 pair 类型。这里就能体现这个函数模板的巧妙之处：

template 
pair (const pair& pr)
    :first(pr.first)
    ,second(pr.second)
{}

当前这个函数模板的两个模板参数实例化出的都是 string 类型，可是整个类模板实例化出的两个模板参数是 const string 和 string 类型。即 pr.first 是 string 类型，this->first 是 const string，用 string 去构造 const string 类型。

其实 template pair (const pair& pr) 已经不一定是拷贝构造了——如果传的类型相同是拷贝构造，如果类型不同则是直接构造。

我们还能这样给 pair 类型插入：

dict.insert(pair("left", "左边"));

只要是相似的类型，都可以插入！

1.5.4 make_pair

make_pair 是一个函数模板，可以用来生成 pair 对象。函数模板有一个特点：可以自动推演模板参数。我们将 Key 和 value 传给 make_pair，它可以自动推导它们的类型，并返回对应的 pair 对象。

make_pair 的底层实现如下：

template 
inline pair make_pair(T1 x, T2 y)
{
    return (pair(x, y));
}

dict.insert(make_pair("right", "右边"));

string s1("xxx"), s2("yyy");
dict.insert(make_pair(s1, s2));

这里 make_pair 推演出来的类型一个是 pair 和 pair，为什么能成功插入？就是因为上面所讲的 pair 的构造函数模板。

1.6 operator[]

operator[] 的声明如下：

mapped_type& operator[] (const key_type& k);

在讲 operator[] 之前，我们先来看一个示例。

1.6.1 示例

我们要统计各个水果出现的次数：

int main()
{
    // 利用 find 和 iterator 修改功能，统计水果出现的次数
    string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
    "苹果", "香蕉", "苹果", "香蕉" };
    map countMap;
    for (const auto& str : arr)
    {
        // 先查找水果在不在 map 中
        // 1、不在，说明水果第一次出现，则插入 {水果, 1}
        // 2、在，则查找到的节点中水果对应的次数++
        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;
}

但其实，中间的判断逻辑用一行代码 countMap[str]++; 就可以搞定：

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

1.6.2 认识 operator[]

为什么只用 countMap[str]++; 就可以完成在和不在两种逻辑的判断呢？

先来看 operator[] 底层的代码实现：

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

其中 key_type 就是 key 的类型，mapped_type 就是 value 的类型。上述代码是将三步合成了一步，可能看不太懂，没关系，我们拆开来看：

mapped_type& operator[] (const key_type& k)
{
    pair tmp1 = ((*this).insert(make_pair(k, mapped_type()));
    iterator tmp2 = *(tmp1).first;
    return tmp2.second;
}

一、insert(make_pair(k, mapped_type())：首先是调用 insert 函数插入一对键值对。key 就是我们的 k，value 调用 value 类型的默认构造函数。

这里我们要重新认识一下 insert 函数，其声明如下：

pair insert (const value_type& val);

可以看到，insert 的返回值是一个 pair，而不是我们以为的 bool。pair 的 first 是一个迭代器，second 是 bool。

• 如果插入成功，返回的 pair 中的 first 就是新插入的值的迭代器，second 为 true。
• 如果插入失败，表明容器中已经有相同的 key 了，此时返回的 pair 中的 first 就是容器中已经存在的 key 的迭代器，second 为 false。

二、*(tmp1).first;：接着取出 insert 返回值 pair 中的 first 成员，这里即容器的迭代器。容器的迭代器也是一个 pair。

需要注意的是，insert 返回的 pair 和迭代器的 pair 不是同一个类型：insert 返回的是 pair，而迭代器类型是 pair。

三、return tmp2.second;：最后就是返回迭代器中的 value 值的引用。

了解了 operator[] 后，就可以明白为什么一句 countMap[str]++; 就能完成整个逻辑的判断：

• 首先调用 insert 进行插入。因为 mapped_type 的类型是 int，其默认构造出的结果是 0，即插入的是 pair。
• insert 返回值的是 pair。
• 如果水果（str）不在，插入成功，iterator 是新插入位置的迭代器。最后返回其 value 值，此时刚刚插入的 value 值是 0，再 ++，变成 1。
• 如果水果（str）在，插入失败，iterator 是容器中原来 key 位置的迭代器。最后返回其 value 值，再对 value 进行 ++，完成计数。

1.6.3 operator[] 的功能

了解 operator[] 的底层后，不难看出 map 的 operator[] 具有三个功能：

• 插入
• 查找
• 修改

int main()
{
    map dict;
    dict.insert(make_pair("sort", "排序"));

    // key 不存在 -> 插入 {"insert", string()}
    dict["insert"];

    // 插入+修改
    dict["left"] = "左边";

    // 修改
    dict["left"] = "左边、剩余";

    // key 存在 -> 查找
    cout << dict["left"] << endl;
    return 0;
}

1.7 map 的其余接口

map 的其余接口与前面 set 的对应接口都类似，这里就不再过多赘述了。

1.8 multimap 与 map 的差异

multimap 和 map 的使用基本完全类似，主要区别在于 multimap 允许关键值 key 冗余，那么 insert / find / count / erase 都围绕着支持 key 冗余这一特性有所差异，这与 set 和 multiset 的关系完全一致。例如，使用 find 时，如果有多个相同 key，返回中序第一个。其次，multimap 不支持 operator[]，因为支持 key 冗余后，operator[] 只能用于插入，无法支持修改，而且也无法确定返回哪个 key 对应的 value 值。

这里特别提一下 equal_range 接口：equal_range 用于获取相等元素的范围。也就是说，你传入一个 key，它会返回一个包含所有相同 key 的范围。该接口 map 也有，但 map 不允许冗余，因此在 map 中用途不大。

int main()
{
    std::multimap mymm;

    mymm.insert(std::pair('a', 10));
    mymm.insert(std::pair('b', 20));
    mymm.insert(std::pair('b', 30));
    mymm.insert(std::pair('b', 40));
    mymm.insert(std::pair('c', 50));
    mymm.insert(std::pair('c', 60));
    mymm.insert(std::pair('d', 60));

    std::cout << "mymm contains:\n";
    for (char ch = 'a'; ch <= 'd'; ch++)
    {
        std::pair::iterator, std::multimap::iterator> ret;
        ret = mymm.equal_range(ch);
        std::cout << ch << " =>";
        for (std::multimap::iterator it = ret.first; it != ret.second; ++it)
            std::cout << ' ' << it->second;
        std::cout << '\n';
    }

    return 0;
}

总结

好啦，本期关于 map 与 multimap 的知识就介绍到这里。希望这篇博客能对你有所帮助。如果有错误的地方，请多指正，让我们在 C++ 的学习路上一起进步。