ฅ(๑˙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()

不支持迭代器


最后

莫言真理无穷尽,寸进自有寸进欢请添加图片描述

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐