set的使用（c++）

set / multiset

STL里面已经为我们实现了两种红黑树，一种是存储关键字的set，另一种是存储双关键字的map，今天主要来了解set，无论是set还是map后面都跟一个multi，它们区别是set 不能存相同元素， multiset 可以存相同的元素（比如往set容器里面插入十个1，最终在set里面之后存储一个1，往multiset容器里插入十个1，这个容器里面就会存在十个1），其余的使⽤⽅式完全⼀致。因此，我们有时候可以⽤ set 帮助我们给数据去重

1 创建set

#include <iostream>
#include <set>
using namespace std;
int main()
{set<int> mp1;set<string> mp2;return 0;
}

2 size / empty

1. size ：返回 set 中实际元素的个数。时间复杂度： O(1) 。
2. empty ：判断 set 是否为空。时间复杂度： O(1) 。

3 begin / end

• 迭代器，可以使⽤范围 for 遍历整个红⿊树。
• 遍历是按照中序遍历的顺序，因此是⼀个有序的序列。

4 insert

• 向红⿊树中插⼊⼀个元素
• 时间复杂度： O(log N) 。

5 erase

• 删除⼀个元素
• 时间复杂度： O(log N) 。

6 find / count

1. find ：查找⼀个元素，返回的是迭代器。时间复杂度： O(log N) 。
2. count ：查询元素出现的次数，⼀般⽤来判断元素是否在红⿊树中。时间复杂度：O(log N)

• 如果想查找元素是否在 set 中，我们⼀般不使⽤ find，⽽是⽤ count。因为 find 的返回值是⼀个迭代器，判断起来不⽅便。但是使用count接口，它的返回值要么是0，要么是1，如果是0说明它不存在这颗红黑树中，如果是1说明他存在红黑树中，判断起来比较方便

7 lower_bound / upper_bound

1. lower_bound ：⼤于等于 x 的最⼩元素，返回的是迭代器；时间复杂度： O(log N) 。
2. upper_bound ：⼤于 x 的最⼩元素，返回的是迭代器。时间复杂度： O(log N) 。

代码：

#include <iostream>
#include <set>using namespace std;int a[] = { 3,6,7,9,4,2,5 };int main()
{set<int> mp;// 插入for (auto x : a){mp.insert(x);}// 遍历 set，最终的结果应该是有序的for (auto x : mp){cout << x << " ";   }cout << endl;//2 3 4 5 6 7 9if(mp.count(2)) cout << "2" << endl;      //2if(mp.count(10)) cout << "10" << endl;if(mp.count(3)) cout << "3" << endl;      //3if(mp.count(30)) cout << "30" << endl;mp.erase(2);mp.erase(3);if(mp.count(2)) cout << "2" << endl;else cout << "no:2" << endl;if(mp.count(3)) cout << "3" << endl;else cout << "no:3" << endl;auto x = mp.lower_bound(7);auto y = mp.upper_bound(7);cout << *x << " " << *y << endl;   //7 9return 0;
}