set & multiset关联式容器 -C++

灰太狼 2023-01-20 13:59 205阅读 0赞

![在这里插入图片描述][20210513141159903.png]

### set & multiset ###

*  目录:
 *   *  一.关联式容器
     *  二.键值对
     *  三.set
     *   *  1.set概念
         *  2.构造函数
         *  3.capacity
         *  4.Modifiers
         *  5.Operations
         *  6.iterator
     *  四.multiset
     *  五.原理总结

# 目录: #

## 一.关联式容器 ##

>  在我们接触过的STL容器中像:vector list deque 这种的统称为序列式容器,底层为线性序列的数据结构  
> ^  
> **关联式容器**也用来存放数据,不过不同的是里面储存的是<key,value>结构的**键值对**,数据检索时的效率更高.

## 二.键值对 ##

> 键值对其实比较好理解,就是在每次存储的数据中有key,和value两个信息,key 代表的是键值,value代表的是与key对应的信息.,你只有通过键值,才能找到对应的value.通过代码理解

template <class T1, class T2>	//类模板
    struct pair	//pair类
    { 
    	typedef T1 first_type;
    	typedef T2 second_type;
    	T1 first;		//对应的first/second
    	T2 second;
    	pair() : first(T1()), second(T2())	//内部对应的就是key,和value
    	{ }
    
    	pair(const T1& a, const T2& b) : first(a), second(b)
    	{ }
    };

> 这就是键值对内部的存储方式,我们可以通过定义的迭代器进行访问.

## 三.set ##

### 1.set概念 ###

>  1.set是按照一定次序存储元素 容器  
> ^  
> 2.在set中value也要进行标识,并且每个value的值是唯一的  
> ^  
> 3.set中的元素不能进行修改(都为const),可以进行插入的删除  
> ^  
> 4.在内部的元素,总是按照内部比较对象所指示的严格特定弱排序进行排序  
> ^  
> 5.set的底层是用二叉搜索树(红黑树)来实现

### 2.构造函数 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]

void test1(){ 
    
    	//数组输入
    	int arr[] = {  1, 1, 2, 3, 4, 4, 5, 5, 6 };
    	set<int>s(arr, arr + sizeof(arr) / sizeof(arr[0]));
    
    	//范围for打印,查看元素是否重复
    	for (auto& e : s)
    		cout << e << " ";
    	cout << endl;
    
    	///迭代器逆置打印
    	for (auto it = s.rbegin(); it != s.rend(); ++it)
    		cout << *it << " ";
    	cout << endl;
    
    
    	set<char>s2(s.begin(), s.end());	//将set1中的数据进行传递
    
    	//利用operator=来实现数据的交换,并且将之前数据置空
    	set<int> s3;
    	s3 = s;
    	s = set<int>();
    }

### 3.capacity ###

![在这里插入图片描述][20210513143530830.png]

void test2(){ 
    
    	set<int>s;
    	s.empty();		//判空操作
    
    	cout << "size:" << s.size() << endl;		//size()使用
    	s.insert(100);
    	cout << "size:" << s.size() << endl;
    	s.insert(10);
    	cout << "size:" << s.size() << endl;
    
    
    	cout << "size:" << s.max_size() << endl;
    
    	if (s.max_size() > 1000){ 		//判断是否大于1000,从而输出前1000个值
    
    		for (int i = 0; i < 1000; i++){ 
    
    			s.insert(i);	//循环对每个元素进行插入
    		}
    	}
    	for (auto& e : s)
    		cout << e << " ";
    	cout << endl;
    }

### 4.Modifiers ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]

void test3(){ 
    
    	set<int>s;
    
    	s.insert(5);		//插入
    	s.insert(10);
    	s.insert(15);
    
    	s.erase(5);		//删除
    	s.erase(1);
    
    
    	set<int>s2;
    	s2.insert(666);
    
    	s.swap(s2);		//交换
    
    	s.clear();		//清空
    
    	s.emplace(66);
    	s.emplace(666);		//类似于插入
    	s.emplace(6666);
    	s.emplace(6);
    }

### 5.Operations ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]

void test5(){ 
    
    	std::set<int>::iterator it;
    	set<int>s;		//定义map的对象
    
    	s.insert(6);
    	s.insert(2);		//插入元素
    	s.insert(8);
    
    	it = s.find(8);		//find找到对应value的值
    
    	for (it = s.begin(); it != s.end(); ++it){ 
    
    		cout << *it << " ";		//循环输出
    	}
    	cout << endl;
    
    	for (auto & e : s)
    		cout << e << endl;
    
    
    	cout << s.count(2) << endl;		//count 0/1打印,因为只存在单一的数据
    	cout << s.count(4) << endl;
    
    
    
    	set<int>sa;
    	set<int>::iterator itlow, itup;		//定义对应的迭代器
    
    	for (int i = 1; i < 10; ++i)
    		sa.insert(i);
    
    	itlow = sa.lower_bound(2);		//设置两端迭代器的区间,用来删除对应的元素(包含2和5)
    	itup = sa.upper_bound(5);
    
    	sa.erase(itlow, itup);		//删除掉所设置区间内部的数据
    	for (auto &e : sa)
    		cout << e << " ";
    }

### 6.iterator ###

> 对于迭代器这一部分是比较简单的,我们可以通过前面讲到的string/vector的迭代器来理解,是一样的.

## 四.multiset ##

>  multiset中的元素可以重复

void test(){ 
    
    	int arr[] = {  1, 2, 3, 4, 4, 5, 5, 5, 7, 2 };		//数据可重复
    	multiset<int> m1(arr, arr + sizeof(arr) / sizeof(arr[0]));
    
    	for (auto& e : m1)
    		cout << e << " ";
    	cout << endl;
    }

**运行结果:**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]

## 五.原理总结 ##

>  1.set和map&multimap不一样,map&multimap底层存放的是真的<key,value>键值对,而set中只存放value,内部其实是<value,value>的键值对  
> ^  
> 2.set中插入元素的时候,只需要输入value即可,不需要创建<key,value>键值对  
> ^  
> 3.set中元素默认按照小于的方式存放  
> ^  
> 4.set中查找某个元素,时间复杂度为log2N

接口的理解其实很简单,主要理解set<value,value>的存放方式,而不是直接创建键值对

[20210513141159903.png]: /images/20221021/9af36512cd5a4c0381112b31da2ea2cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70]: /images/20221021/cff0954002c64077a47ff4c733dde157.png
[20210513143530830.png]: /images/20221021/7de86783f3234cd8af990d1f9d9a6d69.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 1]: /images/20221021/b6b478f6225b475c9ecb851d4e3604c4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 2]: /images/20221021/a2ab04d86d814c14853fee20eff1a9ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NjU1NDU4Mg_size_16_color_FFFFFF_t_70 3]: /images/20221021/d25a5fb0e69d4a539e9784aefc020a88.png