北京大学《C++程序设计》这门课将向你讲授C++程序设计有关的概念和语法，使你能够使用C++语言，以面向对象的方法编写可维护性、可扩充性好的，较大规模的程序。我们建议你在开始本课程之前已经熟悉了C语言和基本程设编写。这门课则将带你掌握C++语言中类、对象、运算符重载、继承、多态等面向对象的程序设计方法，以及模板、标准模板库STL等泛型程序设计的机制，体会和领悟面向对象程序设计方法和泛型程序设计方法的优势。
List和Deque
Loading...
来自 Peking University 的课程
C++程序设计
635 个评分
从本节课中
标准模板库 STL-1
本模块将介绍C++的标准模板库（Standard Template Library，STL），这是泛型程序设计最成功的应用实例。STL是一些常用数据结构（如链表、可变长数组、排序二叉树）和算法（如排序、查找）的模板的集合。有了STL，你就不必编写大多的、常用的数据结构和算法。即便不想用面向对象的程序设计方法编程，学习STL也是大有裨益的。
与讲师见面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
大家好，在这一小节中，我们来进一步了解一下 STL当中顺序容器中间的list和deque。
那么对于 list这样的一个容器呢，它实际上就是我们在数位结构当中非常熟悉的双向链表。
所谓双向链表呢，就是说这个链表当中的每一个元素
它都会包含一个指针，指向其后续的元，元素
此外呢，它还包含一个指针去指向其前一个元素。
那么有了这样一个list之后呢，我们会看到我们在list 当中的任何位置插入和删除呢，都是常数时间的。
比方说，我们希望在ai 这个元素和ai+1这个元素之间呢插入一个新的元素s
那么我们要做的事呢就是去使得ai和ai+1这两个指针呢发生一下改变
使得它们的指向呢都变成指向s就可以了，所以我们说这个插入和删除的过程呢
是非常便捷的。
那么要注意就是我们在list这个容器当中呢 是不可以根据下标来进行随机存储元素的。
那么作用在list这个容器上的迭代器呢，它不是随机访问的。
最后呢我们说，实际上所有的顺序容器 所具有的那些函数呢，在list当中呢都是可以使用的。
对于list来讲呢，它还有几个比较重要的
成员函数，比方说我们之前有提到的这个
push，它push的是谁呢？它push的是front 也就是说我在链表的最前面插入一个元素
同时呢，我也可以去删除链表的，也就是说去删除这个表头，啊去删除最前面的这个元素。
此外呢，它还有单独的一个sort函数来进行排序，那么注意因为本身list呢它
不支持这个随机访问迭代器，因此呢它不能用
STL算法本身的那个sort函数，它是自身自带的。
此外呢，我们还有这个remove 这个函数，那么它主要是用来删除和指定值相同的元素。
那么unique呢是删除所有和前一个元素相同的元素，也就是删除那些 具有一样值的元素。
那么此外呢，你可以去merge，也就是说我们把两个链表merge在一起 那么注意就是我们要清空其中被合并的那个链表。
此外呢我们也可以去颠倒链表，啊我们经常会需要说我们把这个链表呢要
逆序一下，那么自己写的程序呢就会非常的复杂。那么在list这个容器上呢
我们只需要去调用reverse这样一个成员函数，就可以简单地实现这个操作了。
最后呢，我还可以去splice,也就是说我们在指定的位置上呢 去插入另外一个链表当中的一个或者多个元素。
那么注意就是我们需要在插入之后呢把，把它相应在另外一个链表当中的元素呢那就删除掉。
我们来看一下对于list这个容器来讲呢，因为本身 的迭代器是不支持这个完全地这个随机访问的
所以我们说呢，在标准库中间的sort函数呢对它呢是不能使用的。
那么我们list自己本身呢是有一个成员函数的，我们可以呢对于 相应的这个list对应的这个
容器这个链表来讲呢，我们可以用自己定义的这个
compare的函数，也可以去利用我们自带的这个无参的版本，这个sort函数。
注意，这个版本，这个无参的这个sort函数呢，它是由小到大来进行排序的。
那么list本身这个容器呢，它本身只能
使用这个叫做双向迭代器，啊，因为它既要去执行这个
当前元素指向下一个元素，或者是当前的元素指向上一个元素，所以这个迭代器本身呢是双向的。
那么它呢因为是双向迭代器，而不是随机的这种迭代器呢，所以它不能支持这个比大小
这个比较运算符，或者是这个利用方括号来进行下标访问的运算符
以及随机的移动。啊也就是说所谓随机移动就是说我们不能利用list迭代器来加2
做这样的一个操作来进行相应的访问。
那么list这样的一个容器呢，它具体是怎么样使用的呢？我们来看一个例子，啊
我们在这个类A里头呢，重载了这个相应的这个operator这个小于号以及这个
呃 判断是否相等以及这个，呃，左移的符号，是吧
我们把这三个相应的这个运算符呢都重载为
呃，有源。那么此外呢这个A还包含了一个构造函数，啊
那么这是相应我们刚才对应的3个
呃，运算符重载的函数，那么这3个函数呢都被定义为
是类A的这个有源，我们看到像小于号呢就是去 呃，返回对应的这个
相应这个具体A这个类对象中间包含的这个n成员变量的
这个比大小的结果，以及去判断相应它们这两个n值是否相等。
啊，或者是去输出相应的这个a.n
那么此外的话呢，我们还定义自己定义的 一个叫做print
list这样的一个函数模板，啊 我们去相应打印这个链表中间的这个对象。
那么可以看到说呢，这个函数模板呢，它呢实际上呢就是
去定义了一个传递进来的这个，啊，lst这样的一个对应的列表。
那么，我们会看到说我们在这里呢实际上呢，呃
可以用这个typename去定义这个list
T双冒号，const,iterator这样的一个，呃
本身的这个迭代器的类型，啊用来去声明说我们定义的一个迭代器i
那么去，用这个长长的一串呢去标记出它是一个类型，然后这一串呢实际上在VS里面
可以，可以不去写。啊，我们让这个本身的这个定义好的这个迭代器呢，i 呢
让它赋值从list的这个begin开始，啊，依次从这个链表的这个首元素开始
然后去相应地输出其每一个值，啊，一直到这个list的末尾。
那么有了这样的一个print list 的这样的一个函数模板之后呢，我们就可以相应输出 我们希望能够打印的链表中间的对象。
我们来具体看一下，啊，在定义好了这个类A以及相应的打印输出
嗯，链表当中每一个对象的这样的一个print list的一个函数模板之后呢
我们来具体看一看怎么样对这样一系列的list来进行一些操作。
我们在main函数里头呢，首先定义的就是一个A类型的
两个链表，分别是list1和list2
我们接着做的事呢就是对这个list1和list2呢分别其中的每个元素呢来进行赋值，啊进行插入
这个相应元素这样的一个工作。我们首先呢就是对list1呢进行了这样5次push
back的工作
也就是说我们把相应的这个list1当中的元素呢插入进了
1，3，2，4，2这样5个元素，接着呢我们会去
构建这个list2，那么我们首先push
back进来一个10 接着呢，我们要push front,
也就是说我们需要在 这个链表的头部去插入一个元素20
接着我，接着push back是吧，我们就30
然后呢，这个push back 30，3个30
之后呢我又push front 40是吧，也就是说我要重新把40也插到这个
头上去，那么我就在20前面要插入40，然后又push back 40
啊，我们看到说通过这样两个一系列的插入的操作呢，我们就构建好了
两个链表，分别是list1和list2，那么我们首先可以做的事呢就是去cout
对应的这两个链表，那么我们在这里头就使用到了这个
PrintList这样的一个函数模板,相应地去
匹配这个list1和list2这样两个
容器的这个类型，那么它的这个每一个类这个list中间的元素的类型呢都是 类A，我们自己定义的一个类型。
那么有了这样的一个输出之后，我们就会看到我们第一个输出的就是list1是吧，我们输出1，3，2，4，2
接着呢，我们输出list2,就分别是40，20，10，30，30，30和40
那么之后我们接着做的操作呢，我们会去使用list这个容器自身的sort函数
那么自身这个无参的sort函数呢它本身去做
就是从小到大排序这样的一个工作。因此呢我们，它作用在
就list2这样的一个容器上，所以呢我们在这一步cout
3的时候我们会看到 我们会对刚才这个序列来进行重排序
我们会得到10， 20，3个30以及两个40
啊，那么我们接着做的操作呢就是要让list2呢去pop出去第一个首元素。
因为我们再回忆一下，刚才这个类似的2经过sign函数之后，它的排序是：10
、 20 、三个30 、两个40。
是吧？那么要有了这样一个，呃， pop_front这样的一个 操作之后，那么第一个10呢实际上就会在列表当中呢被删除掉。
所以我们在cout<<"4这条语句的时候，我们会看到如果我们打印输出lst2,
那么它对应的值呢，就是20，30，30和两个40 。啊。
之后我们接着做，啊，接着做我们做的事儿是什么呢？我们 remove （2）。
remove 2 这个函数呢他作用在lst 1，那么lst 1呢，刚刚我们看到是
大家还记不记得list 1呢？lst 1是1 3 2 4
2，对吧？ 如果我没有记错的话。那么，这时候我们通过remove（2）
呢开始这样就是删除所有和 A2相等的元素。啊，那么在lst
1里面呢也就是说我们需要把2这个两个元素呢删除掉。
那么这时候如果我们cout>>"5，lst 1 的话呢我们会看到我们输出就是1、3、4。
之后呢我们接做，那我们接着作用在谁上呢？我们要 做回作用回到lst 2了，对吧？第二的lst 2这样的一个列表。
那么它呢我们需要做的事儿呢，是我们调用了Unique这样的一个成员函数。那么它会删除
所有和前一个元素相等的元素。比如说：我们会删掉具有相同值的元素，啊。
所以我们看到说，这三个30呢只能保留一个，而两个40 呢也只能保留一个。所以这
时候我们看到，如果我们cout>>“6， 啊，Printlist (lst2)的时候呢我们会看到我们只能输出20、30、40。
这样三个值。
那么有了这样两个新的lst 1 和lst 2之后我们接着做，我们可以把两个链表
merge在一起，啊，注意，我们是让merge这个函数作用在lst1
这样的一个链表上。而被Merge的对象呢是lst 2。
也就是说我们会将lst 2呢 放到list 1中间并且要清空lst 2。
所以通过这样的lst1.merge （lst 2)这样一个操作之后呢，我们会看到说
lst1就被扩充为了1、3、4、20 、30、40 也就是说我们把这个
链表放到了1、3、4后，而相应的lst2呢就变为了空。
之後呢，我还可以让lst1也就是我们现在这个lst1
让这个链表reverse一下，让它去 逆序排成新重置一下。那么这时候如果我们相应的去
cout9的话呢。你会看到实际上我们就会把刚才这个 序列呢由
最后呢又排到了首，啊，也就是说通过这样的reverse一下。
那么经过上述，那么经过上述一系列操作之后呢
那么，我们看到lst1呢实际上它包含的就是40 、 30 、20 、4、3、1这样一系列的元素。
而lst2呢，它就被清空了。
应该清空之后呢我们就要重新对lst2呢，进行了push_back。那我们重新插入了一些元素，插入了100、
200、300和400。
那么重新构建了lst1和lst2之後呢我们接着做了一些操作。
我们去定义了三个新的迭代器P1、P2、P3他们都是lst
a 这样的一个类型。那么这三个迭代器它都分别指向谁呢？
它指向了是find的这个算法本身 它所返回的相应的那个我们
查找的对应人数所在的迭代器。啊，我们看到说
我们在这里p1指向的就是我在lst1从开始拟定到n的中间
3这个元素所在的这个位置的迭代器。
而这个p2呢它指向的是lst2 这个链表当中从今开始到结束中间
200这个元素那么它所在的这个，嗯，迭代器。
以及p3呢指向的是400这个元素本身。
那么有了这样的一个p1、p2、p3迭代器的这个具体的
这个赋值之后呢，我们来做的操作呢就是我们要在lst1
这个链表上面呢去做splice。splice是谁呢？我们希望能够在p1
这样第一个参数所定义的位置之前
去插入p2 到p3
这样的两个迭代器所定义的这样一个区间的当中的内容，把这个内容呢插入进来。
同时要注意呢，要在 当这个p2到p3的这个内容它作用在lst2这样的链表上。
注意，我们要插入之後呢要在lst2当中去删除p2到p3
这段已经插入到p1当中内容的 插入到这个lst1当中内容的这样一个，嗯，操作。
那么我们看到说，注意，这个P2到p3呢是前毖后开的这么一个区间。
我们要做的事儿呢，p1因为它指向的是lst1
当中3这个元素所在的位置，啊。那么，
P2呢它指向的是lst2中间200，p3 指向的是400 这样相应的几个位置。
那么我们做了splice之後呢，我们要做个事儿，实际上就是在3这个元素的前面
去插入p2到 p3这一段内容。注意，它是不包含400的，
啊， 因为是后开这样的区间。
那么我们会看到我们要做的事儿实际上是我们在lst1里面
3这个位置之前
插入这段两个值，200、300、
然後是3和1。那么相应的，因为splice这个函数它会从
lst2当中删除掉已经插入到st1当中的内容。
所以lst2就会变成100和400。
所以我们看到我们通过这个lst1.splice这个操作之后呢，我们实际上如果
cout11的话呢你会看到，你输出的就是这个40
、30 、20 、4 然後200和300
是被splice进来的，然后是3和1。而相应的lst2呢，就变成了100和400.
。
所以这就是我们整个这个程序的对应的输出的结果。
那么最后呢，就是简单的介绍一下deque这个容器。
那么deque呢它实际上是一个双向的队列。
那么，我们在对于这个Deque来劲使用的时候呢，也要去引用相应的头文件。
那么大家要注意的就是，我们所有能够用在vector上面的操作呢它本身都是使用于deque。
此外呢，因为deque 它是双向队列，所以呢它还包含了这个
push_front和pop_front这样两个操作。比如说你可以是把
这个元素呢插入到容器的头部，以及呢去删除掉 头部的这个
