STL set
头文件set主要包括set和multiset两个容器,分别是“有序集合”和“有序多重集合”
即前者的元素不能重复,而后者可以包含若干个相等的元素
set和multiset的内部实现是一棵红黑树,它们支持的函数基本相同
include声明
#include <set>
函数声明
set<int> s;
struct rec{…}; set<rec> s; // 结构体rec中必须定义小于号
multiset<double> s;
/////
size/empty/clear
与vector类似
size()
empty()
clear()
/////
迭代器
set和multiset的迭代器称为“双向访问迭代器”,不支持“随机访问”,支持星号(*)解除引用,仅支持”++”和--“两个与算术相关的操作
设it是一个迭代器,例如
set<int>::iterator it;
若把it++,则it会指向“下一个”元素。这里的“下一个”元素是指在元素从小到大排序的结果中,排在it下一名的元素
同理,若把it--,则it将会指向排在“上一个”的元素
/////
begin/end
返回集合的首、尾迭代器,时间复杂度均为O(1)。
begin()
end()
s.begin() 是指向s集合中最小元素的迭代器。
s.end() 是指向s集合中最大元素的下一个位置的迭代器
换言之,就像vector一样,因此s.end()是指向集合中最大元素的迭代器
/////
insert
insert()
s.insert(x)把一个元素x插入到集合s中,时间复杂度为O(logn)
在set中,若元素已存在,则不会重复插入该元素,对集合的状态无影响
/////
find
find()
s.find(x) 在集合s中查找等于x的元素,并返回指向该元素的迭代器
若不存在,则返回s.end()
时间复杂度为O(logn)
/////
lower_bound/upper_bound
lower_bound()
upper_bound()
这两个函数的用法与find类似,但查找的条件略有不同,时间复杂度为 O(logn)
s.lower_bound(x) 查找大于等于x的元素中最小的一个,并返回指向该元素的迭代器
s.upper_bound(x) 查找大于x的元素中最小的一个,并返回指向该元素的迭代器。
/////
erase
erase()
设it是一个迭代器,s.erase(it) 从s中删除迭代器it指向的元素,时间复杂度为O(logn)
设x是一个元素,s.erase(x) 从s中删除所有等于x的元素,时间复杂度为O(k+logn),其中k是被删除的元素个数
/////
count
count()
s.count(x) 返回集合s中等于x的元素个数,时间复杂度为 O(k +logn),其中k为元素x的个数
标签:set,指向,迭代,STL,复杂度,元素,集合 From: https://www.cnblogs.com/dianman/p/18450155