1.预备知识

2.map的补充知识

2.1map的插入方式

2.2访问键和值

2.3map::operator[]的补充

2.4另外一些map的成员函数的补充

3.map的应用实践-力扣刷题-前k个高频单词

3.1解法1

3.2解法2

3.3解法3

4.map的应用实践-力扣刷题-随机链表的复制

4.1C语言解法

4.2C++解法

5.总结

1.预备知识

该讲需要用到map的知识，可以见我之前的博客：

C++进阶-map-CSDN博客文章浏览阅读484次，点赞13次，收藏7次。我们要更深入了解map就要了解一下pair，pair翻译成中文就是：一对，的意思，我们在C++官网中可以搜索pair来了解一下：翻译一下就能知道其大概的意思：简单来说就是将T1和T2存储在一起，也就是说map相当于set的区别就是能多存储一个值，相对于原来的只有T适应的情况就更多了，但是也相对更难学了一些。这讲的map是一些比较重要的map的成员函数，还有一部分补充的知识点将会在下讲继续进行讲解，好了，这讲就到这里，喜欢的可以一键三连哦，下讲再见！https://blog.csdn.net/2401_86446710/article/details/149344636?spm=1011.2415.3001.10575&sharefrom=mp_manage_link

2.map的补充知识

2.1map的插入方式

上讲我讲解了一个插入方式就是用emplace_hint的方式进行插入，我们实践中不可能完全用那种方式进行插入，所以这里就有以下的方式：

#include<iostream>
#include<map>
#include<string>
using namespace std;
//map的插入方式
int main()
{map<string, int> m;//C++98//插入方式1//有名对象的插入//比较常用pair<string,int> p("China", 1);m.insert(p);//插入方式2//构造匿名对象插入m.insert(pair<string, int>("Hunan", 2));//插入方式3//自动推导类型进行插入m.insert(make_pair("Zhuzhou", 3));//C++11//插入方式4//最常用m.insert({ "Tianyuan",4 });//插入方式5//原地构造m.emplace("Hut", 5);//插入方式6//建议使用auto c = m.find("China");m.emplace_hint(c, "Base", 6);//插入方式7//建议使用//使用{}进行插入m.insert({ {"Dictroy",7},{"Phone",8} });return 0;
}

插入方式还有：

用迭代器区间进行初始化，这种方式用得实在是不多，需要用一段map的迭代器区间来进行初始化，这种方式不太常见，建议用我推荐的三种方式。

注意：initializer_list不是和之前一样直接进行插入了，还是经过了隐式类型转化的，在一般的题目中知道initializer_list的插入和insert({})的插入和emplace(……,……)的插入即可。

2.2访问键和值

一般情况下我们是用这种方式来访问键和值的：

#include<iostream>
#include<map>
#include<string>
using namespace std;
//map访问键和值
int main()
{map<string, int> m({ {"Apple",1} });//访问键auto c = m.find("Apple");cout << c->first << ' ';//访问值cout << c->second << endl;return 0;
}

但是有些人可能就想问了，为什么我们不能用m->first进行访问？

实际上，这个c指的是一个结点，也就是一个键值对，这个c是pair类型的我之前讲过pair，这个pair里面有first和second用于访问我们的键和值，所以一般情况下我们访问一个键和一个值在map里面最简便的方式只有这个，而且这个c->first实际上是c.operator->()->first。

那么我们还有没有其他方式来访问键和值？

以下这个方式有点难理解，不过也可以用来完成目的：

#include<iostream>
#include<map>
#include<string>
using namespace std;
//map访问键和值
int main()
{map<string, int> m({ {"China",1},{"Hunan",2} });auto it = m.begin();while (it != m.end()){cout << (*it).first << ':' << (*it).second << endl;++it;}cout << endl;return 0;
}

这种(*it).first和(*it).second的方式会让人有点难理解，主要是解引用的问题，我们只要知道如何访问的即可。

2.3map::operator[]的补充

上讲我们讲解过：在正常情况下，我们如果传递的参数就是key，在这个key存在在map时会返回这个key对应的value（即返回：值），如果不存在就用默认构造，但是这个时候又可以修改，这样很绕啊。

我在这里可以举例一下，不然真的很难懂这个函数的行为：

#include<iostream>
#include<map>
#include<string>
using namespace std;
//map::operator[]的行为
int main()
{map<string, int> m({ {"China",2},{"Hunan",3},{"Zhuzhou",4} });//返回：值auto a = m["China"];//插入+默认构造这个键的值为0auto b = m["Tianyuan"];//插入+把这个键的值置为5m["Hut"] = 6;auto c = m["Hut"];cout << "China:" << a << endl;cout << "Tianyuan:" << b << endl;cout << "Hut:" << c << endl;return 0;
}

那么这样的运行结果为：

还有一些公司在面试的时候要求讲解出这个map::operator[]的实现，我在这里简单写一下：

#include<iostream>
#include<map>
#include<string>
using namespace std;
//map::operator[]的模拟实现
namespace td
{template<class Key,class T,class Compare=less<T>>class map{T& operator[](const Key& key){pair<map<string, int>::iterator, bool> ret = insert({ key,V() });return ret.first->second;}};
}

这个bool是判断键是否已经在map对象里面的，然后最后的ret.first->second，其中ret.first就是map<string,int>，然后ret.first->second就是返回对应的键的值，要理解指向还需要更深层次的对底层结构的理解。

2.4另外一些map的成员函数的补充

这些就是需要注意的成员函数，首先find，这个是传入一个key（即键），找到对应的键所对应的迭代器，否则返回map::end，即返回为nullptr。这个函数日常生活用得也比较多，只是需要注意：如果没找到的行为是什么。

第二个是count，它接收一个键，然后找这个键在map对象的数量，在map里面当然是只能取0或1，但是在multimap里面就可以取非负整数，这个也要注意；

后面三个：lower_bound，这个是返回一个迭代器，该迭代器指向键不小于 k 的第一个元素；而upper_bound，这个也是返回一个迭代器，该迭代器指向键大于 k 的第一个元素；equal_range则是返回一个范围的边界，该范围包括容器中具有等效键 k 的所有元素。

这三个函数用得也不是很多，所以这里就不做演示了。

3.map的应用实践-力扣刷题-前k个高频单词

题目链接：

692. 前K个高频单词 - 力扣（LeetCode）

题目描述：

3.1解法1

这个题目的综合难度比较高，但是我们可以用map和multimap的性质完成该题：

首先，map可以先实例化为<string,int>类型，之后就直接进行插入，但是插入之前要先判断是否插入成功，如果没插入成功还要判断，但是我们很容易发现如果这种形式，那么解决就很麻烦，直接用operator[]就可以完成上述操作了啊！因为它会判断是否有，有的话就返回值，没有的话就插入，插入后还会默认构造，这个时候我们遇到一个就++即可，然后再构造一个multimap对象，这个对象实例化为：<int,string,greater<int>>类型，因为我们需要排升序，所以需要这样，最后再一个while循环输出前k个高频词即可。

所以最终代码如下：

//前k个高频词解法1
class Solution
{
public:vector<string> topKFrequent(vector<string>& words, int k){map<string, int> countMap;for (auto& str : words){countMap[str]++;}multimap<int, string, greater<int>> sortMap;for (auto& kv : countMap){sortMap.insert({ kv.second,kv.first });}vector<string> v;auto it = sortMap.begin();while (k--){v.push_back(it->second);++it;}return v;}
};

这个解法循环次数太多了，主要是我们无法同时进行两个map的同时完成，要遍历两次所有数据，很麻烦。

3.2解法2

有些人可能会觉得：如果用一个vector<string>进行排序不就可以了。

这个想法确实没问题，但是主要是我们要知道：算法库里面的快速排序的原理是进行交换的，所以如果这样的话，那么就会导致相对次序发生改变，所以我们需要用一个比较稳定的排序算法进行排序，在算法课里面有一个stable_sort：即稳定排序，这个排序刚好可以，但是又出现了新的问题:

如果我们直接用vector<string>的话，没有vector<string>的比较函数，如果自己写比较函数就很麻烦，所以我们不能直接在vecor<string>上进行操作，因为无法进行排序，所以我们最好还是用另外一个结构：vector<pair<string,int>>进行排序操作，但是这样的那个仿函数怎么写？

我们都知道：这个只要比较每个pair的值就可以了，只是看起来很麻烦而已，所以我们可以这样写：

class kvCompare
{
public:bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2){return kv1.second > kv2.second;}
};

最后拷贝这个v[i].first到最后的返回的那个vector<string>对象即可，所以最终代码如下：

//前k个高频词解法2
class kvCompare
{
public:bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2){return kv1.second > kv2.second;}
};
class Solution
{
public:vector<string> topKFrequent(vector<string>& words, int k){map<string, int> m;for (auto& a : words){m[a]++;}vector<pair<string, int>> v(m.begin(), m.end());stable_sort(v.begin(), v.end(), kvCompare());vector<string> r;for (int i = 0; i < k; i++){r.push_back(v[i].first);}return r;}
};

这个代码的运行时间很快，但是有没有另外一种不用stable_sort的写法呢？

当然有！

3.3解法3

我们可以在写仿函数的时候多判断一个条件，因为string在定义的时候其实是有重载<的运算符的，也就是我们可以在原来的继承上加以限制，当kv1.first<kv2.first并且kv1.second==kv1.second的时候再加上||(kv1.second>kv2.second)即可，这样就能稳定的输出结果，而且我们只要用sort函数即可：

//前k个高频词解法3
class kvCompare
{
public:bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2){return (kv1.second > kv2.second) || (kv1.second == kv2.second && kv1.first < kv2.first);}
};
class Solution
{
public:vector<string> topKFrequent(vector<string>& words, int k){map<string, int> m;for (auto& a : words){m[a]++;}vector<pair<string, int>> v(m.begin(), m.end());sort(v.begin(), v.end(), kvCompare());vector<string> r;for (int i = 0; i < k; i++){r.push_back(v[i].first);}return r;}
};

解法三的运行时间和解法1差不多，但是消耗内存小了很多，喜欢哪个就用哪个吧！

4.map的应用实践-力扣刷题-随机链表的复制

题目链接：

138. 随机链表的复制 - 力扣（LeetCode）

题目描述：

4.1C语言解法

在C语言阶段，我讲解过这个题目，当时代码很长，代码如下：

typedef struct Node Node;
//申请新结点空间
Node* buyNode(int x)
{Node* node = (Node*)malloc(sizeof(Node));node->val = x;node->next = node->random = NULL;return node;
}
//在原链表上进行新结点的连接
void AddNode(Node* head)
{Node* pcur = head;while (pcur){//先把原链表下一个结点存储到一个临时变量里Node* next = pcur->next;Node* newnode = buyNode(pcur->val);//改变链表的结点指向newnode->next = next;pcur->next = newnode;pcur = next;}
}
//置random指针
void setRandom(Node* head)
{Node* pcur = head;while (pcur){Node* copy = pcur->next;if (pcur->random)//如果random指针指向为空，我们不需要赋值{copy->random = pcur->random->next;//这个的意思是原结点的random指针指向的结点的地址}//我们需要把pcur一直在原链表上pcur = copy->next;}
}
//断开连接
struct Node* copyRandomList(struct Node* head)
{if (head == NULL){return head;}Node* pcur = head;AddNode(head);setRandom(head);Node* newHead, * newTail;newHead = newTail = pcur->next;while (newTail->next){pcur = newTail->next;newTail->next = pcur->next;newTail = newTail->next;}return newHead;
}

4.2C++解法

这个题目我们也可以用map进行解答，先实例化出一个map<Node*,Node*> c对象，之后我们可以先把原链表拷贝一份，就是把每个结点的所有指针和val都拷贝到新链表去，要完成这个步骤，我们需要用一个指针为cur，在原链表遍历；在新链表上有两个指针，一个指针是指向尾结点的copytail指针，另外一个指针是新指向的链表的头结点copyhead，然后只要存储一下每个copytail的地址到c里面，这就完成了第一个步骤：

class Solution 
{
public:Node* copyRandomList(Node* head) {map<Node*, Node*> c;Node* copyhead = nullptr;Node* copytail = nullptr;Node* cur = head;while (cur){if (copytail == nullptr){copyhead = copytail = new Node(cur->val);}else{copytail->next = new Node(cur->val);copytail = copytail->next;}c[cur] = copytail;cur = cur->next;}}
};

后面我们还要处理random指针，我们需要先把cur重新置为head，这个时候我们再让Node* copy = copyhead;这个时候我们直接再次遍历，我们需要这样写：copy->random=c[cur->random]这样就解决了，如果cur->random是nullptr，那么这个时候我们就不能copy->random=c[cur->random];了，因为这个传入nullptr会报错，所以这个时候就要直接用copy->random=nullptr即可，最后再让cur=cur->next；copy=copy->next;即可完成。

我们要注意的一点是一定要理解这个：copy->random=c[cur->random];

我们用这题的例子来说明一下：

这里我们的第一步是：c[cur]=copytail;，假设这个时候cur在第一个结点，那么这个时候我们的第一个结点所对应的value就是7这个结点，也就是说把<cur,cur>这种键值对存放起来了。（也就相当于把另外一个新链表的结点指针作为cur存放起来了）

第二步是copy->random=c[cur->random];这一步相对于之前就好理解多了，直接相当于拷贝一下，把原有结点的random指针再次存放到新的对应的结点上去，所以这个思路就是先拷贝过去，再拷贝回来这种，相对于之前C语言的解法简单很多，所以最终代码如下：

class Solution 
{
public:Node* copyRandomList(Node* head) {map<Node*, Node*> c;Node* copyhead = nullptr;Node* copytail = nullptr;Node* cur = head;while (cur){if (copytail == nullptr){copyhead = copytail = new Node(cur->val);}else{copytail->next = new Node(cur->val);copytail = copytail->next;}c[cur] = copytail;cur = cur->next;}cur = head;Node* copy = copyhead;while (cur){if (cur->random == nullptr){copy->random = nullptr;}else{copy->random = c[cur->random];}cur = cur->next;copy = copy->next;}return copyhead;}
};