你是我的映射，我是你的值：C++ map 中的心灵共鸣

map的概念

map是key_value的模型：

一棵树，每个结点存一个pair

1. map是关联容器，它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
2. 在map中，键值key通常用于排序和惟一地标识元素，而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同，并且在map的内部，key与value通过成员类型value_type绑定在一起，为其取别名称为pair: typedef pair<const key, T> value_type;
3. 在内部，map中的元素总是按照键值key进行比较排序的。
4. map中通过键值访问单个元素的速度通常比unordered_map容器慢，但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时，可以得到一个有序的序列)。
5. map支持下标访问符，即在[]中放入key，就可以找到与key对应的value。
6. map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。

一、map的使用

1. 插入删除相关

1）插入

(1) 插入语法

首先，map的插入也是默认去重的，因为map里存的是pair，所以插入操作我们必须要插入pair，一下是几种插入方式：

1.构造一个pair对象进行插入

2. 插入一个pair的匿名对象
   

3. 对于c++98可以调用构造pair的函数，这个函数包含在pair中，他会调用构造函数返回一个pair的对象
   
   

4. 对于c++11可以使用{ }，c++11支持多参数构造函数的隐式类型转化
   这种转化方式是：（1）多参数隐式类型转化。
   （2）构造 + 拷贝构造 -> 直接构造
   

一般来说我们喜欢用后两种~~~

(1) 插入语法

插入支持直接插入pair，也支持迭代器位置，和一段迭代区间。
这里我们重点看第一种：

首先：对于插入操作来说，如果遇到相同的key，不插入，也不覆盖，再插入过程之中，只比较key，与value无关。

然后，对于直接插入pair的insert返回值不是一个单纯的bool，而是一个pair:
pair<iterator, bool>

对于multimap来说，它就不默认去重了，可以插入key相等的元素

2）删除

删除很简单，根据key来删除就可以了

二. map的遍历

因为map的值是pair，因此使用迭代器遍历map，直接*it得到的是pair，而pair没有重载流插入，流输出。
因此，不能cout << *it << " "; ++it

这里提供两种遍历的方式，首先我们看pair，里面包含了两个值，其中第一个是first，第二个是second。因此：

1. 使用迭代器遍历

我们用*it获取pair，再用first()与second()获取pair中的元素

也支持范围for:

2. 使用->进行遍历
   迭代器出来的是it是一个指针，这里pair重载了->，it->返回的是对应pair的指针，因此实际上访问时(it->)->，但这里编译器进行了优化，因此直接用箭头就可以访问first和second

三、map重载operator[]

map中的[ ]是根据key来返回value。

假设我们要统计数组中，水果出现的次数：
如果没有重载[ ]，那么我们只能这样写。

如果重载了[ ]，就不一样了，通过[key]找value:

但是这里面有一个问题，就是如果这个当第一次出现的时候是怎么初始化的？

因此我们就要研究 operator[]的返回值了。
查阅文档我们可以发现 operator[]返回的是这样一串东西：

把他拆分出来看就是返回

1. 调用insert的返回值的是一个pair
2. pair取出first是->iterator
3. *iterator就是对应map中的pair
4. 再取出这个pair中的second就是key对应的value

因此我们就要研究insert的返回值了：

前文提到：对于直接插入pair的insert返回值不是一个单纯的bool，而是一个pair:pair<iterator, bool>
这个pair的first是map中对应的插入值的迭代器，second来判断插入成功还是失败。

这里分两种情况：

因此相当于operator的返回值是这样的：
在传参传insert的pair的second时，传的是一个缺省值V()，如果存在了，就用已经存在的val，如果不存在就用缺省构造出来的value，int类型就是0，string类型就是nullptr等等…

综上，这里operator[ ]可以用key来找到value~

四、小试🐂🔪

1. 前K个高频单词

前K个高频单词

/*
思路：经典的top-k问题
  1. 先采用map统计出每个单词出现的次数
  2. 采用优先级队列，借助map中的前k个元素创建一个小堆，剩余元素向堆中插入一个删除一个，使用保持堆中有k个元素，直到将map中的元素插入完
  3. 堆中剩余的元素就是出现次数最多的k个元素，只不过是次数从小到达的，
     将堆中的元素逐次放置到vector中，注意只放字符串，然后逆置
*/

class Solution {
    // 比较器
    // 因为放入优先级队列的元素为：单词与其出现次数构成的键值对，优先级队列不能直接比较，因此
    // 需要提供一个比较器，在实例化用该比较器实例化
    // 比较方式：
    // 按照次数比较，如果次数相同，再按照单词字典熟序比较
    struct Com{
        bool operator()(pair<string,int> &a,const pair<string,int> &b)
        {
            if(a.second!=b.second)
            {
               return a.second>b.second;
            }
            else
            {
               return a.first<b.first;
            }
        }
    };

public:
    vector<string> topKFrequent(vector<string>& words, int k) 
    {
        // 采用map统计每个单词出现的次数
        map<string, int> m;
        for(auto e : words)
            m[e]++;
        
        // 采用优先级队列，找出现次数最多的前K个IP地址
        priority_queue<pair<string, int>, vector<pair<string, int>>, Com> q;

        // 用map中的元素插入到优先级队列中，当优先级队列中的元素等于k个时，插入一个，删一个
        // 始终保证优先级队列中有k个元素
        for(auto e : m)
        {
            q.push(e);
            if(q.size() > k)
                q.pop();
        }

        // 将优先级队列中元素（键值对）中的字符串部分放置到vector中
        vector<string> ret;
        while(!q.empty())
        {
            ret.push_back(q.top().first);
            q.pop();
        }

        // 因为是根据次数创建的小堆，因此需要逆置
        reverse(ret.begin(), ret.end());
        return ret;
    }
};

2. 单词识别

单词识别

#include <iostream>
using namespace std;
#include <string>
#include <map>
#include <set>



typedef pair<string, int> Word;
class Compare {
  public:
    bool operator()(const Word& left, const Word& right)const {
        // 次数从大到小排序
        // 如果次数相同，再按照单词字典序排序
        return (left.second > right.second) || 
               (left.second == right.second && left.first < right.first);
    }
};



int main() {
    string s;
    while (getline(cin, s)) {
        map<string, int> m;
        string temp;


        // 分割单词，采用map统计每个单词出现的次数
        for (size_t i = 0; i < s.size(); ++i) {
            if (s[i] == ' ' || s[i] == ',' || s[i] == '.') {
                // 一个单词解析结束
                if (temp != "")
                    m[temp]++;


                temp = "";
            } else {
                // 注意：题目已说明不区分大小写，那么A和a算是一个单词，故需要将大小写统一
                temp += tolower(s[i]);
            }
        }


        // 将map中的<单词，次数>放到set中，并按照次数升序，次数相同按照字典序规则排序
        set<Word, Compare> s(m.begin(), m.end());
        
        // 将本次统计到的结果按照要求输出
        for (auto& e : s)
            cout << e.first << ":" << e.second << endl;
        cout << endl;
    }
    return 0;
}

总结

到这里，map与set就结束啦，map与set为后面红黑树与AVL树的学习打下了基础！！！是很重要的数据结构。

创作不易，如果本片文章对各位有帮助的话，求求各位大佬一个一键三连，谢谢大家🤩🤩🤩