北京大学《C++程序设计》这门课将向你讲授C++程序设计有关的概念和语法，使你能够使用C++语言，以面向对象的方法编写可维护性、可扩充性好的，较大规模的程序。我们建议你在开始本课程之前已经熟悉了C语言和基本程设编写。这门课则将带你掌握C++语言中类、对象、运算符重载、继承、多态等面向对象的程序设计方法，以及模板、标准模板库STL等泛型程序设计的机制，体会和领悟面向对象程序设计方法和泛型程序设计方法的优势。
STL-概述（续）
Loading...
來自 Peking University 的課程
C++程序设计
626 個評分
從本節課中
标准模板库 STL-1
本模块将介绍C++的标准模板库（Standard Template Library，STL），这是泛型程序设计最成功的应用实例。STL是一些常用数据结构（如链表、可变长数组、排序二叉树）和算法（如排序、查找）的模板的集合。有了STL，你就不必编写大多的、常用的数据结构和算法。即便不想用面向对象的程序设计方法编程，学习STL也是大有裨益的。
與講師見面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
那个STR上面不同容器里面的那个迭代器，它的种类是不一样的。嗯，对于这个vector
和deque来说 它上面的迭代器都是随机访问迭代器，也就是说vector 和deque支持你给一个下标
它马上就能取到这个下标的人数，这种操作
list，还有这个关联容器，它们上面的迭代器都是双向迭代器，而不是随机访问迭代器
而不是随机访问迭代器，所以，嗯，这5种东西上面
都不支持随机访问，你没法
调用一个成员函数，说我要访问第二个元素，马上就拿到第二个元素，不行
你要访问第二个元素呢，在这5种容器上面，你都得自己写一段代码
嗯，从这个容器的头一个元素一直往后走，走到第二个元素。那至于容器适配器，
它上面根本就没有迭代器，因为容器适配器嘛，并不是说能访问中间的元素，能访问的都是位于什么站顶啊，队头的元素
它不能便利整个容器，除非把所有元素都删掉了
每个元素才能被访问到，所以这里根本不需要迭代器，因为能被访问的元素都是位于站顶、队头这样的位置的
那要注意了，有的算法，比方说sort，还有binary search
它需要通过随机访问迭代器，来访问容器中的元素，注意，这个排序和折半查找，我们知道
它需要在容器里面的各个元素之间作比较大范围跳跃
所以它需要随机访问迭代器的支持
那对于这样的算法来说，list和关联容器就不支持这些算法了
就是说，你不能用一个sort 去对一个list进行排序
当然，你更不能用它来对关联容器进行排序，因为关联容器已经排好序了
还有，你不能，嗯，用binary
search去在关联容器和list上面进行查找
因为，这两个算法它都要求随机访问迭代器的支持，而我们这些list，set/multiset,
map/multimap 上面的迭代器都是双向迭代器，而不是随机访问迭代器
所以这些容器，list以及关联容器就不支持sort和binary search。那这个vector上面的迭代器它是随机访问迭代器
那我们遍历vector就可以用下面几种方法来做，对于deque也是这样的 这条语句定义了一个vector V
这个V呢是个整型数组，一开始它里面有100个元素，这是它构造函数参数的含义 然后我们就可以
遍历这个V，怎么遍历呢，第一中方式，我们可以通过下标随机访问
就是我们可以通过中括号，这个被重载的运算符，来访问V里面的第i个元素
这个v.size 代表v里面的元素个数 v[i]直接就是V里面下标为i的那个元素了
那我们还可以定义一个常量迭代器，ii，让这个ii从v.begin一直走到v.end
然后把这个ii所指向的元素突出
注意这里我们可以用不等号比较两个迭代器，那由于在vector
上面的迭代器 是随机访问迭代器，那两个随机访问迭代器是可以用小于号进行比较的
所以这个循环我们也可以这样写，在这里用小于号也是没有我问题的
而且由于随机访问迭代器，你可以给它加一个整数
所以我们在遍历vector的时候也可以
隔一个输出，那就是这样ii等于ii加2
或者你写ii加等于2都可以 嗯，让它
这样这个循环就可以间隔一个的把v里面的元素给它输出出来了
加一个整数的操作是随机访问迭代器可以做的，但是
双向迭代器就不能做这种操作 那对于list
来说，它上面的迭代器是双向迭代器，不是随机访问迭代器
那我们要遍历list，可以怎么做呢。
list<int>v 这是一个list，刚开始它是空的
那我们要遍历这个list，我们可以定义一个list 上面的迭代器，它叫ii
ii从begin开始，往后走，一直走到end
但这时候你要判断它有没有到达end呢，你就用不等于
你不能在这里用小于号，这是不行的
为什么，因为list上面的迭代器是双向迭代器
双向迭代器是不能用小于号去比较的，这中写法就是错误的
这个位置你这能写不等于，而且这个双向迭代器
不但不支持小于，而且这个list 它也没有中括号成员函数，我们知道
这个list还有关联容器，它不支持随机访问，它没有中括号这种成员函数
所以对于一个list来说，你想要用这种办法去访问它下标为i的那个元素
也是不行的，编译会出错的，你要访问下第i个的元素
你只能自己写一段代码，让一个迭代器从begin开始一直往后走i步，才可以 下面我们来介绍下什么叫算法
前面说了算法就是一个个函数模板，大部分是在algorithm中定义的
STL中提供能在各种容器中通用的算法，比如查找，排序等等
算法是通过迭代器来操作或者访问容器中的元素的
许多算法对容器进行操作，并不见得对整个容器进行操作
它可以只对容器中的某一段，就是中间一个局部区间来进行操作
所以这些算法往往需要两个参数，这两个参数用来指明它所要操作的容器中间的一段
那这两个参数一个就是那一段的起始元素的迭代器
另外一个就是终止元素的，后面一个位置的迭代器
排序查找都是这样，这个后面我们还会细说
然后有的算法会返回一个迭代器
比如说find这个算法，在容器中查找一个元素
并返回一个指向该元素的迭代器 补充一点，像排序和查找算法，作用与某个容器，它并不一定要把整容器排序
或者说一定要在整个容器里进行查找，它可以只把容器中的一小段进行排序
也可以只在容器中的一小段进行查找
然后这个算法可以处理容器
也可以处理普通数组，算法能工作在容器上，也能工作在普通数组上
让我们来看一个算法，find 以此为例，让大家有一个基本了解，算法是什么样的
find 是顺序查找 它是一个函数模板，它的模板的定义就是这样的
那不同的编译器的头文件所列出来的find 模板写法会略有不同
这里，我找出来find的模板的声明
注意，它是一个模板，它有两个类型参数，init和t，这个init实际暗示你这个类型参数是一个迭代器
it代表迭代器嘛 然后这里有first
和last，实际上就指明了你要查找的区间 因为find是用来做顺序查找的
那这个val呢，就代表你要查找的值
然后注意一点，就是说算法是有一定功能的
比如说find，通常来说，它就是实现顺序查找的功能
但它只是一个模板，find并不意味着只能实现顺序查找的功能
你用find这个模板能做什么事情，实际上是取决于你的想象力的
并不局限与顺序查找，这个我们后面还会看到类似的例子 总而言之，对于find这个模板来说
它要查找的区间是first
和last 那注意，这区间是左闭右开的区间
就是这个区间里的第一个元素是由first所指向的，这个区间里的最后一个元素是由last所指向的 但是last
所指向的那个元素，并不在查找范围内，左闭右开的区间嘛
然后find是在fist和last区间查找等于val的这个元素
什么叫等于，是用等等号来判断是否相等
然后，这个函数的返回值是一个迭代器，那如果找到了，返回值实际就是一个迭代器
这个迭代器指向被找到的元素
那如果找不到呢，返回值当然也是一个迭代器，而且这个迭代器就等于last
所以我们在调用find的时候，通过返回值 可以判断是不是找到了
具体的办法就是看看返回值是不是等于last，如果等于last就说明找不到，不等于last
就说明找到了。那这顺序查找的时间复杂度是什么样的呢，是ON的
因为它并不要求查找的区间first和last是有序的，那它查找的过程就是从头一直走到尾，所以复杂度就是ON 我们看一个find例子，include
algorithm 这有一个array，是一个数组，普通数组也可以算容器 这里有个vector<int>，动态数组V，然后我们往V里面放了1，2，3，4，然后在V上面定义了迭代器，
vector<int>迭代器p，然后调用find(v.begin(),v.end(),3)
这个是干嘛？就是在整个容器，整个V容器上面去查找3这个元素
呃，然后下面这条语句就判断是不是找到了。
那在1,2,3,4里面找3呢当然是能够
找得到的，对吧？所以说这个时候，呃，P就会指向被找到的那个元素，也就是3
那你输出*p的话，当然输出的结果就是3。
啊，那我们再来看看find这边用到的这个，这个区间
它查找的区间v.begin，v.end，它是左闭右开的，也就是说v.begin
是位于查找区间之内，但是这个呢，v.end不位于查找区间
之内，这是很合理的对吧？因为v.end本来就v里面最后一个元素的后面的那个位子。
也就是说v.end实际上没指向任何有效的元素，那在 find在进行查找的时候，v.end并不位于查找范围之内也就是很合理的。
那实际山在STL的各种算法里面 只要是提到了这个区间，啊这个区间都是左闭右开的。
再看下面，呃 p等于find v.begin v.end
9，啊，就在V里面去查找9这个元素，v里面有什么啊？是1,2,3,4，那当然就找不到对吧
所以我们看，看到，如果v等于，啊，如果P等于v.end那就说明找不到，这个输出not
found，那当然确实会输出not found 找不到9,。然后p等于find v.begin加1
然后v.end减2，啊，就是在v.begin加1到v.end减2这个区间里面去查找
元素1，但是要注意的v.end减2这个，元素实际上并不在查找范围之内。
那我们看到整个容器是1,2,3,4，那v.
，v.begin加1是什么啊？就是2对吧？那v.end减2是什么呢
呃，这个4是v.end减1，3是v.end减2，啊所以v.end减2是3
但是由于v.end减2实际上并不位于查找区间范围之内
也就是说查找区间2,3是个左闭右开的，但真正有效的元素实际上就只有一个2
所以，你在这里面去，嗯，进行查找1的话，啊，实际上是找不到的。
那找不到的话，这个时候P的值会是什么呢？我们说
p的值它会等于这个查找区间的终点，也就是说p的值是 等于一个迭代器它指向什么？指向这个3
那p当然就不等于end了，所以你输出*p的时候呢就会输出3
呃因为这个时候查找区间的终点实际上就是这个，这个3了。
现在再看int*pp等于find array array加4, 20
啊，这个时候我们在一个普通数组里面也能进行，用find进行查找 这个时候数组的名字就是迭代器，因为数组的名字就是int
*array这个指针 呃，在这个容器里面进行查找，嗯然后
查找区间好像是从array到array加4，array加4并不位于
查找范围内，在这里面查找20，呃，然后呢，我们就
根据查找的结果输出这个*pp，啊输出的结果呢就是这个
20，因为在这个array里面能找到20，啊，那么array定义的它里面是有20的
那我们知道在这个STL里面啊，这个关联容器内部的元素是从小到大排序的。
然后呢有些算法吧它要求它操作的区间是从小到大排序的，这类算法我们称之为“有序区间算法”。
比如说binary_search折半查找，它就要求查找的那个区间 必须是从小到大排好序的，然后才能进行二分查找
然后呢有些算法它会对区间进行从小到大排序，这称为“排序算法”
比如sort,它就能够把处理的那个区间变成从小到大排好序。
还有一些其它算法也会用到这个什么大小的这个这个概念
但但要注意了我这里所说的从小到大可不见得就是什么1一定是小于2这么简单
这个大和小的定义程序员可以自己去设定的
比方说程序员可以规定，哎我在这个呃，呃，容器里面
从小到，这容器里虽然放的都是整数，但我这个从小到大的意思是
按照个位数从小到大排序，也就是说这两个整数谁的个位数小谁就算小 这就叫做自定义大小的这个概念
呃也就是说前面这里说的所有的从小到大，从小到大啊，它的具体的含义都是可以发生变化的
对于两个整数你也可以说绝对值大的就算是小，绝对值小的就算是大，你也可以这么定义，没有问题的。
但是呢在缺省的情况下，就是你没有对这个大小给出任何
自己定义的情况下，在缺省的情况下，那么下面三个说法是等价的
呃，如果我们说x比y小，这个说法就等价于表达式x小于y为真
这也等价于y比x大。哦，这三个说法是等价的。
在缺省的你没有自己定义大小的概念的这个情况下
以下三个表达，以下三个说法等价，然后
在STL里面x和y相等也不见得就是我们那么简单理解的相等的概念。
啊，就有的时候x和y相等，它等价于表达式x等等y为真
在什么情况下，嗯，是这样子的呢？
比如说我们在没有经过排序的区间上进行的算法，比如顺序查找find，我们说在一个区间里面
查找某一个元素，那你要查找的那个，呃查找某一个值，那你要查找那个元素肯定要等于这个值，对吧
那这个时候这个等于就是用等等这个运算符来进行判断的
但有的时候呢x和y相等
它就不再等价与上面的这个，呃，x等等y为真了，它跟这个等等
这个，呃，运算没有关系 有的时候x和y相等，它等价于下面这个描述
就是x小于y和y小于x同时为假，啊
注意这里的小于呢，它还未必就是小于号的那个意义，在这里的小于
也是可以自定义的，反正你在自定义的，就是说有些情况下你自定义了
小于的含义，然后在然后呢x和y相等，它就变成x如果
小于y，和y小于y x同时都不成立，那我们就认为x和y是相等的
哪怕x等等y这个表达式实际上它的访问值是false，我们也认为
x和y是相等的，在什么情况下会是这样呢？啊就是
对有序区间上，比如说birary_search来说 x和y相等，就是上述的这个含义。
还有对于关联容器自身的成员函数find来说，x和y相等，也是这里所说的含义。
呃，那关联容器就是用来查找的，查找速度快，但是你不能用find算法
或者是什么其他的birary_search算法去查找关联容器，关联容器它自身带有成员函数find 可以用来进行查找。
那下面我们就看一个这个关于这个“相等”的概念 的这个这个演示，啊，我们这里有个classA
呃，它里面有成员变量v,然后呢在这里我们
呃，重载了小于运算符，规定了，呃，两个classA
对象比大小的规则，在这运算符里面呢我们先输出了待比较的两个元素的这个
呃，这v的值，然后返回false,返回false意味着什么啊
意味着任何两个classA的对象，一个都不会小于另外一个
任意两个classA的对象x,y，x小于y总是不成立的，y小于x也总是不成立的。
然后我们也定义了一个，一个等等号，呃，它它用来判断两个classA的对象是否相等
呃，呃那是否相等的这个规则比较传统，啊，就是两个的V相等，它就是相等了。
好了，我们在定义了这种小于和等于这种规则的前提下，我们看看用birary_search会发生什么事情
注意，再强调一遍，这里的小于被定义成任何两个classA的对象
一个都不会小于另外一个，好我们在main里面，啊
定义了这样一个classA的数组，呃它们是A1，A2，A3，A4，A5
然后我们用birary_search在这个数组里面去查找A9这个元素
是二分查找 那你想是不是应该能找得到呢？这是，数组里面是1,2,3,4,5,你要查找的是A9，当然应该找不到，对吧
也就是说，birary_search这个函数调用它的返回值应该是0，是false才对。
但实际上的结果呢却是毁三观的，呃它的返回值是1 它告诉你在A1到A5这里面找到了A9
为什么会是这样的结果呢？我们看到输出结果前面还有，前面这四行
也就是说，我们看到在这个程序运行的过程中
呃，程序运行的过程中呢这个，呃，等等号并没有
被调用，这个小于号被多次调用
那也就是说，呃，这个birary_search在执行的过程中，它判断呃这个
数组里面有没有哪一个元素的值跟A9相等，它用的不是等等号 用的是小于号
这就是我们前面所说的那个相等的概念了，就是说如果x小于y不成立，y小于x也不成立
那就认为x和y相等 根据x等等y没有关系，这就是birary_search工作的这个原理。
所以我们看到，呃，birary_search，birary_search首先
看看3小于9是不是成立？结果是不成立，不成立的话
birary_search就应该，就认为我应该在，呃3前面那一半去找，所以它又去找
2小于9是不是成立？又不成立，那它认为应该再到前面一半去找，于是就
判断1小于9是不是成立，还是不成立，那这时候已经不能再向前啦，已经没有啦
所以，birary_search就判断9小于1是不是成立？也不成立，好了，那1小于9不成立，9小于1也不成立
那birary_search就认为1和9是相等的，所以它就认为，呃找到了A9，于此输出一个它的返回值就是1
看上去是不是很奇怪，但它就是这么工作的。
