【C++】STL之树形结构的关联式容器 ----- set和multiset

Love The Way You Lie 2023-07-24 12:00 202阅读 0赞

## set ##

#### 一、set的介绍 ####

[set文档介绍][set]

1.  set是按照一定次序存储元素的容器。
2.  在set中，元素的value也标识它（value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改（元素总是const)，但是可以从容器中插入或删除它们。
3.  在内部，set中的元素总是按照其内部比较对象（类型比较）所指示的特定严格弱排序准则进行排序
4.  set容器通过key访问单个元素的速度通常比unordered\_set容器慢，但它们允许根据顺序对子集进行直接迭代。
5.  set在底层是用二叉搜索树（红黑树）实现的。

注意：

1.  与map/multimap不同，map/multimap中存储的是真正的键值对<key，value>，set中只放value，但在底层实际存放的是由<value，value>构成的键值对。
2.  set中插入元素时，只需要插入value即可，不需要构造键值对。
3.  set中的元素不可以重复（因此可以使用set进行去重)。
4.  使用set的迭代器遍历set中的元素，可以得到有序序列。
5.  set中的元素默认按照小于来比较
6.  set中查找某个元素，时间复杂度为：O(logN)
7.  set中的元素不允许修改
8.  set中的底层使用二叉搜索树（红黑树）来实现

#### 二、set的使用 ####

**1、set的模板参数列表**  
![在这里插入图片描述][20200411210835881.png]  
T：set中存放元素的类型，实际在底层存储<value，value>的键值对。  
Compare：set中元素默认按照小于来比较。  
Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理。

**2、set的构造**

<table> 
 <thead> 
  <tr> 
   <th>函数声明</th> 
   <th>功能介绍</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>set(const Compare&amp; comp = Compare(), const Allocator&amp; = Allocator());</td> 
   <td>构造空的set</td> 
  </tr> 
  <tr> 
   <td>set(InputIterator first, InputIterator last, const Compare&amp; comp = Compare(), const Allocator&amp; = Allocator());</td> 
   <td>用[first，last)区间中的元素构造set</td> 
  </tr> 
  <tr> 
   <td>set(const set&lt;Key, Compare, Allocator&gt;&amp; x);</td> 
   <td>set的拷贝构造</td> 
  </tr> 
 </tbody> 
</table>

**3、set的迭代器**

<table> 
 <thead> 
  <tr> 
   <th>函数申明</th> 
   <th>功能简介</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>iterator begin()</td> 
   <td>返回set中起始位置元素的迭代器</td> 
  </tr> 
  <tr> 
   <td>iterator end()</td> 
   <td>返回set中最后一个元素后面的迭代器</td> 
  </tr> 
  <tr> 
   <td>const_iterator cbegin() const</td> 
   <td>返回set中起始位置元素的const迭代器</td> 
  </tr> 
  <tr> 
   <td>const_iterator cend() const</td> 
   <td>返回set中最后一个元素后面的const迭代器</td> 
  </tr> 
  <tr> 
   <td>reverse_iterator rbegin()</td> 
   <td>返回set第一个元素的反向迭代器，即rend</td> 
  </tr> 
  <tr> 
   <td>reverse_iterator rend()</td> 
   <td>返回set最后一个元素下一个位置的反向迭代器，即rbegin</td> 
  </tr> 
  <tr> 
   <td>const_reverse_iterator crbegin() const</td> 
   <td>返回set第一个元素的反向const迭代器，即crend</td> 
  </tr> 
  <tr> 
   <td>const_reverse_iterator rend() const</td> 
   <td>返回set最后一个元素下一个位置的反向const迭代器，即crbegin</td> 
  </tr> 
 </tbody> 
</table>

**4、set的容量**

<table> 
 <thead> 
  <tr> 
   <th>函数声明</th> 
   <th>功能介绍</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>bool empty() const</td> 
   <td>检测set是否为空，空返回true，否则返回false</td> 
  </tr> 
  <tr> 
   <td>size_type size() const</td> 
   <td>返回set中有效元素的个数</td> 
  </tr> 
 </tbody> 
</table>

**5、set修改操作**

<table> 
 <thead> 
  <tr> 
   <th>函数声明</th> 
   <th>功能介绍</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>pair&lt;iterator, bool&gt; insert(const value_type&amp; x)</td> 
   <td>在set中插入元素x，实际插入的是&lt;x, x&gt;构成的键值对，如果插入成功，返回&lt;该元素在set中的位置，true&gt;，如果插入失败，说明x在set中已经存在，返回&lt;x在set中的位置，false&gt;</td> 
  </tr> 
  <tr> 
   <td>iterator insert(iterator position, const value_type&amp; x)</td> 
   <td>在set的position位置插入x，实际插入的是&lt;x，x&gt;构成的键值对，注意：position位置只是参考，x最终不一定在该位置</td> 
  </tr> 
  <tr> 
   <td>template void insert(InputIterator first, InputIterator last);</td> 
   <td>在set中插入[first，last)区间中的元素</td> 
  </tr> 
  <tr> 
   <td>void erase(iterator position)</td> 
   <td>删除set中position位置上的元素</td> 
  </tr> 
  <tr> 
   <td>size_type erase(const key_type&amp; x)</td> 
   <td>删除set中值为x的元素，返回删除的元素的个数</td> 
  </tr> 
  <tr> 
   <td>void erase(iterator first, iterator last)</td> 
   <td>删除set中[first，last)区间中的元素</td> 
  </tr> 
  <tr> 
   <td>void swap(set&lt;Key, Compare, Allocator&gt;&amp; st);</td> 
   <td>交换set中的元素</td> 
  </tr> 
  <tr> 
   <td>void clear()</td> 
   <td>将set中的元素清空</td> 
  </tr> 
  <tr> 
   <td>iterator find(const key_type&amp; x) const</td> 
   <td>返回set中值为x的元素的位置</td> 
  </tr> 
  <tr> 
   <td>size_type count(const key_type&amp; x) const</td> 
   <td>返回set中值为x的元素的个数</td> 
  </tr> 
 </tbody> 
</table>

**6、set的使用举例**

#include <set>
    
    void TestSet()
    { 
    	//用数组array中的元素构造set
    	int array[] = {  1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4, 6, 8, 0 };
    	set<int> s(array, array + sizeof(array) / sizeof(array[0]));
    	cout << s.size() << endl;
    
    	//正向打印set中的元素，从打印结果中可以看出：set可去重
    	for (auto& e : s)
    		cout << e << " ";
    	cout << endl;
    
    	//使用迭代器逆向打印set中的元素
    	for (auto it = s.rbegin(); it != s.rend(); ++it)
    		cout << *it << " ";
    	cout << endl;
    
    	//set中值为3的元素出现了几次
    	cout << s.count(3) << endl;
    }

## multiset ##

#### 一、multiset的介绍 ####

[multiset文档介绍][multiset]

1.  multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。
2.  在multiset中，元素的value也会识别它（因为multiset中本身存储的就是<value，value>组成的键值对，因此value本身就是key，key就是value，类型为T）。multiset元素的值不能在容器中进行修改（因为元素总是const的），但可以从容器中插入或删除。
3.  在内部，multiset中的元素总是按照其内部比较规则（类型比较）所指示的特定严格弱排序准则进行排序。
4.  multiset容器通过key访问单个元素的速度通常比unordered\_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。
5.  multiset底层结构为二叉搜索树（红黑树）。

注意：

1.  multiset中在底层中存储的是<value，value>的键值对
2.  multiset的插入接口中只需要插入即可
3.  与set的区别是，multiset中的元素可以重复，set中value是唯一的
4.  使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
5.  multiset中的元素不能修改
6.  在multiset中找某个元素，时间复杂度为O(logN)
7.  multiset的作用：可以对元素进行排序

#### 二、multiset的使用 ####

multiset中的接口与set相同，小可爱们可以参考上述的set。  
举个栗子：

#include <set>
    
    void TestSet()
    { 
    	int array[] = {  2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };
    
    	//注意：multiset在底层实际存储的是<int, int>的键值对
    	multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
    	for (auto& e : s)
    		cout << e << " ";
    	cout << endl;
    
    	//测试multiset中是否可以存储值相同的元素
    	s.insert(5);
    	cout << s.count(5) << endl;
    	for (auto& e : s)
    		cout << e << " ";
    	cout << endl;
    
    	//删除所有值为5的元素
    	s.erase(5);
    	for (auto& e : s)
    		cout << e << " ";
    	cout << endl;
    }

[set]: http://www.cplusplus.com/reference/set/set/?kw=set
[20200411210835881.png]: /images/20230528/35aa81f08bf54685ba8a2381afa6333b.png
[multiset]: http://www.cplusplus.com/reference/set/multiset/?kw=multiset