《C++Primer》第十章：泛型算法

其实顺序容器之定义了很少了操作，比如添加删除、访问首尾元素、确定容器元素个数、获取迭代器。但是更多更复杂的操作，比如查找特定元素、替换或者删除一个特定值、重排元素顺序这些并没有实现为每个容器的成员函数，而是提供了一组泛型算法的接口。
大多数算法定义在algorithm中，还有一部分数值泛型算法定义在numeric中。
泛型算法本身不会执行容器的操作（甚至泛型算法接受的可能不是容器而是c-style的数组），他们只会运行在迭代器上，执行迭代器的操作。因此迭代器使得算法不依赖于容器，但是算法依赖于元素类型的操作，比如需要在元素上进行比较。所以一个很重要的原则就是，这些算法不会改变容器的大小，（但是可能改变具体的元素值或者移动元素）。
绝大多数算法通过前两个参数接受一个迭代器范围。
接受三个迭代器表示两个序列的算法中，确保第二个序列不小于第一个序列是程序员的责任。

fill_n很类似于C中的strcpy这种操作，向一个给定位置写入给定长度的内容，因此也很容易发生“缓冲区溢出”，比如vec是一个空序列时调用fill_n(vec,10,0)就会有严重的问题（我这里是编译不通过），但是如果使用插入迭代器就没有问题，比如fill_n(back_inserter(vec), 10, 0)，因为back_inserter会操作底层容器，赋值时调用push_back。
标准库提供sort，接受两个迭代器。标准库还提供unique，功能类似于bash中的uniq，但是注意容器的大小没有改变。unique的返回值是指向不重复元素序列最后一个元素后面位置的迭代器，用该迭代器减去容器首位置迭代器就可以得到不重复元素的个数。希望稳定排序就使用stable_sort。
sort有一个重载过的版本，接受第三个参数，该参数是一个谓词(predicate)。谓词是一个可调用的表达式，返回结果是一个能用作条件的值，标准库算法适用的谓词只有两种：一元和二元。
标准库定义了名为partition的算法，将谓词为true的排在前面，false的排在后面。返回一个迭代器指向最后一个使谓词为true的元素的后面位置。
lambda表达式不能使用默认参数。lambda表达式的捕获列表作用于局部非static变量，对于局部static变量和在它所在函数之外声明的名字，可以直接使用。
find_if、for_each函数功能不言自明，三个参数，前两个是一个迭代器范围，第三个参数接受一个一元谓词。
定义一个lambda时，编译器生成一个全新的类类型，把它赋值给auto变量或者作为参数都会导致类的实例化。lambda捕获的变量作为该类的数据成员。与函数不同，捕获的变量是在lambda创建时拷贝，而不是调用时。意思就是创建lambda对象之后修改被捕获的变量不会影响lambda对象捕获得到的具体值。（这点和python不一样。python默认情况是在lambda运行时再运行时绑定值，如果需要定义时捕获值，就需要在lambda内定义默认参数。）但是如果捕获引用或者捕获指针，那么在外面的后续改动就会影响到lambda了，我们这时也要保证lambda被调用时，这些外界的变量还在。
lambda表达式可以使用隐式捕获，即让编译器自动推断使用哪些捕获变量。在捕获列表内使用=或者&，等号表示值捕获，and号表示引用捕获。也可以显式隐式混合使用。
我们使用lambda表达式的原因是，在书中出现了这么一个情况，find_if接受一个一元谓词表示一个元素符不符合条件，，但是我们这个谓词需要一个额外的参数作为条件中的变量。因此我们定义了lambda表达式把条件变量放在捕获列表中。但是如果想用函数咋处理这个问题？答案是偏函数，我不知道这个名字用在这里是否合适，在C++中通过functional中的bind函数在函数绑定参数，这很类似于python中的partial。其中暂时不绑定的参数使用_position进行占位（在std::placeholder名字空间中，placeholder名字空间在functional头文件中）。
bind函数返回一个可调用对象，其中被绑定的参数是以传值方式拷贝进bind对象中的。比如ostream不能被复制，那么在传参时使用ref(os)（这点还不太懂）。
插入器是一种迭代器适配器，接受一个容器生成一个迭代器，能通过赋值操作调用容器操作来执行插入动作。有三种插入器back_inserter、inserter、front_inserter，分别会调用容器的push_back、insert、push_front方法。对于插入器，存在解引用、自增操作符，但是没有效果，会返回自身。当对于inserter执行*it=val;时等价于it=c.insert(it, val);++it;。而front_inserter，不会执行++it;，因为他要始终指向首元素。
iostream 迭代器

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;
int main(){
    istream_iterator<int> in_iter(cin), eof;
    vector<int> vec(in_iter, eof);
    for(const int &i: vec){
        cout<<i<<" ";
    }
    cout<<endl;
}

算法操作迭代器，因此算法也可以操作流迭代器。
对于输出流迭代器来说，直接向其赋值就可以输出到ostream中，因此可以使用前面提到的copy函数来进行更优美的输出。
反向迭代器的方向和普通迭代器相反，这有好处也有坏处。好处是，比如我们想逆序排序，只要给sort传入反向迭代起即可。坏处是，有些行为可能和我们预期的不一致，这时候，可以使用reverse_iterator的base成员函数转换回普通迭代器。注意，此时迭代器的位置也会改变，会指向正序中的后一个位置，原因在于区间的左闭右开性，画图出来更好理解。
五类迭代器之一

输入迭代器：要支持==、!=、++、*(解引用)、->。输入迭代器只用于顺序访问，比如输入流迭代器，访问可能会导致元素失效，因此只能用于单遍扫描算法。
输出迭代器：要支持++、*(解引用)，而且解引用只能用于赋值。用作目的为主的迭代器通常是输出迭代器，比如copy的第三个参数。ostream_iterator也是输出迭代器。
前向迭代器：可以读写元素，支持所有输入输出迭代器的操作，可以多边扫描。比如算法replace要求前向迭代器，forward_list上的是前向迭代器。
双向迭代器：除了前向迭代器的所有操作，还支持–操作符。
随机访问迭代器：除了双向迭代器中的所有操作，还支持加减常数、两个迭代器之间的解法以及数值比较操作。sort要求该类迭代器，大部分顺序容器的迭代器也是随机访问迭代器。

由于链表结构的特殊性，通用版本的算法函数作用其上可能效率不高，因此list和forward_list自身有成员函数版本的算法：merge、remove、reverse、sort、unique。