笔记

C++STL中map容器的学习笔记

发布于 2018 年 7 月 31 日

弱鸡冻葱虽然瞎吉尔搞了三年的OI,但其实只是一个从pascal起手,后来直接硬套的C艹的语法的沙雕选手。所以之前很少使用STL的相关内容,也很少使用C++11以上的各种特性。而今天我刷题的时候被一道题蜜汁卡60分而困扰不已。后来观察了学长cy的代码之后发现学长使用了一个对我来说很陌生的容器——map。当然,对我来说很陌生就是因为我太菜了。

于是我便去搜了一搜map的相关内容,发现这个东西真的很劲。可以用来解决之前卡住我的很多问题。下面是我学习map的一些笔记和实例。

1.初步了解

Map(映射)是一种有序STL关联容器,提供一种一对一键-值(key-value)对应关系。每个键只能在map中出现一次,而且是按照key的升序有序排列的。Map的内部是通过一颗红黑树排列的(一种非严格意义上的平衡二叉树),这棵树有对数据进行自动排序的功能而这要求key的类有对operator<的定义。关联式容器的特点是增加和删除节点对迭代器的影响很小,并且除了操作节点外,对其他节点不会造成成影响。对于迭代器来说,可以修改value,但是不能修改key。

Map支持自动建立键值对的功能,其中key和value可以使用自定义的类。也支持根据key快速查找记录,查找的复杂度基本是log(N)。快速插入键值对,快速删除键值对,根据key修改value记录和遍历所有记录的功能。当然,Map也支持其他STL容器公用的许多功能。比如查找元素是否存在(find()),查询map大小(size())等等,不在一一赘述。

2. 简单使用

1.构造

Map的构造函数有6个,但是常用的有三(yi)个。我们一般使用如下方法构造一个map:

map<int, string> map_1;

这样,我们就构造了一个名为map_1的,key类型为intvalue类型为string的map。

2.数据的插入

一般插入数据有两种方法——使用insert()或者使用一种类似于数组的结构插入数据。

insert()有两种用法,分别是插入pair类型和value_type类型(其实都挺麻烦的)

`map_1.insert(pair<int, string> (1, “One”));`

`map_1.insert(map<int, string>::value_type (2, “Two”);`

这样,我们就插入了两个键值对。

当然,还有这个最常用的:

map_1[4] = “Four”;

这样,就自动创建了一个( 4 : “Four”)的键值对。比insert函数简洁了很多。而且数组方式和insert方式有一个显著的不同点:当要插入的键值被占用时,insert函数会添加失败并且返回异常值,而数组法会替换掉原来的value值。

3.数据的删除

数据的删除有三种方式,分别是删除一个对象(参数是一个迭代器),删除一个范围(参数是两个迭代器),删除一个key值对应的键值对(参数是key的类)。当然,也可以使用clear()来清空(等价于map_1.erase(map_1.begin(), map_1.end());)。

3.注意点

需要注意的是,如果你使用形如for (auto it = map_1.begin(); it != map_1.end(); it++)来遍历map的话。在这个循环中,迭代器it有两个成员:it->firstit->second,分别表示该键值对中的keyvalue。而如果你使用形如for (auto it : map_1)来遍历的话,在这个循环中,你需要使用.运算符来调用it的两个成员而不是’->’运算符,即it.firstit.second(我还没明白为啥但是这么搞就对了)

4.一个实例

其实就是上边我提到的那道洛谷题。这道题如果使用map的话,就会十分简洁。这里是我的代码,直接放上去算了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

long long int readll() //读入优化
{
	long long n = 0;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar());
	for (; isdigit(ch); ch = getchar())
	{
		n = (n << 3) + (n << 1) + (ch ^ 48);
	}
	return n;
}

bool isprime(ll n) //一个很暴力的质数检查
{
	if (n < 2) return false;
	for (int i = 2; 1ll * i * i <= n; i++)//注意这里并不能使用i < sqrt(n)!
	{
		if (!(n % i)) return false;
	}
	return true;
}

int main(int argc, char const *argv[])
{
	int T; cin>>T;
	while(T--)
	{
		map<ll, int> times; //创建map
		int n, m;
		scanf("%d%d", &n, &m);
		for(int i = 0; i < n; i++)
		{
			times[readll()]++; //对于A的每个因数对应的键值++
		}
		for (int i = 0; i < m; i++)
		{
			times[readll()]--; //对于B的每个因数对应的键值--
		}

		if (times.find(1) != times.end()) //把值为1的键值对删除
		{
			times.erase(1);
		}

		for (auto num : times) //把空了的键值对删除(很不清真的方法233)
		{
			if (!num.second)
			{
				times.erase(num.first);
			}
		}

		if (times.size() > 1 || times.size() < 1) //如果没有键值对/键值对数过多
		{
			puts("NO");//不满足题意
		}
		else
		{
			for (auto num : times) //如果剩下的不是质数或者剩下了数个相同的数
			{
				if (!isprime(num.first) || num.second != 1)
				{
					puts("NO"); //不合题意
				}
				else puts("YES"); //否则通过检查,符合题意
			}
		}
	}

	return 0;
}/* Copyright (c) 2018 DCTewi.com */

至于我一开始一直卡60分的代码,可以在冻葱云公开文件的Code文件夹找到。技术十分菜,还请轻喷。

以上,就是弱鸡冻葱的map学习笔记。

  1. 头像
    冻葱Tewi

    补充1:

    for (auto it : map_1)中,这个it被定义成了一个类似于pair的东西,所以可以直接调用其成员。
    for (auto it = map_1.begin(); it != map_1.end(); it++) 一句中,迭代器是一个指针,所以需要使用->运算符。

    由cy学长提供

来一发吐槽