STL之set容器和multiset容器-蒲公英云

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

1、基本概念

set容器

multiset容器

概念

所有元素都会根据元素的键值自动被排序，

元素即是键值又是实值，不允许两个元素

有相同的键值，元素值不可以被改变

multiset特性及用法和set完全相同，

唯一的差别在于它允许键值重复

实现

set和multiset的底层实现是红黑树，红黑树为平衡二叉树的一种

2、二叉树

2.1 概念

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

2.2 二叉搜索树

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

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

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

3、常用API

	set		multiset
	API	意义	API	意义
构造函数	set<T> st	set默认构造函数	mulitset<T> mst	multiset默认构造函数
set(const set &st)	拷贝构造函数
赋值操作	set& operator=(const set &st)	重载等号操作符
swap(st)	交换两个集合容器
大小操作	size()	返回容器中元素的数目
empty()	判断容器是否为空
插入和删除操作	insert(elem)	在容器中插入元素
clear()	清除所有元素
erase(pos)	删除pos迭代器所指的元素，返回下一个元素的迭代器
erase(beg, end)	删除区间[beg,end)的所有元素，返回下一个元素的迭代器
erase(elem)	删除容器中值为elem的元素
查找操作	find(key)	查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end()
count(key)	查找键key的元素个数
lower_bound(keyElem)	返回第一个key>=keyElem元素的迭代器
upper_bound(keyElem)	返回第一个key>keyElem元素的迭代器
equal_range(keyElem)	返回容器中key与keyElem相等的上下限的两个迭代器

4、对组

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

类模板：template struct 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;

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 }