【C++】STL常用容器_set/multiset容器

博主： Fivk
发布时间：2021 年 04 月 16 日
1177 次浏览
1923字数
分类： C/C++

## set容器基本概念

Set的特性是。所有元素都会根据元素的键值自动被排序。Set的元素不像map那样可以同时拥有实值和键值，set的元素即是键值又是实值。Set不允许两个元素有相同的键值。

我们不可以通过set的迭代器改变set元素的值，因为set元素值就是其键值，关系到set元素的排序规则。如果任意改变set元素值，会严重破坏set组织。换句话说，set的iterator是一种const_iterator.

set拥有和list某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。

## multiset容器基本概念

multiset特性及用法和set完全相同，唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树，红黑树为平衡二叉树的一种。

树的简单知识：

二叉树就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点。

![](https://blog.fivk.cn/usr/uploads/2021/04/389430755.png)

二叉搜索树，是指二叉树中的节点按照一定的规则进行排序，使得对二叉树中元素访问更加高效。二叉搜索树的放置规则是：任何节点的元素值一定大于其左子树中的每一个节点的元素值，并且小于其右子树的值。因此从根节点一直向左走，一直到无路可走，即得到最小值，一直向右走，直至无路可走，可得到最大值。那么在儿茶搜索树中找到最大元素和最小元素是非常简单的事情。下图为二叉搜索树：

![](https://blog.fivk.cn/usr/uploads/2021/04/1205879421.png)

上面我们介绍了二叉搜索树，那么当一个二叉搜索树的左子树和右子树不平衡的时候，那么搜索依据上图表示，搜索9所花费的时间要比搜索17所花费的时间要多，由于我们的输入或者经过我们插入或者删除操作，二叉树失去平衡，造成搜索效率降低。

所以我们有了一个平衡二叉树的概念，所谓的平衡不是指的完全平衡。

![](https://blog.fivk.cn/usr/uploads/2021/04/2828698070.png)

RB-tree(红黑树)为二叉树的一种。

## set常用API

**set构造函数**

```c has-numbering
set<T> st;//set默认构造函数：
mulitset<T> mst; //multiset默认构造函数: 
set(const set &st);//拷贝构造函数
```

**set赋值操作**

```c has-numbering
set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器
```

**set大小操作**

```c has-numbering
size();//返回容器中元素的数目
empty();//判断容器是否为空
```

**set插入和删除操作**

```C++
insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。
```

**set查找操作**

```C++
find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count(key);//查找键key的元素个数
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
```

**set的返回值 指定set排序规则举例:**

```C++
//插入操作返回值
void test01(){

set<int> s;
	pair<set<int>::iterator,bool> ret = s.insert(10);
	if (ret.second){
		cout << "插入成功:" << *ret.first << endl;
	}
	else{
		cout << "插入失败:" << *ret.first << endl;
	}

ret = s.insert(10);
	if(ret.second){
		cout << "插入成功:" << *ret.first << endl;
	}
	else{
		cout << "插入失败:" << *ret.first << endl;
	}

}

struct MyCompare02{
	bool operator()(int v1,int v2){
		return v1 > v2;
	}
};

//set从大到小
void test02(){

srand((unsigned int)time(NULL));
	//我们发现set容器的第二个模板参数可以设置排序规则，默认规则是less<_Kty>
	set<int, MyCompare02> s;
	for (int i = 0; i < 10;i++){
		s.insert(rand() % 100);
	}

for (set<int, MyCompare02>::iterator it = s.begin(); it != s.end(); it ++){
		cout << *it << " ";
	}
	cout << endl;
}

//set容器中存放对象
class Person{
public:
	Person(string name,int age){
		this->mName = name;
		this->mAge = age;
	}
public:
	string mName;
	int mAge;
};

struct MyCompare03{
	bool operator()(const Person& p1,const Person& p2){
		return p1.mAge > p2.mAge;
	}
};

void test03(){

set<Person, MyCompare03> s;

Person p1("aaa", 20);
	Person p2("bbb", 30);
	Person p3("ccc", 40);
	Person p4("ddd", 50);

s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);

for (set<Person, MyCompare03>::iterator it = s.begin(); it != s.end(); it++){
		cout << "Name:" << it->mName << " Age:" << it->mAge << endl;
	}

}

```

## 对组(pair)的声明方式

对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有属性first和second访问。
类模板：`template <class T1, class T2> struct pair.`
创建对组:

```C++
//第一种方法创建一个对组
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;

```

## 案例

```C++
#include<iostream>
#include<set>//这个头文件包含ste和multiset的所有功能
#include<algorithm>
using namespace std;

void printSet(set<int>& s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << ' ';
	}
}

int main()
{
	int t;
	set<int> v;
	//插入节点 不再是 push_back 和 front_back ,insert是set唯一的插入方式
	v.insert(2);
	v.insert(5);
	v.insert(6);
	v.insert(1);
	v.insert(9);

printSet(v);
	cout << endl << endl;
	cout << "请输入需要删除的元素";
	cin >> t;

v.erase(t);
	printSet(v);
	cout << endl << endl;

//一、find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；
	//若不存在，返回set.end();

cout << "请输入一个元素：";
	cin >> t;

if (v.find(t) != v.end())
	{
		cout << "找到了元素" << endl;
	}
	else {
		cout << "没有找到元素" << endl;
	}

//二、count(key);//查找键key的元素个数,在multiset里面才可能有两个以上相同的个数。
	//对于set结果最多为1
	cout << "请输入需要查找元素个数的元素值：";
	cin >> t;
	cout << t << "的个数为" << v.count(t) << endl;

//三、lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
	//返回的是迭代器！！！需要解引用,迭代器的类型iterator
	cout << "请输入一个int型元素：";
	cin >> t;
	cout << "v容器里面第一个大于等于" << t << "元素为：" << (v.lower_bound(t) != v.end() ? *v.lower_bound(t) : 0) << endl;
	cout << endl << endl << endl;
	//四、upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
	//和上面的差不多，就是没有等于了，其他不解释。

//五、equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
	//这个有意思，一个函数返回两个值，见过吗？没见过吧？下面我们来看看

//说明：上下限，上限表示upper_bound，下限表示lower_bound

cout << "请输入一个int型元素：";
	cin >> t;
	pair<set<int>::iterator, set<int>::iterator> it = v.equal_range(t);

if (it.first != v.end())
	{
		cout << "找到了equal_range中的lower_boun的值为：" << *it.first << endl;
	}
	else {
		cout << "未找到";
	}
	cout << endl << endl << endl;
	if (it.second != v.end())
	{
		cout << "找到了equal_range中的lower_boun的值为：" << *it.second << endl;
	}
	else {
		cout << "未找到";
	}

return 0;
}
```

set容器默认是从小到大插入,如果是自定义类型我们要怎么排序？我们如何从大到小插入？
</div>

注意：从小到大插入后不能改变为从大到小，这样会破坏内部结构。我们只能在没有插入前指定插入方式。
</div>

##### 利用仿函数 指定set容器的排序规则

**从小到大排序**

```C++
#include<iostream>
#include<set>//这个头文件包含ste和multiset的所有功能
#include<algorithm>
using namespace std;

//利用仿函数 指定set容器的排序规则
class Mycompare
{
public:
	bool operator()(int v1, int v2)
	{
		return v1 > v2;
	}

};

void printSet(set<int,Mycompare>& s)
{
	for (set<int,Mycompare>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << ' ';
	}
}

int main()
{
	set<int,Mycompare> v;
	v.insert(2);
	v.insert(5);
	v.insert(6);
	v.insert(1);
	v.insert(9);

printSet(v);
	cout << endl << endl;
	return 0;
}
```

我在dev c++编译成功，在vs 2019，会报错 error C3848。

解决方法，在仿函数后，加上const

![](https://blog.fivk.cn/usr/uploads/2021/04/1452359593.png)

##### 对于自定义类型，必须指定排序规则。

同样需要仿函数。operator
</div>

```C++
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;

class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	string m_Name;
	int m_Age;
};

class Mycomper
{
public:
	bool operator()(const Person& p1, const Person& p2)const
	{
		//年龄升序
		return p1.m_Age < p2.m_Age;
	}

};

int main()
{
	set<Person,Mycomper> v;

Person p1("小乔", 10);
	Person p2("干将莫邪", 11);
	Person p3("诸葛亮", 10);
	Person p4("女娲", 7);
	Person p5("武则天", 9);
	Person p6("不知火舞", 10);

v.insert(p1);
	v.insert(p2);
	v.insert(p3);
	v.insert(p4);
	v.insert(p5);
	v.insert(p6);
	//对于自定义类型，必须指定排序规则。

for (set<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << (*it).m_Name << ' ' << it->m_Age << endl;
	}

return 0;
}
```

最后修改：2021 年 04 月 17 日

如果觉得我的文章对你有用，请随意赞赏

【C++】STL常用容器_set/multiset容器

Fivk • 2021 年 04 月 16 日

## set容器基本概念

## multiset容器基本概念

multiset特性及用法和set完全相同，唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树，红黑树为平衡二叉树的一种。

树的简单知识：

二叉树就是任何节点最多只允许有两个字节点。分别是左子结点和右子节点。

![](https://blog.fivk.cn/usr/uploads/2021/04/389430755.png)

![](https://blog.fivk.cn/usr/uploads/2021/04/1205879421.png)

所以我们有了一个平衡二叉树的概念，所谓的平衡不是指的完全平衡。

![](https://blog.fivk.cn/usr/uploads/2021/04/2828698070.png)

RB-tree(红黑树)为二叉树的一种。

## set常用API

**set构造函数**

```c has-numbering
set<T> st;//set默认构造函数：
mulitset<T> mst; //multiset默认构造函数: 
set(const set &st);//拷贝构造函数
```

**set赋值操作**

```c has-numbering
set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器
```

**set大小操作**

```c has-numbering
size();//返回容器中元素的数目
empty();//判断容器是否为空
```

**set插入和删除操作**

**set查找操作**

**set的返回值 指定set排序规则举例:**

```C++
//插入操作返回值
void test01(){

set<int> s;
	pair<set<int>::iterator,bool> ret = s.insert(10);
	if (ret.second){
		cout << "插入成功:" << *ret.first << endl;
	}
	else{
		cout << "插入失败:" << *ret.first << endl;
	}

ret = s.insert(10);
	if(ret.second){
		cout << "插入成功:" << *ret.first << endl;
	}
	else{
		cout << "插入失败:" << *ret.first << endl;
	}

}

struct MyCompare02{
	bool operator()(int v1,int v2){
		return v1 > v2;
	}
};

//set从大到小
void test02(){

for (set<int, MyCompare02>::iterator it = s.begin(); it != s.end(); it ++){
		cout << *it << " ";
	}
	cout << endl;
}

//set容器中存放对象
class Person{
public:
	Person(string name,int age){
		this->mName = name;
		this->mAge = age;
	}
public:
	string mName;
	int mAge;
};

struct MyCompare03{
	bool operator()(const Person& p1,const Person& p2){
		return p1.mAge > p2.mAge;
	}
};

void test03(){

set<Person, MyCompare03> s;

Person p1("aaa", 20);
	Person p2("bbb", 30);
	Person p3("ccc", 40);
	Person p4("ddd", 50);

s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);

for (set<Person, MyCompare03>::iterator it = s.begin(); it != s.end(); it++){
		cout << "Name:" << it->mName << " Age:" << it->mAge << endl;
	}

}

```

## 对组(pair)的声明方式

```

## 案例

```C++
#include<iostream>
#include<set>//这个头文件包含ste和multiset的所有功能
#include<algorithm>
using namespace std;

void printSet(set<int>& s)
{
	for (set<int>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << ' ';
	}
}

int main()
{
	int t;
	set<int> v;
	//插入节点 不再是 push_back 和 front_back ,insert是set唯一的插入方式
	v.insert(2);
	v.insert(5);
	v.insert(6);
	v.insert(1);
	v.insert(9);

printSet(v);
	cout << endl << endl;
	cout << "请输入需要删除的元素";
	cin >> t;

v.erase(t);
	printSet(v);
	cout << endl << endl;

//一、find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；
	//若不存在，返回set.end();

cout << "请输入一个元素：";
	cin >> t;

if (v.find(t) != v.end())
	{
		cout << "找到了元素" << endl;
	}
	else {
		cout << "没有找到元素" << endl;
	}

//五、equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。
	//这个有意思，一个函数返回两个值，见过吗？没见过吧？下面我们来看看

//说明：上下限，上限表示upper_bound，下限表示lower_bound

cout << "请输入一个int型元素：";
	cin >> t;
	pair<set<int>::iterator, set<int>::iterator> it = v.equal_range(t);

return 0;
}
```

set容器默认是从小到大插入,如果是自定义类型我们要怎么排序？我们如何从大到小插入？
</div>

注意：从小到大插入后不能改变为从大到小，这样会破坏内部结构。我们只能在没有插入前指定插入方式。
</div>

##### 利用仿函数 指定set容器的排序规则

**从小到大排序**

```C++
#include<iostream>
#include<set>//这个头文件包含ste和multiset的所有功能
#include<algorithm>
using namespace std;

//利用仿函数 指定set容器的排序规则
class Mycompare
{
public:
	bool operator()(int v1, int v2)
	{
		return v1 > v2;
	}

};

void printSet(set<int,Mycompare>& s)
{
	for (set<int,Mycompare>::iterator it = s.begin(); it != s.end(); it++)
	{
		cout << *it << ' ';
	}
}

int main()
{
	set<int,Mycompare> v;
	v.insert(2);
	v.insert(5);
	v.insert(6);
	v.insert(1);
	v.insert(9);

printSet(v);
	cout << endl << endl;
	return 0;
}
```

我在dev c++编译成功，在vs 2019，会报错 error C3848。

解决方法，在仿函数后，加上const

![](https://blog.fivk.cn/usr/uploads/2021/04/1452359593.png)

##### 对于自定义类型，必须指定排序规则。

同样需要仿函数。operator
</div>

```C++
#include<iostream>
#include<set>
#include<algorithm>
using namespace std;

class Person
{
public:
	Person(string name, int age)
	{
		this->m_Name = name;
		this->m_Age = age;
	}
	string m_Name;
	int m_Age;
};

class Mycomper
{
public:
	bool operator()(const Person& p1, const Person& p2)const
	{
		//年龄升序
		return p1.m_Age < p2.m_Age;
	}

};

int main()
{
	set<Person,Mycomper> v;

Person p1("小乔", 10);
	Person p2("干将莫邪", 11);
	Person p3("诸葛亮", 10);
	Person p4("女娲", 7);
	Person p5("武则天", 9);
	Person p6("不知火舞", 10);

v.insert(p1);
	v.insert(p2);
	v.insert(p3);
	v.insert(p4);
	v.insert(p5);
	v.insert(p6);
	//对于自定义类型，必须指定排序规则。

for (set<Person>::iterator it = v.begin(); it != v.end(); it++)
	{
		cout << (*it).m_Name << ' ' << it->m_Age << endl;
	}

return 0;
}
```

【C++】STL常用容器_set/multiset容器

【踩坑日志】SpringBoot项目启动提示This primary key of "id" is primitive !不建议如此请使用包装类 in Class:

【C】极域电子教室学生端解除控制

【开发技巧】@CrossOrigin注解解决跨域问题

这是好东西

【Fivk】文章归档

【知识总结】SSM配置Redis

【踩坑日志】宝塔设置又拍云备份数据

【ACM】求区间和

【C++】STL常用容器_deque容器

【Java】继承

【C++】STL常用容器_set/multiset容器