set&multiset 集合

1.定义和初始化

set为集合,插入到集合中的元素会在set中按一定顺序排序(故插入的时间复杂度 $O (l o g n)$ ),其中元素若已经存在,则不会重复插入

multiset为可重复集合,可以出现重复元素

dataType中必须包含比较方法(重载比较符号)

创建数据类型为dataType,名称为st的空集合,默认排序为从小到大

multiset<dataType>st;    
set<dataType>st;

创建数据类型为dataType,名称为st的空集合,排序为从大到小的集合

multiset<dataType,greater<>>st;    
set<dataType,greater<>>st;

与优先队列相同,set中也可以使用自定义结构体

struct str { //重载小于号 这里的str实际上就是pair<int,int>
    int first;
    int second;
    bool operator <(const str& a) const{
        if (first == a.first)return second < a.second;
        else return first < a.first;
    }
};
//由于重载小于运算符时返回的是小于号,排序应该小的排在前面,只有优先队列会与sort函数排序顺序不同
set<str>st;

2.遍历

for-auto 遍历按顺序遍历set中所有元素注意这里auto出来的类型是set迭代器(指针),加*号才可以输出具体的元素值

for(auto it:st){
    cout<<*it<<endl;
}

迭代器遍历见迭代器篇

3.内置方法

insert() 插入值为x的元素,set重复插入无效果,multiset可以重复插入

st.insert(x);

erase() 两种用法1.参数填写迭代器,删除迭代器指向的数据 2.填写dataType类型的值x,删除所有值为x的元素

st.erase(st.begin());//st.begin()为指向st第一个元素的迭代器,详见迭代器篇,意为删除第一个元素
st.erase(x);//删除值为x的所有元素,在multiset中一次性可能删除多个元素

lower_bound()&upper_bound() 二分,返回第一个大于等于x的元素的迭代器(第一个大于x的元素的迭代器)

//若st中为 0 1 2 3 4 5 6
int x=2;
auto it=st.lower_bound(x);//it会被赋值为指向数字2的迭代器,若有多个2,指向第一个2;
auto it=st.upper_bound(x);//it会被赋值为指向数字3的迭代器,若有多个3,指向第一个3;
cout<<*it;//输出it的值

count() 返回集合中有几个值为x的元素,set中有就是1,没有就是0,multiset返回具体个数

int cnt=st.count(x);

4.提示

插入时与优先队列复杂度一致,均为log,故set可以完全替代优先队列使用,并且如果知道需要删除的那个数的大小,即使不在队头,一样可以删掉
如果作为vis使用,会比map速度快不少
一般可以用二分查询所要删除的元素在哪里,然后erase删掉
缺点:由于set的内存分布是离散的,所以很难判断这个数在set中是第几个,如有需求还是得用排序后的数组或vector去查询,或采用其他办法

Set&Multiset

set&multiset 集合

1.定义和初始化

2.遍历

3.内置方法

4.提示