从pair到unordered_map，理论+leetcode题目实战

目录

一、auto占位符

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

2.auto可以作为迭代器

二、pair对组

1.pair是什么

2.创建一个对组

3.访问对组的元素

三、map

1.map是什么

2.创建一个map

3.在map中插入元素

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

方法2.使用key引入

4.map的有序性

5.map元素的访问

5.查找map里面的元素

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

7.map里面的函数汇总

四、unordered_map

1.unordered_map是什么

2.创建一个unordered_map

3.unordered_map常用函数汇总

4.find函数与coun函数的比较

5.unordered_map和map的比较

map:

unordered_map

五、实际应用

1、leetcode题目 219 存在重复元素 2

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

3、leetcode题目-525 连续数组

---

一、auto占位符

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

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

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

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

输出结果

值得注意的是：

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

2.auto可以作为迭代器

不会有人连迭代器是啥都不知道吧(bushi

例如for(int i = 0; i < 5; i++) 这个循环，这里面的 i 就是 迭代器

那么请大家来看这段代码

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

输出结果

优雅，实在是太优雅了、

二、pair对组

你可能会好奇为什么map的前置知识要讲这么多。

基础不牢，地动山摇！

其实，map就是由一个一个pair组成的。

1.pair是什么

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

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

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

2.创建一个对组

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

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

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

3.访问对组的元素

对组的第一个元素叫 first, 第二个元素叫 second

请看下面的代码

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

可以看到，直接把pair<int,int>这么多字母打出来不是正常程序员的风格,我们一般使用typedef

pair作为函数返回值时也可以用tie关键字来访问，在下面的代码中一并展示。

#include<iostream>
#include<string>
using namespace std;
typedef pair<int, string> Arr;    // 改个名字，简单些
Arr getArr()
{
	return make_pair(20,"tom");
}
int main()
{
	Arr a;   // 单独声明，既不初始化也不创造
	int n;
	string str; // 事先把tie的变量准备好
	tie(n, str) = getArr();
	cout << n << " " << str << endl;
	// 当然原始方法也可以
	a = getArr();
	cout << a.first << " " << a.second;
	return 0;
}

三、map

首先说一下头文件吧

#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

就像这样，非常简单；

map<int, int>m;

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

3.在map中插入元素

这里总共有三种方法，但我只介绍两种，剩下的一种大家去CSDN一查便知。

主要是学的太多我也记不住。

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

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

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

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

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

输出结果

我们不妨观察一下，这个map的顺序到底是谁的顺序。

方法2.使用key引入

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

int main()
{
	// 方法2. 使用key引入
	m[1] = 20;
	m[2] = 30;
	m[3] = 10;
	//输出
	printMap(m);
	return 0;
}

解释一下：

m[1] = 20； 这句代码

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

4.map的有序性

从方法1的代码中，我们看到，key值的大小就是map的排序方式。

那么，如果key是字母呢？

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

int main()
{
	map<char, int>m;
	m.insert((pair<char, int>('a', 10)));
	m.insert((pair<char, int>('b', 60)));
	m.insert((pair<char, int>('d', 50)));
	m.insert((pair<char, int>('z', 10)));
	m.insert((pair<char, int>('s', 10)));

	//输出
	printMap(m);
	return 0;
}

输出如你所见

可见，key是字母时，排序方式是key的ASCII码值。

大家可以自己探索一下string类型的key的排序方式（虽然没什么意义，毕竟做题是谁也不会放着数组的下标不用去搞个string做key名）

5.map元素的访问

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

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

并且跟结构体的输出很像。

先用auto拿到map的每一个对组，再直接访问对组即可。

访问对组有两种方式，i->first和(*i).first都是直接指向的意思。我个人比较倾向于第一种，因为只有看见跟指针长得很像的东西我就想🤮

5.查找map里面的元素

vector里面的find函数大家都知道吧，这里跟他很像。

find函数查找的是key，当找到了这个key，他返回key的位置，找不到返回map的end()位置。

int main()
{
	map<char, int>m;
	m.insert((pair<char, int>('a', 10)));
	m.insert((pair<char, int>('b', 60)));
	m.insert((pair<char, int>('d', 50)));
	m.insert((pair<char, int>('z', 10)));
	m.insert((pair<char, int>('s', 10)));

	//find函数查找map里面的元素值
	auto i = m.find('d');
	if (i == m.end())
	{
		cout << "not find";
	}
	else
	{
		cout << i->second;
	}
	return 0;
}

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

需要使用erase函数

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

int main()
{
	map<char, int>m;
	m.insert((pair<char, int>('a', 10)));
	m.insert((pair<char, int>('b', 60)));
	m.insert((pair<char, int>('d', 50)));
	m.insert((pair<char, int>('z', 10)));
	m.insert((pair<char, int>('s', 10)));

	//find函数查找map里面的元素值
	int n = m.erase('b'); // 删除成功就返回1，否则返回0
	printMap(m);
	//find函数清除map
	m.erase(m.begin(), m.end());
	printMap(m);
	return 0;
}

偷个小懒，大家自己看吧

输出结果

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<unordered_map>

请看代码：

int main()
{
	// unordered-map的学习
	unordered_map<string, string>umap;
	umap.emplace("tom", "is");
	cout << umap["tom"] << endl;
	return 0;
}

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.find函数与coun函数的比较

关注这点，我讲的不一定好，大家去CSDN上一查便知。

首先我们必须时刻记住他俩是有区别滴。

find函数是查找函数，查找标准是key值。查找成功就返回他查找到的元素的位置(由于map里面key值不允许重复，所以最多只可能有一个)，查找失败就返回map的末尾位置，也就是map.end();

count函数，他也是依照key值查找，count查找成功就返回1，查找失败就返回0。

5.unordered_map和map的比较

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

map:

有序性就是最大的优点。

缺点是速度慢，占用空间大。所以我们一般在做题时不用他。

unordered_map

内部用hash实现。

速度很快，

但是创建hash表需要的时间复杂度很大

五、实际应用

1、leetcode题目 219 存在重复元素 2

题目链接：==>传送门

这是一个unordered_map的简单应用

题目思路不必多说，unordered_map里面第一个元素存储的是nums[i]元素值，第二个元素是该元素的下标i。

我们在遍历的过程中，由于unordered_map的key不能重复，所以，只要我们发现了重复的nums[i],直接访问就可以得到他与现在的值的距离。

上代码：

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

int main()
{
	map<char, int>m;
	m.insert((pair<char, int>('a', 10)));
	m.insert((pair<char, int>('b', 60)));
	m.insert((pair<char, int>('d', 50)));
	m.insert((pair<char, int>('z', 10)));
	m.insert((pair<char, int>('s', 10)));

	//find函数查找map里面的元素值
	int n = m.erase('b'); // 删除成功就返回1，否则返回0
	printMap(m);
	//find函数清除map
	m.erase(m.begin(), m.end());
	printMap(m);
	return 0;
}

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

题目链接: ==>传送门

这题可以说是模板题了。

我首先想到的是DFS，但此题数据太大，不容易过，所以，我们用hash求前缀和。

为什么要求前缀和呢？

假如，我们遍历nums数组，此时拿到的元素是nums[i],那么只要这个元素前面的一段元素的和为k-nums[i],那么这就是一种符合条件的情况。

但是，如果说前面总共有四个元素，而我们只需要取下标为1~3的元素，也就是第一个元素不能取，该怎么办呢？

我们默认随着数组的遍历，数组的前缀和是增加的。对于每一个前缀和，我们都把它放到unordered_map并计算次数。这就相当于把所有的前缀和都用一个数组存起来了。

既然已经得到了这个前缀和数组，那么后面的前缀和 减去 前面的前缀和 就等于中间这段的和了。

上代码：

#include<unordered_map>

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int>arr;    // 第一个int表示前缀和，第二个int表示这个前缀和出现的次数
    arr[0] = 1;
    int ret = 0;   // 用于计算前缀和
    int ans = 0;
    for (auto& i : nums)
    {
        ret += i;
        if (arr.find(ret - k) != arr.end())    // ret-k 如果跟前面的前缀和有重复，重复的那个前缀和就是ret-k.
                                               // 而此时的前缀和是ret, 所以中间的那一段和就是k
            ans += arr[ret - k];
        arr[ret]++;  // 重新创建前缀和pair
    }
    return ans;
}

int main()
{
    vector<int>nums = { 1,2,3};
    cout << subarraySum(nums, 3);
    return 0;
}

3、leetcode题目-525 连续数组

题目链接：==》传送门

这个题是模板题稍微变了一下形状。

我们让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存储的数点缀和与此前缀和的结束元素的下边。

上代码;

#include<unordered_map>

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int>arr;    // 第一个int表示前缀和，第二个int表示这个前缀和出现的次数
    arr[0] = 1;
    int ret = 0;   // 用于计算前缀和
    int ans = 0;
    for (auto& i : nums)
    {
        ret += i;
        if (arr.find(ret - k) != arr.end())    // ret-k 如果跟前面的前缀和有重复，重复的那个前缀和就是ret-k.
                                               // 而此时的前缀和是ret, 所以中间的那一段和就是k
            ans += arr[ret - k];
        arr[ret]++;  // 重新创建前缀和pair
    }
    return ans;
}

int main()
{
    vector<int>nums = { 1,2,3};
    cout << subarraySum(nums, 3);
    return 0;
}