set,顾名思义,它是一个集合,它当中没有重复的元素,并按照顺序排列好
使用场景 : set一般用于查找问题中的查找有无,即给定一个元素判断这个元素是否存在于这个数组中。还可以用来删除数组中特定的数(因为复杂度低),配合set中的lower_bound()函数使用;
头文件 : #include < set >
定义 : set< typename > s //这里的typename可以是任何一种数据类型
使用
s.insert(x); //插入一个元素,复杂度为log(n)
s.erase(x); //删除一个元素,复杂度为log(n) 在遍历时删除的话,先用一个变量存当前的值,先让迭代器++,再删除
s.size(); //返回当前set中的大小
s.empty(); //判断set是否为空,为空返回true
s.begin() ; //返回set第一个元素的迭代器,注意不是数值
s.end(); //返回set最后一个元素下一位置的迭代器
s.find(x); //返回x在set中的迭代器,若不存在则返回s.end()
set的遍历
首先我们需要定义set的一个迭代器来进行遍历
set<int>::iterator it; //定义迭代器
for(it=s.begin();it!=s.end();it++)
{
cout << *it << " "; //注意是迭代器,需要加上*才可以输出值
}
set的lower_bound和upper_bound函数
lower_bound(x):返回set中第一个大于等于x的迭代器
upper_bound(x):返回set中第一个大于x的迭代器
cout << *s.lower_bound(x) << endl;
cout << *s.upper_bound(x) << endl;
cout << *--s.lower_bound(x) << endl; //输出set中比x小的最大的元素
s.earse( *s.lower_bound(x) ); //删除set中第一个大于等于x的值
set的元素更新
更新集合里面的元素值时,一定要先删除,再更新,最后再插入。若直接更新,则序无法保证。若先更新,则无法删除对应的元素。所以必须先删除,再更新,最后再插入。
multiset的使用
set里面不允许有重复的元素,但是我们要是希望解除掉这个束缚,用multiset就可以了
使用的话跟set没有区别,只要在声明的时候用multiset即可
multiset<int> s