STL(六)(set篇)

1.set集合

• set是一种容器,用于存储一组唯一的元素,并按照一定的排序规则进行排序,set中的元素是按照升序排序的,默认情况下,它使用元素的比较运算符(<)来进行排序

set的定义和结构如下:

template <class Key,class Compare=less<Key>,
class Allocator=allocator<Key>>
class set;

1. Key:表示存储在set中的元素的类型
2. Compare:表示元素之间的比较函数对象的类型,默认为less,即按照元素的值进行比较
3. Allocator:表示用于分配内存的分配器类型,默认为allocator

• set的内部实现使用了红黑树(一种自平衡的二叉搜索树)来存储元素,并保持元素的有序性
• 这使得在set中插入,删除和查找元素的时间复杂度都是对数时间,即O(logn）
• set中的元素是唯一的,即不允许重复的元素存在,当插入一个重复的元素时,set会自动忽略该元素

?

---

• ?修改set的常见手段:

1.

#include<bits/stdc++.h>
using namespace std;
int main(){
	set<int,greater<int>>mySet;
	
	mySet.insert(89);
	mySet.insert(67);
	mySet.insert(39);
	mySet.insert(92);
	 
	for(const auto& elem:mySet){
		cout<<elem<<" ";
	}
	cout<<"\n";
	return 0;
}

2.

#include<bits/stdc++.h>
using namespace std;

struct MyCompare{
	bool operator()(const int&a,const int&b){
		//自定义比较逻辑
		return a>b; //改为逆序 
	}
};

int main(){
	set<int,MyCompare>mySet;
	
	mySet.insert(89);
	mySet.insert(67);
	mySet.insert(39);
	mySet.insert(92);
	 
	for(const auto&elem:mySet){
		cout<<elem<<" ";
	}
	cout<<"\n";
	return 0;
} 

---

?2.multiset多重集合

• multiset是一种容器,它与set类似,用于存储一组元素,并按照一定的排序规则进行排序不同之处在于,multiset容器允许存储重复的元素

multiset的定义和结构与set类似,如下所示：

template <class Key,class Compare=less<Key>
class Allocator=allocator<Key>>
class multiset;

1. Key:表示存储在multiset中的元素的类型
2. Compare:表示元素之间的比较函数对象的类型,默认为less,即按照元素的值进行比较
3. Allocator:表示用于分配内存的分配器类型,默认为allocator

• multiset的内部实现也使用红黑树来存储元素,并保持元素的有序性,与set不同的是,multiset中的元素可以重复出现

?

---

3.unordered_ set无序集合

• unordered_set是一种容器,用于存储一组唯一的元素,并且没有特定的顺序
• unordered set容器使用哈希表来实现元素的存储和访问,因此元素的插入,删除和查找的时间复杂度都是常数时间,即0(1)

unordered_set的定义和结构如下:

template <class Key,class Hash=hash<Key>,
    class KeyEqual=equal_to<key>,
    class Allocator=allocator<Key>>
class unordered_set;

1. Key：表示存储在unordered set中的元素的类型。
2. Hash：表示用于计算元素哈希值的哈希函数对象的类型，默认为hash，使用Key类型的默认哈希函数。
3. KeyEqual：表示用于比较元素是否相等的函数对象的类型，默认为equal to，使用Key类型的默认相等比较函数
4. Allocator:表示用于分配内存的分配器类型,默认为allocator

• unordered_set中的元素是唯一的,即不允许重复的元素存在,当插入一个重复的元素时,unordered_set会自动忽略该元素

• 这些时间复杂度是基于哈希函数的性能和哈希冲突的情况来计算的
• 平均情况下，unordered_set的插入,查找和移除操作都具有常数时间复杂度0(1),然而,在最坏情况下这些操作的时间复杂度可能为0(n),其中n是无序集合中的元素数量
• 最坏情况通常发生在哈希冲突较为严重的情况下,导致需要线性探测或链式解决冲突,从而影响性能,所以我们一般情况下不会使用unordered_set,而选择使用复杂度更稳定的set?

  ---

  4.代码示例:

?

#include<bits/stdc++.h>
using namespace std;
int main(){
	set<int>mySet;
	
	//插入元素
	mySet.insert(5);
	mySet.insert(2);
	mySet.insert(8);
	mySet.insert(2); //重复元素 
	
	//遍历集合
	cout<<"Set elements:";
	for(const auto&elem:mySet){
		cout<<elem<<" ";
	} 
	cout<<"\n";
	
	//查找元素
	int searchValue=5;
	auto it=mySet.find(searchValue);
	if(it!=mySet.end()){
		cout<<searchValue<<"found in the set."<<"\n";
	}
	else{
		cout<<searchValue<<"not found in the set."<<"\n";
	}
	
	//移除元素
	int removeValue=2;
	mySet.erase(removeValue);
	
	//再次遍历集合
	cout<<"Set elements sfter removel:";
	for(const auto& elem:mySet){
		cout<<elem<<" ";
	}
	cout<<"\n";
	
	//清空集合
	mySet.clear();
	
	//检查集合是否为空
	if(mySet.empty()){
		cout<<"Set is empty."<<"\n";
	}
	else{
		cout<<"Set is not empty."<<"\n";
	} 
	return 0;
}

输出:

?