C++ STL 体系结构与内核分析(五)算法入门/迭代器分类/算法源码剖析（11个例子）

C++标准库算法入门

概念：STL六大部件，算法就是模版函数，很独特，标准库的样子如下图右下角那两框代码所示。

其实算法是要处理容器里的data,只探讨迭代器。：算法看不见容器，算法所获取的信息，需要从迭代器去取，如果算法获取不到迭代器的信息则会报错。

迭代器分类

迭代器移动规则：array/vector（双端队列）/链表：list（双向）、forward_list（单向）/红黑树：set和map

五种迭代器如下图所示

打印各种迭代器分类形式

各种类型迭代器都产生临时对象，定义对象名称，传进去的数据都有一个模版。五个迭代器输入输出都不一样，用对象来表示。编译器会根据你的输入调用上面的display方法。打印字符串。

如上图所示，通过利用typeid可以打印迭代器类型名称。

optream迭代器：都是自己定义自己的category

迭代器分类对算法影响

求距离：

difference_type：问迭代器这个输入的类型；

放入第三参数category,编译器会判断他的类型调用不同的方法。

前进：走n个距离

五种迭代器为什么只有三种方法？虽然只有三种但是实际有四种分类。

copy:

输入：first起始端/last末尾端/result目的地址。

copy不断做检查传入的指针，判断他们是哪一种类型，会调用内部函数memory more。如果不是这两种继续往后泛化特化，又去检查，如果不是继续往后找。强化后面分重要和不重要，如果判定不了就需要去typetralts问返回结果（不重要）。会引发拷贝构造。copy是多么的精细，得一步一步的去算找到最快的方法。

destroy:

查看他的析构函数重不重要，不重要就不需要做析构函数里面的操作。

主函数根据不同迭代器调用不同版本。

算法对迭代器的分类只要暗示，没有强制性的只接受该类迭代器的情况

比如sort里面定义的RandomAccessIterator first,暗示接受迭代器是RandomAccessIterator。而find用的另一种迭代器，如上图所示。

算法源码剖析（11个例子）

qsort

accumulate加减或者可以自己写一个function myclass return x +2*y;

for_each在元素范围做一个指定的事情

C++11新特性 decl : coll/ i : {1,3,4,5}

relacce替换

replace_if 符合条件才替换，replace_copy 比较一段元素不会取代它而是把它放到另一个命名空间

count计数器

count_if 符合条件才+1

同样的find 查找搜寻,循序式查找，最坏情况得全部走一遍。

sort

+4 是第四个位置到终点或者起点到倒数第四个位置排序。重载 i < j由小到大。

使用list/forward_list要小心，不用使用sort，它自带就有sort()

reverse 逆向，闭环。

二分查找：使用lower_bound来找