ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客：面向阿尼亚学习
算法学习笔记系列持续更新中~

---

---

一、前言

在 C++ 中，set作为一个容器也是用来存储同一数据类型的数据类型，并且能从一个数据集合中取出数据，在set中每个元素的值都唯一，而且系统能根据元素的值自动进行排序。

set内部采用的就是一种非常高效的平衡检索二叉树：红黑树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于一般平衡二叉树，所以被STL选择作为了关联容器的内部结构。因此set每次插入，查找和删除的时间和元素个数的对数呈线性关系。

---

二、set的定义

set<数据类型> name;
    
如：
set<int> st; 

set<string>st;

---

三、set的常用函数

​ 使用set得包含set类所在的头文件

#include < set >

size(); 返回元素个数

empty(); 返回set是否是空的

clear(); 用来清空set中的所有元素

begin(); 第0个数，支持++或--，返回前驱和后继

end(); 最后一个的数的后面一个数，支持++或--，返回前驱和后继

insert(); 插入一个数//insert(x)可将x插入set容器中，并自动递增排序和去重

find(); 查找一个数//find(value)返回set中对应值为value的迭代器

count(); 返回某一个数的个数

erase();

​ （1）输入是一个数x，删除所有x 时间复杂度O(k + log n)

​ （2）输入一个迭代器，删除这个迭代器

①删除单个元素

st.erase(st.find(100));

st.erase(value)

value就是所需要删除的值

②删除一个区间内的所有元素

st.erase(first,last)可以删除一个区间内的所有元素

其中first为所需要删除区间的起始迭代器，而last则为所需要删除区间的末尾迭代器的下一个地址

[first,last)

set<int>::iterator it=st.find(30);

st.erase(it,st.end());

删除元素30至set末尾之间的元素

lower_bound(x); 返回大于等于x的最小的数的迭代器

​ upper_bound(x); 返回大于x的最小的数的迭代器

 #include <iostream>
 #include <set>
  
  using namespace std;
  
  int main()
  {
      set<int> s;
  }
  for(int i=1;i<=5;i++)
   {
	s.insert(i);
   }
     cout<<*s.lower_bound(0)<<endl;
      cout<<*s.lower_bound(1)<<endl;
     cout<<*s.lower_bound(3)<<endl;
     cout<<*s.upper_bound(1)<<endl;
      cout<<*s.upper_bound(2)<<endl;
   
     return 0;
 }

//输出
//  1
//  1
//  3
//  2
//  3

---

四、set的遍历方法

​    假设有个set <int> s;

​    第一种：
	for(set<int>::iterator it=s.begin(); it!=s.end(); it++) {
		cout<<*it<<" ";
	}

​    第二种：
​    for(auto it:s) {
	cout<<it<<" ";
	}//C++11的新语法
	

---

五、set的自定义排序

方法：重载<

#include <iostream>
#include <set>
using namespace std;
struct node
{
    int x;
    bool operator<(const node y) const
    {
        return x > y.x;
        // return x < y.x;
    }
};
int main()
{
    set<node> s;
    s.insert({1});
    s.insert({3});
    s.insert({2});
    for (auto i : s)
    {
        cout << i.x << " ";
    }
    cout<< endl;
}

输出
3 2 1

---

六、multiset

set不允许元素重复，如果有重复就会被忽略，但multiset允许.
定义：
multiset<数据类型> name;
如：
multiset<int> s
multiset<string> s

multiset与set的区别：multiset支持重复，而set会去重
其余可参考set

---

七、unordered_set

unordered_set需要引用: #include < unordered_set >

C++11标准中还增加了unordered_set

以散列代替set内部的红黑树（一种自平衡二叉查找树）

使其可以用来处理只去重但不排序的需求

速度比set快很多

注
对于unordered_set容器，其遍历顺序与创建该容器时输入元素的顺序是不一定一致的，遍历是按照哈希表从前往后依次遍历的

和上面类似，增删改查的时间复杂度是O(1)

不支持lower_bound()和upper_bound()

不支持迭代器

---

八、unordered_muliset

unordered_muliset集结了以上两种结构的特点

注
和上面类似，增删改查的时间复杂度是O(1)

不支持lower_bound()和upper_bound()

不支持迭代器

---

最后

莫言真理无穷尽，寸进自有寸进欢