一、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;elsecout << "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;
}