北京大学《C++程序设计》这门课将向你讲授C++程序设计有关的概念和语法，使你能够使用C++语言，以面向对象的方法编写可维护性、可扩充性好的，较大规模的程序。我们建议你在开始本课程之前已经熟悉了C语言和基本程设编写。这门课则将带你掌握C++语言中类、对象、运算符重载、继承、多态等面向对象的程序设计方法，以及模板、标准模板库STL等泛型程序设计的机制，体会和领悟面向对象程序设计方法和泛型程序设计方法的优势。
Set和Multiset
Loading...
来自 Peking University 的课程
C++程序设计
644 个评分
从本节课中
标准模板库 STL-2
本模块将继续介绍C++的标准模板库（Standard Template Library，STL），这是泛型程序设计最成功的应用实例。STL是一些常用数据结构（如链表、可变长数组、排序二叉树）和算法（如排序、查找）的模板的集合。有了STL，你就不必编写大多的、常用的数据结构和算法。即便不想用面向对象的程序设计方法编程，学习STL也是大有裨益的。
与讲师见面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
呃，同学们好呃，这节课我们说说标准模板库 STL 里面的这个 set 和 multiset 呃，这个
这个东西特别的好用，那我们知道前面讲的这个顺序容器，现在该讲这个关联容器了。
关联容器呢有这个四种，set， multiset， map 和 和 multimap， 它们的特点呢就是内部元素是
从小到大排好序的，当然什么叫小什么叫大你可以自己定义。
呃，那这些关联容器除了各种容器都共有的那些成员函数以外，它还有以下这些成员函数。
呃，最常用的一个就是 find。
find 呢它能够查找等于某个值的元素啊，这里所说的等于不是用那个恒等
恒等号去判断等于，什么叫等于呢，如果 x 小于 y 和 y 小于 x 同时不成立， 那这个就认为
x 和 y 是相等的啦呃，至于这个什么叫小于呢，以后这个可以自己定义了。
呃，这个 lower_bound 是查找某个下界，哦还有 还有这个 up_bound
是找上界，equal_rang 呢就是同时查找上界和下界，count 是计算等于某个值的元素的个数。
然后 insert 是用来插入一个元素或者一个区间到这个关联容器里面呃，进一步学习这个关联容器之前，
之前我们首先要学一个预备知识就是这个 pair
模版，这个 pair 模版呢是这，这个 STL
里面预先定义好的一个类模版啊，我们前面学模版的这个知识的时候实际上自己也写了一遍。
跟那个有点像，这个 pair 模版它有两个类型参数 T1 和 T2 啊，这个 pair 模版被写成了
struct 的这个形式，这样它里面所有的成员 成员呢不需要声明就都是公有的，然后把这个，在这里面把
T1 它的 define 成 first_type, 那我们以后用 first_type
就能够 代表 T1 类型啦，然后把 T2 定义成 second_type
这种类型的，那重要的是我们要知道 pair 模版有两个成员变量 一个叫做 first
一个叫做 second， first 是 T1 类型的 second 是 T2 类型 的，接下来我们要看的就是
pair 模 模版的几个构造函数，第一个构造函数无参构造函数嗯，我们看这里有一个初始化列表，
first 和 second 是对象的话是成员对象的话，那么
first 和 second 都是用无参构造函数来初始化的。
那如果 first 和 second 是基本类型的变量的话呢呃，那后面加个圆括号从语法上来讲也没有问题，那等于也就
不初始化它啦呃，再看第二个构造函数呃，第二个构造函数呢它有两个参数
a 和 b， a 呢是 T1 类型的，b 是 T2
类型的嗯，然后在这个初始化里面呢用 a 去初始化 first 用 b 去初始化 second
呃，这个非常的符合逻辑呃，那我们看第三个构造函数呃，第三个构造函数它不是一个普通的构造函数。
构造函数，它实际上是一个模版啊，它是一个函数模版呃，那这个函数
函数模版呢仅在我们真的用到了这种形式的构造函数的时候它才会被实例化出来，等会会讲到它如何被实例化。
这个函数模版它有两个参数 U1 和 U2，类型参数啊，然后这个
pair 构造函数它的参数呢是另外一个 一个呃，pair
模版类的对象，在这个 pair 模版类的对象 p 里面呢呃，这个
first 成员变量呢， 是 U1 类型的，然后 second 成员变量呢是 U2
类型的。然后我们在这个构造函数里面啊呃，用 p.first 去初始化 去初始化呃，first
，用这个 p.second 去初始化呃，这个 second 呃，这也呃，看上去也没有任何问题吧。
pair 模版这么重要呢，那是因为啊，这个 map 和 multimap
这种容器里面放着的东西全都是从 pair 模版 模版实例化出来的类的对象，而且它们是按
first 这个成员变量从小到大排序的呃，按大小
按大小，什么叫小什么叫大你可以自己定义呃，除此之外呢 set 里面和 multiset 里面也有一些成员函数。
那个 equal_rang 它的返回值就是一个 pair
模版类的对象，所以我们要先说 pair 模版呃，那
那，那接下来我们先看一下第三个构造函数模版在什么时候会起作用，比方说我们定义的一个
pair 模版类，pair<int, int> 啊，它是一个 pair
模版类，然后我们定义了这样一个类的对象叫做 P ，那 P 后面跟的这个括号呢
括号就给出了构造函数的参数，然后看这个构造函数的参数呢只有一个，那肯定是呃，调用了
那边这个构造函数的对吧，这个唯一的函数呢是另外一个 pair 模版类的对象，那个
pair 模版类是 pair<double, double> 好，那这个 pair
模板类的对象呢是一个没有名字的零时对象它的类型是 pair<double, double>，
那么这个零时对象它的 它的 first 成员变量当然就是 double 类型的而且它的值是 5.5
对吧，然后这个零时对象它的 second 成员变量也是 double 类型 类型的，它的值是
4.6， 那，那总而言之我们就会用 5.5 去初始化 P 的
first，用这个 呃，4.6用 p.second
是在这块就对应4.6呃，去 p.second
那当然初始化的结果就是呃，把这个浮点数去尾取整啊，因为我们这个 P 里面的
first 和 second second 它都是 int 类型的对吧，所以我们就去尾取整结果
p.first 呢变成了5，p.second 变成了4.6 好我们学过了 pair
的预备知识啊，接下来我们就要近距离的看看这些关联容器都长什么样。
啊我们先看这个 multiset 它在 STL 里面的定义是这样的啊，我们首先看到
它有三个类型参数，一个叫 Key ，那 Key 呢就代表这个 multiset
里面放着的元素的 这个类型呃，第二个类型参数 Pred
呃，这里看上去比较奇怪，它还有一个等于什么 less<Key>，这是
类型参数也可以有缺省值的这个意思，等会再解释，
解释。那总而言之 Pred 它是用来规定 呃，multiset 里面的元素比大小是按什么规则来进行的。
呃，也就是说 Pred 类，类型的变量， 它决定了比大小的这个规则，这个
multiset 在运行的过程中在需要比较两个元素 x y 的时候。
multiset 会生成一个 Pr 类型，Pred 类型的变量，假设这个 Pred 类型的变量叫做 op。
那么怎么比较元素 x y 的大小呢，multiset 就会去计算 op(x,y) 这个表达式的值。
如果这个表达式的值返回为 true 的话那么就认为 x 比 y 小也就是说 x 要排在 y 的前面。
那我们看到这样一个表达式要有定义，那 op 得是一个什么东西才行呢？
那我们知道 op 它可以是一个函数指针或者函数名字或者是函数对象啊那
那真正 multiset 在运行的过程中这一块的话实际上是有可能是函数指针也有可能是一个函数对象。
很多的情况都是函数对象，那如果 op 是一个函数对象的话，op(x,y)
怎么解释呢，这当然就是调用 op 这个对象的 operator 圆括号成员函数。
对吧，那我们说了这个呃，这个 Pr 呃，Pred 它的缺省值是
less<key>，那这意味着 什么呢？那我们就要看这个 less 到底是个什么东西。
less 呢它是一个函数对象类模版，在 STL 里面就有的 呃，把它定义成一个 struct，它从什么东西派生过来这个不重要我们不管它。
我关心的是 less 这个类模版里面它重载了圆括号 那这个圆括号呢一般就是被用来比大小的，对吧，比较 x y 的大小。
那这个，这个圆括号成员函数返回 true 的时候就意味着 x 是小于 y 的。
那我们看这个圆括号里面怎么比大小呢啊，我们看到啊，如果 x 小于号 y 这个表达式返回值为 true 的话。
那么呃，整个函数的返回值就为 true，那归根到底我们就 知道了，这个 less 模版它是靠小于号来比较大小的。
那也就是说你在使用 multiset 的时候你从这个 multiset
实例化出来一个类的时候，第二个类型参数和第三个类型参数你都可以不给的。
其中这个第三个类型参数根本就不重要，我们就当作没看见不理它了啊，第二个类型参数如果不给的话呢。
第二个类型参数的类型就会用 less<key> 来替代呃，那也就是说如果你
嗯 不给第二个类型参数的话呃，那 multiset 在执行的过程
过程中比大小的时候用到的这个变量 op 就是 less<key> 这种类型的。
那这个时候要用 op(x,y) 这个表达式进行 进行比大小的时候呢就会调用这里定义的这个圆括号。
那在此情况下我们看到比大小的规则是什么？就是用小于号来比大小。
那也就是说，你使用了 multiset 的时候，如果你没有自己定义比大小的规则。
那在这个缺省的情况下，multiset 就是用小于号去比大小，去比较 元素的大小了。那接下来呢我们来看看 multiset 都有哪些成员函数啊。
呃，第一个是 find 啊，它是在容器中 查找值为 val 的元素，就是说值等于 val 的元素。
如果查到了呢就返回其这个元素的迭代器，如果查不到呢，返回值就是 end() 这个迭代器。
那这里所说的等于它的意思不是用那个恒等号去判断啊，而是 x 小于 y 和 y 小于 x 同时不成立，那就算 x 等于 y。
至于什么叫小于呃，你可以自己定义也可以用缺省的这种小于号。
然后这个 insert 就是把一个元素。
把一个值插到这个容器里面 那就能够新添加一个元素了嘛，然后就返回这个新增元素的这个迭代器。
下面这个 insert 呢是把一整个区间插入到这个容器里面去，它的返回值是 void。
Count就是统计有多少元素的值和这个val相等。相等的意思是X小于Y和Y小于X同时不成立。呃，然后这个lowerbound它是查找一个迭代器，
它实际上是相当于查找一个下界啊，下界的意思是就是说它找一个迭代器， 这个迭代器it，
使得从begin到it中的所有元素都比val要小。当然it所指向的那个元素它，
不比这个val要小。呃，然后这个upperbound，它是查找一个上界。
呃。
它呢是查找一个最小的位置it，嗯，所谓最小就是，最靠左边吧，
那这边的这个最大就最靠右边吧。呃，那upperbound是找一个最小的位置it，使得这个左闭右开的区间，就是从it到end这个区间里面的所有元素，
都比val要大，也就说val，小于这个区间里的，呃，所有元素
那么我们要知道，这个，find,
insert, 呃，插入一个元素，以及，以及这个，呃，lowerbound,
upperbound， 他们的时间复杂度呢，就都是这个，呃，logN的。
那insert的时间，insert一个区间的时间复杂度是多少呢？ 那跟这个区间有多少个元素有关系，对吧？
区间有n个元素那就，那就再，再，再乘以logN。
然后，呃，multiset还有一个成员函数叫做equal range。
equal range它是同时求得lowerbound和upperbound。
那lowerbound和upperbound两个值啊，怎么同时返回两个值呢？所以这个时候equal range它，
呃，它的返回值就是一个pair类模板的对象。啊，这个pair类模板，
实际上画出来的类型是pair, iterator, iterator。
也就是说，在这个pair对象里面，它的first成员变量和second成员变量，
类型全都是，呃，这个容器上的迭代器。然后实际上呢，在这个返回值里面，
反而是对象里的first实际上就是存放着lowerbound的结果，second就会存放着upperbound的这个结果。
呃，还有一个重要的成员函数erase，就是删除，呃。
某一个迭代器所指向的元素。它的返回值呢也是一个iterator，就是C++的标准，
它并没有说erase的返回值是iterator。但是在好多现在的编译器里面，
这个erase它删掉了it所指向的元素以后，
它的返回值就是被删除元素后面那个元素的，这个迭代器。
那这样用起来会很方便呐。那我们使用erase的时候要注意就是，如果一个迭代器指向的元素被删掉了，那这个迭代器就会失效。
那你就不能，再去使用这个迭代器了。呃，你不能说，it所指向的元素被删掉了，
你还用it，让it++，它还能自动指向被删除元素的后面的元素，或者再后面一个元素。
这是不行的，总之吧，一个迭代器所指向的元素一旦被删掉，这个迭代器你最好就不要再用它了。
那我们下面看一下这个multiset具体的这个用法。
这是一个完整的程序啊，但是它是会出错的。在这里面有个class a，我们使用multiset要include set这个头文件。
呃，然后我们定义了一个multiset的模板类。
就是multiset尖括号a， 然后定义了一个这个模板类的对象。那我们知道multiset它有三个
那个类型参数a，我们只给了一个类型参数a，
表明这个multiset里面呢，每一个元素都是class a这种类型的对象。
不打也可以，对吧，因为我们后面两个类型参数是可以有缺省值的。
呃，这条语句没有什么问题。但是呢，我们在写这个a点insert，啊这条语句，就会编译出错了。
为什么会编译出错呢？那我们就分析一下 这个multisetA到底是一个什么样的东西。啊，我们写multiset
a这么一个简单的写法， 它是等价于下面这种写法的。
当然下面这种写法它也少掉了一个类型参数，那个第三个类型参数我们不管它。
所以我们就关心这里，第二个类型参数它的缺省值是，less a。
那么这个multiset在插入元素，就是执行erase，执行insert。
在执行插入元素的时候，multiset会将被插入的元素和已有的元素进行比较。
这时候比大小的规则是什么啊？就是这个less a。
那less a 这个类里面它的圆号有重载，它，它，
它重载的圆号的这个成员函数，然后那个成员函数里面呢，用了小于号去对两个class a的对象进行比较。
然后我们整个程序里面都没有重载这个小于号，那也就是说，两个class a的对象是不能比大小的。
所以，呃，程序在这就会编译出错。归根到底就是因为程序编译器会从，
会实地化出来一个less a这个类，这个类里面圆号用到了小于号，
然后这个类里面呢圆号成员函数用到了小于号，然后你这个小于号呢又没有定义，
所以就编译错了。呃，那下面我们看一个能编译过的这个例子啊。
呃，在这个例子里面我们看啊，先写了一个print这个模板。
呃，它是能够把一个区间，first和last里面内容都给它用celt输出出来。
呃，然后这个class a，还有个成员变量n。然后class a 呢定义了一些友元，
其中有一个是小于号，被重载的小于号。这个小于号所规定的比较大小的规则是什么啊？
就是谁的n成员变量数学上小，
那谁就算小。啊，然后还有这个，有运算符用来输出，这个对象n的值。
嗯，还有另外一个类，叫做myless，啊，这个myless是干什么的呢？
啊，我们看到这个myless，它是一个函数对象类。
它里面重载了圆号，这个圆号所规定的比大小的规则是什么呢？
我们看看，就是说，谁的个位数数学上小，谁就算小，啊。
好了，那现在，我们接下来看， 去用这个multiset。这里我们用到了一个multiset a。
呃，这种类型。那这个类型写起来可能比较长吧，这我就把它typedefine一下，啊，
让它变成了这个mset1。那这个mset1，
我们定义的时候并没有去制定比大小的规则。
那也就是说mset1这种容器吧，它是用小于号来比大小的。
那我们再来typedefine另外一个类型，multiset a, myless。
呃，给它一个新的名字，啊，mset2。
那就是说mset2 这种容器，它是用什么东西去比大小的呢？ 呃，我们看到它用到myless这种类型。
呃，实际上归根到底就是用myless里面的这个operator的这个圆号，这个成员函数去，
呃，比大小的。那也就是说，myless所定义的这个比大小的规则就是，
呃，谁的个位数数学上小，谁就算小。
好那我们再看main里面啊， 首先定义了一个size, 呃，它有6个元素吧，宿主有6个元素。
然后呢，我们定义了一个mset1类的容器，叫m1。
然后在m1里面调用insert1成员函数，啊，才能够把一整个区间插入进去。
那插入进去以后这些元素就自动排好序了，在这个过程中肯定会去调用比大小的小于号了。
啊，然后我们在m1 里面再插入一个22，呃，
那multiset它是排好序的一种容器，而且它里面的元素是可以重复的，
所以我们接下来看，我们调用count成员函数算一下有多少个元素它等于22，那输出的结果当然都是2，对吧因为
原来有一个22，你又插入一个22，那它有两个22。
呃，接下来我们调用print这个模板把m1的内容全部输出了， 那我们看到，是按照从小到大
的顺序输出的。因为m1里面的元素是排好序的，而且那个排序的规则就是用小于号， 而且是，
这个小于号所定义的这个排序规则，就是谁的成员变量n数学上小，谁就算小。所以这里面我们看到，这些是，数学上从小到大排序输出了。
接下来呢，我们调用这个find去查找这个元素19，好那我们看这个m1里面
不是18，19什么之类的对吧？那这个时候呢，肯定是能找到的。那判断能否找到的办法就是看一下返回值这个迭代器是不是
等于and，如果等于and就说明找不到。那这个程序它肯定能找到啊，所以这一行会被执行出一个found。
呃，那再接下来呢我们看，哎，在m1上面调用lowerbound，lowerbound它的返回值是一个迭代器。
然后我们通过星号再把这个迭代器指向的内容给它输出，那这个lowerbound它是做些什么呢？
嗯，这个lowerbound啊，它，
我们看它的定义啊，lowerbound，嗯，它是，在这个容器里面查找一个最大的位置it，使得从begin到it里所有元素都比这个val要小。
那这个最大的位置，就是说最靠右的这个位置，或者说是最接近and的这个位置，
注意这个区间是一个左闭右开的这个区间，那么我们这个m1点lowerbound22，
呃，就是要在这里面查找一个迭代器，嗯，这个这个it，然后使得从4，啊，这第一个元素begin，4到这个it
这个区间里面的所有元素都比22小，那这个lowerbound找到的迭代器应该指向哪儿呢？它当然应该指向这个22，对吧？那这样的话我们从begin
所有元素，当然它都比22要小了，对吧？注意这是左闭右开的这个区间，所以这个22本身是并不算在内的。嗯，那总而言之吧，
我们这个m1点lower bound找到的迭代器就指向了这个22，是吧？所以，我们给它输出的时候，输出的值当然就是
22了。那接下来我们再看upper bound。Upper
bound是干什么的呢？Upper bound是要求一个左闭右开的这个区间。
它的这个左边的那个迭代器，左边这个迭代器要尽可能靠begin
尽可能向左。那求出这个左闭右开的区间里面呢，每一个元素呢，都要比这个22 要大。
那这个左闭右开的区间就是这样。
那么这时候我们这个upper bound所求出来的那个迭代器，等于就是指向这个33。就是指向33
这个迭代器。所以我们这里输出的结果，你要输出，新m1点upper
bound输出的结果当然就是33了。
好，接下来我们呢，再调用erase，就把这整个区间都给它删掉，
就是lower bound 和upper bound之间的元素给它删掉。那我们看到这个区间是什么呢？这个区间它是
一个左闭右开的区间，就是22，
然后，这个，33。由于这是一个
左闭右开的区间，所以呢，这两个22就被删掉了，但是33呢，还留着。然后我们这个PP就等于
erase的返回值，它是迭代器指向了被删除那个区间的后面的一个元素。那当然就指向了这个33。
所以我们这个，一开始输出这个m1里面的内容，它有两个22
被删了。然后再输出新pp，就是pp指向的元素，那当然就是33了。接下来我们再看有一个m2，
这个是MSET2。MSET2这个容器里面比大小的规则是什么呢？就是个位数小的，
就算是小。嗯，于是我们在这条INSERT语句中一下把一个区间插到m2中间去，这个区间就是
数组A，那就是说数组A里面的元素都被拷贝到m2里边去了，而且是按个位数从小到大排序了，
我们把它输出，果然，按个位从小到大排序，就是这个样子。OK，这个输出
是这样的。好，这个multi-set呢，总算说完了。接下来就讲讲这个set。Set也特别常用。
它跟multi-set的差别就在于啊，这个set里面是不能够有重复元素的。嗯，什么叫
重复元素啊？并不是说A等于B，A就叫重复了啊。实际上，如果有A小于B不成立，而且B小于A也不成立，那么
A和B就算是重复了。好，那，如果你插入的一个元素
如果你想往set里面插入一个值的时候，这个值跟set里头已有的元素重复了，那就是说会怎么样呢？
这个插入当然就不成功了。我们来看看set的这个用法。嗯
在这里我们定义一个，当然include头文件set ，然后我们定义了一个类型，就是set<int>这种容器上面的
迭代器。这种类型我们称之为大写的这个IT。Inter
rate，这里有一个数组。
3、4、6、12，然后我们定义了一个，set容器，里面都是整形的
变量。把这个数组的全部内容都拷过去，那我们在这里定义set的时候，我们并没有指明这个
排序的方式，对吧？那当然这个set<int>就是用小于号去排序的。
所以在这里面ST里面的元素当然就是按照数学上的小从小到大排序的，就是1、2、3、4、6。
嗯，接下来我们定义一个pair，内模板，pair模板类的对象对照，那这个result它有两个层面，一个叫
first，一个叫second。那First的成员变量呢，它的类型IT，就是set<int>上面的迭代器，second的成员变量类型呢，就是booi类型，
定义这个result类型干什么用呢？有用。下面我们调用st一点insert，要往里插一个5，
那我们知道这个set里边它是不能有重复元素的，所以你要往里头插一个元素的时候，是有可能不成功的。
如果你要插的东西在这个set里边本来就有了，那你就不能成功了。可是，你怎么判断插进去的那个元素
你想要插的那个元素在set里边是不是存在呢？就是这个插入到底是不是成功，如何判断呢？那答案就是我们要拿到insert成员函数的
返回值。具体到这条语句，当然是能够插入成功的，对吧？因为它要插入5。
5在原来并没有。那我们怎么判断插入是否成功呢？我们就看这个返回值，它是？对象，看这个返回对象second的
成员变量，这个second的成员变量是booi类型的，其值是true或者false。如果这个second的值为
true，就是说插入成功了。那这个时候result点first就是一个迭代器，它
指向刚刚被插入的这个元素。然后我们就输出新result
first，那就是刚刚被插入的那个5，对吧？
所以这一行就输出了5，inserted。好，那我们下回再来插入一个5，
然后判断是不是成功。最后当然就不成功，是吧？因为你刚刚已经把5放进去了，就是你再插入5就重复了，于是就不成功。
既然插入不成功，那程序肯定就会走这条语句，插入不成功是因为set里面已经有一个元素它的值
跟你要插入的东西重复了，在这种情况下，insert成员元素它的返回值的first成员变量会是
一个迭代器，就会指向那个重复的元素。那在这里，重复的元素就是5。所以在这里输出新的result
first当然就会输出5。
那就是输出5，already exists。接下来我么再看调用了这个set的equal
range的函数，求4这个值的 equal range。Equal range就是同时求lower
bound和upper bound。那这个equal range它的返回值也是一个pair对象。
这个pair对象的first和second成员变量全部都是迭代器。那实际上，这个lower bound求出来的东西就是一个迭代器嘛。
就会放到first的成员变量里面。Upper bound这个迭代器就会放在second的成员变量里面。那这个st是1、2、3、4、5。
那求lower bound。Lower bound是什么呢？Lower bound是求一个最靠右边的迭代器。
啊，这个，这个迭代器，再往左的那些元素，都比这个值要小。那最靠右边的，这样一个迭代器求出来就是
指向4这个位置。它的右边的元素，嗯，它的左边的元素都比4要小，而且这个迭代器，你就
没法儿再往右移了。再往右移，4就不比4小，那就错了，对吧？所以我们输出的这个
bounds点first就是，lower bound就指向4嘛。然后upper
bound是什么呢？ 就是求做靠左边的一个迭代器。然后从这个迭代器开始，一直再往右，直到元素都要比4都要大。那当然这个迭代器就指向5这个位置。
对吧？它是最靠左边的，而且从它开始往右的元素都比4要大。所以，所以输出新的bounds点second当然就是5了。
因为这个upper bound被放到bound点second里面去了。
那总算讲完了，费了好大劲。
