[学习笔记]——STL-set

常用的set包含 set 和 multiset 两个容器，分别表示“有序集合”和“有序多重集合”。即前者不能可以重复而后者可以重复。

两个容器都是基于红黑树实现，时间复杂度都单次log级别。

size(),clear(),empty() 操作认仍为 O ( 1 )_

set<int>s ;
struct rec{ xxx } ;  set<rec>s ;
multiset<long long> s ;
同时 set 和 multiset 必须定义“ < ”运算符

设迭代器为 it

set<int>::iterator it ;

it++ 会指向从小到大中排在 it 下一名的元素。（更小）
it-- 会指向从小到大中排在 it 上一名的元素。（更大）

---

multiset<int>s ;
multiset<int>::iterator it ;
int main(){
    s.insert(1); // 插入1
    s.erase(1); //删除所有1
    s.erase(it); //删除it所指的元素
    s.erase(it,it2)//删除it和it2所指区间中的所有元素

    cout<<s.count(1)<<endl ; //输出1的个数
    s.clear();//清空当前set

    it = s.begin() ;//返回最小元素的迭代器
    it = s.end()-1 ;//返回最大元素的迭代器

    it = s.find(x)//返回x的迭代器，失败返回 s.end()
    it = s.lower_bound(x) ;
    //二分查找 >= x 的最小元素，返回迭代器
    it = s.upper_bound(x) ;
    //二分查找 > x 的最小元素，返回迭代器
}

删除给定数x至多一次

if( (it = s.find(x) ) != s.end() )s.erase(it);

实现排序

multiset<int>s ;
multiset<int>::iterator it ;
int a[ MAXN ] , N ;
int main(){
    N = read() ;
    for( int i = 1 ; i <= N ; ++i ){
        a[ i ] = read() ; s.insert( a[ i ] ) ;
    }
    for( it = s.begin() ; it != s.end() ; it++ )
        printf("%d ",*it );
}

未完结