STL教程（九）：C++ STL常用容器之 set
1、 set/multiset容器基本概念
所有元素都会根据元素的键值自动被排序。
set/multiset属于关联式容器，底层结构是用二叉树实现。
2、set容器特点
set的元素不像map那样可以同时拥有实值和键值，set的元素即是键值又是实值。
set不允许两个元素有相同的键值。
不能通过set的迭代器改变set元素的值。因为set元素值就是其键值，关系到set元素的排序规则。如果任意改变set元素值，会严重破坏set组织。
set容器的迭代器为可读迭代器。
3、set/multiset容器区别
multiset特性及用法和set完全相同，唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树，红黑树为平衡二叉树的一种。 树的简单知识： 二叉树就是任何节点最多只允许有两个字节点。 分别是左子结点和右子节点。
二叉树示意图
二叉搜索树，是指二叉树中的节点按照一定的规则进行排序，使得对二叉树中元素访问更加高效。二叉 搜索树的放置规则是：任何节点的元素值一定大于其左子树中的每一个节点的元素值，并且小于其右子树的值。因此从根节点一直向左走，一直到无路可走，即得到最小值，一直向右走，直至无路可走，可得到最大值。那么在儿茶搜索树中找到最大元素和最小元素是非常简单的事情。下图为二叉搜索树：
上面我们介绍了二叉搜索树，那么当一个二叉搜索树的左子树和右子树不平衡的时候，那么搜索依据上图表示，搜索9所花费的时间要比搜索17所花费的时间要多，由于我们的输入或者经过我们插入或者删除操作，二叉树失去平衡，造成搜索效率降低。 所以我们有了一个平衡二叉树的概念，所谓的平衡不是指的完全平衡。
4、set/multiset容器常用API
4.1set/multiset构造函数
set<T> st;//set默认构造函数：
mulitset<T> mst; //multiset默认构造函数: set(const set &st);//拷贝构造函数
4.2set赋值操作
set& operator=(const set &st);//重载等号操作符 swap(st);//交换两个集合容器
4.3set大小操作
size();//返回容器中元素的数目 empty();//判断容器是否为空
4.4set插入和删除操作
insert(elem);//在容器中插入元素。 clear();//清除所有元素 erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。 erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。 erase(elem);//删除容器中值为elem的元素。
4.5set查找操作
find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end(); count(key);//查找键key的元素个数 lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。 upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。 equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器
使用案例：
#include <iostream>#include <set>using namespace std;void printSetInt(set<int> &s){
set<int>::iterator it=s.begin();
for(;it!=s.end();it++)
{
cout<<*it<<" ";
}
cout<<endl;}
void test(){
set<int> s;
//set容器 会根据键值 自动排序
s.insert(20);
s.insert(50);
s.insert(40);
s.insert(30);
s.insert(10);
printSetInt(s);
set<int>::iterator p = s.begin();
//*p = 100;//set容器的迭代器为只读迭代器 不允许修改内容
set<int>::const_iterator ret;
//如果find没有找到相关数据 返回结束迭代器end
ret = s.find(30);
if(ret == s.end())
{
cout<<"未找到相关数据"<<endl;
}
else
{
cout<<"找到数据为:"<<*ret<<endl;
}
//set容器的键值 唯一的。
//count统计元素在set容器的个数：结果只能是1 或 0
cout<<s.count(100)<<endl;//0
set<int> s1;
s1.insert(10);//ok
s1.insert(20);//ok
s1.insert(10);//err
s1.insert(10);//err
s1.insert(30);//ok
printSetInt(s1);//10 20 30}
int main(int argc, char *argv[]){
test();
return 0;}
5、常见应用
5.1set容器的排序规则(仿函数 更改 set的排序规则)
#include <iostream>#include <set>using namespace std;
//仿函数class MyCompare{public:
bool operator()(int v1, int v2)
{
return v1>v2;
}};
void printSetInt01(set<int, MyCompare> &s){
set<int, MyCompare>::iterator it=s.begin();
for(;it != s.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;}void test01(){
//排序规则：必须是类型 但同时又可以执行函数
//set<int,排序规则> s;
set<int, MyCompare> s;
s.insert(5);
s.insert(2);
s.insert(3);
s.insert(4);
s.insert(1);
printSetInt01(s);}int main(int argc, char *argv[]){
test01();
return 0;}
5.2set容器 存放自定义数据 必须指定 排序规则。
#include <iostream>#include <set>using namespace std;
class Person{public:
string name;
int num;
int age;public:
Person(string name, int num, int age)
{
//this‐>
this->name = name;
this->num =num;
this->age = age;
}};class MyComparePerson{public:
bool operator()(Person ob1, Person ob2)
{
return ob1.num < ob2.num;
}};void printSetPerson(set<Person, MyComparePerson> &s){
set<Person, MyComparePerson>::iterator it=s.begin();
for(;it != s.end(); it++)
{
cout<<it->name<<", "<<it->num<<", "<<it->age<<endl;
}
cout<<endl;}
void test(){
set<Person, MyComparePerson> s;
s.insert(Person("lucy", 101, 19));
s.insert(Person("bob", 107, 19));
s.insert(Person("tom", 105, 19));
s.insert(Person("hehe", 104, 19));
printSetPerson(s);}int main(int argc, char *argv[]){
test();
return 0;}
5.3multiset容器使用(允许重复)
#include <iostream>#include <set>using namespace std;
void printSetInt(multiset<int> &s){
multiset<int>::iterator it=s.begin();
for(;it != s.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;}void test(){
multiset<int> s;
s.insert(10);
s.insert(10);
s.insert(10);
printSetInt(s);}int main(int argc, char *argv[]){
test();
return 0;}
6、对组(补充)
对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公 有属性fifirst和second访问。 类模板：templatestruct pair. 如何创建对组？
//第一种方法创建一个对组
pair<string, int> pair1(string("name"), 20);
cout << pair1.first << endl; //访问pair第一个值
cout << pair1.second << endl;//访问pair第二个值 //第二种
pair<string, int> pair2 = make_pair("name", 30);
cout << pair2.first << endl;
cout << pair2.second << endl; //pair=赋值
pair<string, int> pair3 = pair2;
cout << pair3.first << endl; cout << pair3.second << endl;
更多关于只能物联网培训的问题，欢迎咨询千锋教育在线名师，如果想要了解我们的师资、课程、项目实操的话可以点击咨询课程顾问，获取试听资格来试听我们的课程，在线零距离接触千锋教育大咖名师，让你轻松从入门到精通。
