欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

#2020寒假集训#C++STL-set代码笔记

程序员文章站 2022-06-02 12:31:42
...
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>//万能头文件 
#include<set>//set头文件
using namespace std;
int main()
{
	printf("\n");
	set<int> s;//set自动去重升序 
	multiset<int> m;//multiset自动升序
	//multiset不去重!它和set的区别仅在于去不去重
	s.insert(3);
	m.insert(3);
	s.insert(5);
	m.insert(5);
	s.insert(2);
	m.insert(2);
	s.insert(8);
	m.insert(8);
	s.insert(1);
	m.insert(1);
	s.insert(3);
	m.insert(3);
	s.insert(5);
	m.insert(5);
	s.insert(8);
	m.insert(8);
	s.insert(1);
	m.insert(1);
	//依次插入3 5 2 8 1 3 5 8,观察s和m的反应
	for(set<int>::iterator it=s.begin();it!=s.end();it++)
	{
		if(it!=s.begin()) printf(" ");
		else printf("set中依次插入3 5 2 8 1 3 5 8 1后的反应:"); 
		printf("%d",*it);
	}
	printf("\n\n");
	for(multiset<int>::iterator it=m.begin();it!=m.end();it++)
	{
		if(it!=m.begin()) printf(" ");
		else printf("multiset中依次插入3 5 2 8 1 3 5 8 1后的反应:");
		printf("%d",*it);
	}
	printf("\n\n");
	//set插入的时候不用写位置,因为插入后位置到底在哪无法提前预知
	s.erase(5);
	m.erase(5);
	for(set<int>::iterator it=s.begin();it!=s.end();it++)
	{
		if(it!=s.begin()) printf(" ");
		else printf("用s.erase(x);在set中删除值为5的x后的反应:"); 
		printf("%d",*it);
	}
	printf("\n\n");
	for(multiset<int>::iterator it=m.begin();it!=m.end();it++)
	{
		if(it!=m.begin()) printf(" ");
		else printf("用m.erase(x);在multiset中删除值为5的x后的反应:");
		printf("%d",*it);
	}
	printf("\n\n");
	/*
		注意multiset中删除x是删除所有的x,不管x有几个 
		但如果按下面的方法()内填写迭代器的话
		就算有重复元素,multiset也仅删除迭代器位置的元素 
		强调!!!用迭代器的时候不能出现s.begin()+2或m.begin()+2等 
	*/
	s.erase(s.begin());
	m.erase(m.begin());
	for(set<int>::iterator it=s.begin();it!=s.end();it++)
	{
		if(it!=s.begin()) printf(" ");
		else printf("用s.erase(it);在set中删除迭代器为it的元素后的反应:"); 
		printf("%d",*it);
	}
	printf("\n\n");
	for(multiset<int>::iterator it=m.begin();it!=m.end();it++)
	{
		if(it!=m.begin()) printf(" ");
		else printf("用m.erase(it);在multiset中删除迭代器为it的元素后的反应:");
		printf("%d",*it);
	}
	printf("\n\n");
	int num=m.count(8);
	printf("num=m.count(x);返回x出现了几次,一般用于multiset,不然仅1次:%d\n\n",num);
	//注意不能用set[i]访问set内的元素,只能用迭代器访问
	/*
		s.find(x)函数
		可用于寻找x是否出现过(multiset同) 
		如果出现过就返回对应迭代器
		如果没出现过就返回s.end()
		
		m.lower_bound(x)函数
		返回>=x的最小的迭代器
		m.upper_bound(x)函数 
		返回>x的最小的迭代器
		
		由于迭代器类似于地址,代码演示并不明显,故省略 
	*/
	for(set<int>::reverse_iterator rit=s.rbegin();rit!=s.rend();rit++)
	{//定义反转迭代器 
		if(rit!=s.rbegin()) printf(" ");
		else printf("set中反转迭代器遍历后的反应:"); 
		printf("%d",*rit);
	}
	printf("\n\n");
	for(multiset<int>::reverse_iterator rit=m.rbegin();rit!=m.rend();rit++)
	{
		if(rit!=m.rbegin()) printf(" ");
		else printf("multiset中反转迭代器遍历后的反应:");
		printf("%d",*rit);
	}
	printf("\n\n");
	/*
		s.begin() 第一个元素的迭代器
		s.end() 最后一个元素的下一个的迭代器
		s.rbegin() 最后一个元素的迭代器
		s.rend() 第一个元素的前一个的迭代器
		
		反转迭代器rit从右往左倒着遍历
		
		不存在从"=rend()"或"=end()"开始的情况
		因为这两个迭代器在set/multiset中并没有指向的元素 
	*/
	return 0;
}

运行结果如下
#2020寒假集训#C++STL-set代码笔记

下面从百度百科中摘录了一些与set容器原理有关的二叉树知识点

二叉树
二叉搜索树

set容器自动升序,其内部运用了二叉搜索树,二叉树的基本概念如下

#2020寒假集训#C++STL-set代码笔记
#2020寒假集训#C++STL-set代码笔记

二叉树的常用术语如下

#2020寒假集训#C++STL-set代码笔记

二叉搜索树的原理

二叉排序树的查找过程和次优二叉树类似,通常采取二叉链表作为二叉排序树的存储结构
中序遍历二叉排序树可得到一个关键字的有序序列,一个无序序列可以通过构造一棵二叉排序树变成一个有序序列,构造树的过程即为对无序序列进行排序的过程
每次插入的新的结点都是二叉排序树上新的叶子结点,在进行插入操作时,不必移动其它结点,只需改动某个结点的指针,由空变为非空即可
搜索、插入、删除的复杂度等于树高,O(log(n))
#2020寒假集训#C++STL-set代码笔记

相关标签: 2020寒假集训