背景
今天考试深受平衡树之害,可以参见上一篇博客,想到了set却苦于实用的不熟练。同时QTY询问set的具体用法,所以写这篇博客,同时留作自用。
分类
参看了一下网上其他set博客,上来都是长篇大论概念。其实set很好理解,就是把一棵平衡树(红黑树)封装起来。这就是STL的牛×之处。
set分为set和multiset 后者中的元素可以重复而前者不同
set的插入查询操作效率很高,复杂度为O(logn),所以大多数情况下可以放心使用
使用方法
插入操作
set<int> s; s.insert(10);
删除操作
set<int> s; s.erase(10);
清空所有元素
set<int> s; s.clear();
返回第一个元素
set<int> s; cout<<*s.begin();
返回最后一个元素(注意s.end()指向的是最后一个元素的后一位置)
set<int> s; s.insert(12);s.insert(10); set<int>::iterator it; it=s.end();it--; cout<<*it;
判断是否为空
set<int> s; if(s.empty()){ cout<<"it is empty"; }
返回元素个数
set<int> s; cout<<s.size();
查找是否出现过
count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用,因为一个键值在set只可能出现0或1次,这样就变成了判断某一键值是否在set出现过了
set<int> s; s.insert(1); cout<<"set 中 1 出现的次数是 :"<<s.count(1)<<endl;
创建定位器,具体删除操作
erase(iterator) ,删除定位器iterator指向的值
erase(first,second),删除定位器first和second之间的值
erase(key_value),删除键值key_value的值
set<int> s; set<int>::const_iterator iter; set<int>::iterator first; set<int>::iterator second; for(int i = 1 ; i <= 10 ; ++i) s.insert(i); //第一种删除 s.erase(s.begin()); //第二种删除 first = s.begin(); second = s.begin(); second++; second++; s.erase(first,second); //第三种删除 s.erase(8);
元素检索
find()若找到,返回该键值迭代器的位置,否则,返回最后一个元素后面一个位置。
set<int> s; set<int>::iterator it; it=s.find(5); //查找键值为5的元素 if(it!=s.end()) //找到 cout<<*it<<endl; else //未找到 cout<<"未找到";
查找前驱和后继
set<int> s; s.insert(1); s.insert(3); s.insert(4); cout<<*s.lower_bound(2)<<endl; cout<<*s.lower_bound(3)<<endl; cout<<*s.upper_bound(3)<<endl;
小结:具体就是这样,非常实用,部分参考自他人