数据结构十三、set & map

一、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、全部测试代码

1. #include <iostream>
2. #include <set>
3. using namespace std;
5. int a[] = { 10,60,20,70,80,30,90,40,100,50 };
7. int main()
8. {
9.         set<int> mp;
11.         for (auto e : a)
12.         {
13.                 mp.insert(e);
14.         }
16.         for (auto x : mp)
17.         {
18.                 cout << x << " ";
19.         }
20.         cout << endl;
22.         if (mp.count(1))
23.                 cout << "1" << endl;
24.         if (mp.count(10))
25.                 cout << "10" << endl;
27.         mp.erase(10);
29.         if (mp.count(10))
30.                 cout << "YES" << endl;
31.         else
32.                 cout << "NO" << endl;
34.         auto x = mp.lower_bound(20);
35.         auto y = mp.upper_bound(20);
37.         cout << *x << " " << *y << endl;
39.         return 0;
40. }

复制代码

二、map

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

        向红黑树中插入一个元素。这里必要一个pair，可以用{}的情势。

1. #include <iostream>
2. #include <map>
3. using namespace std;
5. void print(map<string, int>& mp)
6. {
7.         for (auto& p : mp)
8.         {
9.                 cout << p.first << " " << p.second << endl;
10.         }
11. }
13. int main()
14. {
15.         map<string, int> mp;
17.         mp.insert({ "zhangsan", 1 });
18.         mp.insert({ "lisi", 2 });
19.         mp.insert({ "wangwu", 3 });
21.         print(mp);
23.         return 0;
24. }

复制代码

2、operator[]

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

1. #include <iostream>
2. #include <map>
3. using namespace std;
5. void print(map<string, int>& mp)
6. {
7.         for (auto& p : mp)
8.         {
9.                 cout << p.first << " " << p.second << endl;
10.         }
11. }
13. int main()
14. {
15.         map<string, int> mp;
17.         mp.insert({ "zhangsan", 1 });
18.         mp.insert({ "lisi", 2 });
19.         mp.insert({ "wangwu", 3 });
21.         print(mp);
23.         cout << mp["zhangsan"] << endl;
24.         mp["zhangsan"] = 110;
25.         cout << mp["zhangsan"] << endl;
27.         return 0;
28. }

复制代码

三、例题

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

1. #include <iostream>
2. #include <set>
3. using namespace std;
5. const int INF = 1e7 + 10;
7. int n;
8. set<int> mp;
10. int main()
11. {
12.         cin >> n;
13.         int ret;
14.         cin >> ret;
15.         mp.insert(ret);
17.         mp.insert(-INF);
18.         mp.insert(INF);
20.         for (int i = 2;i <= n;i++)
21.         {
22.                 int x;
23.                 cin >> x;
25.                 auto it = mp.lower_bound(x);
26.                 auto tmp = it;
27.                 tmp--;
29.                 if (*it == x)
30.                         continue;
32.                 ret += min(abs(*tmp - x), abs(*it - x));
33.                 mp.insert(x);
34.         }
35.         cout << ret << endl;
37.         return 0;
38. }

复制代码