一、set文档介绍
1. set是按照一定次序存储元素的容器
2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素 不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。
3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直 接迭代。
5. set在底层是用二叉搜索树(红黑树)实现的。
注意：
1. 与map/multimap不同，map/multimap中存储的是真正的键值对，set中只放value，但在底层实际存放的是由构成的键值对。
2. set中插入元素时，只需要插入value即可，不需要构造键值对。
3. set中的元素不可以重复(因此可以使用set进行去重)。
4. 使用set的迭代器遍历set中的元素，可以得到有序序列
5. set中的元素默认按照小于来比较
6. set中查找某个元素，时间复杂度为：$log_2 n$
7. set中的元素不允许修改(底层使用二叉搜索树实现的）
8. set中的底层使用二叉搜索树(红黑树)来实现。
总结一下，set最重要的几个功能：
1、判断在还是不在
2、去重
3、排序
二、set常用接口举例
1、排序+去重
void test()
{
int array[] = { 1, 1, 2, 2, 3, 3, 8, 5, 6 };
set<int> s(array, array + sizeof(array) / sizeof(int));
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}
int main()
{
test();
system("pause");
return 0;
}输出结果：
2、插入元素的时候，元素已经存在的不插入
void test()
{
int array[] = { 1, 1, 2, 2, 3, 3, 8, 5, 6 };
set<int> s(array, array + sizeof(array) / sizeof(int));
s.insert(2);
s.insert(3);
s.insert(9);
s.insert(10);
set<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}输出结果：
3、构建键值对插入：pair insert ( const value_type& x )
在set中插入元素x，实际插入的是构成的键值对， 如果插入成功，返回(该元素在set中的位置，true),如果插入失败，说明x在set中已经存在，返回(x在set中的位 置，false).
void test()
{
int array[] = { 1, 1, 2, 2, 8, 5, 6 };
set<int> s(array, array + sizeof(array) / sizeof(int));
set<int>::iterator it;
pair<set<int>::iterator, bool> ret;
ret = s.insert(1);
if (ret.second == false)
{
it = ret.first;
}
s.insert(it,2);
s.insert(it,3);
s.insert(it,9);
s.insert(it,10);
while (it != s.end())
{
cout << *it << " ";
it++;
}
cout << endl;
}输出结果：
4、iterator insert ( iterator position, const value_type& x）
在set的position位置插入x，实际插入的是构成的键值对，注意：position位置只是参考，x最终不一定在该位置。
三、与multiset的区别
1、set与multiset最大的区别是multiset中的元素可以重复
下面举例说明：
void test()
{
int array[] = { 1, 1, 2, 2, 8, 5, 6 };
multiset<int> s(array, array + sizeof(array) / sizeof(int));
s.insert(2);
s.insert(3);
s.insert(9);
s.insert(10);
for (auto& e:s)
{
cout << e << " ";
}
cout << endl;
}输出结果：
所以排序的时候选择multiset较为方便。
2、使用multiset查找重复元素时，找到的是中序访问的第一个元素
下面用一段代码举例说明：
void test()
{
int array[] = { 1, 1, 2, 2, 8, 5, 6 };
multiset<int> s(array, array + sizeof(array) / sizeof(int));
multiset<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
it++;
}
cout <<endl;
it = s.find(2);
cout << *it << endl;
it++;
cout << *it << endl;
it++;
cout << *it << endl;
it++;
}输出结果：
因为multiset底层是一个搜索二叉树，按中序遍历刚好是排完序的，由输出结果可知，找到的是中序遍历的第一个数。