C++之set、multiset

1、set简介

set是一种关联式容器，包含的key值唯一，所有元素都会在插入时自动被排序，其存储结构为红黑树。set只能通过迭代器(iterator)访问。

set和multiset的区别：

（1）set不允许容器中有重复的元素；

（2）multiset允许容器中有重复的元素

2、set库函数

2.1、构造函数

（1）默认构造函数：set<T> st；

（2）拷贝构造函数：set(const set &st);

2.2、赋值函数

（1）重载等号运算符：set &operator =（const set &st）

2.3、判断函数

（1）返回容器中的元素数目: size();

（2）判断容器是否为空: empty();

（3）交换两个容器: swap();

2.4、增删改查

（1）在容器中插入元素：insert(elem)；

（2）清除所有元素：clear()；

（3）删除pos所指元素，返回下一个元素的迭代器：earse()；

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

（5）删除指定元素：earse(elem)；

（6）查找元素是否存在，如果存在，返回该元素的迭代器，如果不存在返回end()：find()；

（7）统计key的元素个数：count(key)；

3、multiset

（1）快速查找区间：lower_bound()；

（2）快速查找区间：upper_bound()；

4、multiset与set的相似点与区别

相似点：

（1）两种容器内部元素默认都是按照升序排列的。

（2）都不支持随机访问，元素只能通过迭代器依次访问。

（3）由于内部实现采用了二叉搜索树（红黑树），在元素查找上具有较高的效率。

不同点：
（1）multiset容器允许出现重复的元素，而set容器中不允许出现重复元素。换句话说，set容器中的元素是唯一的。

（2）在插入元素时，set容器会检查元素是否存在，如果相同则插入无效，而multiset容器插入元素时则不会检查元素是否已经存在，可以插入重复元素。

（3）在删除元素时，set容器只会删除指定值的第一个元素，而multiset容器则会删除所有符合条件的元素。

5、示例

#include <set>
#include <iostream>
using namespace std;

void print_set(set<int> v)
{
	cout << "set: ";
	for (auto it = v.begin(); it != v.end(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}

int main()
{
	//默认构造：
	set<int> d1;
	d1.insert(24);
	d1.insert(24);
	d1.insert(243);
	d1.insert(73);
	d1.insert(63);
	cout << "默认构造结果为：";
	print_set(d1);

	//拷贝函数
	set<int> d2(d1);
	cout << "拷贝构造结果为：";
	print_set(d2);

	//重载等号运算符
	set<int> d3 = d1;
	cout << "重载等号运算符结果为：";
	print_set(d3);

	//交换set
    set<int> d4;
	d4.swap(d1);
	print_set(d1);
	print_set(d4);
	d1.swap(d4);

    //插入
	d1.insert(100);
	cout << "插入元素之后：" << endl;
	print_set(d1);

	d1.erase(100);
	cout << "删除指定元素后" << endl;
	print_set(d1);

	d1.erase(d1.begin());
	cout << "删除指定头位置元素后" << endl;
	print_set(d1);

	d1.erase(d1.begin(), d1.end());
	cout << "删除指定区间元素后" << endl;
	print_set(d1);

	cout << "重新赋值后结果为：";
	d1.insert(24);
	d1.insert(24);
	d1.insert(243);
	d1.insert(73);
	d1.insert(63);
	print_set(d1);

	d1.clear();
	cout << "清空容器后结果为：";
	print_set(d1);

	// 
	set<int>::iterator pos = d2.find(73);
	cout << *pos << endl;

	cout << "24元素的个数为: " << d2.count(24);

	return 0;
}

结果为：