set/multiset

set/multiset容器

Set的特性是。所有元素都会根据元素的键值自动被排序。Set的元素不像map那样可以同时拥有实值和键值，set的元素即是键值又是实值。Set不允许两个元素有相同的键值。

我们可以通过set的迭代器改变set元素的值吗？不行，因为set元素值就是其键值，关系到set元素的排序规则。如果任意改变set元素值，会严重破坏set组织。换句话说，set的iterator是一种const_iterator.

set拥有和list某些相同的性质，当对容器中的元素进行插入操作或者删除操作的时候，操作之前所有的迭代器，在操作完成之后依然有效，被删除的那个元素的迭代器必然是一个例外。

​ multiset特性及用法和set完全相同，唯一的差别在于它允许键值重复。set和multiset的底层实现是红黑树，红黑树为平衡二叉树的一种。

1.set容器是关联式容器，容器自身有规则，通过键值排序，set容器中的元素是键值也是实值

2.set容器和multiset容器的区别是multiset允许有相同的元素

3.数据结构：平衡二叉树

4.迭代器：双向迭代器

5.常用的api:

​ 1.构造

set<T> st;//set默认构造函数：
mulitset<T> mst; //multiset默认构造函数: 
set(const set &st);//拷贝构造函数

​ 2.赋值

set& operator=(const set &st);//重载等号操作符
swap(st);//交换两个集合容器

​ 3.大小

size();//返回容器中元素的数目
empty();//判断容器是否为空

​ 4.插入和删除

insert(elem);//在容器中插入元素。
clear();//清除所有元素
erase(pos);//删除pos迭代器所指的元素，返回下一个元素的迭代器。
erase(beg, end);//删除区间[beg,end)的所有元素 ，返回下一个元素的迭代器。
erase(elem);//删除容器中值为elem的元素。

​ 5.查找操作

find(key);//查找键key是否存在,若存在，返回该键的元素的迭代器；若不存在，返回set.end();
count(key);//查找键key的元素个数
lower_bound(keyElem);//返回第一个key>=keyElem元素的迭代器。
upper_bound(keyElem);//返回第一个key>keyElem元素的迭代器。
equal_range(keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器。pair类型 返回大于等于的数

6.改变规则：默认是从小到大，改变规则，加入谓词到<>第二个参数中

//验证set插入是否成功 因为插入失败或成功不会报错
void test01(){

	set<int> s;
	pair<set<int>::iterator,bool> ret = s.insert(10);
	if(ret.second){
		cout <<"插入成功:"<<*ret.first << endl;
	}
	else{
		cout <<"插入失败:"<<*ret.first << endl;
	}
}

//谓词
struct MyCompare02{
	bool operator()(int v1,int v2){
		return v1 > v2;
	}
};

//set从大到小
void test02(){

	srand((unsignedint)time(NULL));
	//我们发现set容器的第二个模板参数可以设置排序规则，默认规则是less<_Kty>
	set<int, MyCompare02> s;
	for(int i =0; i <10;i++){
		s.insert(rand()%100);
	}
	
	for(set<int, MyCompare02>::iterator it = s.begin(); it != s.end(); it ++){
		cout <<*it <<" ";
	}
	cout << endl;
}

//set容器中存放对象
class Person{
public:
	Person(string name,int age){
		this->mName = name;
		this->mAge = age;
	}
public:
	string mName;
	int mAge;
};

//排序谓词
struct MyCompare03{
	booloperator()(const Person& p1,const Person& p2){
		return p1.mAge > p2.mAge;
	}
};

void test03(){

	set<Person, MyCompare03> s;

	Person p1("aaa",20);
	Person p2("bbb",30);
	Person p3("ccc",40);
	Person p4("ddd",50);

	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);

	for(set<Person, MyCompare03>::iterator it = s.begin(); it != s.end(); it++){
		cout <<"Name:"<< it->mName <<" Age:"<< it->mAge << endl;
	}

}

7.注意：

​ 1.set容器插入相同元素时，不会报错，但是不插入数据

​ 2.set容器存储对象时，需要告诉set容器的规则