set是STL 中一种标准关联容器。它底层使用平衡的搜索树——红黑树实现，插入删除操作时仅仅需要指针操作节点即可完成，不涉及到内存移动和拷贝，所以效率比较高。
set，顾名思义是 “集合” 的意思，在 set 中元素都是唯一的，而且默认情况下会对元素自动进行升序排列，支持集合的交 (set_intersection), 差 (set_difference) 并 (set_union)，对称差 (set_symmetric_difference) 等一些集合上的操作，如果需要集合中的元素允许重复那么可以使用 multiset
1.头文件：<set> 2.定义：set<int> q; 3.输入（插入）：insert(x); 4.删除指定元素：erase(x); 5.清空：clear(); 6.判空：empty(); 7.大小：size(); 8.二分查找：q.lower_bound(x);
9.有序输出
set<int>::iterator it; for(it = q.begin();it != q.end();it++) { cout<<*it<<endl; }
set 模板原型
template <class Key, class Compare=less<Key>, class Alloc=STL_DEFAULT_ALLOCATOR(Key) > //Key为元素(键值)类型 greater是从升序排序（默认），可以改为less（降序排序）
set 容器的创建
#include <iostream> #include <set> #include <functional> using namespace std; set<int> s; int main() { set<int,greater<int> > seta; //greater<int>可以不写，默认是升序 set<int, less<int> > setb; //创建一个降序的set，需包含头文件functional int a[5] = {1,2,3,4,5}; set<int > setc(a,a+5); //数组a初始化一个set； set<int > setd(setc.begin(),setc.end()); //setc初始化一个set //上述两例均为区间初始化 set<int > sete(setd); //拷贝构造创建set return 0; } //注意写法set<int,less<int> >或set<int,greater<int> >，如果不空格，“>>”被当作位运算可能报错
set 容器的增删改查
1. 插入
#include <iostream> #include <set> using namespace std; set<int >s; void setprint(int cnt) { cout << "Test output :" << cnt << ":" << endl; for(set<int>::iterator it = s.begin(); it!= s.end(); it++) cout << *it << " "; puts(""); return ; } int main() { int cnt = 1; s.insert(1); s.insert(2); s.insert(5); setprint(cnt++); s.insert(2); //set只允许用一个值出现一次，要插入相同元素请用multiset setprint(cnt++); int a[4] = {11,12,13,14}; s.insert(a,a+4); //将区间[a, a+4]里的元素插入容器 setprint(cnt++); return 0; }
2. 删除
//s.erase(); 删除一个元素 //s.clear(); 删除set容器中的所有的元素 #include <iostream> #include <set> using namespace std; set<int >s; void setprint(int cnt) { cout << "Test output :" << cnt << ":" << endl; for(set<int>::iterator it = s.begin(); it!= s.end(); it++) cout << *it << " "; puts(""); return ; } int main() { int cnt = 1; for(int i = 1; i < 11; i++){ s.insert(i); } setprint(cnt++); s.erase(9); //根据元素删除 setprint(cnt++); set<int>::iterator ita = s.begin(); set<int>::iterator itb = s.begin(); s.erase(ita); //删除迭代器指向位置的元素 setprint(cnt++); ita = s.begin(); itb = s.begin(); itb++;itb++; s.erase(ita,itb); //删除区间[ita,itb)的元素 setprint(cnt); s.clear(); return 0; }
3. 修改
不能直接修改容器内数据，所以只能删除某元素再插入要修改的数值。
4. 查找
//s.find() 查找一个元素，如果容器中不存在该元素，返回值等于s.end() #include <iostream> #include <set> using namespace std; set<int >s; void setprint(int cnt){ cout << "Test output :" << cnt << ":" << endl; for(set<int>::iterator it = s.begin(); it!= s.end(); it++) cout << *it << " "; puts(""); return ; } int main(){ int cnt = 1; s.insert(1); s.insert(2); s.insert(5); setprint(cnt++); if(s.find(2) != s.end()) cout << "2 is existent" << endl; else cout << "2 is non-existent" << endl; if(s.find(3) == s.end()) cout << "3 is non-existent" << endl; else cout << "2 is existent" << endl; return 0; }
set 的其他常用操作
s.lower_bound(); 返回第一个大于或等于给定关键值的元素
s.upper_bound(); 返回第一个大于给定关键值的元素
s.equal_range(); 返回一对定位器，分别表示 第一个大于或等于给定关键值的元素 和 第一个大于给定关键值的元素，这个返回值是一个 pair 类型，如果这一对定位器中哪个返回失败，就会等于 s.end()
#include <iostream> #include <set> using namespace std; int main(){ set<int> s; s.insert(1); s.insert(2); s.insert(5); cout << "lower_bound & upper_bound test:" << endl; cout << "第一个大于或等于3的元素: " << *s.lower_bound(3) << endl; cout << "第一个大于或等于2的元素: " <<*s.lower_bound(2) << endl; cout << "第一个大于2的元素: " <<*s.upper_bound(2) << endl; cout << "equal_range test:" << endl; cout << "第一个大于或等于2的元素: " << *s.equal_range(2).first << endl; cout << "第一个大于2的元素: " << *s.equal_range(2).second << endl; return 0; }
//判断元素是否在set中 & 判断set是否为空 #include <iostream> #include <set> #include <functional> using namespace std; int main(){ set<int > s; if(s.empty()) cout << "容器为空" << endl; s.insert(1); if(!s.empty()) cout << "容器不为空" << endl; if(s.count(1)) cout << "1在容器中" << endl; if(!s.count(2)) cout << "2不在容器中" << endl; return 0; }
//自定义比较函数 #include <iostream> #include <set> #include <functional> using namespace std; struct cmp{ bool operator () (const int &a, const int &b){ return a > b; } }; set<int, cmp>s; //自定义排序函数构造set void setprint(int cnt){ cout << "Test output :" << cnt << ":" << endl; for(set<int,cmp>::iterator it = s.begin(); it!= s.end(); it++) cout << *it << " "; puts(""); return ; } int main(){ s.insert(1); s.insert(2); s.insert(6); setprint(1); return 0; }
