C++的set / multiset容器

一、介绍

C++的set容器又被称为集合，所有元素在被插入后都会自动排序。

二、数据结构

set / multiset属于关联式容器，底层数据结构是用二叉树实现的。

其余的容器比如vector、deque和list等为序列式容器，因为他们底层使用线性序列结构，里面存储的是元素本身。而关联式容器所存储的是键值对<key，value>，这种方式相比于线性序列在数据检索时效率更高。

常见的关联式容器有：map、set、multimap、multiset，这四种容器的共同点是：

使用红黑树 / 平衡搜索树作为其底层结构，容器中的元素是一个有序的序列。

三、set与multiset的区别

3.1 二者插入元素的区别

set	不允许值相同的元素出现
multiset	允许相同的元素出现

在插入元素的时候，set的insert函数会返回bool类型的值，来表示插入是否成功。

（※注意※ 其实set的insert返回值是一个pair类型的变量，其中包含着bool，也有别的值）

而multiset的insert函数不会返回任何值。

3.2 pair “对组”类型

pair类型，称为对组类型。它是由两种类型的数据组合的，数据的类型是模板（由自己确定）

对组的初始化有以下两种形式：

pair<type1, type2> p(value1, value2);

创造一个第一个变量类型为type1，第一个值为value1；

第二个变量类型为type2，第二个值为value2的对组对象

pair<type1, type2> p = make_pair(value1, value2);

同上

对组的第一个变量为first，第二个变量为second。为了便于理解，请看以下例子：

//打印Pair变量的信息
void printPair(const pair<string, int>& p) {
	cout << p.first << "今年" << p.second << "岁." << endl;
}

int main() {
    pair<string, int> c("小C", 18);
    printPair(c);
    pair<string, int> daniel = make_pair("Daniel", 30);
    printPair(daniel);

    return 0;
}

程序执行的结果如下所示：

四、set / multiset的使用

为了便于观察，我们以下所有测试用例，均采用自己编写的printSet函数打印全部元素：

//打印set集合的所有元素
void printSet(const set<int> &s) {
	if (s.empty()) {
		cout << "This set is EMPTY now." << endl;

		return;
	}

	for (int elem : s) {
		cout << elem << ' ';
	}
	cout << endl;
}

4.1 set初始化

声明	解释
set<T> s	初始化一个空集合
set<T> s(const set<T> &s1)	拷贝构造函数，用s1的所有元素初始化一个集合

set<int> s;//初始化空集合
printSet(s);
set<int> s1(s);//拷贝构造函数
printSet(s);

程序执行结果如下所示：

4.2 set赋值

两个set对象之间的赋值采用重载后的=运算符：

set<int> s0;//s0 = EMPTY
set<int> s1;//s1 = EMPTY

for (int i = 0; i < 10; i++) {
	s0.insert(i);
}//s0 = 0 1 2 3 4 5 6 7 8 9

cout << "Before s1 = s0, s1 : ";
printSet(s1);//s1 = EMPTY
s1 = s0;
cout << "Before s1 = s0, s1 : ";
printSet(s1);//s1 = 0 1 2 3 4 5 6 7 8 9

程序执行结果如下所示：

4.3 set容量和大小

声明	解释
empty()	判断集合是否为空
size()	返回集合中元素的个数

set<int> s0;//s0 = EMPTY
set<int> s1;//s1 = EMPTY

for (int i = 0; i < 10; i++) {
	s0.insert(i);
}//s0 = 0 1 2 3 4 5 6 7 8 9

cout << "s0.empty() : " << boolalpha << s0.empty() << endl;//false
cout << "s0.size() : " << s0.size() << endl;//10

程序的执行结果如下所示：

4.4 set交换元素

声明	解释
swap(set<T> s1)	将当前集合的全部元素和s1的全部元素交换

set<int> s0;
set<int> s1;

for (int i = 0; i < 10; i++) {
	s0.insert(i);
	s1.insert(i+10);
}

cout << "Before Swap : " << endl;
cout << "s0 : "; printSet(s0);
cout << "s1 : "; printSet(s1);

s0.swap(s1);//swap

cout << "After Swap : " << endl;
cout << "s0 : "; printSet(s0);
cout << "s1 : "; printSet(s1);

程序如下所示：

4.5 set插入元素

声明	解释
insert(T elem)	将elem插入当前集合

set<int> s0;
cout << "Before Insert : " << endl;
cout << "s0 : "; printSet(s0);

//为s0 插入0~9
for (int i = 0; i < 10; i++) {
	s0.insert(i);
}

cout << "Atfer Insert : " << endl;
cout << "s0 : "; printSet(s0);

程序运行的结果如下所示：

4.6 set删除元素

声明	解释
erase(T elem)	删除当前集合中值为elem的元素
erase(pos)	删除当前集合中pos迭代器指向的元素
erase(begin, end)	删除当前集合中[begin, end)区间的元素
clear()	删除当前集合中全部元素

set<int> s0;
for (int i = 0; i < 10; i++) {
	s0.insert(i);
}//s0 = 0 1 2 3 4 5 6 7 8 9 

//删除值为7的元素
s0.erase(7);
cout << "s0 : "; printSet(s0);//s0 = 0 1 2 3 4 5 6 8 9

//删除begin+1指向的元素
set<int>::iterator s_begin = s0.begin();
s_begin++;
s0.erase(s_begin);
cout << "s0 : "; printSet(s0);//s0 = 0 2 3 4 5 6 8 9

//删除[begin+2, end-2)
s_begin = s0.begin();
set<int>::iterator s_end = s0.end();
s_begin++; s_begin++;//begin + 2
s_end--; s_end--;//end - 2
s0.erase(s_begin, s_end);
cout << "s0 : "; printSet(s0);//s0 = 0 2 8 9

//清空全部元素
s0.clear();
cout << "s0 : "; printSet(s0);//s0 = EMPTY

程序运行结果如下所示：

4.7 set查找与统计指定元素

声明

解释

find(T elem)

找到指向第一个elem元素的迭代器

(如果没有找到，则返回end())

count(T elem)

统计值为elem的元素个数

multiset<int> ms0;
for (int i = 0; i < 10; i++) {
	ms0.insert(i); 
	ms0.insert(i);
}//s0 = 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 

cout << "s0 : "; printSet(ms0);

multiset<int>::iterator it = ms0.find(7);
cout << *it << endl;//7
cout << "ms0.find(5) : " << ms0.count(5) << endl;//2

程序的执行结果如下所示：

4.8 set排序

4.8.1 内置类型的set排序

set容器默认的排序规则：从小到大。可以使用仿函数改变排序规则。

仿函数可能是一个类或者结构体，重载了函数调用运算符operator()，使得对象可以像函数一样被调用。它本质上就是一个只重载了operator( ) 的类，它的出现是为了代替C语言中的函数指针。下面用一个例子具体表现仿函数在set内置排序中的应用：

//打印set集合的所有元素
template<typename T,typename ELEM_T>
void printSet(const set<ELEM_T, T>& s) {
	if (s.empty()) {
		cout << "This set is EMPTY now." << endl;

		return;
	}

	for (ELEM_T elem : s) {
		cout << elem << ' ';
	}
	cout << endl;
}

//仿函数：重载了（）运算符的类
class MySetCompare {
public :
	//重载（）运算符
	bool operator()(int a, int b) const{
		return a > b;//降序
	}
};

int main() {
	set<int, MySetCompare> ms0;
	for (int i = 0; i < 10; i++) {
		ms0.insert(i);
	}//s0 = 9 8 7 6 5 4 3 2 1 0  
	cout << "s0 : "; printSet(ms0);

	return 0;
}

4.8.2 自定义数据类型set排序

和上边内置类型类似，我们只需要通过仿函数设置自己的排序规则即可。以下例子为了便于说明问题，将成员均设置为public：

//士兵类：排名规则，先按年龄升序，再按身高降序
class Soldier {
public:
	string name;//姓名
	int age;//年龄
	int height;//身高

	Soldier(string n, int a, int h) : name(n), age(a), height(h) {}
};

//重载<<运算符
ostream& operator<< (ostream& cout, Soldier &s) {
	cout << s.name << "今年" << s.age << "岁，身高" << s.height << "cm。";

	return cout;
}

//仿函数：比较规则
class SoldierCompare {
public:
	bool operator()(Soldier s0, Soldier s1) const {
		if (s0.age == s1.age) {
			return s0.height > s1.height;
		}
		else {
			return s0.age < s1.age;
		}
	}
};

//打印set集合的所有元素
void printSet(const set<Soldier, SoldierCompare>& s) {
	if (s.empty()) {
		cout << "This set is EMPTY now." << endl;

		return;
	}

	for (Soldier elem : s) {
		cout << elem << endl;
	}

	cout << endl;
}

int main() {
	set<Soldier, SoldierCompare> soldiers;

	//添加士兵
	Soldier A("A", 30, 180);
	Soldier B("B", 18, 189);
	Soldier C("C", 35, 165);
	Soldier D("D", 18, 175);
	Soldier E("E", 35, 170);
	Soldier F("F", 25, 180);
	soldiers.insert(A);
	soldiers.insert(B);
	soldiers.insert(C);
	soldiers.insert(D);
	soldiers.insert(E);
	soldiers.insert(F);

	cout << "soldiers : " << endl;
	printSet(soldiers);
	
	return 0;
}

上述例子中的程序运行结果如下所示：