STL与泛型编程第三周笔记

2017-03-13 本文已影响0人竺沛

算法的形式

算法就是一组模板函数，用于操作容器，算法所需的一切信息都由迭代器来提供，迭代器必须能够回答算法的所有问题，才能使用该算法进行操作，算法并不能改变容器的大小，如果迭代器不能提供该信息便宜就会报错。

算法的形式

迭代器的分类

对于连续空间的迭代器，其可以连续移动并能够提供随机访问的功能；而对于list其迭代器只能单步向前或向后移动，而far ward_list起迭代器只能单向移动；对于树和list差不多；

迭代器分类

字符串分类

class_name（）可以用于产生一个临时对象；
istream和ostream也具有迭代器，分别为input和output迭代器；
typinfo头文件可以使用typeid（it）.name（）可以输出it的类型；

通过typeid实现上一个程序

迭代器的分类对算法的影响：
　　对于判断两个迭代器之间距离的迭代器distance（）对于不同的迭代器有不同的实现方式，连续空间就直接迭代器相减；而非连续的迭代器通过首尾迭代器的加加减减然后记数实现；

distance

copy算法

算法源代码剖析
　　accumulate累记算法，如果只传入一个初值，那么就是累加求和运算。如果传入加入一个二元操作，那么就会对初值和每一个元素进行操作运算。

accumulate

for_each传入两个迭代器和一个函数或仿函数，对迭代器区间中每一个元素通过传入的函数进行操作；C++11的范围for也可以起到类似的作用。

for_each

replace接受两个迭代器和两个值，将整个范围中出现的前面的值换成后面的值，replace_if传入两个迭代器和一个判断语句和一个新值，只要满足条件就替换为新值；

image.png

count，count_if用于特定值记数，有部分容器带有同名的成员函数，用于更快速的记数；sort由于范围内元素排序，对于map/set之类的不需要进行sort排序，因为这些容器本身就是排好序的，而链表必须要使用成员函数sort，因为迭代器不能随机访问；
find和find_if由于遍历容器范围进行查找，对于map/set具有更快速的查找方法。