一、auto占位符

在介绍高级STL数据结构之前，我们先来说说auto这个关键的占位符

1.auto可以根据后面的数据来推测前面的数据类型

因此，我们可以用auto随心所欲的声明变量，就像下面这样：

  1. int main()
  2. {
  3.     auto i = 1;
  4.     auto j = 12.05;
  5.     auto arr = { 1,2,3,4 };
  6.     cout << i << endl << j << endl;
  7.     return 0;
  8. }

输出结果
image.png
值得注意的是：

  1. 使用auto声明的变量必须初始化(你想啊，auto可以是任何类型，假如没有初始化，系统怎么知道他是什么类型呢)
  2. 函数和参数不能被声明为auto

2.auto可以作为迭代器

不会有人连迭代器是啥都不知道吧(bushi
例如for(int i = 0; i < 5; i++) 这个循环，这里面的 i 就是 迭代器

那么请大家来看这段代码

  1. int main()
  2. {
  3.     auto arr = { 1,2,3,4,4,5,5,6,7 };
  4.     for (auto i : arr)
  5.         cout << i << " ";
  6.     return 0;
  7. }

输出结果
image.png
优雅，实在是太优雅了、

二、pair对组

你可能会好奇为什么map的前置知识要讲这么多。
基础不牢，地动山摇！
其实，map就是由一个一个pair组成的。

1.pair是什么

中文名叫 对组。跟结构体很像，它里面可以一次存两个数据。就像这样：

  1. //初始化一个对组
  2. pair<int, int>p0(1, 2);

<>里面的是两个数据的类型，（）里面是数据的值，当然这两个数据类型可以不一样。

2.创建一个对组

pair又专门的创建函数 make_pair ，是不是很高级

  1. //创建一个对组
  2. pair<string, int>p1 = make_pair("tom", 30);

当然，除了使用内置函数，你直接初始化一个也算创建了一个对组。

3.访问对组的元素

对组的第一个元素叫 first, 第二个元素叫 second
请看下面的代码

  1. int main()
  2. {
  3.     //pair 对组的学习
  4.     //初始化一个对组
  5.     pair<int, int>p0(1, 2);
  6.     //创建一个对组
  7.     pair<string, int>p1 = make_pair("tom", 30);
  8.     //输出
  9.     cout << p1.first << " " << p1.second << endl; // 访问对组用序数词！！！
  10.     return 0;
  11. }

可以看到，直接把pair这么多字母打出来不是正常程序员的风格,我们一般使用typedef
pair作为函数返回值时也可以用tie关键字来访问，在下面的代码中一并展示。

  1. #include<iostream>
  2. #include<string>
  3. using namespace std;
  4. typedef pair<int, string> Arr;    // 改个名字，简单些
  5. Arr getArr()
  6. {
  7.     return make_pair(20,"tom");
  8. }
  9. int main()
  10. {
  11.     Arr a;   // 单独声明，既不初始化也不创造
  12.     int n;
  13.     string str; // 事先把tie的变量准备好
  14.     tie(n, str) = getArr();
  15.     cout << n << " " << str << endl;
  16.     // 当然原始方法也可以
  17.     a = getArr();
  18.     cout << a.first << " " << a.second;
  19.     return 0;
  20. }

三、map

首先说一下头文件吧

  1. #include<map>

1.map是什么

map是STL的一个关联容器，它提供一对一的hash。第一个可以称为关键字(key)，每个关键字只能在map中出现一次；第二个可能称为该关键字的值(value)。map以模板(泛型)方式实现，可以存储任意类型的数据，包括使用者自定义的数据类型。Map主要用于资料一对一映射(one-to-one)的情況，map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的。

关键点就是：

  1. 能提供一对一的hash，所以map几乎是哈希算法的标配函数；
  2. map里面的每一个pair的第一元素叫做key（关键字）,第二个元素叫做value（值）,可以用key访问到value;
  3. map里面的每一元素都是有序的。

    2.创建一个map

    就像这样，非常简单；
    1. map<int, int>m;
    表示这个map里面每一个pair都必须是pair的，也就是说，pair虽然不限制类型，但是map限制了pair的类型，如果将理解为一种类型的话，那么，map里面的pair必须是同类型的。

    3.在map中插入元素

    这里总共有三种方法，但我只介绍两种，剩下的一种大家去CSDN一查便知。
    主要是学的太多我也记不住。

    方法1.使用insert函数插入，这里我们就可以看到map的有序性了

    请看下面的代码（里面的打印函数大家可以先看下面的代码） ```cpp

    include

    include

    include

    using namespace std;

void printMap(map& m) { for (auto i = m.begin(); i != m .end(); i++) { cout << “key= “ << i->first << “ “; cout << “value= “ << (*i).second << endl; } }

int main() { mapm; //乱序插入，顺序输出，不许重复 m.insert((pair(1, 10))); m.insert((pair(4, 60))); m.insert((pair(3, 50))); m.insert((pair(2, 10))); m.insert((pair(6, 10))); //输出 printMap(m); return 0; }

  1. 输出结果<br />![image.png](https://cdn.nlark.com/yuque/0/2022/png/26170262/1655714651354-c0f32707-783b-4f4f-bd7d-7a90e51e2288.png#clientId=u97930a11-a19a-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=511&id=u67b5b464&margin=%5Bobject%20Object%5D&name=image.png&originHeight=639&originWidth=1223&originalType=binary&ratio=1&rotation=0&showTitle=false&size=37585&status=done&style=none&taskId=u860ace11-8495-41f7-8ccf-734a7ef4ba5&title=&width=978.4)<br />我们不妨观察一下，**这个map的顺序到底是谁的顺序**。
  2. <a name="v0I5V"></a>
  3. ### 方法2.使用key引入
  4. ```cpp
  5. void printMap(map<int, int>& m)
  6. {
  7.     for (auto i = m.begin(); i != m .end(); i++)
  8.     {
  9.         cout << "key= " << i->first << "  ";
  10.         cout << "value= " << (*i).second << endl;
  11.     }
  12. }
  14. int main()
  15. {
  16.     // 方法2. 使用key引入
  17.     m[1] = 20;
  18.     m[2] = 30;
  19.     m[3] = 10;
  20.     //输出
  21.     printMap(m);
  22.     return 0;
  23. }

解释一下：
m[1] = 20； 这句代码
[1] 表示key，这说明map是支持用“下标引用运算符[]”来访问key的，当使用了m[1], map就会去找first元素为1的对组，如果找不到，就创建一个，并将他的value值赋为20，如果找到了，就修改这个值。

4.map的有序性

从方法1的代码【在map中插入元素+打印[1]】中，我们看到，key值的大小就是map的排序方式。
那么，如果key是字母呢？

  1. void printMap(map<char, int>& m)
  2. {
  3.     for (auto i = m.begin(); i != m .end(); i++)
  4.     {
  5.         cout << "key= " << i->first << "  ";
  6.         cout << "value= " << (*i).second << endl;
  7.     }
  8. }
  10. int main()
  11. {
  12.     map<char, int>m;
  13.     m.insert((pair<int, int>('a', 10)));
  14.     m.insert((pair<int, int>('b', 60)));
  15.     m.insert((pair<int, int>('d', 50)));
  16.     m.insert((pair<int, int>('z', 10)));
  17.     m.insert((pair<int, int>('s', 10)));
  19.     //输出
  20.     printMap(m);
  21.     return 0;
  22. }

输出如你所见
image.png
可见，key是字母时，排序方式是key的ASCII码值。
大家可以自己探索一下string类型的key的排序方式（虽然没什么意义，毕竟做题是谁也不会放着数组的下标不用去搞个string做key名）

5.map元素的访问

结合输出map的输出函数，不难看出有两种方式。

  1. void printMap(map<int, int>& m)
  2. {
  3.     for (auto i = m.begin(); i != m .end(); i++)
  4.     {
  5.         cout << "key= " << i->first << "  ";
  6.         cout << "value= " << (*i).second << endl;
  7.     }
  8. }

并且跟结构体的输出很像。
先用auto拿到map的每一个对组，再直接访问对组即可。
访问对组有两种方式，i->first和(*i).first都是直接指向的意思。我个人比较倾向于第一种，因为只有看见跟指针长得很像的东西我就想🤮

5.查找map里面的元素

vector里面的find函数大家都知道吧，这里跟他很像。
find函数查找的是key，当找到了这个key，他返回key的位置，找不到返回map的end()位置。

  1. int main()
  2. {
  3.     map<char, int>m;
  4.     m.insert((pair<int, int>('a', 10)));
  5.     m.insert((pair<int, int>('b', 60)));
  6.     m.insert((pair<int, int>('d', 50)));
  7.     m.insert((pair<int, int>('z', 10)));
  8.     m.insert((pair<int, int>('s', 10)));
  10.     //find函数查找map里面的元素值
  11.     auto i = m.find('d');
  12.     if (i == m.end())
  13.     {
  14.         cout << "not find";
  15.     }
  16.     else
  17.     {
  18.         cout << i->second;
  19.     }
  20.     return 0;
  21. }

6.删除map里面的元素和清空map

需要使用erase函数

  1. void printMap(map<char, int>& m)
  2. {
  3.     for (auto i = m.begin(); i != m .end(); i++)
  4.     {
  5.         cout << "key= " << i->first << "  ";
  6.         cout << "value= " << (*i).second << endl;
  7.     }
  8. }
  10. int main()
  11. {
  12.     map<char, int>m;
  13.     m.insert((pair<int, int>('a', 10)));
  14.     m.insert((pair<int, int>('b', 60)));
  15.     m.insert((pair<int, int>('d', 50)));
  16.     m.insert((pair<int, int>('z', 10)));
  17.     m.insert((pair<int, int>('s', 10)));
  19.     //find函数查找map里面的元素值
  20.     int n = m.erase('b'); // 删除成功就返回1，否则返回0
  21.     printMap(m);
  22.     //find函数清除map
  23.     m.erase(m.begin(), m.end());
  24.     printMap(m);
  25.     return 0;
  26. }

偷个小懒，大家自己看吧
输出结果
image.png

7.map里面的函数汇总

函数名 功能
begin() 返回指向map头部的迭代器
clear(） 删除所有元素
count() 返回指定元素出现的次数
empty() 如果map为空则返回true
end() 返回指向map末尾的迭代器
equal_range() 返回特殊条目的迭代器对
erase() 删除一个元素
find() 查找一个元素
insert() 插入元素
key_comp() 返回比较元素key的函数
lower_bound() 返回键值>=给定元素的第一个位置
max_size() 返回可以容纳的最大元素个数
size() 返回map中元素的个数
swap() 交换两个map
upper_bound() 返回键值>给定元素的第一个位置

四、unordered_map

1.unordered_map是什么

map是有序的，ordered是排好序的意思，那么顾名思义，unordered-map就是不排序的map

hash_map ≈ unordered_map，最初的 C++ 标准库中没有类似 hash_map 的实现，但不同实现者自己提供了非标准的 hash_map。 因为这些实现不是遵循标准编写的，所以它们在功能和性能保证方面都有细微差别。从 C++ 11 开始，hash_map 实现已被添加到标准库中。但为了防止与已开发的代码存在冲突，决定使用替代名称 unordered_map。这个名字其实更具描述性，因为它暗示了该类元素的无序性。

2.创建一个unordered_map

直接定义即可
需要使用头文件
#include
请看代码：

  1. int main()
  2. {
  3.     // unordered-map的学习
  4.     unordered_map<string, string>umap;
  5.     umap.emplace("tom", "is");
  6.     cout << umap["tom"] << endl;
  7.     return 0;
  8. }

3.unordered_map常用函数汇总

unordered_map和map的使用函数很像，大家直接看汇总吧

函数 功能
begin() 返回指向容器中第一个键值对的正向迭代器。
end() 返回指向容器中最后一个键值对之后位置的正向迭代器
empty() 若容器为空，则返回 true；否则 false。
size() 返回当前容器中存有键值对的个数。
max_size() 返回容器所能容纳键值对的最大个数
at(key) 返回容器中存储的键 key 对应的值，如果 key 不存在，则会抛出 out_of_range 异常。
find(key) 查找以 key 为键的键值对，如果找到，则返回一个指向该键值对的正向迭代器；反之，则返回一个指向容器中最后一个键值对之后位置的迭代器（如果 end() 方法返回的迭代器）。
count(key) 在容器中查找以 key 键的键值对的个数。
equal_range(key) 返回一个 pair 对象，其包含 2 个迭代器，用于表明当前容器中键为 key 的键值对所在的范围。
emplace() 向容器中添加新键值对，效率比 insert() 方法高。
insert() 向容器中添加新键值对
erase() 删除指定键值对
clear() 清空容器，即删除容器中存储的所有键值对
swap() 交换 2 个 unordered_map 容器存储的键值对，前提是必须保证这 2 个容器的类型完全相等。

4.unordered_map和map的比较

网上关于这方面的博客很多。我只列举比较重要的一点。

map:

有序性就是最大的优点。
缺点是速度慢，占用空间大。所以我们一般在做题时不用他。

unordered_map

内部用hash实现。
速度很快，
但是创建hash表需要的时间复杂度很大

五、实际应用

1、leetcode题目 剑指offer 2-010 和为k的子数组

题目链接: ==>传送门
image.png
这题可以说是模板题了。
我首先想到的是DFS，但此题数据太大，不容易过，所以，我们用hash求前缀和。
为什么要求前缀和呢？
假如，我们遍历nums数组，此时拿到的元素是nums[i],那么只要这个元素前面的一段元素的和为k-nums[i],那么这就是一种符合条件的情况。
但是，如果说前面总共有四个元素，而我们只需要取下标为1~3的元素，也就是第一个元素不能取，该怎么办呢？
我们默认随着数组的遍历，数组的前缀和是增加的。对于每一个前缀和，我们都把它放到unordered_map并计算次数。这就相当于把所有的前缀和都用一个数组存起来了。
既然已经得到了这个前缀和数组，那么后面的前缀和 减去 前面的前缀和 就等于中间这段的和了。
上代码：

  1. #include<unordered_map>
  3. int subarraySum(vector<int>& nums, int k) {
  4.     unordered_map<int, int>arr;    // 第一个int表示前缀和，第二个int表示这个前缀和出现的次数
  5.     arr[0] = 1;
  6.     int ret = 0;   // 用于计算前缀和
  7.     int ans = 0;
  8.     for (auto& i : nums)
  9.     {
  10.         ret += i;
  11.         if (arr.find(ret - k) != arr.end())    // ret-k 如果跟前面的前缀和有重复，重复的那个前缀和就是ret-k.
  12.                                                // 而此时的前缀和是ret, 所以中间的那一段和就是k
  13.             ans += arr[ret - k];
  14.         arr[ret]++;  // 重新创建前缀和pair
  15.     }
  16.     return ans;
  17. }
  19. int main()
  20. {
  21.     vector<int>nums = { 1,2,3};
  22.     cout << subarraySum(nums, 3);
  23.     return 0;
  24. }

2、leetcode题目-525 连续数组

题目链接：==》传送门
image.png
这个题是模板题稍微变了一下形状。
我们让0和1的数量相等，加入把0看成-1，那么，这个题就是要求和为0的最长连续子数组。
按照第一题的思路，我们用一个counter了存储前缀和，在遍历nums时每次更新counter,然后再map里面寻找这个前缀和是否重复。
如果重复了，也就是说，前i个元素和前j个元素的前缀和相等。那只能说明：
从i+1到j 的元素的和为0.
接下来计算长度：
从下标为i的元素到下标为j的元素的这一段的数组长度为 j - i + 1;
但是，我们这里的长度从i + 1开始算起，所以，本次数组的长度为 j - i;在每次循环符合条件是更新最大长度即可。
map存储的数点缀和与此前缀和的结束元素的下边。
上代码;

  1. #include<unordered_map>
  3. int findMaxLength(vector<int>& nums) {
  4.     int n = nums.size();
  5.     unordered_map<int, int>map;  // map第一个元素存储的是前缀和，第二个元素是此前缀和出现的结束下标
  6.     map[0] = -1;    // 边界条件
  7.     int counter = 0;   // 用于计算前缀和
  8.     int ans = 0;        // 连续数组的最大长度
  9.     for (int i = 0; i < n; i++)
  10.     {
  11.         if (nums[i] == 1)
  12.             counter++;
  13.         else
  14.             counter--;
  15.         if (map.count(counter) != 0)   // 以value值查找用find,以key值查找用count
  16.             ans = max(ans, i - map[counter]);
  17.         else
  18.             map[counter] = i;   // 将此前缀和的结束下标连同前缀和放进map
  19.     }
  20.     return ans;
  21. }
  23. int main()
  24. {
  25.     vector<int>nums = { 0,1 };
  26.     cout << findMaxLength(nums);
  27.     return 0;
  28. }