网站开发网站设计案例_深圳论坛网站设计哪家公司好_哈尔滨关键词排名工具_宁波网站优化公司电话

---

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树的学习打下了基础！！！是很重要的数据结构。

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