Boolan C++标准库 第四周
第四讲
二十七、算法的形式
1.算法
从语言层面看：
容器Container是个class template
算法Algorithm是个function template
迭代器Iterator是个class template
仿函数Functor是个class template
适配器Adapter是个class template
分配器Allocator是个class template
Algorithms看不见Containers，所以它所需要的一切信息（迭代器怎么走）都必须从Iterators取得，而Iterators（由Containers供应）必须能够回答Algorithm的所有提问，才能搭配该Algorithm的所有操作。
二十八、迭代器的分类（category）
1.各种容器的iterators的iterator_category
_display_category()函数重载。
为什么不用1、2、3、4、5表示迭代器分类，而用struct：
（1）_display_category()，编译器会自动找到该调用哪个迭代器，如果用整数表示分类，就不能这么写。
（2）struct有继承关系。
2.各种容器的iterators的iterator_category的typeid
#include<typeinfo> //typeid
typeid(iterator_category).name()
二十九、迭代器分类（category）对算法的影响
1.iterator_category对算法的影响
不同category计算distance的效率不一样。
struct有继承关系，category有五种，_distance()只有两种。
不同category前进advance的效率不一样。
因为struct有继承关系，category有五种，_advance ()只有三种。
2.iterator_category和type traits对算法的影响
iterator traits
type traits：不属于STL（六大部件）的部分，但属于标准库。
3.算法源码中对iterator_category的暗示
不强制参数类型，通过名字暗示。
三十、算法源代码剖析
1.算法accumulate
累计
仿函数
2.算法for_each
range-based for statement(C++11)
3.算法replace,replace_if,replace_copy
4.算法count,count_if
5.算法find,find_if
6.算法sort
7.关于reverse iterator,rbegin(),rend()
适配器
8.算法binary_search
使用前必须先排序。
三十一、仿函数/函数对象
1.仿函数functors
一个class重载了operator()。这个class创建的对象叫做仿函数或函数对象。
STL六大部件中最简单的，也是最有可能自己写的。
只为算法服务。
STL三大类仿函数：
算术类
逻辑运算类
相对关系类
2.GNU C++独有
3.仿函数functors的可适配条件
STL规定每个Adaptable Function都应该挑选适当者继承，因为Function Adapter将会提问红色问题。（可以被适配器修饰或改造）
struct没有data，大小为0。
继承了typedef。
三十二、存在多种Adapters
1.Adapters
三种适配器：
容器适配器
迭代器适配器
仿函数适配器
适配器的共性：A（适配器）取用B的功能。
A取用B可以用两种方式：继承或复合。适配器都用复合的方式。
2.容器适配器：stack，queue
都内含了一个底层容器deque。
3.函数适配器：binder2nd
4.函数适配器：not1
5.新型适配器，bind(C++11)
取代binder2nd
#include <functional>
std：：bind可以绑定：
functions
function obiects
member functions
data functions
6.迭代器适配器，reverse_iterator
7.迭代器适配器，inserter
inserter辅助函数，帮助用户使用适配器insert_iterator。
Effective C++(10) 重载赋值操作符时，返回该对象的引用（return *this）。
insert_iterator重载了*，++，=等运算符，*和++返回的都是迭代器本身。
8.X适配器:ostream_iterator
不属于上面三种适配器，所以叫X。
