set知识点整理总结

往期内容： STL总目录-超详细

目录

1. set是什么？
2. 变量声明及成员函数
3. 进阶语法
4. 时间复杂度即返回值总表

set是什么

首先，set是c+ +标准模板库（STL）中提供的一个“容器”（即一个放置、包含数据的地方）。set所能存储的数据种类是多种多样的，不论是int还是string都能存下。
那么set存储数据方式有什么与众不同的地方呢？换句话说，它存在的意义是什么呢？
如果你学过高中数学，想必你对集合的概念肯定不会陌生，那么set就是这样的一个集合。让我们回忆一下高中数学中集合的几个基本性质：
1.确定性 这一点不必多说，对于任意一个元素，要么它属于某个指定集合，要么它不属于该集合，二者必居其一。这一点在c+ +中也是必然成立的。
2.互异性 这一点同样在set中适用，这也是set被广泛使用的最重要原因（之一），一个set中存入的数据不会出现重复，即∀a,b∈A,a≠b。
3.无序性 无序性是集合的最后一条性质，即集合中元素的顺序不固定，如{1，2，3} = {3，1，2}但要注意的是，set并不是无序的。

看过数学上的集合，我们再回过头来看c+ +中的set 其实上面已经说的差不多了 ：
1.确定性 同集合确定性，略。
2.互异性 同上，即如果存入的数据set中已经存在即自动忽略。如当set中元素为{1,2}时，向该set中添加元素1或2不会使set改变。
3.有序性 即存入同一个set中的所有元素均是从小到大排好序的。如当依次存入元素3 1 2时，set中存储的内容为1,2,3。
4.可删性 自己瞎取的名字 即可以删除set中任意一个位置的元素。

看过这些，我们对set应该有了一些初步的了解，接下来，我们就该用一用它了。

c+ +是一门实践的语言
————y总

变量声明及成员函数

头文件

#include <set>
这个应该不许要过多的解释了吧 /懒癌发作

定义一个set

用法（格式）：set< /*set中存储的数据的类型*/ > 名称
比如

set<int> a; //存整形变量
set<string> b; //存字符串
set<double> c; //存小数
...

存入 .insert(x)

当我们完成了一个set的定义后，当然需要向里面存入一些数据了，那么这时候就会用到读入的函数了: insert()。
用法（格式）：名称.insert(与set同类型的数据)

a.insert(1); //向a中存入1  ->  a={1}
a.insert(3); //向a中存入3  ->  a={1,3}
a.insert(2); //向a中存入2  ->  a={1,2,3} 这里用到了set的有序性，其中元素会自动排序
b.insert("Hello set!"); //其他数据类型的也同理

查看元素数量 .size()

相必会string和vector这些stl容器的也都很了解了，与它们的.size()是完全相同的。
如果我们想要知道set中共存入了几个元素，在存入时单独用一个变量计数就显得太麻烦了，stl当然会帮我们解决这个小问题，于是就有了.size()。

懒是推动人类进步的一大动力，比如洗衣机的发明和.size()的使用
————作者瞎说的

用法（格式）：名称.size()

//a={1,2,3}

cout << a.size() << endl; 
//输出：3
//.size()返回的是一个整数值，所以直接输出是完全没有问题的

会用string和数组的朋友请不要激动，与这两种数据结构不同的是，set不能用.size()为循环条件的for循环遍历每一个元素

错误示例：

//a={1,2,3};

for (int i = 0; i < a.size(); i++) {
    cout << a[i] << " ";
}

你想象中的输出：1 2 3
实际：
错误原因：set类型不存在名称[位数]的调用方法！！！
那么正确的方法是什么呢？别急，让我们再看两个调用前必须先学会的函数。

调用/查看/迭代器

较为重要，但也较为难写，需要记住！
set可能是很多OIer接触的第一个需要使用迭代器调用的变量（应该，至少本蒟蒻是的）。
首先我们要知道，这个所谓的迭代器（iterator）到底是个什么东西？

迭代器（iterator）有时又称光标（cursor）是程序设计的软件设计模式，可在容器对象（container，例如链表或数组）上遍访的接口

更通俗的说，迭代器就是数组或string中调用其中某一个元素时a[i]中的那个i。借助这样一个“接口”，我们就能查看“接口”所对应的元素。还要注意的是迭代器的虽然可以理解为”i”，但它的使用方法与”i”并不相同
在数组和string中，其中的一个元素用a[i]表示
在set中，其中的某一个元素用*迭代器名称表示
用法（格式）：*迭代器名称

//当迭代器名称为 it
//a={1,2,3}
//当it指向第二个元素 it -> 2
*it == 2;

迭代器同样也可以通过+ +和- -转为上一位和下一位
即

//当迭代器名称为 it
//a={1,2,3}
//当it指向第二个元素 it -> 2
*it == 2;

it++;
*it == 3;
it--;
it--;
*it == 1;

用法（格式）：set<所对应的set存储的数据类型>::iterator 迭代器的名称=所对应的set的名称.begin()或set<所对应的set存储的数据类型>::iterator 迭代器的名称=所对应的set的名称.end()
估计这时候又有人在屏幕前一脸懵了：这个.end()和.begin()又是什么鬼？？？别急，听我慢慢道来

.begin() & .end()

当我们理解了迭代器的基本概念和作用，这两个函数的作用就能轻松的理解了，他们返回的便是集合的首/尾迭代器了

.begin() 返回集合的首迭代器，即指向集合中最小元素的迭代器

.end() 返回集合的尾迭代器，但需要注意的是它指向的并不是集合中的最大元素而是最大元素的后一位，所以如果我们想得到最大元素，我们应该使用的是--.end()（“–”固定在.end()前而不能放在后面）

用法（格式）：名称.begin() 名称.end()

//a={1,2,3}

int minn = *a.begin(); //minn=1;
int maxn = *(--a.end()); //maxn=3 此行中括号（*和--间及最后）可以省去，但避免出现不必要的麻烦，建议在写代码时带上

看过.begin()和.end()，我们再回头看一看迭代器的初始化：
set<所对应的set存储的数据类型>::iterator迭代器的名称=所对应的set的名称.begin()或set<所对应的set存储的数据类型>::iterator 迭代器的名称=所对应的set的名称.end()
emm，似乎还是不太便于理解。或许是因为汉字太多了，那么…

set<int> a;

set<int>::iterator it = a.begin(); 
/*
int与定义a时a的类型保持一致
it为迭代器的名字，可以根据喜好选择
.begin()说明这个迭代器的初始位置是指向a的最小元素的
其余部分是固定的迭代器构造格式
*/

应该，差不多了吧…

.find()

这个函数同样也是与迭代器相关的，它的功能分两部分 1.判断一个元素是否存在于集合中 2.如果存在即返回一个迭代器（如果存在即返回该元素的位置的迭代器，反之则返回集合末尾元素的位置的迭代器（即.end()））
用法（格式）：名称.find(x)

set<int> a; //集合a
int x; //查找的元素x
cin >> x;
...
if(a.find(x) != s.end()) { //如果.find()返回的结果不是.end()
    cout << "Have" << endl; //说明集合a中存在x这个元素
}

检查集合是否为空 .empty()

放到数学里就是判断集合是否为空集，应该没什么好说的吧QAQ
返回值是bool类型的，一般用于if条件句
用法（格式）：名称.empty()

set<int> a;
//不插入任何元素
a.empty() == true;

a.insert(1);//放入一个元素1   ->   a={1}≠Ø
a.empty() == false;

检查集合中某一元素的个数 .count()

但凡你把前面的内容认真看过，你都知道这是个废物，其实他也并非一无是处，由于互异性，所以在set中不可能出现一个元素多次出现的可能，所以这个函数的返回值显然只有0或1两种可能性，利用这一特点，我们也可以用它来判断一个元素是否存在于集合中…
用法（格式）：名称.count(x)

清除某一元素 .erase()

这就印证了性质的最后一个，你可以通过.erase()随意清除集合中的某一个元素
用法（格式）：名称.erase(x) 此处x可以直接写想要清除的元素，也可以是元素所对应的迭代器

//a={1,2,3}

a.erase(2); //a={1,3}

清空set集合 .clear()

如名，清空整个set集合中的所有元素
用法（格式）：名称.clear()

//a={1,2,3}

cout << a.size() << endl; //输出：3
a.clear(); //清空a
cout << a.size() << endl; //输出：0

以上应该就是set最常用也是最基本的函数了，那么它的功能只止步于此吗？不，下面还有

set进阶函数指令

.erase()的更多用法

set作为一个集合，如果.erase()只能删一个元素，那当我们需要删掉某一区间内的所有元素时就显得过于麻烦了，所以，贴心的STL给了它更加丰富的功能：
删除某一区间内的所有元素：
用法（格式）：名称.erase(first, last) 即删除[first, last)（注意此处last后面为开区间，即不包括last所指向的元素）内的所有元素，需要注意的是，此处的first和last都必须是迭代器（指针）而不是元素本身。
如

//a={1,2,3}

cout << a.size() << endl;//输出：3
a.erase(a.find(2), a.end());//即删除由2到末元素（包括2和末尾元素）的所有元素
cout << a.size() << endl;//输出：1   ->   a={1}

//b={1,2,3,4}

cout << b.size() << endl; //输出：4
b.erase(b.find(2), b.find(4)); //即删除由2到4（包括2但不包括4）的所有元素
cout << b.size() << endl; //输出：2   ->   b={1,4}

.insert()的更多用法

与.erase()相同的，既让可以同时删除多个元素，我们也当然可以同时存入多个元素，用法基本与.erase()相同，不再赘述
此处引用 @wuog 巨佬在《c++STL容器》 中的一段代码

vector<int> ivec;
for(vector<int>::size_type i = 0; i != 10; ++i) {
ivec.push_back(i);
ivec.push_back(i);
}
set<int> iset(ivec.begin(), ivec.end());
cout << ivec.size() << endl;//20个
cout << iset.size() << endl;// 10个

.lower _bound() & .upper _bound()

这两个神奇的东西，我们把他们放在一起看吧
他们与.find()是有相似之处的，都具有查找的功能，但他们查找的内容和条件与.find()有所不同，其中
.lower_bound()表示=> 查找≥x的元素中最小的一个，并返回指向该元素的迭代器
.upper_bound()表示=> 查找>x的元素中最小的一个，并返回指向该元素的迭代器
用法（格式）：名称.lower_bound() 名称.upper_bound()

//a={1,2,3}

cout << *(a.lower_bound(2)) << endl;//即输出≥2的第一个元素
//输出：2
cout << *(a.upper_bound(2)) << endl; //即输出>2的第一个元素
//输出：3

a.erase(2);//删除元素2
cout << *(a.lower_bound(2)) << endl; //同样为输出≥2的第一个元素，但此时集合中没有=2的元素，所以等价于输出>2的第一个元素
//输出：3

Ps：特殊的，对于比set中最大的元素大的元素，两个函数返回的都是s.end()

各函数时间复杂度及返回值

不得不说，set的时间复杂度还是蛮高的Orz

尾声

爆码280行，求个赞求个收藏不过分吧QAQ，希望能帮到你！

谢谢！