北京大学《C++程序设计》这门课将向你讲授C++程序设计有关的概念和语法，使你能够使用C++语言，以面向对象的方法编写可维护性、可扩充性好的，较大规模的程序。我们建议你在开始本课程之前已经熟悉了C语言和基本程设编写。这门课则将带你掌握C++语言中类、对象、运算符重载、继承、多态等面向对象的程序设计方法，以及模板、标准模板库STL等泛型程序设计的机制，体会和领悟面向对象程序设计方法和泛型程序设计方法的优势。
算法
Loading...
来自 Peking University 的课程
C++程序设计
659 个评分
从本节课中
标准模板库 STL-2
本模块将继续介绍C++的标准模板库（Standard Template Library，STL），这是泛型程序设计最成功的应用实例。STL是一些常用数据结构（如链表、可变长数组、排序二叉树）和算法（如排序、查找）的模板的集合。有了STL，你就不必编写大多的、常用的数据结构和算法。即便不想用面向对象的程序设计方法编程，学习STL也是大有裨益的。
与讲师见面
Jiaying Liu 刘家瑛, Ph.D.Associate Professor
Institute of Computer Science & Technology
郭 炜讲师
北京大学信息科学技术学院教学所
大家好，在这一小节中呢，我们来介绍一下STL算法，那么这次课呢，会比较不一样，是由我和郭老师一起来讲。
因为这个STL算法，它比较杂，又比较多，讲起来特别枯燥，
那我们要一个人讲的话，就我们讲得也累，同学们可能听得也累。所以我们就变化一下形式，两个人一块讲。
这样挺好。那么STL本身的分类呢，郭老师，这七类应该是您分的吧？
对，我也参考一些其它书吧，然后也有一些自己的观点吧，这就分了七类，其实你爱怎么分，我觉得也都无所谓了。
那这个算法的话呢，可以有这种不变序列算法和变值算法。
还有删除算法，变序算法，排序算法。以及这种有序区间算法和数值算法。
嗯，大概就这七类把。
那么算法本身呢，我们在这个实现的时候呢，这种一般来说都是重载了两个版本。
那么通常可以用这个 “==”等等来判断元素是否相同，当然也可以用“<"，主要来用“<"来判断这个大小。
对，那还有一个版本呢，它就会多出一个类型参数，这个”Pred“。
然后这个模板的函数形参部分就会多出一个”Pred“类型的参数op， 那么这样的算法啊在
执行的过程中，它需要比较两个元素x，y大小的时候，它就会去计算表达式"op(x,y)"，看这个表达式的返回值。
如果为true的话，那么这个算法就会认为x是小于y的，
那么如果我们举个例子的话呢，对于这个
min_element的这个算法的话，它实际上就会对应有这样的两个版本， 那么就会有，除了有这个
first和last作为，两个迭代器作为这个参数之外呢，
还会有，存在第二种，就是会多出这样的一个，刚才郭老师提到的，
一个表达式来进行判断。对，这个第一个版本嘛，它就是用这个“<"来比较大小的。
因为它没有让你自定义比较大小的方式，而第二个版本呢，就用这个op
去定义比较大小的办法。那你真正调用min_element的时候呢，这个实参，这个op，你可以给一个函数的名字，
也可以给一个函数对象，都是可以的。也就是说这个函数如果是你自己定义的话，那这个大小就可以
变得更为丰富多样化了。对对，就不见得是我们传统意义上的数学上的大或者小了。
好，那么后面可以继续看， 那么对于第一类这种不变序列算法的话呢，
它主要就是不会去修改算法本身所作用的容器或者对象，
那么它通常呢，适用于这种顺序容器，或者我们讲到的那种关联容器，就是所谓第一类容器。
那么它的时间复杂度呢，通常都是O(n)量级的。对，因为它们做的时候，一般都会从头到尾，便利一下
整个容器，所以它一般就是O(n)级的。那么对于这个不变序列
算法的话呢，它主要包含了以下这个表格中间的一系列算法，
难道我们都要念一遍吗？念一遍，念一遍，来，来，请。那么第一个的话呢，就是那个min，
min的话，它主要用来去求这两个对象中间较小的一个
算法。那么对应的话呢，还有一类呢，叫做min_element,
那么这个算法本身的话，注意是第三个哦，那么它呢，是用来去求某个区间中间最小的值。
对，这里标注出可定义，自定义比较器的， 一般就是有两个版本，一个是用“<"或者“==”判断相等
或者是小于，另外一个就自己去定义一个什么规则去
比较相等或者大小。这个min和max这两个 东西是特别常用的。
像这种min_element，max_element嘛，你自己要写的话，也就是两行的事，就是一个循环，对吧，那你要能记得住的话，
也总比写两行要稍微好点吧。
还有这个for_each嘛，就是对区间中的每一个元素都做某种操作，这个for_each它实际上有两个版本。
一个是不变序列了，它不会改变
容器里面的对象。另外一个是变化序列了，它或者是变值的，它会改变容器里面的
容器的内容。对，那个我们在后面再说。
那么下面的话呢，在不变序列算法中间呢，还有这个count，那么它主要就是用来去
计算区间中间等于某个具体，就是你count的那个元素的
个数，然后同时的话，你还可以按照某种条件去count这个个数。
某种条件是count_if，这个count就是用 “==”。find，find特别常用了。
find其实您之前不都讲过了吗？它就是顺序查找。因为它太重要了，所以再讲一遍也不嫌累。哎，这个find我们标红了哦，说明很重要哦。
它在区间中查找等于某值的元素，这个等于呢，就是"=="。
所以呢，那你也可以find_if根据某些条件来去查找具体某一个元素。对，那就更灵活一些。
然后，这个，这个find_end查找最后一个位置，这个好像不太常用啊。
find_first_of也不是那么常用。这个我们在string里面有提到过。它有一个成员函数，叫find_first_of，对，嗯。
然后就是这个adjacent_find，这个就更，我好像从来没用过。
对，我也没有用过，虽然我写的程序也不少了啊。
反正STL里面有很多东西吧，你要是不嫌记着累，你都能记住，那用起来也还是蛮方便的。
这些，有些很简单的函数，你自己写两行就能写得出来的，你要懒得去记，也无所谓。
对，adjacent_find就是用来去发现第一次出现的这种连续两个相等的元素的位置。对。
好，下面。好，那接着。
那么对于不变序列算法呢，还有这种search，它主要就是说 在一个区间中间，去查找另外一个区间当中第一次出现的这个位置。
嗯，这就有点像那个string里面的什么 find_first_of去找
就是在一个字符串里面找另外一个子串里面的任何一个字母第一次出现的地方。对，这两个 会比较类似，看起来。然后同时的话，还可以search_n，也就是说你可以去在这个区间当中查找出现某个值连续n个元素。
equal就是判断两个区间是不是一模一样啊， 那么这个mismatch的话呢，就是逐个去比较
两个区间中间的这个元素，那么返回的是第一次不相等的那个元素的位置。
返回一个迭代器，是吧？，对对，是，啊，这个 lexcographical_compare，就是按字典序比较两个区间的大小。这两个大小什么，你都可以
自己去定义了。就是lexcographical。呵，这是最复杂的一个STL算法的名字了。
那么我们具体来看的话，就是说，对于find这样的一个算法的话，它实际上就是说
是在我们定义好这个区间当中，去寻找这个相应
对应我们去查找这个value的这样一个值，然后返回的是一个相应的这个迭代器。
然后如果没有找到的话呢，就返回的是这个last。
find_if呢，它是查找符合某种条件的这个元素。
条件就用这个pr来表示了，pr(*i)==true。那这个(*i)这个元素就是符合要求的。
那就返回这个i。第二遍录果然比第一遍录，感觉机器差了很多啊。对啊，
是啊，好，那我们再。再打打鸡血，是吧。这个那么对于for_each这样的一个操作的话呢，
它实际上主要就是说，在这个区间当中的每个元素e，都去执行这个f(e)这样的一个你定义好的一个操作。
但注意就是说f(e)本身，它是不会去改变这个e的，也就是说，对于这种
不变序列算法，是吧，第一类是，它本身是不会去修改任何容器当中的这个元素值的。
它只会去计算，按照你定义好这个某一个操作，这个f来去相应计算一个值。是吧？是的。
对，算出一个新的值来。反正做某种操作吧，但是这个操作不会改变e。
count就是用来计算这个区间里面有多少个元素等于这个值value。然后这个
等于是用"=="号来判断的，那count_if呢，就是判断
这个first,last区间里面有多少个元素，满足某种条件，这个
条件，就是pr(e)==true。这个e指的就是那个元素
然后那么，刚才提到就是说，有讲了max，min是比较常用的两类这个
两个算法啊。除此之外的话，还有min_element和max_element也是非常常用的。也是比较好用的。
那么对于这个min_element的话呢，它主要就是说在这个区间当中去 返回这个最小元素的这个迭代器。注意它这是返回的是一个区间当中的最小元素。
min是返回两个对象比较的这个元素。对，这个 min_element呢，这个版本是用"<"
做比较器的。然后什么叫最小呢？ 最小指的是没有元素比它小。
但注意，不是说它比任何元素都小。对对对对 对。这个东西很绕口。是，所以我把它变红了啊，下面的程序能够看到这个例子。
因为就是说，即便a不等于b的话，a<b，和b<a也有可能
同时都不成立。就取决于你这个"<"是怎么编写的嘛。因为"<"有可能被重载， 那max_element也类似啊，它找最大的元素。
最大，什么叫最大啊？就是它不比任何其它元素都小，那它就叫最大。
那么它也是可以用这个"<"来进行作比较器的。它确实，这个版本就是用"<"作比较器的。
那我们来具体看一个例子。（怪异的例子啊），那么在这个例子当中的话呢，这个
我定义好了一个类A，然后呢，它中间包含了一个
这个int型的成员变量，然后我们还定义了一个构造函数，让它来初始化，用这个参数i来去初始化这个n。
然后大家来具体看看郭老师这个很怪异的operator<。
对，这个"<"嘛， 它确实比较独特，精神病，它每次被
调用都会输出一个called，但是它规定只有3<7，
这是true的，所有其它情况，
a1都不会小于a2。只有a1.n==3.a2.n==7的时候，这个小于号才成立。也就是说
在这个"<"的定义下面，任何两个class A的对象比大小，
返回都是false，除非，第一个是3，第二个是7。
7,啊只有3＜7是成立的。那现在我们在这个数组a[ ]里面， 去求最小
元素，求这个最大元素，那我们先看看，这个求最小元素。这个
函数被调用被执行的时候会有哪些输出啊， 它输出的结果是啊，4个＜called，然后输出一个3.
这是为什么呢？是不是很奇怪？对呀，因为明明这个
最小的这个数组里面明明有1和2的存在，为什么输出的居然是3呢？
就是我每次讲到这个，呵呵，在课堂里讲到这段，这段代码的时候都感觉就在台上很囧，
嗯，好啦，这个问题是这样的，就是你想一下，如果你写这个min_element,
你怎么写呢？你只能顺序遍历整个数组对吧，那你肯定要有一个，一开始要假设一个最小值，
那那很自然的你会假设，第一个3是最小值，就是一开始我们假设3最小，对吧。
接下来我们就会拿3跟其他的去比较了，比如说，3跟5比较
这个时候呢，min_element是怎么比较的呢？它是去看5＜3的值是不是为真，
如果5＜3为真的话，那么5就是这个
比3更小了。那这个时候最小值就要被更新成5了。当然在这个例子里面
显然不是，对呀，所以3现在依然还是最小的。然后又比较7＜3，
啊还是假，所以3还是最小。然后2＜3，1＜3，全都是假， 啊所以经过四次比较以后，这个3依然是最小的。
就被记下来了，3是最小值。那刘老师你来说说max的情况。
那么在max这种情况下的话呢，我们是去比较这个 呃首先是应该是去比较
3和5是吧。对，先假设3是最大值，对，然后假设3是最大值，
然后去比较3和5.然后这时候你会发现说呢这个确实是满足这个
3＜5不成立，然后这时候就会被
3依然最大，替换成7和3进行比较。然后因为我们在刚刚的这个operate小于号里面
定义说当满足一个是3一个是7的时候，它就自动会变成是TRUE了。
所以那么这个时候的话呢，我们就会认为说这个 呃更大的这个值是7，然后这个7的话呢会进一步去跟这个2比较，
然后它也是false，那么这个时候就会7会去跟1比较，然后所以呢最后返回的最大值就是7了。
啊，对。那就是min 和max它工作的这个过程，
呃就是这样的。有点怪是吧。但是我觉得可能知道这个还是有必要吧，所以就讲啦，就这样了啊。
OK,那我们先进一步， 再看变值算法，那么第二类呢就是这个所谓的变值算法，那么这个变值算法的话呢，它实际上刚刚
对应第一类呢我们刚刚说到它不会去修改就是这个算法作用在这个容器上的话呢它不会去修改任何容器中间的元素，
但是变值算法的话呢它就会去修改这个原区间或者是目标区间中间元素的值。
然后注意这个有一个区间的值如果被修改的话，这个区间它不能是属于关联容器的。
那为什么呢？ 啊考我吧。啊你知道吧，那你说吧。对呀，这个因为本身关联容器大家也应该知道
说它实际上是一个具有排序好的这样的一个容器，那如果你
直接就通过这种变值算法去进行修改的话，那么这个容器当中的这个所有的这个排序好的内容就被
彻底打破了，如何你在做其他的操作的话，有序性破坏了啊，如果你去做其他操作的话呢，实际上就是都是，可能就会出现
不一样跟预期的结果不一样的值。你要查找可能就找不到了。
嗯，所以变值算法不能够使得关联容器上面的元素被改变。
那变值算法有这个几个啊，有这个for_each,
它用来对区间中的每一个元素都做某种操作，那这个操作它是
可以改变这个元素的值的。那这个版本跟上一个版本就在于参数 呃，
那个参数是一个，可以是一个函数或者函数对象，然后那个函数对象或者函数的那个参数它一个是const,一个不是const。
说起来挺罗嗦的，大家自己去查查吧。呵呵，然后呢，第二个这个算法的话就是copy，
copy的话呢我们通常直观上根据这个词也能想到，它就是去完成一个复制其中
一段区间到另外一块儿的这样的一个操作，那其实copy本身呢它还有一些
呃我们会在后续的例子当中看到它有一些独特之处，我们还可以通过一些其他的方式，通过COPY来实现一些
其他的这个功能，对，就是X+里面的算法吧，你看名字好像觉得它应该只能干这个事情，你说COPY你就觉得它
只能是干copy的事情，其实不是的，它里面只不过是一个代码的形式，你用 这个模板能做什么是取决于你的想象力的。
我们后面会看到COPY的习惯用法。
还有这个copy_backward,它也是复制一个区间到别处。但是它跟COPY的差别在于
它的 在目标区间是从后往前被修改的，就是拷贝的时候是从后面到前面拷贝的。
copy呢是从前面到后面拷贝的。
那郭老师你要不给大家介绍一下说为什么会考虑从后往前这种操作呢？ 我不刚刚教你了吗，你说一下。
呵呵呵呵。挖坑，我想给郭老师挖坑没挖住是吧？ 那么郭老师刚才在我们在第一遍录的时候，
郭老师就提到这个本身这个函数这个算法呢 它呢实际上主要是当你它主要考虑说两个这个区间本身有重叠的时候，
那么如果你都是从前往后去来进行这个拷贝的话呢，
那么可能就会出现后面的这个内容在没有拷贝之前就已经被这个覆盖掉了。
对，就重叠部分的内容还没有被拷贝到目标区间就已经被覆盖掉了。
所以呢，那么有了这个copy_backward之后的话它就是它实现的实际上是从后往前拷贝。对，就能解决这个问题。
嗯，好。然后还有这个transform它是把一个区间的元素变形以后拷贝到另外一个区间，那也就是说
你用一个区间的元素作为函数的参数算出一个什么新的值然后 把它新的值弄到另外一个区间去，基本上就是这个意思。
那么除此之外的话呢还有一系列变值算法， 其中就包括这种swap_ranges，那么它主要是用来去直接交换两个区间之间的内容的。
啊那念swap啊，我一直念swap.
到底是什么呀？swap,呵呵，好啦，那就swap吧。
还有，还有这个fill,fill是用某个值填充某个区间。然后你也可以fill_n，
就是刚开始用某个值去填充区间，那么这时候的话可以直接去替换区间中的n个元素。
generate就用某个操作的结果填充区间，它就填充的办法可以更复杂一些啦。对，它是一个操作啊。
然后完了之后的话呢，就replace的话，就是将这个区间中的某个值替换为另外一个值。
replace_if 就是把符合某种条件的值换成另外一个值。
然后还有这个replace_copy，也就是说我们把一个区间拷贝到另外一个区间的时候，
那么拷贝时候的这个值要替换成一个新值拷贝过去。就是不是原模原样的拷贝啦， 那这个跟replace_if 感觉好像蛮类似的啊。
呃replace_if 是替换一个区间里面的元素，
replace_copy是把一个区间的元素拷贝到另外一个区间，考过去的时候 还要做一些操作。replace_copy它不会改变原区间的内容。哦。
然后这个replace_copy_if 就是把一个区间里面
符合某种条件的那个值拷贝到另外一个区间。那拷贝过去
的又不是原有的东西，而是把原有的东西经过某个计算变形以后， 变成新的值。我觉得后面这几个做法实在都，
确实很少用啦，还不如自己写呢，你自己写也就是两三行的事嘛，去记它还累的半死。
OK。那这个transform的话呢，本身这个操作呢，
这个算法呢它实际上就是说，对这个我们定义好这个区间当中的每一个迭代器，都会相应的去执行这个
我们定义好的uop这样的一个操作。然后并且把这个结果呢就依次放在这个从x开始的这个地方。
嗯，对啊。然后还要求这个原区间是不会发生变化的啊，
它返回值也是一个迭代器，就是目标区间被考过去的最后一个元素的那个，后面的那个
那个位置，然后x和first可以相等。就是它的原区间和目标区间嘛，它可以重叠， 就是这个意思。嗯。
那我们来具体看这个关于这个变值算法本身的一系列的这个，啊对对对，例子。还有包括clactstorm.
这里面有一个ClessThen9,它存在了一个这个圆括号，这个函数对象类。
它实际上就规定了一种条件，这个条件就是 返回＜9的值，对，看这个n是不是＜9.如果是的话就返回true。
那完了之后呢还定义了几个这个，呃全局函数。
对对，呃。一个是outputSquare，主要就是用来去计算对应这个value去求这个
平方的这个值。把平方值给它输出出来。然后还有这个calculateCube,
cube还是cube?cube吧。哦，OK。然后呢它主要就是去计算这个立方的这个值。然后它就返回立方，立方的值。
然后在main里面，这个好长啊，对啊。呃。
接着读，这个这个a1里面有1,2,3,4，5,6,7,8,9,10啊，a2看上去没有什么顺序可言。
然后这个呢就把a1的内容全部搞到v里面去了。定义好了一个vector，
对，然后下面这个东西好古怪啊，太古怪了，你来说。这是什么东西啊？ 这个我也没有看懂耶。呵呵，不会吧你装的。
这主要是郭老师挖坑后面具体讲这个copy这个
具有想象力的这个算法。这个东西吧，ostream_iterator是X1里面自己定义的一个内模板啦。
然后，你就知道它叫ostream_iterator就行了啊。然后把这个内模板实际化，啊
整型常数把它实际化，它的意思就是说以后你要通过这个ostream_iterator<int>去输出的东西都是
都是这个int类型的。好，这个，这个我们现在就定义了一个ostream_iterator<int>这种类型
的对象，它的名字叫做output。然后我们初始化这个对象的时候呢，给了两个参数，一个是cout，
一个是这个空格字符串。那就意味着以后我们把什么东西交给output的时候，
都会出现在 都会等价于交给cout，输出到屏幕上。而且被输出的东西，
都是一个个的整数。而且每输出完一个整数，后面都要加一个空格。
这句话就是这个意思。具体怎么实现呢？我们等会再看。
啊，下面这个东西。然后就是对应这个random_shuffle，这个算法实际上应该
不算是在这个变值算法。它叫变序算法。对。然后它主要是用来这个
随机的这个，打乱一下这个，我们刚看到对应的这个vector v中间的值。
对，这个，这个东西特别好使。因为有时候你经常会需要随机打乱一个数组，比如你写一个打牌的程序什么的。
你要随机给大家发牌，你就会把所有的牌先random_shuffle一下，对吧，这个真的特别好使。这个是伪随机吧？
当然是伪随机了，计算机不能实现真正的随机啊。然后呢，
完了之后呢，我们就让它这个cout一下，我们就可以看到说这个
我们先去看输出的结果吗？对，对对，就是这个编号为1的这个 这个输出啊。它是5 4 1
3。啊，那这块，当然你每次 （因为它是随机的嘛），每次都不一样，接下来就是问题的重点，就是这个copy
copy我们前面说到它是用来把一个区间的内容拷贝到另外一个区间里面的。
现在我们执行的这个东西，这个output它好像不是一个容器啊。它确实不是一个容 器，它也不会是一个什么区间的开始位置，但是我们确实就可以这样用copy。
然后copy以后，输出的结果，这是会导致输出的哦。输出的结果，是什么东西呢？
啊，这个输出结果实际上就是这个，刚才这个随机的结果被输出了，就是在这条copy语句里面导致它输出了。
对，你会发现，1和2之间没有任何其它的这个直接输出的语句。
通过copy来实现的。对，就是通过copy来实现这个输出的。然后我们看到输出的每一项都是整数，然后
输出的每一项后面都被加了一个空格，当然这个2后面也是有空格的啊。这也就是copy所做的事情。它为什么能做这个事情呢？
这个我们一会再讲，卖个关子。好。
接下来这个干嘛了？接下来这个copy实际上就是执行了一个copy的工作。
啊，对。它是把a2的内容拷贝到v里面去。啊，但这时候要提醒大家
一下啊，这个copy操作，它要求这个目标区间的这个位置，它本身有足够的空间。
就是比如说，你在这里copy了SIZE这个元素过去，那么在目标区间里面v.begin开始往后的地方，它应该有
至少有SIZE这么多个元素的空间。要不然就会怎么样啊？要不然就会相当于数组越界，就会出错了。
就是事先你要为目标区间已经准备好了空间，你才能拷，没有空间你是不能拷的。就是说这个事情，主要是要程序员
本身来保证的。对，是的啊。好了。然后接着我们应该把这个a2整个copy给了这个v之后的话呢，
那么我们就可以相应地在这个v上进一步做操作。对。我们就
进一步去cout这个，第二行输出的什么呢？输出的实际上是这个
count。我们在这个v之间去count 8。
出现了这个8这个元素。有几个？对，然后呢，这时候的话，我们会看到，因为现在这个
v变成了是a2这个数组。然后这时候你会发现说对于a2这个数组呢，出现了两次8。
对啊。所以这时候我们count一下的话，就可以对应输出就是2。然后同时的话，
你也可以count_if，也就是说我们按照某一个条件限制下去count这个相应的值。
那么我们对应的话呢，就是我们刚才定义好的这个CLess Then9这样的一个类。
这是个函数还是个类？嗯， 这个是个对象，（哦，这是个对象）它是个函数对象。CLess
Then9是一个 我比较喜欢中英结合啊，你就会CLess Then Nine，哎哟，高大上。我是CLess Then9。
好吧，这个CLess Then9吧，是一个类的名字，对吧。那 它后面加了一个圆括号，就成了一个对象的名字了。这个对象呢，它没有名称。
那这个CLess Then9这个对象是怎么起作用的呢？ 就是说count_if，假设我们把这个对象名字叫做op吧，那么
count_if在计算是不是有某个元素符合条件的时候，
它所谓的条件是什么呢？就是op(e)=true。
就是e就是它要考察的一个个的这个v里面的元素。如果发现op(e)=true的话，
那count_if就认为哎，我找到一个元素了。那算一下，有多少个？
多少个元素满足op(e)=true这个条件呢？那op(e)是什么呢？就是op.
operator(e)。对吧。那么这个op.operator(e)是什么呢？就是前面看到的CLess Then9。
这块的这个，n<9了，对吧？所以在这里就统计出来了小于9的元素的个数。是什么呢？
小于9的元素个数有几个啊？有6个，对吧？算一下，就是6个吧。
肯定不会错啊。所以就是第三行数据就是这样了。然后你继续。
然后接着话呢，我们就要去，实际上去找这个min_element，我们去对应这个在这个v这个
数组中间的话呢，去寻找这个最小的这个值。当然我们在这个例子当中，并没有自己去定义，额外定义一个
operator<，所以我们就满足直接找了一个最小的值。那么现在这个v的话呢，就是刚才看到的这个
a2数组。是a2数组吧？对啊。这时候，a2最小值就是（最小就是数学上最小的意思）这个1。
就是1，嗯。然后呢，相应的，如果是max_element的时候的话呢？ 我们找的就是最大值。我们对这个a2这个最大的话呢，就是刚才看到的这个100。
然后此外呢，还有这个accumulate，这应该是一个，
（累加）算是计算的这个，算是是数值计算的，（数值算法）数值计算的
一个算法，你就把刚才这个a2当中数组中间所有的这个值累加起来的话呢，
那么一算，计算机就得到是193。那这个accumulate的源代码是什么样的？得放到前面去了。
就比较啰嗦了。这个就先这样吧。为什么要放到前面去啊？accumulate的源代码在哪里啊？
accumulate就是累加，是吧。（这不是就是用的现成的）对对，没错，我的意思是
你要理解accumulate是怎么工作的。就得看accumulate的源代码。前面有没有出现过啊？我已经忘了。
好像没有哎。是吧，呵呵。反正它做一个累加的工作，从v.begin到v.end，
累加到初始值0上面。如果你这个初始值是0，所以就是求这个的和了。
好吧，那我们再看这个for_each。
for_each是干什么的呢？就是对于v.begin，v.end里面的每一个元素e
它都会去执行output
square(e)。它就干这个事情。
嗯，就是去计算相应的这个平方，然后输出出来。是啊，那个output square
是什么呢？我们得回忆一下，是吧？要不都忘掉了。output square在这干什么啊？
它把参数的平方给它输出了，再提醒一下啊，这里有 calculateCube是返回这个参数的立方哦。
好吧，那我们就看这个
呵呵 在哪里啊？再往前，很前很前。
这个咱们助教怎么处理呢？这种情况。他会剪掉，（剪掉，OK）没关系，接着讲，我们接着往下讲 就完了。好，嗯
那我们再看这个for_each啊，这个for_each对每个元素都执行这个操作。
那也就是说，这条语句会导致输出。什么样的输出呢？
就是输出了这个
这个东西。因为对v里面的每一个元素都输出了它的平方。对吧。
相应地，transform也是去做了，但它实际上是去做了这个calculateCube这样一个操作。
对，而且把操作的结果，要放到了这个cubes.begin
开始的地方。（嗯，对）反正cubes已经有空间了。对吧。
那现在实际上就是把a1里面的每一个元素，它的立方，
放到了这个cubes.begin开始的往后的地方去，
所以我们在输出cubes，结果就会是
这个1 2 3 4 5 6 7 8 9 10的这个立方。对，然后我们输出
cubes的时候也是利用了copy这样的一个，看起来稍显怪异的
算法来输出的。对，并不是说用copy来进行输出多么有必要。只不过
我是举这个例子，是为了说明一下copy它可以被如何来使用。就是嘚瑟贴呗。呵呵，就是提醒大家
写程序要具有想象力哦。接下来咱们要讲讲这个copy的奇怪用法了啊。对，然后会看见这个copy它本身并不是去实现
这个复制，拷贝的工作。我觉得这么讲很久，好像很累啊，咱们放点什么背景音乐好不好？郭老师，有什么推荐吗？
你喜欢听什么样的音乐啊？ 我其实都随便听的。最近在听这个什么儿童歌曲，陪我们家妹子
整天听“什么门前大桥下，什么游过一群鸭”之类这样的。好吧，好吧，不适合用来做背景。
我喜欢听一些电影的音乐。我们现在来放一个熟悉的这个东西。大家一定能听得出来是什么东西的。
好，我们就着这个音乐讲，会很兴奋的。好，现在这个 我们要说copy的妙用，对吧。
我们注意到这条语句，我们在前面定义了一个这个ostream_iterator这个
这种类型的对象， 然后把cout和这个空格字符串作为参数传进去。
结果我们来一条copy， 结果这东西就能够在cout上输出，这到底是怎么回事呢？
我们接着往下看啊，那我们对这里，首先，知道这个，首先要对copy算法有一些了解。
你来说说copy是个什么样的啊？ 这个copy的话呢，那我们刚才其实已经在前面那个例子里面，就是例题中间就可以看到，对吧。
我们copy如果正儿八经地实现的话，它实际上做的事呢，就是对应在这个
定义好的这个区间范围内，那么它实际上执行的是说，从这个
0到这个last减去first中间，那么去执行，就是
去执行N次，每一次它实际上执行的事呢，都是把这个对
first加上N之后，拷贝给这个x+N,也就是对应把这个区间中间的内容拷贝给我这个
输出处，等于说定义目标口的把这个 希望拷贝给谁，具体的这个位置上，来执行这个
呃，呃，相应这个拷贝的工作。>>我们来看它的源代码吧，就能够更清楚地说出来这件事了，啊。
这是copy的源代码，不见得所有C++的编译器， 都是这么实现的，但它的核心，实际上就是这里的这个循环。
那我们就来看看这个参数啊，这个copy它有两个类型参数，一个叫II，一个叫
OI。实际上这是暗示你，这个是输入叠在一起，这个是输出叠在一起的意思。那我们来看看这边的
还有copy的前两个函数的参数是F到L，它可以是一个区间的起点和终点。
然后这个X呢，它可以是一个区间的，呃，这个所谓的目标的位置，然后我们看下copy做了一些什么呢？看到
F一直走到L，对吧，在走的过程中呢，++F，也++X，
然后呢，在这个循环里面做的事情就是把新F的值复制给新X， 那也就是说，把F所指向的那个内容，
拷贝到X的所指向的那个位置上去。>>对，这就是最传统copy的实现。>>对啊，它成为一个循环，就把
区间FL里面的内容拷贝到从X开始的
地方。就是从这个源代码看，我们觉得它应该是干这样的事情的。但是。>>对啊，就
直观上看，感觉跟那个output什么就完全不搭界嘛。>>没有什么关系，对吧。但实际上它可以做到输出的这个
功能。它为什么能够实现呢？那我们来看啊。
呃，我们看这个程序，就是说，如果假设让你自己写一个，
My_ostream_iterator，然后它的功能嘛，是跟前面那个ostream_iterator
接近，你会怎么写？这里假设我们自己定义了一个模板，叫做My_ostream_iterator， 然后，然後呢，在这里，它能够把整形的东西输出。
然后，实际上它能够把整形的东西交给cout输出，然后输出一个整形的东西，后面就跟一个*号。
这个My_ostream_iterator的对象的名字叫oit，然后我们copy （a， a+4，oit）呢，就会在屏幕上输出一星，二星，三星，四星。
那如果我们定义的一个文件，test.txt，
把这个文件对象关联到test.txt上面，然后这个文件是用来输出的，
然后呢，我们下面定义一个新的这个My_ostream_iterator对象的时候，是用文件
对象oFile作为参数，而且这个型号不变，那么下面这条copy语句呢，就会导致
一星，二星，三星，四星被写到这个文件里面去了。
>> 好神奇啊！也就是说，本身这个copy既可以实现在屏幕中间的输出，也可以实现在 >> 文件里面的输出。对。
然后文件用完了，你当然得关掉了，对吧？ 那好了，现在就假设我出的题目就是让你去写一个类模板My_ostream_iterator，
你该怎么去写？>>对，所以我们的问题就是如何去编写
这个My_ostream_iterator？>>啊，这个如果作为作业就是很难的一个作业了。
很需要想象力，那你要会写这个东西呢，你首先要对copy的源代码，要了解地清楚。
那我们copy的源代码，就写在这儿了。对吧。那好了，现在我们，如果有一条语句copy(a,a+4,oit)，
它就会把a里面的内容， 弄到屏幕上给它输出，对吧，那么当我们
编译器编译到这条语句的时候，就会从这个
copy模板实例化出来一个copy函数。那copy函数，
就是这样的，这里面的部分肯定是原样照抄，但是呢，这些参数，它需要把具体的类型给实例化出来。
这个a是int型类型的， 对吧，所以说，这里的II就变成了这个int*。
那这边的，这个这块嘛，这当然也是int*，
然后我们看到这个oit，它是什么类型的啊？ oit它不是My_ostream
_iterator<int>类型的，对吧。所以说在我们实例化出来的这个copy函数里面，
最后一个参数就是My_ostream_iterator<int>型类型的，然后它的名字叫做X。
这里面，当然就都不变了。对吧。好了，现在的问题就是，编译器，
从这个copy模板，实例化出来的一个具体的copy函数，
它长这个样子的，那现在我们要让这样一个copy函数能够编译通过， 你需要解决哪些问题呢？
>> 那显然是要这个，我们看到说要对应乘法这个++这个运算符。>>对啊，你要不++的
，不重载++的话，这个X是一个对象，你对它++，怎么能够说得通呢？说不过去，对吧。>>然后我们还需要去考虑这个，
星花这个运算符也需要去重载。>>对啊，也不然星X不也没有定义，是吧。>>对，然后另外呢，这个
等于号，因为我们等于号两边呢，可能类型也是不一致的。>>对啊。>>所以我们需要要等于号上也要进行处理。
>> 啊，对，我们等于还要重载一个等于号这个运算符，对吧，否则这些++，*，和=都会不过。
>> 等等，那本身输出这个语句还是没有体现出来啊，感觉。>>对啊， 就是我们，我们会把F到L里面的所有内容都输出了，对吧。
那到底在哪里进行这个输出呢？ 当然要输出的东西就是这个*F，是吧，那这个*F，
到底是通过什么办法去输出的呢？在什么地方被输出的呢？
那我们首先来考虑一下，就是这有三个运算符被重载，这三个运算符
我们重载它一方面是要解决编译过不了的问题，对吧，另一方面，我们重载它，也需要让这些运算符具体干一些事情。
比方说，想办法把这个*F给它输出，
好了，那我们表面，我们分析一下，我们觉得这个++X，
是否没有什么事情可以干？你把它重载一下，让它 能够编译过就行了，不需要在++里面做一些事情。
那由于这边要输出的内容就是个*F，
然后等号要能够执行的话，这个*X得是一个什么东西？
才能在上面执行这个等号呢？ 那首先啊，我们认为，这个*经过重载以后，它就是一个函数了，那*X
就是一个函数调用的这个表达式了。一个函数调用的表达式，它能出现在
等号的左边，它的返回值应该是个什么啊？>>引用啊。>>应该是引用，对吧。那它引用了谁呢？
引用了谁合适呢？ 当然就是引用了这个X合适了，对吧。也就是说，
这个*X这个表达式，它的返回值是一个引用，它就引用了这个X， 那然后这个X=*F怎么解释呢？就变成X
.operator= （*F）了。
好，那么接下来我们在，这是个等号啊，接下来我们在这个operator=这个函数里
面，就可以把这个*F给它输出了。对吧。嗯。所以说我们重组了++,但是++不用干事情，
我们重载了*X，这个*X只要返回X的引用就行了。然后我们重载了=，在这个=里面，
把这个参数*F给它输出了。这就是我们要做的事情。>>好，接着下面继续看。
对，我们这时候就得出一个结论，就是我们 对于My_ostream_iterator这个类来说，我们应该重载++和
*运算符，还应该重载=运算符，那现在我们就可以写出My_ostream_iterator这个类模板了。
实际上，我们在比如说这个dev C++或者其它一些编译器里面，我们还要写一个public这个东西，
才能过，那是因为那些编译器里面的copy，它不像我写的那么简单。虽然那些copy，它的核心部分是一样的。但是
它可能会有一些额外的其它东西，这我们不管它，我们要为了使这个程序编译过的话，可能
要加这一条。这个不是问题的重点，重点的是我们看看下面的这些内容。
怎么写？就是我们看到这个
使用这个My_ostream_iterator的时候，它不是有构造函数，对吧？构造函数里面有个cout，有个*。这个东西是有用的，这就意味着，以后
通过copy进行输出的时候，你要输出的内容会出现在cout里面，然后
输出内容后面的每一项都要加*，但是显然，我们得用一个什么东西，把这个cout和这个
字符串*给它记下来，对吧。那应该用什么东西来记呢？那只能是用成员变量来记了，就要用My_ostream
_iterator的成员变量来记了，那我们可以用一个string来记录那个分隔符，就是就是每输出一项，就是那个*啊。
然后我们还得用一个东西把cout给记下来了啊、那cout我们知道它是ostream_iterator的对象，对吧，
包括前面这个oitf，它是
ofstream的对象，ofstream是从ostream派生而来的，所以这个ofstream，它也是ostream的对象。
因此说，我们呢，可以用一个ostream对象来记录它，但是要注意了， 由于ofstream它的
成员函数，它的那个无参构造函数是私有的，所以我们在里面，没有办法定义一个ostream
的对象，所以我们只好用一个ostream的引用， 来记录这件事情。好，现在所以在它的构造函数里面，它不是接受两个参数吗？一个是ostream的
呃，引用，一个是字符串，那我们就用这o和s把这两个成员变量给它初始化了。这就
记下了你要把东西输出到cout，还是输出到一个什么文件对象里面，
以及分隔符是什么。我们都记下来了。然后我们就重载这个++，这个++什么事情都不用干，
那++的返回值，按理说，符合习惯的写法应该是引用，对吧， 在我们这里反正没用了，无所谓，你写一个简单的void也没有什么关系。
好了，然后我们再看到，这里要重载的又是一个*，我们要重载*，
那*我们说了，让它返回值是一个引用，在这，那引用谁呢？
就是*X返回值就应该引用X，那所以我们就return*this。
是吧，*就解决了。最后一个要重载的就是这个=。
这个=号，=号我们按照惯例的话，它应该返回那个引用，对吧，那我们就这么写吧。
然后这个=号要把这个val给它输出，那我们怎么输出呢？ 那不就是交给这个os输出，对吧？
就是这个东西，然后输出val，然后再输出后面的一个分隔符，然后再return*this。
那就行了。所以这个My_ostream_iterator就是这么写，
那写了这个东西以后呢，我们看看copy它的作用就变了，对吧，就不再是执行什么拷贝了。这里面你看不到执行什么拷贝的操作。
实际上就变成copy用来往文件或者往屏幕上进行输出了。
所以这就说明了我前面要讲的这个重点就是，一个STL里面东西，具体能干什么，并不是由它的
名字所决定的，它能完成什么样的功能，是取决于你的想象力的。
