在完成了STL与泛型编程前三周的学习之后，有一些总结和心得在这里通过学习笔记的方式分享出来，笔记我是跟着老师在视频中所讲的内容按照顺序记录的，也不能说是流水账，对课程中的一些问题还是添加了自己的理解和分析，供也在学习C++的小伙伴用作学习交流，如有理解不到位的地方，欢迎批评指正。

上两周，老师就分配器和容器的结构与分类做了详细的介绍，本周接着之前的内容继续学习STL的另一个重要组成部分——算法。

一．算法简介

从语言层面上讲，STL几个重要部件中，只有算法Algorithm是函数模板，容器Container、迭代器Iterator、仿函数Functor、适配器Adaptor、分配器Allocator都是类模板。

算法是看不见容器的，它无法直接获得容器中的信息。它所需要的一切信息都必须从迭代器取得，所以迭代器必须能够回答算法的所有提问才能搭配该算法的所有操作。

不同容器提供了不同的迭代器，各种迭代器之间实际是一种继承关系：

可以随意位置进出的容器迭代器继承自双向进出的容器迭代器，双向进出的容器迭代器继承自单向进出的容器迭代器，单向进出的容器迭代器又继承自input_iterator，output_iterator非容器提供。

二．Iterator_category和type_traits对算法的影响

对于以上代码，是计算两个迭代器之间的距离，返回类型是difference_type；从上面的代码可以看出，算法本身是一个主函数，根据迭代器不同的分类而调用不同的次函数。

至于type_traits对算法的影响，老师举了一个copy算法的例子：

该算法需要三个变量，即来源端起始端、来源端终止端以及目的端起始端。从课件可以看出，算法copy不断地检查，到了分支的地方，决定调用哪个次函数，来保证算法的最高效。

算法源码中对iterator_category没有限制，但会有“暗示”：

在C++标准库中，它提供的algorithms以函数形式呈现，老师举了7个算法当作例子。

1.算法accumulate

2.算法for_each

3.算法replace，replace_if，replace_copy

4.算法count，count_if

5.算法sort（这里需要注意：对于unordered容器，不需要调用sort算法，遍历之后元素自动排序，自然形成sorted状态）

6.算法find，find_if（这里需要注意的是：对于unordered容器，有自己的find算法，对于array，vector，list，forward_list，deque容器，它们带有成员函数sort，因此标准库中的find算法不适用）

7.算法binary_search（这里需要注意的是：lower_bound(v.begin(),v.end(),x)，元素x安插在能够安插进去的最低点；upper_bound(v.begin,v.end(),x)，元素x安插在能够安插进去的最高点）

三．仿函数（functors）

当要求算法需要有一些特定准则时，就会编写仿函数去告诉算法。标准库提供的functors有几大类：算术类（Arithmetic）、逻辑运算类（Logical）、相对关系类（Relational），且标准库提供的functors都有继承关系。

仿函数functors的可适配（adaptable）条件：希望functors可以被修改，则必须选择继承适当的函数struct；adaptor提问，functors回答，才能融合进STL中。

存在多种Adapters：Functor Adapter与Functor、Iterator Adapter与Iterator、Container Adapter与Container之间都是内含的关系，其实就相当于改造。

在之前的内容中，我们学过容器stack和容器queue可以用Sequence当作底层容器，此时stack和queue被称作容器适配器。同样也存在函数适配器，这里老师举了函数适配器binder2nd和not1的例子：

Binder2nd继承自unary_function，将某个Adaptable Binary function转换为Unary Function：

这里需要注意的是：Typename（）表示创建临时对象，在很长的提问之前都加上typename

C++11之后又添加了新型适配器bind，std：：bind可以绑定functions、function objects、member functions以及data members

四．迭代器适配器Iteratoradaptors

1.reverse_iterator

reverse_iterator默认排序是由小到大，用rbegin()和rend()来由大到小排序。

逆向迭代器取值，是将对应正向迭代器退一位：

2.inserter

上述代码中foo是容器，it是迭代器

这个adapter将iterator的赋值操作改为安插（insert）操作，并将iterator右移一个位置。如此便可连续执行表面上赋值而实际上insert的行为。

另外，在C++标准库中，除了迭代器适配器，还有X适配器ostream_iterator和instream_iterator