STL之set容器和multiset容器

柔情只为你懂 2023-10-11 13:28 16阅读 0赞

## 摘要：本文主要介绍了set容器和multiset容器的相关内容。 ##

##  1、基本概念 ##

<table style="border-color:#19e519;border-width:2px;"> 
 <tbody> 
 <tr> 
 <td style="text-align:center;">&nbsp;</td> 
 <td style="text-align:center;">set容器</td> 
 <td style="text-align:center;">multiset容器</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">概念</td> 
 <td style="text-align:center;"> 所有元素都会根据元素的键值自动被排序， 元素即是键值又是实值，不允许两个元素 有相同的键值，元素值不可以被改变 </td> 
 <td style="text-align:center;"> multiset特性及用法和set完全相同， 唯一的差别在于它允许键值重复 </td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">实现</td> 
 <td style="text-align:center;" colspan="2"> set和multiset的底层实现是红黑树，红黑树为平衡二叉树的一种 </td> 
 </tr> 
 </tbody> 
</table>

## 2、二叉树 ##

### 2.1 概念 ###

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

![1510791-20190821202718844-744261107.jpg][]

### 2.2 二叉搜索树 ###

![1510791-20190821202824883-1645944449.png][]

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

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

![1510791-20190821202940119-1011022328.png][]

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

## 3、常用API ##

<table style="border-color:#1de220;border-width:2px;border-style:solid;"> 
 <tbody> 
 <tr> 
 <td style="text-align:center;">&nbsp;</td> 
 <td style="text-align:center;" colspan="2">set</td> 
 <td style="text-align:center;" colspan="2">multiset</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">&nbsp;</td> 
 <td style="text-align:center;">API</td> 
 <td style="text-align:center;">意义</td> 
 <td style="text-align:center;">API</td> 
 <td style="text-align:center;">意义</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">构造函数</td> 
 <td style="text-align:center;">&nbsp;set&lt;T&gt; st</td> 
 <td style="text-align:center;">&nbsp;set默认构造函数</td> 
 <td>&nbsp;mulitset&lt;T&gt; mst</td> 
 <td>&nbsp;multiset默认构造函数</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">set(const set &amp;st)</td> 
 <td style="text-align:center;">拷贝构造函数</td> 
 <td style="text-align:center;" colspan="2">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">赋值操作</td> 
 <td style="text-align:center;">&nbsp;set&amp; operator=(const set &amp;st)</td> 
 <td style="text-align:center;">&nbsp;重载等号操作符</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">swap(st)</td> 
 <td style="text-align:center;">交换两个集合容器</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">大小操作</td> 
 <td style="text-align:center;">&nbsp;size()</td> 
 <td style="text-align:center;">&nbsp;返回容器中元素的数目</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">empty()</td> 
 <td style="text-align:center;">判断容器是否为空</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">插入和删除操作</td> 
 <td style="text-align:center;">&nbsp;insert(elem) </td> 
 <td style="text-align:center;">&nbsp;在容器中插入元素</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">clear()</td> 
 <td style="text-align:center;">清除所有元素</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">erase(pos)</td> 
 <td style="text-align:center;">删除pos迭代器所指的元素，返回下一个元素的迭代器</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">erase(beg, end)</td> 
 <td style="text-align:center;">删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">erase(elem)</td> 
 <td style="text-align:center;">删除容器中值为elem的元素</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">查找操作</td> 
 <td style="text-align:center;">&nbsp;find(key)</td> 
 <td style="text-align:center;">&nbsp;查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end()</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">count(key)</td> 
 <td style="text-align:center;">查找键key的元素个数</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">lower_bound(keyElem)</td> 
 <td style="text-align:center;">返回第一个key&gt;=keyElem元素的迭代器</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">upper_bound(keyElem)</td> 
 <td style="text-align:center;">返回第一个key&gt;keyElem元素的迭代器</td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">equal_range(keyElem)</td> 
 <td style="text-align:center;">返回容器中key与keyElem相等的上下限的两个迭代器</td> 
 </tr> 
 </tbody> 
</table>

## 4、对组 ##

对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的两个公有属性first和second访问。

类模板：template <class T1, class T2> struct pair.创建对组的方式如下：

<table style="border-color:#20eb13;border-width:2px;"> 
 <tbody> 
 <tr> 
 <td style="text-align:center;">第一种方法创建一个对组</td> 
 <td style="text-align:center;"> pair&lt;string,&nbsp;int&gt; pair1(string("name"), 20); cout &lt;&lt; pair1.first &lt;&lt; endl;&nbsp;//访问pair第一个值 cout &lt;&lt; pair1.second &lt;&lt; endl;//访问pair第二个值 </td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">第二种方法创建一个对组</td> 
 <td style="text-align:center;"> pair&lt;string,&nbsp;int&gt; pair2 = make_pair("name", 30); &nbsp; &nbsp; &nbsp; &nbsp;cout &lt;&lt; pair2.first &lt;&lt; endl; &nbsp; &nbsp; &nbsp; cout &lt;&lt; pair2.second &lt;&lt; endl; </td> 
 </tr> 
 <tr> 
 <td style="text-align:center;">第二种方法pair=赋值 </td> 
 <td style="text-align:center;"> &nbsp; &nbsp; &nbsp;pair&lt;string,&nbsp;int&gt; pair3 = pair2; &nbsp; &nbsp; &nbsp; &nbsp;cout &lt;&lt; pair3.first &lt;&lt; endl; &nbsp; &nbsp; &nbsp; cout &lt;&lt; pair3.second &lt;&lt; endl; </td> 
 </tr> 
 </tbody> 
</table>

## 5、代码示例 ##

1 #include<iostream>
 2 #include <set>
 3 #include <string>
 4 
 5 using namespace std;
 6 
 7 void printSet(set<int>&s) {
 8 for (set<int>::iterator it = s.begin(); it != s.end();it++) {
 9 cout << *it << " ";
 10 }
 11 cout << endl;
 12 }
 13 
 14 void test01() { //定义容器、插入数据、判断是否为空，删除数据
 15 set<int>s;
 16 s.insert(10); //set容器会自动将添加的数据进行排列，只能用insert
 17 s.insert(8);
 18 s.insert(11);
 19 s.insert(19);
 20 s.insert(2);
 21 printSet(s);
 22 
 23 if (s.empty()) //测试是否为空
 24 {
 25 cout << "容器为空" << endl;
 26 }
 27 else {
 28 cout << "容器不为空，且大小为：" <<s.size()<< endl;
 29 }
 30 
 31 s.erase(s.begin()); //指明删除数据的位置
 32 printSet(s); 
 33 s.erase(11); //指明具体要删除的数据值
 34 printSet(s);
 35 }
 36 
 37 void test02(){ //进行数据查找
 38 set<int>s;
 39 s.insert(10);
 40 s.insert(8);
 41 s.insert(11);
 42 s.insert(19);
 43 s.insert(2);
 44 
 45 set<int>::iterator pos = s.find(2); //类函数find返回值是迭代器
 46 if (pos!=s.end()) {
 47 cout << "数据存在，值为：" << *pos << endl;
 48 }
 49 else {
 50 cout << "数据不存在" << endl;
 51 }
 52 
 53 int num = s.count(2);
 54 cout << num << endl; //输出相应的元素的个数，在set中，只有0和1
 55 
 56 //lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器
 57 set<int>::iterator it = s.lower_bound(10); 
 58 if (it != s.end())
 59 {
 60 cout << "找到了 lower_bound (10)的值为：" << *it << endl;
 61 }
 62 else
 63 {
 64 cout << "未找到" << endl;
 65 }
 66 // upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器
 67 set<int>::iterator it2 = s.upper_bound(10);
 68 if (it2 != s.end())
 69 {
 70 cout << "找到了 upper_bound (10)的值为：" << *it2 << endl;
 71 }
 72 else
 73 {
 74 cout << "未找到" << endl;
 75 }
 76 //equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器
 77 //上下限 就是lower_bound upper_bound
 78 //注意这里用到了对组
 79 pair<set<int>::iterator, set<int>::iterator> ret = s.equal_range(10);
 80 if (ret.first != s.end()) //第一个值
 81 {
 82 cout << "找到equal_range中 lower_bound 的值 ：" << *(ret.first) << endl;
 83 }
 84 else
 85 {
 86 cout << "未找到" << endl;
 87 }
 88 if (ret.second != s.end()) //第二个值
 89 {
 90 cout << "找到equal_range中 upper_bound 的值 ：" << *(ret.second) << endl;
 91 }
 92 else
 93 {
 94 cout << "未找到" << endl;
 95 }
 96 }
 97 
 98 void test03() { //证明set容器不可以重复插入某一个键值
 99 set<int>s;
 100 pair<set<int>::iterator, bool>ret = s.insert(10); //第二个bool值可以反映是否插入成功
 101 if (ret.second)
 102 {
 103 cout << "插入成功" << endl;
 104 }
 105 else {
 106 cout << "插入失败" << endl;
 107 }
 108 ret = s.insert(10);
 109 if (ret.second)
 110 {
 111 cout << "第二次插入成功" << endl;
 112 }
 113 else
 114 {
 115 cout << "第二次插入失败" << endl;
 116 }
 117 printSet(s);
 118 
 119 //multiset允许插入重复值
 120 multiset<int> mul;
 121 mul.insert(10);
 122 mul.insert(10);
 123 }
 124 
 125 //指定set排序规则 从大到小
 126 //仿函数
 127 class myCompare
 128 {
 129 public:
 130 //重载 ()
 131 bool operator()(int v1, int v2)
 132 {
 133 return v1 > v2;
 134 }
 135 };
 136 //set容器的排序
 137 void test04()
 138 {
 139 set<int, myCompare>s1;
 140 
 141 s1.insert(5);
 142 s1.insert(1);
 143 s1.insert(9);
 144 s1.insert(3);
 145 s1.insert(7);
 146 
 147 //printSet(s1);
 148 
 149 //从大到小排序
 150 //在插入之前就指定排序规则
 151 
 152 for (set<int, myCompare>::iterator it = s1.begin(); it != s1.end(); it++)
 153 {
 154 cout << *it << " ";
 155 }
 156 cout << endl;
 157 }
 158 
 159 //自定义数据类型
 160 class Person
 161 {
 162 public:
 163 Person(string name, int age)
 164 {
 165 this->m_Name = name;
 166 this->m_Age = age;
 167 }
 168 
 169 string m_Name;
 170 int m_Age;
 171 };
 172 
 173 class myComparePerson
 174 {
 175 public:
 176 bool operator()(const Person & p1, const Person & p2)
 177 {
 178 if (p1.m_Age > p2.m_Age) //降序
 179 {
 180 return true;
 181 }
 182 return false;
 183 }
 184 
 185 };
 186 
 187 void test05()
 188 {
 189 set<Person, myComparePerson> s1;
 190 
 191 Person p1("大娃", 100);
 192 Person p2("二娃", 90);
 193 Person p3("六娃", 10);
 194 Person p4("爷爷", 1000);
 195 
 196 s1.insert(p1);
 197 s1.insert(p2);
 198 s1.insert(p3);
 199 s1.insert(p4);
 200 
 201 //插入自定义数据类型，上来就指定好排序规则
 202 
 203 //显示
 204 for (set<Person, myComparePerson>::iterator it = s1.begin(); it != s1.end(); it++)
 205 {
 206 cout << "姓名：" << (*it).m_Name << " 年龄： " << it->m_Age << endl;
 207 }
 208 
 209 }
 210 
 211 int main() {
 212 //test01();
 213 //test02();
 214 //test03();
 215 //test04();
 216 test05();
 217 system("pause");
 218 return 0;
 219 }

转载于:https://www.cnblogs.com/lzy820260594/p/11391260.html

[1510791-20190821202718844-744261107.jpg]: https://img2018.cnblogs.com/blog/1510791/201908/1510791-20190821202718844-744261107.jpg
[1510791-20190821202824883-1645944449.png]: https://img2018.cnblogs.com/blog/1510791/201908/1510791-20190821202824883-1645944449.png
[1510791-20190821202940119-1011022328.png]: https://img2018.cnblogs.com/blog/1510791/201908/1510791-20190821202940119-1011022328.png