题解 | 【模板】集合操作

本题重要知识点在求解后继结点和前驱结点上，为此必须要清楚s.lower_bound和s.upper_bound的区别，以及s.begin和s.end的意义与边缘的处理

#include<bits/stdc++.h>
#include <set>

using namespace std;

set<int> s;

void insertValue(int x){//TODO 实现插入逻辑
    s.insert(x);
}
void eraseValue(int x){//TODO 实现删除逻辑
    s.erase(x);
}

int xInSet(int x){//TODO 实现存在性检查
    return s.count(x);
    //功能： 返回集合中等于 x 的次数。
    //s.find则是返回你要查找的元素的下标，便于你后面操作它

}

int sizeOfSet(){//TODO 返回集合大小
    return s.size();
}

int getPre(int x){//TODO 实现找前驱
    auto pre = s.lower_bound(x);//寻找第一个大于或等于x的元素。
    //注意返回的是“结点”，那肯定是指针，那么it的变量类型绝不会是int，而应该是指针类型，
    //又因为变量类型是std::set<int>::iterator无比复杂，所以偷懒使用auto
    
    if (pre == s.begin()) {//从这里也可以发现s.begin, s.end也同样是个迭代器(指针)，并不是int
        return -1;//lower_bound返回的是大于等于x的第一个元素的迭代器，--之后即得到前驱结点
    }
    pre--;
    return *pre; //pre是指针，函数是int类型，要对pre解引用
}

int getBack(int x){//TODO 实现找后继
    auto back = s.upper_bound(x);//寻找第一个严格大于x的元素
    if (back == s.end()) {
        //s.end()并不指向集合里的最后一个元素，而是指向最后一个元素之后的“虚空位置”。
        return -1;
    }
    return *back;
}

int main(){
    int q,op,x;
    cin>>q;
    while(q--){
        cin>>op;
        if(op==1){
            cin>>x;
            insertValue(x);
        }
        if(op==2){
            cin>>x;
            eraseValue(x);
        }
        if(op==3){
            cin>>x;
            if(xInSet(x)){
                cout<<"YES\n";
            }else{
                cout<<"NO\n";
            }
        }
        if(op==4){
            cout<<sizeOfSet()<<endl;
        }
        if(op==5){
            cin>>x;
            cout<<getPre(x)<<endl;
        }
        if(op==6){
            cin>>x;
            cout<<getBack(x)<<endl;
        }
    }
    return 0;
}