map的使用（c++）

在了解map之前，我们先看看两个场景，通过这两个场景的对比，让我们知道为什么要存在存储双关键字的容器

场景一：判断一堆字符串中，某一个字符串是否出现过

在没学set容器之前，我们只能想到把这一堆字符串存到一个字符型数组里面，从前往后遍历每一个字符，判断某一个字符串是否出现过，这个时间复杂度是O（N）级别的，如果我们学过set的话，我们就可以把这一堆字符串存到set容器里面，判断某一字符串是否出现过的时候直接调用里面的count接口就可以了，时间复杂度是O（logN）级别的，所以我们用set特解决场景一问题的时候，时间复杂是更优的

场景二：找出一堆字符串中，某一个字符串出现的次数

如果找的是次数，那么set容器就用不了了，set容器存储的是单关键字，而且里面是不能有重复元素的，大家可能想到有multiset，它可以存储重复的元素，因此要判断某一个字符串出现的次数，直接调用multiset里面的count不就完了吗？其实还有一个问题，如果这一堆字符串中，所有的字符全都长一样，比如有10,000个字符串里面的每个字符都是a，当我想找“aa”这个字符串出现的次数的时候，用multiset来解决的话是要遍历整个红黑树一遍的，要全部把它扫描一遍才能统计出a次数，此时它的时间复杂度是O（N）级别的，那和数组存储没有任何的差别，所以我们想判断某一个字符串出现的次数是不能用set容器的

此时存储双关键字的map就登场了，它可以做到存储双关键字，它把两个关键词绑定在一起，存到红黑树里面的，比如在这个问题里面，我想统计某一个字符串出现的字数，map绑定的两个关键字可以设置成，第一个是string第二个是int，它的意思是把字符串和出现的次数绑定在一起，放进红黑树里面的一个一个节点中，也就是说红黑树的节点存的是一个结构体，结构体的第一个关键字是字符串，第二个是字符串出现的次数，此时在查找某一个字符串出现的次数的时候，直接在这个红黑中找出对应的字符串，拿到它出现的次数就可以了，至于如何解决这样的一个问题，我们学完map的方式之后，在一起编写代码

map / multimap 

map 与 multimap 的区别： map 不能存相同元素， multimap 可以存相同的元素，其余的使⽤⽅式完全⼀致。因此，这⾥只练习使⽤ map 。 map 与 set 的区别： set ⾥⾯存的是⼀个单独的关键字，也就是存⼀个 int 、 char 、 double 或者 string 。⽽ map ⾥⾯存的是⼀个 pair<key, value> ，（k-v 模型）不仅有⼀个关键字，还会有⼀个与关键字绑定的值，⽐较⽅式是按照 key 的值来⽐较。 也就是中序遍历的结果是按照第一个关键字的的大小来做比较的；可以这样理解：红⿊树⾥⾯⼀个⼀个的结点都是⼀个结构体，⾥⾯有两个元素分别是 key 和 value 。插⼊、删除和查找的过程中，⽐较的是 key 的值。 

⽐如，我们可以在 map 中： 

1. 存 <int, int> ，来统计数字出现的次数； 
2. 存 <string, int> ，来统计字符串出现的次数； 
3. 存 <string, string> ，表⽰⼀个字符串变成另⼀个字符串； 
4. 甚⾄存 <int, vector<int>> 来表⽰⼀个数后⾯跟了若⼲个数......，可以用来存储树，就是一个根结点，后面跟了一堆孩子，int表示根，vector<int>存它的一堆孩子，但用map存储树的效率不高，因为查找的时间复杂是O（logN），后面我们在学习哈希表的时候，可以给大家演示一下如何用这个东西存储树，因为用哈希表来存储这样的形式，查找是很快的

1 创建 map 

#include <iostream> 
#include <vector> 
#include <map> 
using namespace std; 
int main() 
{ map<int, int> mp1; map<int, string> mp2; map<string, int> mp3; map<int, vector<int>> mp4; // 甚⾄可以挂⼀个 vectorreturn 0;
}

2 size / empty

1. size ：求红⿊树的⼤⼩。时间复杂度： O(1) 。
2. empty ：判断红⿊树是否为空。时间复杂度： O(1) 。

3 begin / end

• 迭代器，可以使⽤范围 for 遍历整个红⿊树。
• 遍历是按照中序遍历的顺序，因此是⼀个有序的序列。

4 insert

• 向红⿊树中插⼊⼀个元素。这⾥需要插⼊⼀个 pair，可以⽤ {} 形式。⽐如： mp.insert({1, 2}) 。时间复杂度： O(log N) 。

5 operator []

• 重载 [] ，使得 map 可以像数组⼀样使⽤。
• 这是 map 最好⽤的接⼝，有了这个重载，map 的使⽤就变得特别轻松，不⽤写很多冗余的代码。
• 它的底层其实就是调⽤了 insert 函数，并且会返回 val 的引⽤。我们⽬前就先学会使⽤即可。

6 erase

• 删除⼀个元素。时间复杂度： O(log N) 。

7 find / count

1. find ：查找⼀个元素，返回的是迭代器。时间复杂度： O(log N) 。
2. count ：查询元素出现的次数，⼀般⽤来判断当前元素是否在红⿊树中。时间复杂度：O(log N) 。

8 lower_bound / upper_bound

1. lower_bound ：⼤于等于 x 的最⼩元素，返回的是迭代器。时间复杂度： O(log N) 。
2. upper_bound ：⼤于 x 的最⼩元素，返回的是迭代器。时间复杂度： O(log N) 。

代码：

#include <iostream>
#include <map>
#include <string>
using namespace std;//传引用使得mp不需要拷贝
void print(map<string, int>& mp)
{//&避免拷贝//双关键字用auto提取出来的是一个pair类型，所以打印要用first、secondfor (auto& p : mp){cout << p.first << " " << p.second << endl;}
}void test1()
{map<string, int> mp;//插入mp.insert({ "张三", 1 });mp.insert({ "李四", 2 });mp.insert({ "王五", 3 });print(mp); //打印出来的结果按第一个关键字作比较，后面的关键字只起到绑定作用//李四 2//王五 3//张三 1//operator[] 可以让 map 像数组一样使用int a[2] = { 1,2 };a[1] = 4;cout << a[1] << endl; //4cout << mp["张三"] << endl; //1mp["张三"] = 110;cout << mp["张三"] << endl; //110// 注意事项：operator[] 有可能会向 map 中插入本不想插入的元素if (mp["赵六"] == 4) cout << "yes";else cout << "no" << endl;  //no//虽然我们只是想判断赵六存不存在，但是一旦调用了[]，就把赵六插入进来了// [] 里面的内容如果不存在 map 中，会先插入，然后再拿值// 插入的时候：第一个关键字就是 [] 里面的内容，第二个关键字是一个默认值print(mp);//李四 2//王五 3//张三 110//赵六 0//这样的逻辑去写就没有插入张飞，从mp.count("张飞")这句话就断掉了//后面的语句没有执行了，此时打印张飞是不存在map里的if (mp.count("张飞") && mp["赵六"] == 4) cout << "yes" << endl;else cout << "no" << endl;  //noprint(mp);cout << endl;//李四 2//王五 3//张三 110//赵六 0//删除mp.erase("张三");print(mp);cout << endl;//李四 2//王五 3//赵六 0//auto x = mp.lower_bound("李四");map<string, int>::iterator x = mp.lower_bound("李四");cout << x->first << " " << x->second << endl; //李四x = mp.upper_bound("李四");cout << x->first << " " << x->second << endl; //王五
}// 统计一堆字符串中，每一个字符串出现的次数
void fun()
{string s;map<string, int> mp; // <字符串，字符串出现的次数>for (int i = 1; i <= 5; i++){cin >> s;mp[s]++; // 体现了 operator 的强大，s字符串不存在会先插入	}print(mp);//输入//sdf//aa//dd//aa//dd//输出//aa 2//dd 2//sdf 1
}int main()
{test1();//fun();return 0;
}