数据结构十三、set & map-EW帮帮网

一、set

1、size / empty

size：返回set中实际元素的个数

empty：判断set是否为空

2、begin / end

这是两个迭代器，因此可以使用范围for来遍历整个红黑树。其中，遍历是按照中序遍历的顺序，因此是一个有序序列。

3、insert / erase

insert：向红黑树中插入一个元素

erase：删除一个元素

4、find / count

find：查找一个元素，返回的是迭代器

count：查询元素出现的次数

如果想查找元素是否在set中，我们一般不使用find，而是使用count。因为find的返回值是一个迭代器，判断起来不方便。

5、lower_bound / upper_bound

lower_bound：大于等于x的最小元素，返回的是迭代器

upper_bound：大于x的最小元素，返回的是迭代器

6、所有测试代码

#include <iostream>
#include <set>
using namespace std;

int a[] = { 10,60,20,70,80,30,90,40,100,50 };

int main()
{
	set<int> mp;

	for (auto e : a)
	{
		mp.insert(e);
	}

	for (auto x : mp)
	{
		cout << x << " ";
	}
	cout << endl;

	if (mp.count(1))
		cout << "1" << endl;
	if (mp.count(10))
		cout << "10" << endl;

	mp.erase(10);

	if (mp.count(10))
		cout << "YES" << endl;
	else
		cout << "NO" << endl;

	auto x = mp.lower_bound(20);
	auto y = mp.upper_bound(20);

	cout << *x << " " << *y << endl;

	return 0;
}

二、map

map与set的区别：set里面存储的是一个单独的关键字（也就是存一个int、char、double或者string）。而map里面存的是一个pair<key, value>（k-v模型），不仅有一个关键字，还有一个与关键字绑定的值，比较方式是按照key的值来比较。比如，我们可以在map中存<string, int>来统计字符串出现的次数。

1、insert

向红黑树中插入一个元素。这里需要一个pair，可以用{}的形式。

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

void print(map<string, int>& mp)
{
	for (auto& p : mp)
	{
		cout << p.first << " " << p.second << endl;
	}
}

int main()
{
	map<string, int> mp;

	mp.insert({ "zhangsan", 1 });
	mp.insert({ "lisi", 2 });
	mp.insert({ "wangwu", 3 });

	print(mp);


	return 0;
}

2、operator[]

重载[]，使得map可以像数组一样使用。

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

void print(map<string, int>& mp)
{
	for (auto& p : mp)
	{
		cout << p.first << " " << p.second << endl;
	}
}

int main()
{
	map<string, int> mp;

	mp.insert({ "zhangsan", 1 });
	mp.insert({ "lisi", 2 });
	mp.insert({ "wangwu", 3 });

	print(mp);

	cout << mp["zhangsan"] << endl;
	mp["zhangsan"] = 110;
	cout << mp["zhangsan"] << endl;

	return 0;
}

三、例题

算法原理：求出最小波动值，我们只需要针对某一天的营业额，找出前面的数中哪个数离它最近（大于等于x的最小值或者小于等于x的最大值）。前一种情况可以调用lower_bound函数，后一种情况可以利用迭代器来解决。

#include <iostream>
#include <set>
using namespace std;

const int INF = 1e7 + 10;

int n;
set<int> mp;

int main()
{
	cin >> n;
	int ret;
	cin >> ret;
	mp.insert(ret);

	mp.insert(-INF);
	mp.insert(INF);

	for (int i = 2;i <= n;i++)
	{
		int x;
		cin >> x;

		auto it = mp.lower_bound(x);
		auto tmp = it;
		tmp--;

		if (*it == x)
			continue;

		ret += min(abs(*tmp - x), abs(*it - x));
		mp.insert(x);
	}
	cout << ret << endl;

	return 0;
}

数据结构十三、set & map