【c++STL——第八讲】set系列 (常用知识点总结)

大家好，我是quicklysleep，欢迎大家光临我的博客,算法学习笔记系列持续更新中~

• 一、前言
• 二、set的定义
• 三、set的常用函数
• 四、set的遍历方法
• 五、set的自定义排序
• 六、multiset
• 七、unordered_set
• 八、unordered_muliset
• 最后

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

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

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

    setst;

​ 使用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::iterator it=st.find(30);

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

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

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

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

 #include 
 #include 
  
  using namespace std;
  
  int main()
  {
      set s;
for(int i=1;i<=5;i++)
{
	s.insert(i);
}
     cout<<*s.lower_bound(0)< 
//输出
//  1
//  1
//  3
//  2
//  3
 
 
四、set的遍历方法 
​    假设有个set  s;

​    第一种：

	for(set::iterator it=s.begin(); it!=s.end(); it++) {
		cout<<*it<<" ";
	}

​    第二种：

​      	for(auto it:s) {
		cout< 
 
五、set的自定义排序 
方法：重载<
 
#include 
#include 
using namespace std;
struct node
{
    int x;
    bool operator<(const node y) const
    {
        return x > y.x;
        // return x < y.x;
    }
};
int main()
{
    set 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 s
 multiset 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()
 
不支持迭代器
 
 
最后 
 
 
莫言真理无穷尽，寸进自有寸进欢·