set的简单讲解

一、set的基本用法

set集合容器实现了红黑树(Red-BlackTree）的平衡二叉查找树的的数据结构。要
注意的是，它不会重复插入相同键值的元素，而是采取忽略处理。
使用set前,需要在程序头文件中包含声明“#include <set>"

二、set的常用函数?

函数	功能
begin()	返回指向第一个元素的迭代器
clear()	清除所有的元素
count()	返回某个值元素的个数
empty()	如果集合为空，返回true
end()	返回指向最后一个元素的迭代器
erase()	删除集合中的元素
find()	返回一个指向被查找到元素的迭代器
insert()	在集合中插入元素
lower_bound()	返回>=某值的第一个元素的迭代器
upper_bound()	返回大于某个值元素的迭代器
size()	返回集合中元素的个数

三、创建set集合对象?

创建set对象时，需要指定元素的类型，这一点和其他的容器一样。

#include <iostream>
#include <set>
//也可以直接用#include <bits/stdc++.h>

using namespace std;

int main() {
    set<int> s;
    return 0;
}

四、元素的插入与中序遍历?

采用insert()的方法把元素插入到集合中，时间复杂度O(logn)，插入规则在默认的比较规则下，是按照元素值从小到大建树，如果自己制定了比较规则函数，则按照自定义比较规则函数建树。

使用迭代器对集合遍历，只需要在迭代器++默认按中序遍历的顺序访问所有元素，结果正好是元素排序后的结果，时间复杂度O(n)。

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> s;
    s.insert(5); //第一次插入5，可以插入
    s.insert(1);
    s.insert(6);
    s.insert(3);
    s.insert(5); //第二次插入5，重复元素不插入
    set<int>::iterator it; //定义迭代器
    //中序遍历集合中所有元素
    for (it = s.begin(); it != s.end(); it++) {
        cout << *it << " ";
    }
    cout << endl; //怕cout超时的也可以关闭输入输出流或者用printf
    return 0;
}

五、元素的删除?

与插入元素的处理一样，集合具有高效的删除处理功能，并自动重新调整内部的红黑树的平衡。删除的对象可以是某个迭代器位置上的元素O(1)、等于某键值的元素O(logn)、一个区间上的元素和清空集合O(n)。
?

#include<iostream>
#include<set>

using namespace std;

int main() {
	set<int> s;
	s.insert(5);
	s.insert(1); 
	s.insert(6); 
	s.insert(3);
	s.erase(6); //删除键值为6的元素
	//定义迭代器,并赋值首元素地址
	set<int>::iterator it = s.begin();
	s. erase(it); //删除第一个元素
	for(it = s.begin(;it != s.end(); it++) {
		 cout << *it << " ";
	}
	cout << endl;
	s.clear();
	cout << s.size() << endl;
	return 0;
}

六、元素的查找

使用find()方法对集合进行查找,如果找到键值,则返回该键值的迭代器；否则，返回集合最后一个元素后面的一个迭代器即end()。
也可以使用count()方法判断某值是否在集合中。

#include<iostream>
#include<set>

using namespace std;

int main() {
	set<int> s;
	s.insert(5);
	s.insert(1); 
	s.insert(6); 
	s.insert(3);
	set<int>::iterator it;
	it = s.find(6); //查找键值为6的元素
	if(it != s.end()) {
		cout << *it << endl;
	} else {
		cout << "not find it" << endl;
	}
	if(s.count(2)) { //不存在
		printf("exist\n");
	} else {
		printf("does not exist\n");
	}
	return 0;
}

七、自定义比较方式?

与priority_queue类似，set默认使用less，less默认使用小于运算符，所有平衡树是左小右大的。
当然你也可以使用其他的方式,改变元素之间的排列关系，方法类似priority_queue。
方法有三种：使用greate函数类、使用运算符重载或者自己写一个比较函数类。
下面给出常用的修改：

#include<iostream>
#include<set>

using namespace std;

int main() {
	set<int, greater<int> > s;
	s.insert(5);
	s.insert(1); 
	s.insert(6); 
	s.insert(3);
	set<int, greater<int> >::iterator it;
	for(it = s.begin(); it != s.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
	return 0;
}