C++STL：set/multiset（集合）类模板

set型容器能顺序存储一组数值，这些数值既充当存储的数据，又充当数据的键值。该集合更像一个有序链表，其中的元素以升序顺序存储。

1.set的定义

set类模板的声明如下：

其中，参数Key是存储在集合中元素的数据类型；参数Traits是用于实现集合内部排序的仿函数，默认值为less＜Key＞；参数Allocator代表集合的内存配置器，负责内存的分配和销毁。使用set类模板时，需要包含头文件＜set＞。set类模板的构造函数包含以下几种：

上述是set类模板中构造函数的6种形式。第一种形式最简单，定义一个空对象（容器），参数包含了一个谓词，用于容器内部排序用；第二种形式除包含一个谓词之外，还加入了内存配置器；第三种形式用于使用已存在的set定义新的set；第四种形式包含了使用迭代器指定固定范围，用于定义新的set；第五种形式在第四种形式的基础增加了参数_Comp，从而可以自定义排序规则；第六种形式在第五种形式的基础上增加了内存配置器的内容。

在本节之前，本书已经大量使用了“排序”。在此对排序准则进行简要描述。所谓排序准则，应具备如下特征：

1）必须是“反对称的”。对操作符“operator＜”而言，若x＜y为真，则y＜x为假。对判断式predicateop（）而言，若op（x，y）为真（1），则op（y，x）为假（0）。

2）必须是“可传递的”。对“operator＜”而言，若x＜y为真且y＜z为真，则x＜z为真。对于判断式op（）而言，如果op（x，y）为真且op（y，x）为真，则op（x，z）为真。

3）必须是“非自反的”。对“operator＜”而言，x＜x永远为假是不可能的。对判断式predicateop（）而言，op（x，x）永远为假。

总结

以上内容是STL学术理论的一部分。STL先建立起一个抽象概念阶层体系，继而形成一个软件组件分类学，最后再以实际工具（template）将各个概念实现。《Generic Pro-gramming and the STL》一书对这些理论做了诸多描述，其中文译本为《泛型编程与STL》。

要具体实现排序准则，可采用两种形式：①在类模板中以参数形式实现；②以构造函数参数定义之。具体形式如下：

set虽然具有排序功能（multiset同样），但也有其局限性。一旦元素被输入至容器中，就无法再对其进行“确定的”访问，因为元素的位置改变了。原有的输入顺序被自动排序功能打乱了。要改变元素的值，需要先删除原有的元素，再重新插入新元素。所以，set(和multiset)没有提供任何直接存取元素的成员函数。虽然STL提供了多种set定义方法，但Visual C＋＋ 6.0并没有提供所有定义方法，而Linux环境下的C++编译系统提供了所有定义方法。通过例3-27对以上内容加以详细说明。

例3-27

例3-27的执行效果如图3-28所示。

图3-28 例3-27的执行效果

例3-27中的几种定义形式，在Visual C＋＋ 6.0中调试通过。但在模板中使用多个参数的定义形式没有调试通过。另外，除了允许元素重复之外，multiset的定义形式和set是相同的。

提示

在main（）函数的第9行，输入了一个重复元素“20”，但程序输出时，并没有这个元素。说明了set中不允许有重复的元素。

2.set和multiset的容量，搜寻及统计

和其他容器一样，set型容器提供了获取容器容量的size（）函数，判断容器是否为空的empty（）函数以及返回容器可容纳最大元素数的成员函数max_size（）。

set（multiset）型容器还提供了元素个数统计count（）函数。

set（multiset）型容器提供了查找find（）函数，还提供了low_bound（）、upper_bound（）和equal_range（）函数。

以上几个函数的原型为：

find（Key）函数的功能是返回键值为Key的元素的位置，其返回值是迭代器类型。count（Key）函数的功能是统计键值为Key的元素个数。

low_bound（const Key＆_Key）函数的返回值是迭代器，该迭代器指向集合中键值大于并等于参数Key的第一个元素。

upper_bound（onst Key＆_Key）函数的返回值是迭代器，该迭代器指向集合中键值大于参数Key的第一个元素。

equal_range（const Key＆_Key）函数的返回值是迭代器对（pair），该迭代器对（pair）的两个迭代器分别指向集合中键值大于并等于参数Key的第一个元素和集合中键值大于参数Key的第一个元素。

下面使用例3-28来说明以上几个函数的使用方法。

例3-28

例3-28的执行效果如图3-29所示。

图3-29 例3-28的执行效果

3.set和multiset的迭代器相关函数及赋值函数

set和multiset提供了所有容器均拥有的基本赋值操作：“＝”，swap函数。赋值操作的两端容器必须具有相同型别。

set和multiset类模板中，和迭代器相关的成员函数主要包括begin（）、end（）、rbegin（）和rend（）。其中，begin（）和end（）函数是双向迭代器，rbegin（）和rend（）函数是逆向迭代器。对于迭代器，所有元素都被视为常数，确保不会人为改变元素值或打乱既定顺序。set和multiset中的元素是无法调用任何修改性算法的。set和multiset是不能使用remove（）算法函数的，如果要移除set和multiset中的元素，必须使用它们本身提供的成员函数。

swap（）函数的原型为：(www.xing528.com)

begin（）和end（）函数的原型为：

rbegin（）和rend（）函数的原型为：

例3-29

例3-29的执行效果如图3-30所示。

图3-30 例3-29的执行效果

4.set和multiset的插入和移除

set和multiset中用于实现插入元素和删除元素的函数主要包括insert（）、erase（）和clear（）。迭代器需要指向有效位置，但序列起点不能位于终点之后，并且不能从空容器中删除元素。因此当删除元素时，首先要判断容器的容量。

insert（）函数的原型为：

上述第一种模型，insert（）函数的返回值是pair＜iterator，bool＞类型。pair型返回值的第1个参数是迭代器，代表插入元素的位置；pair型返回值的第2个参数是bool类型，代表是否插入成功？

insert（）函数可以向容器中加入一个对象、一个对象的若干副本或者某个范围内的多个对象。其插入位置是使用迭代器指定的。

erase（）函数可以删除一个由迭代器指定的元素，也可以删除某个范围内的多个元素。

erase（）函数原型为：

第一种形式的功能是将迭代器所指向的元素删除，第二种形式的功能是将迭代器所限定范围内的元素全部删除，第三种形式的功能是将元素Key删除。

下面请参考例3-30。

例3-30

例3-30的执行效果如图3-31所示。

图3-31 例3-30的执行效果

提示

请读者注意，在例3-30中，第一次使用了distance（）算法函数，用于计算容器中两个元素的距离。本例较详细地使用了pair类型的两个成员first和second，这两个成员分别代表pair对象中的两个元素。本例仅使用了set型容器。

5.set和multiset的比较运算符

容器之间的比较只能用于相同型别。因此，若要排序，就必须是相同型别的元素，否则编译时会产生错误。ISO/IEC 14882提供了关于运算符的声明和定义。运算符的使用和序列式容器是一致的。

Visual C＋＋ 6.0没有提供比较运算符的成员函数，但提供了另外两个函数：key_comp（）和value_comp（）。其中key_comp（）函数用于键值的比较，value_comp（）函数用于实值比较。这两个函数的原型为：

key_comp（）函数的返回值是key_compare类型，key_compare决定了集合中元素的排列顺序。通过对返回值的测试，可以确定序列排序形式。value_comp（）函数的返回值是value_compare类型。其意义和key_compare是一致的。

（1）键值比较

下面举例说明key_comp（）函数的使用方法。请读者认真阅读下面的源代码。

例3-31

例3-31的执行效果如图3-32所示。

图3-32 例3-31的执行效果

总结

在例3-31中，关于set和multiset两个类型，使用了较复杂的定义对象形式（见源代码第19行和第24行）。在使用时，注意“less＜double＞”和其后面的“＞”之间一定要有一个空格，否则编译时会出错。

（2）实值比较

value_comp（）函数的使用方法和key_comp（）的使用方法相同。只不过value_comp（）函数的返回类型为value_compare。此处就不再重新举例，在例3-31稍作改动即可。