泛型算法引入<algorithm>头文件

algorithm(xx.begin(), xx.end(), otherAvgs)

谨记: 算法只能使用迭代器, 不可以使用容器自带的操作

引入自定义函数的有三种方式

重载方式: 常见于不需要额外参数的算法, 此算法只需要一个起始迭代器和尾后迭代器
_if后缀: 例如find(), 本来就需要第三个参数代表要查找的内容, 如果仍采用重载将产生歧义.
_copy, 得到的内容是否写入第三个参数代表的迭代器中

算法对于迭代器有五种不同等级的要求

输入迭代器, 最起码实现递增和==运算, 并且能够单次扫描, 例如find()函数需要的迭代器
输出迭代器, 最起码能够递增, 单次扫描.
前向迭代器: 能够递增, 能够多次扫描
双向迭代器: 能够增减,能够多次扫描
随机迭代器: 能够随机访问(使用[ ]), 能够多次扫描

count(b, e, std)

从b到e的位置, 如果元素满足 == , 则std++

因此, count不可用于C风格的字符串, 因为这种字符串不支持==操作

fill(b, e, val)

fill()函数和fill_n()函数都是覆盖掉原来迭代器所指的内容, 而不是插入新值. 因此我们要保证容器内元素要足够大

插入迭代器

引入头文件<iterater>

auto a = back_inserter(*container*);
fill_n(a, 10 , 'a');

新来的元素都相当于被调用了一次push_back()

类似的还有front_inserter()

还有插入在任意位置的inserter(*container*, *position*)
对于inserter迭代器, 每插入一个元素, inserter会在指向的元素前面插入元素

IO迭代器

IO迭代器的类型一般是

i(o)stream_iterator<TYPE> NAME(STREAM)
i(o)stream_iterator<TYPE> NAME; // 创建一个空的IO迭代器, 相当于.end()或者EOF

STREAM里能填什么? 只要是支持>>运算符的对象就可以. 同理, ostream的STREAM 只要是支持<<运算符的对象.

用法: 将读入的整形存入vector

istream_iterator<int> in(cin), eof;
vector<int> i = (in, eof);

逆序

rbegin(),rend()等反向迭代器, ++时会向前移动. 如果希望得到当前迭代器并开始正向移动, 调用对象的base()方法, 此时迭代器为当前元素的下一个元素, 并可正向迭代.
这样做的理由是因为迭代器满足左闭右开的区间要求.

sort()算法

注意可能存在不稳定, 有stable_sort()可以考虑.

sort(b, e, fun)可以利用fun返回值进行排序, 此时fun()称作谓词. 每个算法, 只能接收1或2元的一个谓词. 一元即值只能传入一个迭代器所指的元素, 二元则为传入两个. 这些谓词都不能接受额外的参数, 因此考虑使用lambda语句或bind()代替谓词.

lambda

lambda公式格式

capture list: 从局部作用域中捕获的变量,函数外的变量和static变量不用写进去
parameter list: 迭代器解引用后的类型, 或者加const, 或者加&

function body只有return语句, 则不用写->return type,如:

//isShorter
[ ] (const string &a, const string &b) { return a.size()<b.size()}

lambda是在被定义的时候进行值捕获,而不是被调用的时候
也可以引用捕获, 则在被调用的时候捕获, 但是要注意引用的变量是否已经失效?

[=] 自动根据后面使用的变量进行值捕获
[&] 同上
[=, &c] 除了变量c进行引用捕获, 其他的都是用值捕获. 注意其他的内容一定写在前面

对于值捕获的变量, 如果要进行修改, 则返回类型需加上mutable
例如:

[sz] () -> mutable int{ return sz++; }
#for_each()

for_each(b, e, F)算法

对于迭代范围中的每一个元素, 都使用F操作.
这里的F操作就可以用lambda表达式

bind()函数

需要引入头文件<functional>, 并加入命名空间std::placehoders

对于谓语, 不能接受额外的参数, 我们使用bind函数将其他的参数赋过去.

bind(被调用的函数, _谓语位置, 其他参数)

例如:

//f(a, b, c, d, e);
auto g = bind(f, 0, 3, _2, 5, _1);

g(3, 6); // =f(0, 3, 6, 5, 3)

Chapter 10 Generic algorithm