3 set
3.1 简介
数学中的集合
| 特性 | 说明 |
|---|---|
| 确定性 | 给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一。 |
| 互异性 | 一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。有时需要对同一元素出现多次的情形进行刻画，可以使用多重集。 |
| 无序性 | 一个集合中，每个元素的地位都是相同的，元素之间是无序的。集合上可以定义序关系，定义了序关系后，元素之间就可以按照序关系排序。但就集合本身的特性而言，元素之间没有必然的序。 |
3.2 操作
set特点值唯一
3.2.1 初始化
1、默认构造(可带参数)
2、复制构造
3、范围赋值构造
3.2.2 基本操作
- 迭代器
| 迭代器 | 作用 |
|---|---|
c.begin() | 头迭代器 |
c.end() | 尾迭代器 |
c.rbegin() | 反向头迭代器 |
c.rend() | 反向尾迭代器 |
与vector相似。
- 数据量操作
| 函数 | 作用 |
|---|---|
c.size() | 大小 |
c.max_size() | 最大大小 |
c.empty() | 判空 |
c.clear() | 清空 |
3.3 添加数据
1、insert插入数据
实例：插入数据
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
void Display(int val){
cout << val << endl;
}
int main(){
set<int> m;
for(int i=0;i<10;i++){
m.insert(i);
}
for_each(m.begin(),m.end(),Display);
}
2、insert指定位置插入数据
通过返回值pair<iterator,bool>判断插入数据是否成功。
#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
void Display(int val){
cout << val << endl;
}
int main(){
set<int> m;
for(int i=0;i<10;i++){
m.insert(i);
}
m.insert(m.begin(),100);
for_each(m.begin(),m.end(),Display);
}
注：插入数据总是认为成功,如果已经存在，则返回已经存在的位置迭代器，否则，添加新的值，且返回位置迭代器。
3.4 遍历
1、迭代器for循环
for(set<int>::iterator it = m.begin();it != m.end();it++){
cout << *it << endl;
}
2、for_each()循环[推荐]
- 定义函数指针
inline void Display(int val){
cout << val << endl;
}
- 执行
for_each
for_each(m.begin(),m.end(),Display);
3、C++11auto迭代器写法
for(auto it = m.begin();it != m.end();it++){
cout << *it << endl;
}
4、C++11 for-loop-scope迭代器写法[推荐]
for(auto p : m){
cout << p << endl;
}
5、C++11 for_each()与lamdba表达式
for_each(m.begin(),m.end(),[](int p){
cout << p << endl;
});
3.5 查找
1、count()判断值是否存在
if(m.count(val) == 1){
...
}
2、find()判断值是否存在以及位置
set<int>::iterator it = m.find(val);
if(m.end() != it){
...
}
实例：
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
void DisPlay(int val){
cout << val << " ";
}
int main(){
vector<int> vec = {1,5,2,3};
cout << vec.back() << endl;
//放入数据自动排序/去重
set<int> s = {1,3,3,5,5,2,2,4};
for(auto it = s.begin();it!= s.end();++it){
cout << *it << " ";
}
cout << endl;
for(auto n:s){
cout << n << " ";
}
cout << endl;
//插入元素
pair<set<int>::iterator,bool> res = s.insert(6);
for_each(s.begin(),s.end(),DisPlay);
cout << endl;
if(res.second){
cout << "出入成功" << endl;
}
auto res2 = s.insert(7); //自动推导
for_each(s.begin(),s.end(),DisPlay);
cout << endl;
if(res2.second){
cout << "出入成功" << endl;
}
//指定位置插入
s.insert(s.begin(),100);
for_each(s.begin(),s.end(),DisPlay);
cout << endl;
//查找元素
int n = 4;
if(s.count(n) == 1){
cout << "存在数字:" << n << endl;
}else{
cout << "不存在数字:"<< n << endl;
}
set<int>::iterator it = s.find(n);//find()返回一个迭代器，指向查找到的元素所在的位置
if(it != s.end()){
cout << "存在数字:" << n << endl;
}else{
cout << "不存在数字:"<< n << endl;
}
}
3
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5 6
出入成功
1 2 3 4 5 6 7
出入成功
1 2 3 4 5 6 7 100
存在数字:4
存在数字:4
3.6 区域查找
| 成员变量 | 作用 |
|---|---|
m.lower_bound(val) | val下边界 |
m.upper_bound(val) | val上边界 |
m.equal_range(val) | val上下边界 |
3.7 删除
1、关键字删除
m.erase(val);
2、迭代器删除
m.erase(m.begin());
3、区域删除
m.erase(it_a,it_b);
3.8 排序
默认按照val升序排列。自定义排序时，可以在实例化加上val的comp仿函数或者重载<运算符>。
set<value类型,comp> m;
3.9 实例
set的初始化、添加、删除、遍历、查找
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
void DisPlay(int val){
cout << val << " ";
}
int main(){
vector<int> vec = {1,5,2,3};
cout << vec.back() << endl;
//放入数据自动排序/去重
set<int> s = {1,3,3,5,5,2,2,4};
for(auto it = s.begin();it!= s.end();++it){
cout << *it << " ";
}
cout << endl;
for(auto n:s){
cout << n << " ";
}
cout << endl;
//插入元素
pair<set<int>::iterator,bool> res = s.insert(6);
for_each(s.begin(),s.end(),DisPlay);
cout << endl;
if(res.second){
cout << "出入成功" << endl;
}
auto res2 = s.insert(7); //自动推导
for_each(s.begin(),s.end(),DisPlay);
cout << endl;
if(res2.second){
cout << "出入成功" << endl;
}
//指定位置插入
s.insert(s.begin(),100);
for_each(s.begin(),s.end(),DisPlay);
cout << endl;
//查找元素
int n = 4;
if(s.count(n) == 1){
cout << "存在数字:" << n << endl;
}else{
cout << "不存在数字:"<< n << endl;
}
set<int>::iterator it = s.find(n);//find()返回一个迭代器，指向查找到的元素所在的位置
if(it != s.end()){
cout << "存在数字:" << n << endl;
}else{
cout << "不存在数字:"<< n << endl;
}
//删除数据
//关键字删除
s.erase(1);
for_each(s.begin(),s.end(),DisPlay);
cout << endl;
//迭代器删除
s.erase(--s.end());
//auto del_it = s.begin();
set<int>::iterator del_it = s.begin();
++del_it;
s.erase(del_it);
s.erase(s.begin());
for_each(s.begin(),s.end(),DisPlay);
cout << endl;
//区域删除
++del_it;
s.erase(del_it,--s.end());
for_each(s.begin(),s.end(),DisPlay);
cout << endl;
}
3
1 2 3 4 5
1 2 3 4 5
1 2 3 4 5 6
出入成功
1 2 3 4 5 6 7
出入成功
1 2 3 4 5 6 7 100
存在数字:4
存在数字:4
2 3 4 5 6 7 100
4 5 6 7
4 7
