#include <set>
set 集合容器:实现了红黑树的平衡二叉检索树的数据结构,插入元素时,它会自动调整二叉树的排列,把元素放到适当的位置,以保证每个子树根节点键值大于左子树所有节点的键值,小于右子树所有节点的键值;另外,还得保证根节点左子树的高度与右子树高度相等。
平衡二叉检索树使用中序遍历算法,检索效率高于vector、deque和list等容器,另外使用中序遍历可将键值按照从小到大遍历出来。时间复杂度:logn
构造set集合主要目的是为了快速检索,不可直接去修改键值。
1. 自定义比较函数
(1)元素不是结构体:
例:
//自定义比较函数myComp,重载“()”操作符
bool myComp(const your_type &a,const your_type &b)
{
return a.data-b.data>0;
}
set<int,myComp> s;
......
set<int,myComp>::iterator it;
(2)如果元素是结构体,可以直接将比较函数写在结构体内。
例:
struct Info
{
string name;
float score;
//重载“<”操作符,自定义排序规则
bool operator < (const Info &a) const
{
//按score从大到小排列
return a.score<score;
}
}
set<Info> s;
......
set<Info>::iterator it;
2. set的基本操作:
begin() 返回指向第一个元素的迭代器
clear() 清除所有元素
count() 返回某个值元素的个数
empty() 如果集合为空,返回true
end() 返回指向最后一个元素的迭代器
equal_range() 返回集合中与给定值相等的上下限的两个迭代器
erase() 删除集合中的元素
find() 返回一个指向被查找到元素的迭代器
get_allocator() 返回集合的分配器
insert() 在集合中插入元素
lower_bound() 返回指向大于(或等于)某值的第一个元素的迭代器
key_comp() 返回一个用于元素间值比较的函数
max_size() 返回集合能容纳的元素的最大限值
rbegin() 返回指向集合中最后一个元素的反向迭代器
rend() 返回指向集合中第一个元素的反向迭代器
size() 集合中元素的数目
swap() 交换两个集合变量
upper_bound() 返回大于某个值元素的迭代器
value_comp() 返回一个用于比较元素间的值的函数