【C++历险记】STL之set详解

Myth丶恋晨 2024-04-27 07:03 90阅读 0赞

> 个人主页：[兜里有颗棉花糖][Link 1]?  
> 欢迎 点赞? 收藏✨ 留言✉ 加关注?本文由 [兜里有颗棉花糖][Link 1] 原创  
> 收录于专栏【[C++之路][C]】?  
> 本专栏旨在记录C++的学习路线，望对大家有所帮助?  
> 希望我们一起努力、成长，共同进步。?  
> ![在这里插入图片描述][e60337cae1b0476bbac5ce5858ac1974.png]

#### 目录 ####

*  set
 *   *  Modifiers
     *   *  insert（插入数据）
         *  erase(删除元素)
     *  Operations:
     *   *  find（查找数据）
         *  count
         *   *  find函数和count函数的区别
         *  lower\_bound & upper\_bound
     *  补充（multiset）
     *   *  equal\_range

## set ##

集合（Set）：是一种**不允许重复元素**的容器，它的元素是按照某种特定顺序组织的。

**头文件：**

>  *  `#include<set>`

**迭代器访问：**

// 方式1:
    set<int>::iterator it = s.begin();
    while (it != s.end())
    {
        
    	cout << *it << ' ';
    	it++;
    }
    // 方式2
    for (auto e : s)
    	cout << e << ' ';
    // 方式3
    for (set<int>::iterator it1 = s.begin(); it1 != s.end(); it1++)
    	cout << *it1 << ' ';
    // 其实这里方式1和方式3是等同的

### Modifiers ###

#### insert（插入数据） ####

void test_set1()
    {
        
    	set<int> s;
    	s.insert(1);
    	s.insert(2);
    	s.insert(3);
    	s.insert(4);
    	s.insert(4);
    	set<int>::iterator it = s.begin();
    	while (it != s.end())
    	{
        
    		cout << *it << ' ';
    		it++;
    	}
    	cout << endl;
    }

运行结果如下：  
![在这里插入图片描述][544bc718494c4e2db2d6e2d838f433dd.png]  
可以看到结果中并没有打印两个`4`，因为set容器会对其中的元素进行去重操作。

#### erase(删除元素) ####

void test_set2()
    {
        
    	set<int> s;
    	s.insert(1);
    	s.insert(2);
    	s.insert(3);
    	s.insert(4);
    	s.insert(4);
    	set<int>::iterator it = s.begin();
    	for (auto e : s)
    		cout << e << ' ';
    	cout << endl;
    	// 删除元素方式1
    	auto pos = s.find(3);
    	s.erase(pos);
    	//s.erase(3); // 删除元素方式2
    	for (auto e : s)
    		cout << e << ' ';
    	cout << endl;
    }

> **运行结果如下：**  
> ![在这里插入图片描述][15d00ea9eac147d7a4ef09f32c673691.png]

上面提供了两种删除元素的方式，我们要根据不同的场景来选择不同的方式来进行删除元素。

### Operations: ###

#### find（查找数据） ####

> set的find函数用于在set中查找指定的元素，**如果找到了，它返回`指向该元素的迭代器`**；如果没有找到，返回一个`指向set末尾元素的迭代器`。  
> ![在这里插入图片描述][5646544d7b9f401eaf5ecd04cc4e770b.png]

**请看举例：**

void test_set3()
    {
        
    	set<int> s;
    	s.insert(1);
    	s.insert(2);
    	s.insert(3);
    	s.insert(4);
    	s.insert(4);
    	auto pos1 = s.find(5);
    	auto pos2 = s.find(4);
    	if (pos1 != s.end())
    		s.erase(pos1);
    	else
    		cout << "没找到该元素" << endl;
    	if (pos2 != s.end())
    		s.erase(pos2);
    	for (auto e : s)
    		cout << e << ' ';
    }

**运行结果如下：**

![在这里插入图片描述][a68b28315f7c44b3ac8d8604fa332145.png]  
**需要注意的是，set的find函数和库中的find函数是不同的函数。**

> **区别主要是查找速度上，set的find函数查找元素的时间复杂度是`O(logN)`**
> 
> **而库中的find函数查找的速度是`O(N)`**

所以日常当中如果我们需要使用set中的find函数来查找元素时，我们可以这样使用，请看：

set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);
    s.insert(4);
    if (s.find(4) != s.end())
    	cout << "该元素已被找到" << endl;
    else
    	cout << "未找到该元素" << endl;

#### count ####

> ![在这里插入图片描述][f228bc74584e4d19a00ef7b67ed77f97.png]  
> **如果该元素存在的话则返回1，否则返回0。**

这里只举一个简单的例子即可，请看：

set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(4);
    s.insert(4);
    if (s.count(4))
    	cout << "集合中存在该元素" << endl;
    else
    	cout << "集合中不存在该元素" << endl;

**运行结果如下：**  
![在这里插入图片描述][315280dc28714984beb933b13f28918e.png]

##### find函数和count函数的区别 #####

set的find函数和count函数都是用来查找集合元素的函数，但要说区别的话还是有的。

**返回值**：find函数返回一个指向集合元素的迭代器，如果集合中不存在该元素，则迭代器指向集合的末尾；而count函数则返回集合中值等于给定值的元素数量，因为集合中元素是唯一的，所以返回值只能是0或1。

**时间复杂度**：count函数的时间复杂度要比find函数快，因为count函数只需要确定是否存在该元素，而不必遍历整个集合。

**如果只需要知道`一个元素是否存在于集合`中，可以使用count函数；如果需要获取该元素的迭代器，或者`对集合进行修改、删除、插入等操作`，就需要使用find函数。**

#### lower\_bound & upper\_bound ####

`lower_bound`函数用于查找**大于或等于指定元素的`第一个元素`的迭代器**，`如果找到指定元素，则返回指向该元素的迭代器`，否则返回指向`set末尾（即end）`的迭代器。

`upper_bound`函数用于查找**大于指定元素的第一个元素的迭代器**；如果没有找到则返回指向`set末尾（即end）`的迭代器。

请看举例：

void test_set5()
    {
        
    	set<int> s;
    	for (int i = 1; i <= 10; i++) s.insert(i * 10); // 10 20 30 40 50 60 70 80 90 100
    
    	set<int>::iterator itlow, itup;
    	itlow = s.lower_bound(30), itup = s.upper_bound(60);
    	cout << *itlow << ' ' << *itup << endl;
    	s.erase(itlow, itup);
    	for (auto e : s) cout << e << ' ';
    	cout << endl;
    }

**运行结果如下：**  
![在这里插入图片描述][e45834354656400e899fcdeb8484ed24.png]

> 这里我们需要注意的是，erase函数删除的范围是`左闭右开`的，即实际删除的元素包括第一个迭代器指向的元素，但不包括第二个迭代器指向的元素。  
> **同时这里要再次强调`lower_bound`函数查找的是`大于或等于`指定元素的`第一个元素`的迭代器，而`upper_bound`用于查找`大于`指定元素的第一个元素的迭代器。**

### 补充（multiset） ###

这里要补充一点，在C++中`set`和`multiset`是C++标准库中的两个关联容器，**二者的唯一区别在于容器中的元素是否唯一**。

这里举一个简单的例子即可，请看：

void test_set6()
    {
        
    	multiset<int> s;
    	s.insert(1);
    	s.insert(2);
    	s.insert(4);
    	s.insert(5);
    	s.insert(5);
    	s.insert(5);
    	s.insert(3);
    	s.insert(6);
    	for (auto e : s) cout << e << ' ';
    	cout << endl;
    	cout << "容器中元素5的个数是:" << s.count(5) << endl;
    	
    	auto ret = s.equal_range(5);
    	auto itlow = ret.first;
    	auto itup = ret.second;
    	s.erase(itlow, itup);
    	for (auto e : s) cout << e << ' ';
    	cout << endl;
    }

> 运行结果如下：  
> ![在这里插入图片描述][6d4e6f14b3f24661b7362526a989d1d8.png]

**这里我们要注意的是，如果multiset容器中有多个元素`5`，那么，如果使用find函数来查找元素`5`的话，此时应该返回的是中序的第一个元素`5`。请看举例：**

multiset<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(4);
    s.insert(5);
    s.insert(5);
    s.insert(5);
    s.insert(3);
    s.insert(6);
    for (auto e : s) cout << e << ' ';
    cout << endl;
    auto pos = s.find(5);
    while (pos != s.end())
    {
        
    	cout << *pos << ' ';
    	pos++;
    }
    cout << endl;

> 运行结果如下：  
> ![在这里插入图片描述][337d3c2b575e4b45aeb019ed5733e8df.png]

#### equal\_range ####

我们其实可以认为`count`函数和`equal_range`函数就是专门为`multiset`容器设计的。因为set容器中不存在相等的值，而multiset容器才存在相等的值。

下面我们来看一下`multiset`容器是如何使用`equal_range`函数的。

方式1：

void test_multiset1()
    {
        
    	multiset<int> s;
    	s.insert(1);
    	s.insert(2);
    	s.insert(4);
    	s.insert(5);
    	s.insert(5);
    	s.insert(5);
    	s.insert(3);
    	s.insert(6);
    	for (auto e : s) cout << e << ' ';
    	cout << endl;
    	auto ret = s.equal_range(5);
    	auto itlow = ret.first;
    	auto itup = ret.second;
    
    	s.erase(itlow, itup);
    	for (auto e : s) cout << e << ' ';
    	cout << endl;
    }

![在这里插入图片描述][e42525b3c7644a6b9c1bcb2a142be696.png]

> **方式2：**  
> ![在这里插入图片描述][5b8303047b5d4bc8818c3a23a376f79d.png]  
> 这里注意itlow和itup迭代器指向的值。

**错误演示1：**  
![在这里插入图片描述][8709fd98dfbb4f58b78b2e045d5d2308.png]

这里`equal_range`返回的是一个`不存在的区间`。所以最终肯定会报错。

**错误演示2：**

> ![在这里插入图片描述][62b0d9f6c4c74335bf1b4586e545e84c.png]  
> 这里出错点就在于返回给itup的值是一个不合法的值，所以`*itup`的时候就会报错。

**以上就是对set容器用法的介绍，本文就到这里吧，再见啦友友们！！！**

[Link 1]: https://xiaofeizhu.blog.csdn.net/
[C]: https://blog.csdn.net/m0_743525071/category_12287222.html?spm=1001.2014.3001.5482
[e60337cae1b0476bbac5ce5858ac1974.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/3b3cad06d31e4520850509f9173baff1.png
[544bc718494c4e2db2d6e2d838f433dd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/b38794362ae848e796e05df1e36b3f0f.png
[15d00ea9eac147d7a4ef09f32c673691.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/06af85ffadad41758bbd638677b552d5.png
[5646544d7b9f401eaf5ecd04cc4e770b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/9cb0c4105c75457bb11937ccbfe6dc20.png
[a68b28315f7c44b3ac8d8604fa332145.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/ee807da55bba4580888dc1b47a175190.png
[f228bc74584e4d19a00ef7b67ed77f97.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/ebc0a1a23d744c9d98f53ac74b508447.png
[315280dc28714984beb933b13f28918e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/3f7083a238d64b9f8325c869d34bf08d.png
[e45834354656400e899fcdeb8484ed24.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/582976b388b74a29b15a6acabfe0abf7.png
[6d4e6f14b3f24661b7362526a989d1d8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/ecfcae8884ef428b99afbbccd24b61f1.png
[337d3c2b575e4b45aeb019ed5733e8df.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/0b56ce1877c34e29bfa42900cff18e51.png
[e42525b3c7644a6b9c1bcb2a142be696.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/a56dd84f0f244ea09c235d8af603a36e.png
[5b8303047b5d4bc8818c3a23a376f79d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/204422b6c3d746a198c4685ab04b6fd8.png
[8709fd98dfbb4f58b78b2e045d5d2308.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/e38b3c9bbaab4bbe8e0a8f673961f045.png
[62b0d9f6c4c74335bf1b4586e545e84c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/27/4ecbfd08046343fbac40d816a3a22b28.png