set/multiset容器

set/multiset容器是以红黑树（平衡二叉树的一种）为底层实现机制，set不允许元素重复，multiset允许元素重复，树查找效率高

二叉树，二叉搜索树，平衡二叉树，

list不能支持随机访问

list采用动态分配，不会造成内存浪费和溢出

list执行插入操作十分方便，修改指针即可，不需要移动大量元素

list灵活，但是空间和时间额外耗费较大

链表和数组区别

1、数组必须事先定义固定长度（元素个数），不能适应数据动态的增减情况，当数据增加时，可能***原先定义的元素个数，当数据减少时，造成内存浪费

2、链表动态进行存储分配，可以适应动态的增减情况，且可以方便的插入，删除数据元素

set/multiset容器

1、set构造函数

set<T> st;//set默认构造函数；

multiset<T> mst;//multiset默认构造函数

set(const set &st);//拷贝构造

2、set赋值操作

set& opertator=(const set &st);//重载等号操作

swap(st);交换两个集合容器

3、set大小操作

size();

empty();

4、set插入和删除

insert(elem);//

clear();

erase(pos);删除pos迭代器所指的元素，返回下一个元素的迭代器

erase(beg,end);删除区间[beg,end)的所有元素，返回下一个元素的迭代器

erase(elem);删除容器中值为elem的元素

5、set查找操作

find(key);//查找键key是否存在，若存在，返回该键的元素的迭代器，若不存在，返回map.end();

lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器

upper_bound(keyElem)//返回第一个key>=keyElem元素的迭代器

equal_range(keyElem);//返回容器中key与keyElem相等的山下限的两个迭代器

6、pair的用法

7、multiset使用方法和set类似，只是可以有重复的元素而已

#include<iostream>
#include<set>
#include<functional> //预定义函数对象

using namespace std;
//init
void test01(){
	set<int> myset;
	set<int> myset2(myset);//capy构造
}

//使用迭代器
void printSet(set<int> myset){
	for (set<int>::iterator it = myset.begin(); it != myset.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;

}
//插入和删除
void test02(){
	set<int> myset;//默认从小到大排序
	
	myset.insert(4);
	myset.insert(2);
	myset.insert(3);
	printSet(myset);
	myset.erase(myset.begin());
	myset.erase(2);
	printSet(myset);
	myset.erase(myset.begin(), myset.end());
	cout << "size:" << myset.size() << endl;
}
//set容器查找
template<class T> 
class mycompare03{
public:
	bool operator()(int v1,int v2) const{
		if (v1 > v2){

			cout << v1 << endl;
			return v2 > v1;
		}
	}
};
void test03(){
	//set<int> myset//默认从小到大排序
	//mycompare03 mycom;
	//mycom(10);//函数对象，仿函数，可以当函数用
	set<int, mycompare03<int>> myset;
	myset.insert(4);
	myset.insert(2);
	myset.insert(3);
	myset.insert(9);



	/*set<int>::iterator pos=myset.find(20);//返回值为2的元素所在的位置
	if (pos == myset.end()){
		cout << "没有查找到" << endl;
	}
	else
	{
		cout << *pos << endl;
	}*/
	
	
}

class Teacher{
public:
	Teacher(int id, int age) :id(id), age(age){}
	int id;
	int age;
};
//排序方法
class mycompare04{
public:
	bool operator()(Teacher t1, Teacher t2){
		return t1.id > t2.id;

	}
};
void test04(){
	set<Teacher, mycompare04> myset;
	Teacher t1(1, 2), t2(3, 4), t3(5, 6);
	myset.insert(t1);
	myset.insert(t2);
	myset.insert(t3);
	for (set<Teacher, mycompare04>::iterator it = myset.begin(); it != myset.end(); it++)
	{
		cout << it->age << it->id << endl;
	}
	cout << endl;
	//查找
	set<Teacher, mycompare04>::iterator pos = myset.find(t2);
	if (pos == myset.end()){
		cout << "没有查找到" << endl;
	}
	else
	{
		cout << "查找到" << pos->age << pos->id << endl;

	}
   //按照值查找，pos前面已经定义
	pos = myset.find(Teacher(3, 4));
	if (pos == myset.end()){
		cout << "没有查找到" << endl;
	}
	else
	{
		cout << "查找到" << pos->age<<":" << pos->id << endl;

	}



}
void test05()
{
	set<int> myset;
	myset.insert(4);
	myset.insert(2);
	myset.insert(3);
	myset.insert(9);

	set<int>::iterator pos=myset.lower_bound(9);//返回大于等于5迭代器
	if (pos == myset.end()){
		cout << "没有查找到" << endl;
	}
	else
	{
		cout << "lower_bound" << *pos << endl;
	}
	pos = myset.upper_bound(3);
	if (pos == myset.end()){
		cout << "没有查找到" << endl;
	}
	else
	{
		cout << "upper_bound" << *pos << endl;
	}
	pair<set<int>::iterator, set<int>::iterator> pos2 = myset.equal_range(3);
	if (pos2.first== myset.end()){
		cout << "no find" << endl;
	}
	else
	{
		cout << "find" << *(pos2.first) << endl;
	}

	if (pos2.second == myset.end()){
		cout  << "no find" << endl;
	}
	else
	{
		cout << "find" << *(pos2.second) << endl;
	}




}

int main()
{
	//test02();
	//test04();
	test05();
	return EXIT_SUCCESS;
}

#C/C++#