set就是集合,STL的set用二叉树实现,
集合中的每个元素只出现一次(参照数学中集合的互斥性),
并且是排好序的(默认按键值升序排列)
(1)set的创建
set<int> a;
set<int> a = {1,2,3,4};
set<int,greater<int>> q = {1,2,3,4};//倒叙创建
其中可以是各种类型,包括结构体
(2)判断set是否为空 O(1)
a.empty();
(3)set的大小 O(1)
a.size();
(4)将set清空
a.clear();
(5)set中加入元素 O(log(n))
a.insert(2);
(6)set删除元素 O(log(n)
a.erase(1);
(7)set的二分 O(logn)
a.lower_bound(1);//找到大于等于x的最小的元素的迭代器
a.upper_bound(2);//找到大于x的最小的元素的迭代器
(8)set返回某个元素的个数(判断某个元素是否存在) O(k + log(n))
a.count(4) == 1;
(9)set的遍历
for(auto x : a)
(10)用hash实现的set
unordered_set<int> s;
里面的增删改查都为O(1)
赞