1. 迭代器
1.1 迭代器的种类
使用随机访问迭代器的容器：array， vector，deque
使用双向迭代器的容器：list，红黑树作为底层支撑的容器
使用单向迭代器的容器：forward_list
hash_table作为底层支撑的容器的迭代器取决于其中的链表采用的迭代器类型。
还有两个特殊的迭代器类型：
input迭代器：istream_iterator
output迭代器：ostream_iterator
共有五种迭代器类型，其中四种是相互继承的关系input（父类）<-farward<-bidirectional<-random_access（子类）. 还有一种output_iterator是单独的。
5种迭代器作为类的原因之一：通过迭代器的萃取器得到类型。typename iterator_traits<T>::iterator_category category;
typeid(itr).name()输出取决于不同的library，返回值由不同的实现定义的。
1.2 迭代器对算法的影响
eg. template <class InputIterator> inline iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last)计算两个迭代器间的距离，内部首先会识别iterator的类型，之后根据不同的迭代器类型调用不同的__distance(first, second, category())函数计算距离，category()是个临时对象，表示iterator的类型。
eg. template<class InputIterator, class Distance> inline void advance(InputIterator &i, Distance n) 是将iterator移动n个元素的位置，其内部会调用__advance(i, n, iterator_category(i)), iterator_category函数用于获取iterator的类型。根据不同的迭代器类型调用不同的__advance函数。如果是input迭代器，那么会将iterator逐个移动n个位置；如果是双向迭代器，那么会先判断n是正整数还是负整数，再决定是向前还是向后逐个移动。如果是随机访问迭代器，那么处理起来就简单了，直接将指针加n个位置。
由于不同迭代器间有继承的关系，在调用__distance, __advance等这类重载的函数时，如果没有特别对这种迭代器类型的实现函数，那么会根据迭代器类型的父类找到重载的函数。（这是迭代器是类且相互继承的意义之二）
eg. template<class InputIterator, class OutputIterator> OutputInterator copy(InputIterator first, InputIterator last, OutputIterator result)内部有多出检查，首先会检查first和last的类型，如果是const char类型，那么会调用memmove()；如果是const wchar_t类型，那么也会调用memmove(). 如果是InputIterator类型，那么就调用__copy_dispatch()，再去判断是const T, 还是T，还是迭代器。如果是迭代器，那么会再去检查是随机的还是其他类型的迭代器。如果是指针类型，那么会利用type traits询问它的拷贝构造重不重要（has trivial op=(), has non-trivial op=()，对于不需要自己定义，可以使用编译器给的默认拷贝构造函数，才叫做不重要的拷贝构造）.
eg. destroy函数的内部实现和copy类似，都是会将传入的类型做判断，不同的类型采用不同的处理方式。如果传入的是forward_iterator或其派生的迭代器，那么会再利用type_traits判断析构函数是否是重要的，如果是重要的，那么会调用用户定义的~dtor.
eg. __unique_copy(first, last, result)函数中result如果是outputIterator，由于output iterator无法read, 无法执行*result != *first, 对于这种情况的处理就不同于result传入的是forward iterator.
算法中模板参数的命名具有暗示作用，是给调用者看的，对于编译来说，只有编译到内部，出现传入的迭代器无法进行的操作时，才会报错。eg. template<class InputIterator> inline iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last) { ... }
2. 算法源码剖析
qsort()和bsearch()是c的函数，不是c++标准库的算法。
c++标准库的算法有标准格式
template<typename Iterator>
std::Algorithm(Iterator itr1, Iterator itr2, ...)
{ ... }
accumulate(first, last, init);
accumulate(first, last, init, binary_op); //binary_op可以传自定义的函数，或是泛函数，binary_op(init, first)这个函数定义了初值init和first之间的计算方法。
for_each(first, last, func); 内部会调用func(first)
replace, replace_if, replace_copy.
replace(first, last, old_value, new_value)是将first到last内等于old_value的元素替换为new_value.
replace_if(first, last, pred, new_value)这里predicate表示要传一个能返回真假的判断函数pred(first), 返回真的话，会做替换。
replace_copy(first, last, res, old_value, new_value)是将将first到last区间内的值拷贝给res, 如果是old_value，替换为new_value再拷贝给res，原有的值不做替换。
count, count_if
count(first, last, value) 对于其中等于value的元素进行计数。
count_if(first, last, pred) 对于其中符合pred(*first)的元素进行计数.
如果容器中有自己的版本，要用自己的，效率更高。
find, find_if 是循序搜索。
sort(first, last);
sort(first, last, op); op可以是自定义比较大小的函数，也可以是泛函（就是传入泛函的对象或临时对象， eg.less<int>()）。
binary_search() 内部调用lower_bound()进行查找。
3. 泛函数/函数对象
泛函数主要用于配合算法使用。标准库中已经定义了多种泛函数，分为算术类（plus, minus...），逻辑运算类（logical_and...），相对关系类（equal_to, less...）等。他们的共同点在于继承自unary_function（一个操作数）或是binary_function（两个操作数）类，他们内部定义了一些typedef, 共适配器询问，他们的内部并没有数据成员，对于自定义的泛函数只有遵循stl的体系架构，继承于unary_function或是binary_function才能作为泛函数适配器。
gnu c++独有的泛函。下面是G2.9下的泛函。G4.9的名称改了。
identify传入什么元素就传出什么元素。
select1st传入pair, 传出pair中第一个元素。
select2nd传入pair, 传出pair中第二个元素。
4. 多种适配器
适配器可以改造泛函数、迭代器和容器。适配器中可以拥有泛函数、迭代器或容器。
4.1 泛函数适配器
泛函数适配器：binder2nd
eg. bind2nd(less<int>(), 40)给less函数绑定第二个参数为40，使得第一个参数和40进行比较，这里less<int>()是一个临时对象，并没有被调用 。bind2nd内部调用binder2nd, 重载()（这里会询问less第一个参数类型和返回值类型），将操作的第二个参数传入绑定的值，再以返回值的形式传出操作。对于需要绑定的值在调用binder2nd的时候会检查，首先bind2nd会向operation询问他的第二个参数的类型，之后创建一个这个类型的临时对象，并将需要绑定的值赋给它。这时会检查类型是否匹配。typename是因为编译器在编译时还不知道其要传入的类型，所以要告诉编译器这是一个类型。
<functional> bind可以替代bind1st、bind2nd、binder1st、binder2nd.
泛函数适配器： not1
not1(pred), 对pred的结果取非。
bind (C++11) 可以绑定函数、泛函、成员函数（_1必须是某个object地址）、数据成员（_1必须是某个object地址）。
