STL:set的使用

关于set

set是以特定的顺序存储相异元素的容器。

set是关联式容器，C++ STL中标准关联容器set, multiset, map, multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。

查找、插入、删除的时间复杂度都是O(logn)

一些特点：

1、在插入或赋初值时会自动排序（除非是unordered_set）

2、不能直接改变元素值，因为那样会打乱原本正确的顺序，要改变元素值必须先删除旧元素，则插入新元素

3、不提供直接存取元素的任何操作函数，只能通过迭代器进行间接存取，而且从迭代器角度来看，元素值是常数

4、每次insert或者erase之后，以前保存的iterator不会失效（关联式容器，只改变了一些指针的指向，原指针指向的内存没变）（当然，直接erase保存的指针肯定改变了）

set中的模板函数

begin() 返回指向第一个元素的迭代器

end() 返回指向最后一个元素的后一个位置的迭代器

clear() 清空内容

size() 返回当前元素个数

count(key_value)　　用来查找set中某个键值出现的次数，在set只可能为0或1

erase(key_value) 删除键值为key_value的元素

erase(iterator) 删除迭代器iterator指向的元素

erase(first,second) 删除迭代器first和second之间的元素，[first,second)

find(key_value) 返回指向key_value的迭代器，如果没有找到返回end()

insert(key_value) 将key_value插入到set中

lower_bound(key_value) 返回第一个大于等于key_value的迭代器

upper_bound(key_value) 返回第一个大于key_value的迭代器

equal_range(key_value) 返回一对迭代器,first等同于lower_bound,second_bound等同于upper_bound,即 [lower_bound,upper_bound)

//若set<int>a,b; vector<int>c

set_union(a.begin(),a.end(),b.begin(),b.end(),back_insert(c)) 　　　　　　　　并集

set_intersection(a.begin(),a.end(),b.begin(),b.end(),back_insert(c))　　　交集

set_difference(a.begin(),a.end(),b.begin(),b.end(),back_insert(c))　　　　差集

set_symmetric_difference(a.begin(),a.end(),b.begin(),b.end(),back_insert(c)) 对称差

//使用实例

//初始化set

//这个参考资料好少啊，自己尝试了这几种

 #include<cstdio>

 #include<set>

 using namespace std;

 int main()

 {

     int arr[] = { ,,,, };

     //定义时赋初值

     set<int>st1{,,,,};

     set<int>st2 = { ,,,, };

     set<int>st3(arr, arr + );

     //先定义，后赋值

     set<int>st4;

     st4 = { ,,,, };

     set<int>st5;

     st5.insert(arr, arr + );

     return ;

 }

//基本操作

 #include<cstdio>

 #include<set>

 using namespace std;

 int main()

 {

     int arr[] = { , , , , , , ,  };

     set<int>st(arr,arr + );

     //遍历

     //不像vector,只能通过迭代器进行间接存取

     for (set<int>::iterator it = st.begin(); it != st.end(); it++)

         printf("%d ", *it);

     printf("\n");

     //查找

     //未找到返回end()

     set<int>::iterator it = st.find();

     if(it != st.end())  printf("%d\n", *it);

     //插入

     //返回值为pair<set<int>::iterator,bool>

      st.insert(); st.insert();

      //删除

      //不要去删除不存在的元素

      st.erase(); st.erase();

      //计数，是否在集合中

      if (st.count())  printf("In\n");

      else  printf("Out\n");

      //上下界函数

     set<int>::iterator it1 = st.lower_bound();

     set<int>::iterator it2 = st.upper_bound();

     //区间定位

     pair<set<int>::const_iterator, set<int>::const_iterator>pr;

     pr = st.equal_range();

     if(pr.second != st.end())  printf("%d %d\n", *pr.first, *pr.second);

     for (set<int>::iterator it = st.begin(); it != st.end(); it++)

         printf("%d ", *it);

     return ;

 }

//集合操作

 #include<cstdio>

 #include<set>

 #include<vector>

 #include<iterator>      //inserter函数定义在里面

 #include<algorithm>        //set_union,set_intersection等定义在里面

 using namespace std;

 int main()

 {

     //若待处理的集合用vecter保存，必须确保无重复且有序

     //若用vector保存结果，使用函数back_inserter(dest)

     vector<int>v1 = { ,,,,, };

     vector<int>v2 = { ,,,,,, };

     vector<int>dest1;

     set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(dest1));

     //set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(dest));

     //set_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(dest));

     //set_symmetric_difference(v1.begin(), v1.end(), v2.begin(), v2.end(), back_inserter(dest));

     //若用set保存结果,使用函数inserter(dest,dest.begin())

     set<int>dest2;

     set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), inserter(dest2, dest2.begin()));

     //若待处理的集合用set保存，可以无序重复（会自动去重、排序）

     set<int>s1 = { ,,,,,,,, };

     set<int>s2 = { ,,,,,, };

     set<int>dest3;

     set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), inserter(dest3, dest3.begin()));

     return ;

 }

参考资料：

1、http://www.cplusplus.com/reference/set/set/?kw=set

2、https://blog.csdn.net/changjiale110/article/details/79108447

3、https://blog.csdn.net/rocky_56X/article/details/81772646

4、https://blog.csdn.net/yang20141109/article/details/51782027

巴特西

STL:set的使用

关于set

set中的模板函数

最新文章

热门文章