[学习笔记]——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 );
}
未完结