stl容器有哪几种，Cpp浅析系列-STL之set
stl容器有哪几种，Cpp浅析系列-STL之setbegin()返回指向第一个元素的迭代器clear()清除所有元素count()返回某个值元素的个数，0或1，可以用来判断是否存在某数empty()如果集合为空，返回trueend()返回指向最后一个元素的迭代器equal_range()返回集合中与给定值相等的上下限的两个迭代器erase()删除集合中的元素set集合中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。find()返回一个指向被查找到元素的迭代器；如果没有找到，返回指向集合最后一个元素的迭代器。get_allocator()返回集合的分配器insert()在集合中插入元素可以在集合中插入其他数组中指定个数的值lower_bound()返回指向大于（或等于）某值的第一个元素的迭代器key_comp()返回一个用于元素间值比较的函数max_size()返回集合能容纳的元素的最大限值rbe
前言
CPP
集合(Set)t是一种元素唯一的、包含已排序对象的数据容器。
C STL中标准关联容器set， multiset， map， multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。
对于map和set这种关联容器来说，不需要做内存拷贝和内存移动。以节点的方式来存储，其节点结构和链表差不多。
博主当前的CPP版本为c 14，所以相关源码内容就是以这个版本的为准。
Set定义#include<set>
usingnamespacestd;
set<int>s1;//空对象
set<int>s2{3 4 2 1};//列表清单 默认less递增 输出为{1 2 3 4}
set<int greater<int>>s3{6 5 7 8};//列表清单 输出为{8.7.6.5}
Set常规操作
支持正向和反向迭代器，但是不支持随机迭代器访问元素。
C 中文在线手册：https://zh.cppreference.com/
begin()返回指向第一个元素的迭代器clear()清除所有元素count()返回某个值元素的个数，0或1，可以用来判断是否存在某数empty()如果集合为空，返回trueend()返回指向最后一个元素的迭代器equal_range()返回集合中与给定值相等的上下限的两个迭代器erase()删除集合中的元素
set集合中的删除操作是不进行任何的错误检查的，比如定位器的是否合法等等，所以用的时候自己一定要注意。find()返回一个指向被查找到元素的迭代器；如果没有找到，返回指向集合最后一个元素的迭代器。get_allocator()返回集合的分配器insert()在集合中插入元素
可以在集合中插入其他数组中指定个数的值lower_bound()返回指向大于（或等于）某值的第一个元素的迭代器key_comp()返回一个用于元素间值比较的函数max_size()返回集合能容纳的元素的最大限值rbegin()返回指向集合中最后一个元素的反向迭代器rend()返回指向集合中第一个元素的反向迭代器size()集合中元素的数目swap()交换两个集合变量upper_bound()返回大于某个值元素的迭代器value_comp()返回一个用于比较元素间的值的函数
允许多个元素的插入，使用迭代器指定位置。
/*
*insert能插入多个，慢但是实用
**/
voidadd1(){
set<int>demo{1 2};
//在第一个元素后面插入3
demo.insert(demo.begin() 3);//{1 2 3} 结果遵循递增规则
//直接插入元素 也是按照规则排列
demo.insert(-1);//{-1 1 2 3}
//C 11之后 可以用emplace_hint或者emplace替代
//插入其他容器的部分序列
vector<int>test{7 8 9};
demo.insert( test.begin() --test.end());//{-1 1 2 3 8}
//插入初始化列表
demo.insert({10 11});//{-1 1 2 3 8 10 11}
set<int>s=demo;
set<int>::iteratoriter;
for(iter=s.begin();iter!=s.end(); iter){
cout<<*iter<<"";
}
}
emplace插入
注意是每次只能插入一个，而且是只有构造函数，效率高！
/*
*emplace，只能插入一个
*而且如果元素已经存在，是不会再次插入的
**/
voidadd2(){
set<int>demo{1 2};
demo.emplace(4);//{1 2 4}
demo.emplace(4);//还是{1 2 4}
set<int>s=demo;
set<int>::iteratoriter;
for(iter=s.begin();iter!=s.end(); iter){
cout<<*iter<<"";
}
}
遍历元素
/*
*直接用迭代器，注意const_iterator还是iterator
**/
voidsearch(){
set<int>demo{1 2};
//如果参数为constvector<int>需要用const_iterator
//vector<int>::const_iteratoriter=v.begin();
set<int>s=demo;
set<int>::iteratoriter;
for(iter=s.begin();iter!=s.end(); iter){
cout<<*iter<<"";
}
}
删除元素
/*
*删除有两种方式，
*clear是直接清空
*erase是删除指定迭代器范围内的数字
*也可以用来删除指定的单个元素
**/
voiddel(){
set<int>demo{1 2 3 4 5};
//清空
demo.clear();//{}
if(demo.empty()){//判断Vector为空则返回true
demo.insert({6 7 8 9 10 11});//{6 7 8 9 10 11}
//删除第一个元素
demo.erase(demo.begin());//{7 8 9 10 11}
//删除指定元素
demo.erase(11);
//删除前三个
demo.erase(demo.begin() next(demo.begin() 3));//{10 11}
//只保留最后一个
demo.erase(demo.begin() demo.end());//{11}
}
set<int>s=demo;
set<int>::iteratoriter;
for(iter=s.begin();iter!=s.end(); iter){
cout<<*iter<<"";
}
}
比较函数元素为基本类型使用函数对象
当元素是基本类型，一般是变动规则为递增或者递减。
推荐使用自带的less或者greater函数比较。
//基础类型，变动规则为递增或者递减
voidBasicCompare(){
set<int less<int>>s2{6 5 7 8};//小数靠前。递增 输出为{5 6 7 8}
set<int greater<int>>s3{6 5 7 8};//大数靠前。递减 输出为{8 7 6 5}
//遍历查看内容
set<int>s=s2;
set<int>::iteratoriter;
for(iter=s.begin();iter!=s.end(); iter){
cout<<*iter<<"";
}
}
类外重载括号
当元素是基本类型，变动规则后不能用自带的less或者greater函数比较，就只能新建一个结构体来描述规则。这种方式是适用性最广的。
//基础类型，但是有特殊的比较规则
//此处以递增递减为例
//当然也可以指定为其他自定义类型
structSpecial{
booloperator()(constint&a constint&b){
//returna>b;//等价greater<int>
returna<b;//等价less<int>
}
};
//基础类型需要类外重载
voidSpecialCompare(){
set<int Special>s2;
s2.emplace(3);
s2.emplace(2);
s2.emplace(1);
s2.emplace(4);
//遍历查看内容
set<int Special>s=s2;
set<int>::iteratoriter;
for(iter=s.begin();iter!=s.end(); iter){
cout<<*iter<<"";
}
}
/*1234*/
元素为自定义类型
当元素是自定义结构体，可以在类外重载括号()；也可以在类内重载小于号<，例子如下。
类内重载小于号//自定义结构体
structInfo{
stringname;
floatscore;
Info(){
name="a";
score=60;
}
Info(stringsname floatfscore){
name=sname;
score=fscore;
}
//类内重载方法
booloperator<(constInfo&a)const{
/*名字递减；若名字相同，则分数递减*/
if(a.name<name)
returntrue;
elseif(a.name==name){
returna.score<score;
}else
returnfalse;
}
};
voidInfoCompare(){
pair<set<Info>::iterator bool>result;//获取插入的结果
set<Info>s;
//插入默认对象和指定对象
s.insert(Info());
s.insert(Info("a" 53));
s.insert(Info("keen" 68));
result=s.insert(Info("keen" 60));
//遍历查看内容
for(autoiter=s.begin();iter!=s.end(); iter){
cout<<iter->name<<""<<iter->score<<endl;
}
cout<<"插入元素的信息："<<result.first->name<<""<<result.first->score<<endl;
cout<<"插入是否成功"<<boolalpha<<result.second<<endl;
//再次插入相同元素
result=s.insert(Info("keen" 60));
cout<<"插入元素的信息："<<result.first->name<<""<<result.first->score<<endl;
cout<<"插入是否成功"<<boolalpha<<result.second<<endl;
}
/*
keen68
keen60
a60
a53
插入元素的信息：keen 60
插入是否成功true
插入元素的信息：keen 60
插入是否成功false
*/
类外重载括号
#include<iostream>
#include<set>
usingnamespacestd;
/*Student结构体*/
structStudent{
stringname;
intage;
stringsex;
Student(){}
Student(conststring&name intage conststring&sex):name(name) age(age) sex(sex){}
};
/*
*为Student指定排序准则
*先比较名字；若名字相同 则比较年龄。小的返回true
*如果想要部分参数匹配，可以用正则表达式来规定
**/
classStudentCompare{
public:
booloperator()(constStudent&a constStudent&b)const{
if(a.name<b.name)
returntrue;
elseif(a.name==b.name){
if(a.age<b.age)
returntrue;
else
returnfalse;
}else
returnfalse;
}
};
intmain(){
set<Student StudentCompare>stuSet;
stuSet.insert(Student("张三" 13 "male"));
stuSet.insert(Student("李四" 23 "female"));
/*构造一个用来查找的临时对象 可以看到 即使stuTemp与stu1实际上并不是同一个对象
*但当在set中查找时 仍能够查找到集合中的元素成功。
*这是因为已定义的StudentCompare的缘故。
*/
StudentstuTemp;
stuTemp.name="张三";
stuTemp.age=13;
set<Student StudentCompare>::iteratoriter;
iter=stuSet.find(stuTemp);
if(iter!=stuSet.end()){
cout<<(*iter).name<<""<<(*iter).age<<""<<(*iter).sex<<endl;
}else{
cout<<"Cannotfinethestudent!"<<endl;
}
return0;
}
查找函数count统计元素个数
count函数是用来统计一个元素在当前容器内的个数。由于Set的特性，所以只能返回1或者0。
/*
*用count函数寻找元素，
**/
voidfind1(set<int>s){
if(s.count(4)==1){
cout<<"元素4存在"<<endl;
}
if(s.count(8)==0){
cout<<"元素8不存在";
}
}
追查源码，我发现他是用的红黑树的__count_unique方法，从根节点开始比对，如果要查找的元素是比当前节点的数值要小就去左子树找，如果要查找的元素是比当前节点的数值要大就去右子树找，当匹配到节点值相等时，就返回1；当到最后的叶子结点仍然没有找到就返回0。
底层是使用的红黑树，所以查找起来还是很方便的。
源码如下。
size_type__tree<_Tp _Compare _Allocator>::__count_unique(const_Key&__k)const
{
__node_pointer__rt=__root();
while(__rt!=nullptr)
{
if(value_comp()(__k __rt->__value_))
{
__rt=static_cast<__node_pointer>(__rt->__left_);
}
elseif(value_comp()(__rt->__value_ __k))
__rt=static_cast<__node_pointer>(__rt->__right_);
else
return1;
}
return0;
}
find获取元素迭代器
/*
*用find函数寻找元素，
**/
voidfind2(set<int>s){
if(s.find(4)!=s.end()){
cout<<"元素4存在"<<endl;
}else{
cout<<"元素4不存在";
}
if(s.find(8)!=s.end()){
cout<<"元素8存在"<<endl;
}else{
cout<<"元素8不存在";
}
}
追查源码，我发现他是用的红黑树的find方法，从根节点开始比对，如果要查找的元素是比当前节点的数值要大就去右子树找；如果查找的元素比当前节点的数值要小于等于匹配到节点值时，就赋值一次结果节点并去左子树找。一直到最后所查找的节点为空再结束。最终返回结果节点。
源码如下。
iterator__lower_bound(const_Key&__v __node_pointer__root __iter_pointer__result)
{
while(__root!=nullptr)
{
if(!value_comp()(__root->__value_ __v))
{
__result=static_cast<__iter_pointer>(__root);
__root=static_cast<__node_pointer>(__root->__left_);
}
else
__root=static_cast<__node_pointer>(__root->__right_);
}
returniterator(__result);
}
暂时看来，两个方法的底层实现逻辑是相似的，都是用平衡二叉树的方式去寻找节点。
区别是count返回1或0来标明元素是否存在；find函数是返回指针可以方便下一步修改或者取用。
感谢谨以此文，送给未来笨兮兮又回来看的博主自己
哦，我看到了，过去那个很努力但是很皮的我哦
感谢现在努力的自己。
感谢现在的好奇，为了能成为更好的自己。
离线下载链接
C 中set用法详解
C STL set::find的用法
C STL set容器完全攻略
