前言

CPP

集合(Set)t是一种元素唯一的、包含已排序对象的数据容器。

C++ STL中标准关联容器set， multiset， map， multimap内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也称为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。

对于map和set这种关联容器来说，不需要做内存拷贝和内存移动。以节点的方式来存储，其节点结构和链表差不多。

博主当前的CPP版本为c++14，所以相关源码内容就是以这个版本的为准。

Set定义

#include
using?namespace?std;
set?s1;//空对象
set?s2{3,?4,?2,?1};//列表清单,默认less递增?,输出为{1,2,3,4}
set?>?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插入

允许多个元素的插入，使用迭代器指定位置。

/*
?*?insert能插入多个，慢但是实用
?*?*/
void?add1()?{
????set?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?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?s?=?demo;
????set::iterator?iter;
????for?(iter?=?s.begin();?iter?!=?s.end();?++iter)?{
????????cout?<

emplace插入

注意是每次只能插入一个，而且是只有构造函数，效率高！

/*
?*?emplace，只能插入一个
?*?而且如果元素已经存在，是不会再次插入的
?*?*/
void?add2()?{
????set?demo{1,?2};
????demo.emplace(4);//{1,2,4}
????demo.emplace(4);//还是{1,2,4}
????set?s?=?demo;
????set::iterator?iter;
????for?(iter?=?s.begin();?iter?!=?s.end();?++iter)?{
????????cout?<

遍历元素

/*
?*?直接用迭代器，注意const_iterator还是iterator
?*?*/
void?search()?{
????set?demo{1,?2};
????//?如果参数为const?vector?需要用const_iterator
????//?vector::const_iterator?iter=v.begin();
????set?s?=?demo;
????set::iterator?iter;
????for?(iter?=?s.begin();?iter?!=?s.end();?++iter)?{
????????cout?<

删除元素

/*
?*?删除有两种方式，
?*?clear是直接清空
?*?erase是删除指定迭代器范围内的数字
?*?也可以用来删除指定的单个元素
?*?*/
void?del()?{
????set?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?s?=?demo;
????set::iterator?iter;
????for?(iter?=?s.begin();?iter?!=?s.end();?++iter)?{
????????cout?<

比较函数

元素为基本类型

使用函数对象

当元素是基本类型，一般是变动规则为递增或者递减。

推荐使用自带的less或者greater函数比较。

//?基础类型，变动规则为递增或者递减
void?BasicCompare()?{
????set?>?s2{6,?5,?7,?8};//小数靠前。递增,输出为{5,6,7,8}
????set?>?s3{6,?5,?7,?8};//大数靠前。递减,输出为{8,7,6,5}
????//?遍历查看内容
????set?s?=?s2;
????set::iterator?iter;
????for?(iter?=?s.begin();?iter?!=?s.end();?++iter)?{
????????cout?<

类外重载括号

当元素是基本类型，变动规则后不能用自带的less或者greater函数比较，就只能新建一个结构体来描述规则。这种方式是适用性最广的。

//?基础类型，但是有特殊的比较规则
//?此处以递增递减为例
//?当然也可以指定为其他自定义类型
struct?Special?{
????bool?operator()(const?int?&a,?const?int?&b)?{
????????//?return?a?>?b;//等价greater
????????return?a?
????}
};
//?基础类型需要类外重载
void?SpecialCompare()?{
????set?s2;
????s2.emplace(3);
????s2.emplace(2);
????s2.emplace(1);
????s2.emplace(4);
????//?遍历查看内容
????set?s?=?s2;
????set::iterator?iter;
????for?(iter?=?s.begin();?iter?!=?s.end();?++iter)?{
????????cout?<

元素为自定义类型

当元素是自定义结构体，可以在类外重载括号()；也可以在类内重载小于号<，例子如下。

类内重载小于号

//?自定义结构体
struct?Info?{
????string?name;
????float?score;
????Info()?{
????????name?=?"a";
????????score?=?60;
????}
????Info(string?sname,?float?fscore)?{
????????name?=?sname;
????????score?=?fscore;
????}
????//?类内重载方法
????bool?operator<(const?Info?&a)?const?{
????????/*名字递减；若名字相同，则分数递减*/
????????if?(a.name?::iterator,?bool>?result;//获取插入的结果
????set?s;
????//?插入默认对象和指定对象
????s.insert(Info());
????s.insert(Info("a",?53));
????s.insert(Info("keen",?68));
????result?=?s.insert(Info("keen",?60));
????//?遍历查看内容
????for?(auto?iter?=?s.begin();?iter?!=?s.end();?++iter)?{
????????cout?<name?<score?<name?<score?<name?<score?<

类外重载括号

#include?
#include?
using?namespace?std;
/*Student结构体*/
struct?Student?{
????string?name;
????int?age;
????string?sex;
????Student()?{}
????Student(const?string?&name,?int?age,?const?string?&sex)?:?name(name),?age(age),?sex(sex)?{}
};
/*
?*?为Student指定排序准则
?*?先比较名字；若名字相同,则比较年龄。小的返回true
?*?如果想要部分参数匹配，可以用正则表达式来规定
?*?*/
class?StudentCompare?{
public:
????bool?operator()(const?Student?&a,?const?Student?&b)?const?{
????????if?(a.name??stuSet;
????stuSet.insert(Student("张三",?13,?"male"));
????stuSet.insert(Student("李四",?23,?"female"));
????/*构造一个用来查找的临时对象,可以看到,即使stuTemp与stu1实际上并不是同一个对象,
?????*但当在set中查找时,仍能够查找到集合中的元素成功。
?????*这是因为已定义的StudentCompare的缘故。
?????*/
????Student?stuTemp;
????stuTemp.name?=?"张三";
????stuTemp.age?=?13;
????set::iterator?iter;
????iter?=?stuSet.find(stuTemp);
????if?(iter?!=?stuSet.end())?{
????????cout?<

查找函数

count统计元素个数

count函数是用来统计一个元素在当前容器内的个数。由于Set的特性，所以只能返回1或者0。

/*
?*?用count函数寻找元素，
?*?*/
void?find1(set?s?){
????if?(s.count(4)?==?1)?{
????????cout?<

追查源码，我发现他是用的红黑树的__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_);
????????}
????????else?if?(value_comp()(__rt->__value_,?__k))
????????????__rt?=?static_cast<__node_pointer>(__rt->__right_);
????????else
????????????return?1;
????}
????return?0;
}

find获取元素迭代器

/*
?*?用find函数寻找元素，
?*?*/
void?find2(set?s?){
????if?(s.find(4)!=?s.end()?)?{
????????cout?<

追查源码，我发现他是用的红黑树的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_);
????}
????return?iterator(__result);
}

暂时看来，两个方法的底层实现逻辑是相似的，都是用平衡二叉树的方式去寻找节点。

区别是count返回1或0来标明元素是否存在；find函数是返回指针可以方便下一步修改或者取用。

感谢

谨以此文，送给未来笨兮兮又回来看的博主自己

哦，我看到了，过去那个很努力但是很皮的我哦

感谢现在努力的自己。

感谢现在的好奇，为了能成为更好的自己。

离线下载链接

C++中set用法详解

C++ STL set::find的用法

C++ STL set容器完全攻略