set

创建

set <int> s         //创建一个普通的set,默认越小越前
set <int, great<int>> s     //创建一个越大越前的set
multiset <int> s            //创建一个元素可以重复的set

初始化

1. 利用数组初始化

int a[3] = {111, 222, 333};
set <int> s (a, a + 3);

2.复制一个set

set <int> s1;
set <int> s2 (s1);  //s2与s1完全相同

3.区间复制一个set

set <int> s2 (开始元素的迭代器, 结束元素的迭代器);

遍历

1.正向遍历

set<int>::iterator it;  //定义前向迭代器
    for (it = s.begin(); it != s.end(); it++)
//*it即为每一个元素的值,it为指向每一个元素的迭代器

2.反向遍历

set<int>::reverse_iterator rit; //定义反向迭代器
    for (rit = s.rbegin(); rit != s.rend(); rit++)
//*rit即为每一个元素的值,rit为指向每一个元素的迭代器 

insert

复杂度\(O(log n)\)

s.insert(x);        //普通地在s中插入元素x

s.insert(开始元素的迭代器, 结束元素的迭代器);

erase

复杂度\(O(log n)\)或\(O(k+log n)\) (k为删除元素的个数)

s.erase(it);            //it为一个迭代器
s.erase(x);             //  x为一个元素,删除所有值为x的元素

如果在multiset中只想删除一个值为x的元素,可以执行以下操作

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

size

复杂度\(O(1)\)

s1.size()   //返回s1中元素的个数

empty

复杂度\(O(1)\)

s1.empty()  //判断是否为空,若为空则返回true,否则返回false

clear

s1.clear();     //清空s1中的所有元素

begin/end

复杂度\(O(1)\)

s1.begin()  //指向s1的第一个位置,*s1.begin()即为第一个元素的值
s1.end()        //指向s1的最后一个位置的下一个位置,*s1.begin()即为s1的元素个数,和s1.size()的值相同

find

复杂度\(O(log n)\)

判重的时候直接用

if(s.find(1)==s.end())

count

复杂度\(O(k+log n)\) (k为x出现的次数)

s1.count(x)     //返回x出现的次数

lower_bound/upper_bound

复杂度均为O(log n)

s.lower_bound(x)            //返回a,使得a满足a>=s且a最小
s.upper_bound(x)            //返回a,使得a满足a>s且a最小
//如果没有满足条件的a则返回s.end()

发表评论

邮箱地址不会被公开。 必填项已用*标注