10.1 概述

1. 标准库提供的泛型算法分布于algorithm和numeric头文件中

2. 算法并不直接操作容器，而是遍历由两个迭代器指定的元素范围进行操作

3. 泛型算法本身不会执行容器操作，只会执行迭代器操作。算法可能改变容器中元素的值，或者在容器内移动元素，但不会改变底层容器的大小

10.2 初识泛型算法

1. 假定1：操作两个序列的算法有时候会接受第三个迭代器：前两个表示第一个序列的元素范围，第三个表示第二个序列的元素范围，这种情况嘉定第二个序列至少于第一个一样长

2. 假定2：向目的位置写入n个数据的算法，应假定目的位置>=n

10.2.1 只读算法

1. accumulate函数（定义在头文件numeric中）用于计算一个序列的和。它接受三个参数，前两个参数指定需要求和的元素范围，第三个参数是和的初值（非内置类型时，需要该类型重载+运算符）

2. equal函数用于确定两个序列是否保存相同的值。它接受三个迭代器，前两个指定第一个序列范围，第三个指定第二个序列的首元素。equal函数假定第二个序列至少与第一个序列一样长（上述假定2）

3. find_if函数用于确定一个序列中是否存在满足条件的元素，存在则返回该元素迭代器，不存在返回end()

std::find_if(vec.begin(), vec.end(), callable_obj);//其中callable_obj为可调用对象，可以是已定义的函数，也可以是lambda表达式

建议在只读算法中使用cbegin和cend函数

10.2.2 写容器元素的算法

1. fill函数接受两个迭代器参数表示序列范围，还接受一个值作为第三个参数，它将给定值赋予范围内的每个元素

std::fill(vec.begin(), vec.end(), 0);

2. fill_n函数接受单个迭代器参数、一个计数值和一个值，它将给定值赋予迭代器指向位置开始的指定个元素

std::fill_n(vec.begin(), vec.size(), 0);

3. 插入迭代器（insert iterator）是一种向容器内添加元素的迭代器。通过插入迭代器赋值时，一个与赋值号右侧值相等的元素会被添加到容器中；back_insert函数定义在头文件iterator中，接受指向容器的引用，返回与该容器绑定的插入迭代器，通过此迭代器赋值时，赋值运算符会调用push_back将元素添加到容器中

std::vector<int> vec;
auto it = std::back_inserter(vec);
*it = 42;//现在vec里有一个元素了
fill_n(back_inserter(vec), 10, 0);//通过back_insert产生插入迭代器，作为算法的目的位置

4. copy函数接受三个迭代器，前两个参数指定输入序列，第三个参数指定目的序列的起始位置，将输入序列拷贝到目的序列，返回目的位置迭代器（递增后）的值

std::copy(std::begin(a1), std::end(a1), a2);

5. replace函数接受四个参数，前两个迭代器参数指定输入序列，后两个参数指定要搜索的值和替换值，将序列中的搜索值替换为目标值

std::replace(list.begin(), list.end(), src_value, dst_value);

6. replace_copy函数可以保留原序列不变。它接受第三个迭代器参数，将替换后的序列保存到新位置

std::replace_copy(list,begin(), list.end(), back_insert(vec), src_value, dst_value);

10.2.3 重排容器元素的算法

std::sort(vec.begin(), vec.end());//默认按照从小到大的顺序排列
auto iter = std::unique(vec.begin(), vec.end());//将元素重排，将重复的元素都排放到序列后端，返回指向第一个重复元素的位置
vec.erase(iter, vec.end());//删除所有重复元素

//举例：

//unique执行前

//unique执行后

//unique执行后，返回的迭代器指向倒数第二个位置

10.3 定制操作

10.3.1 向算法传递函数

1. 谓词（predicate）是一个可调用的表达式，其返回结果是一个能用作条件的值；谓词分为一元谓词（unary predicate，接受一个参数）和二元谓词（binary predicate，接受两个参数）；谓词的参数类型必须是容器元素可以转换到的类型，因为谓词的实参是输入序列的元素，而不是迭代器

bool isShorter(const string &s1, const string &s2)
{
    return s1.size() < s2.size();
}
sort(words.begin(), words.end(), isShorter);

10.3.2 lambda表达式

1. 可调用对象汇总：函数、函数指针、重载了operator ()的类，lambda表达式

2. 一个lambda表达式表示一个可调用的代码单元，可以定义在函数内部，形为：

[capture list] (parameter list) -> return type { function body }
//capture list（捕获列表）是一个由lambda所在函数定义的局部变量的列表（通常为空）
//return type、parameter list和function body分别表示返回类型、参数列表和函数体，其中返回类型和参数列表都可以省略

3. lambda可以使用其所在函数的局部变量，但必须先将其包含在捕获列表中，捕获列表只能用于局部非static变量

auto iter = std::find_if(words.begin(), words.end(), [sz](const string &a) { return a.size() >= sz; });
std::for_each(wc, words.end(), [] (const string &s) { cout << s << " "; });//for_each会对输入序列的每个元素调用可调用对象

10.3.3 lambda捕获和返回

1. 被lambda捕获的变量的值是在lambda创建时拷贝，而非调用时拷贝。在lambda创建后修改局部变量不会影响lambda内对应的值；lambda可以以引用方式捕获变量，但必须保证lambda执行时变量存在，引用捕获可以用于捕获变量是IO类型时

size_t v1 = 42;
auto f2 = [&v1] { return v1; };
v1 = 0;
auto j = f2(); //此时j为0，如果第二行去掉&，即改成值捕获，那么j值为42

2. 隐式捕获：隐式捕获情况下，编译器会根据lambda中的代码来推断要使用的变量，隐式捕获只需在捕获列表中写一个&或=即可，分别代表引用捕获和值捕获

3. 可以混合使用显式捕获和隐式捕获。混合使用时，捕获列表中的第一个元素必须是&或=符号，用于指定默认捕获方式。显式捕获的变量必须使用与隐式捕获不同的方式

for_each(words.begin(), words.end(), [&, c] (const string &s) { os << s << c; });//其他参数引用捕获，c明确是值捕获
for_each(words.begin(), words.end(), [=, &os] (const string &s) { os << s << c; });//其他参数值捕获，os明确是引用捕获

4. 捕获列表形式总结：

a) [], [参数序列] //空列表与显示捕获

b) [=], [&] //隐式值捕获与隐式引用捕获

c) [=, 参数序列], [&, 参数序列] //混合捕获

5. 可变lambda

auto f = [v1] () mutable { return ++v1; };
//对于引用方式捕获的变量，lambda是否可以修改依赖于此引用指向的是否是const类型

6. transform函数接受三个迭代器和一个可调用对象。前两个迭代器指定输入序列范围，第三个迭代器表示目标位置。它对输入的每个元素调用可调用对象，将结果写回目标位置

std::transform(vi.begin(), vi.end(), vi.begin(), [](int i) -> int { if (i < 0) return -i; else return i; });

10.3.4 参数绑定

1. bind函数定义在functional头文件中，接受一个可调用对象，生成一个新的调用对象来适应原对象的参数列表

auto newCallable = std::bind(callable, arg_list);
compare1(5, 6); //比较5和6的大小
auto compare2 = std::bind(compare1, _1, 6);//_1表示compare2的第一个参数，表示将compare2的第一个参数和compre1的第一个参数绑定在了一起
compare2(7); //自动映射成compre1(7, 6);代表比较7和6的大小

2. 占位符：_1为newCallable的第一个参数，_2为newCallable的第二个参数，依次类推，这些名字都定义在命名空间std::placeholders中，将_n放在bind中不同的参数位置，表示将新可调用对象的第n个参数和旧可调用对象在该位置的参数绑定在了一起

//举个例子
auto f2 = std::bind(f, std::placeholders::_3, std::bind(g, std::placeholders::_3), std::placeholders::_3, 4, 5);
f2(10, 11, 12);//代表执行f(12, g(12), 12, 4, 5);此时实参10 11其实并没有用到

3. 默认情况下，bind函数的非占位符参数被拷贝到bind返回的可调用对象中，但是有些类型不支持拷贝操作；如果希望传给bind一个对象又不拷贝它，必须使用std::ref函数

std::ostream &print(std::ostream &os, const string &s, char c);
for_each(words.begin(), words.end(), std::bind(print, std::ref(os), _1, ' '));

10.4 再探迭代器

除了为每种容器定义的迭代器之外，标准库还在头文件iterator中定义了另外几种迭代器。

• 插入迭代器（insert iterator）：该类型迭代器被绑定到容器对象上，可用来向容器中插入元素
• 流迭代器（stream iterator）：该类型迭代器被绑定到输入或输出流上，可用来遍历所关联的IO流
• 反向迭代器（reverse iterator）：该类型迭代器向后而不是向前移动。除了forward_list之外的标准库容器都有反向迭代器
• 移动迭代器（move iterator）：该类型迭代器用来移动容器元素

10.4.1 插入迭代器

分类：

• back_inserter：创建一个调用push_back操作的迭代器
• front_inserter：创建一个调用push_front操作的迭代器
• inserter：创建一个调用insert操作的迭代器。此函数接受第二个参数，该参数必须是一个指向给定容器的迭代器，元素会被插入到该参数指向的元素之前

使用方式：

std::list<int> lst = { 1,2,3,4 };
std::list<int> lst2, lst3, lst4;//空表
std::copy(lst.cbegin(), lst.cend(), std::back_inserter(lst2));//拷贝之后，lst2中是1,2,3,4
std::copy(lst.cbegin(), lst.cend(), std::front_inserter(lst3));//拷贝之后，lst3中是4,3,2,1
std::copy(lst.cbegin(), lst.cend(), std::inserter(lst4, lst4.begin()));//拷贝之后，lst4中是1,2,3,4

10.4.2 iostream迭代器

1. istream_iterator从输入流读取数据，ostream_iterator向输出流写入数据

2. 流迭代器可以绑定到iostream, fstream, stringstream，它将对应的流当作一个元素序列来处理

3. istream_iterator使用>>来读取流，因此istream_iterator要读取的类型必须定义了>>运算符。创建istream_iterator时，可以将其绑定到一个流。如果默认初始化，则创建的是尾后迭代器。

std::istream_iterator<int> int_it(std::cin); //从std::cin读取整数值
std::istream_iterator<int> int_eof; //尾后迭代器
std::ifstream in("afile");
std::istream_iterator<std::string> str_it(in); //从文件中读取string
while (int_it != int_eof)
{
    vec.push_back(*int_it++)
}//这里一旦int_it关联的std::cin遇到了文件尾或IO错误，迭代器的值就与尾后迭代器相等

4. 使用流迭代器构造容器

std::istream_iterator<int> in_iter(std::cin), eof; //从std::cin读取整数
std::vector<int> vec(in_iter, eof);//用in_iter返回的整数构造vec，直至遇到尾后迭代器

5. istream_iterator操作：

• in1 == in2; in1 != in2;//in1和in2必须读取相同类型
• *in1; //返回从流中读到的值
• in->mem; <=>(*in).mem
• ++in, in++; //递增操作

6. 将istream_iterator绑定到一个流时，标准库并不保证迭代器立即从流读取数据。但可以保证在第一次解引用迭代器之前，从流中读取数据的操作已经完成

7. ostream_iterator操作：

• out = val; //用<<操作符将value写入out绑定的ostream上，必须保证value的类型能够转换到out能写入的类型
• *out, ++out; //不会对ostream_iterator对象做任何操作

ostream_iterator的赋值操作等价于输出流的输出操作，每赋值一次，输出一次

std::ostream_iterator<double> out(os); //out将double值写到输出流os中
std::ostream_iterator<double> out(os, cstr); //out将类型为double的值写到os中，每个值后面都跟着一个C风格字符串
for (auto e : vec) *out++ = e; //赋值语句相当于像ostream写入元素

8. 巧妙用法：用copy打印vector中的元素

std::ostream_iterator<int> out(std::cout, “ “); //用空格隔开元素
std::vector<int> vec{1, 2, 3, 4};
std::copy(vec.begin(), vec.end(), out); //直接输出1,2,3,4

10.4.3 反向迭代器

1. 递增反向迭代器会移动到前一个元素，递减会移动到后一个元素

2. 不能从forward_list或流迭代器创建反向迭代器

3. 调用反向迭代器的base函数可以获得其对应的正向迭代器，正向迭代器指向靠后一个元素

auto riter = string.rbegin(); //反向迭代器指向string尾元素
auto iter = riter.base(); //正向，指向string的尾后元素
auto rcomma = std::find(line.crbegin(), line.crend(), ‘,’);//从line中找到,最后出现的位置
std::cout << std::string(line.crbegin(), rcomma);//有问题，此举将会产生倒序字符串
std::cout << std::string(rcomma.base(), line.cend()); //ok，产生正序字符串

10.5 泛型算法结构

10.5.1 5类迭代器

10.5.2 算法形参模式

• alg(beg, end, other args);
• alg(beg, end, dest, other args); //dest经常是一个插入迭代器或ostream_iterator
• alg(beg, end, beg2, other args);
• alg(beg, end, beg2, end2, other args);

dest表示输出范围，beg2和end2表示第二个输入范围

向输出迭代器写入数据的算法都假定目标空间足够容纳写入的数据

10.5.3 算法命名规则

1. 重载谓词的算法：一些算法使用重载形式传递一个谓词，来代替> <或==

std::unique(beg, end);
std::unique(beg, end, compare);

2. _if版本算法：接受一个元素值的算法通常有另一个不同名的_if版本

std::find(beg, end, value);
std::find(beg, end, pred);//查找第一个令pred为true的版本

3. 拷贝版本的算法：将执行结果写入额外目的空间的算法

std::reverse(beg, end);
std::reverse_copy(beg, end, dest); //把反转后的序列写入dest

10.6 特定容器算法

1. list和forward_list定义了几个成员函数形式的算法，他们定义了独有的sort, merge, remove, reverse, unique

2. 通用版本的sort要求随机访问迭代器，但是list和forward_list分别只有双向迭代器和前向迭代器，因为不能用std::sort作用于list和forward_list

3. 优先使用成员函数版本的算法

list和forward_list的splice函数可以进行容器合并：

lst.splice(args) or flst.splice_after(args)，其中args可以采用如下形式：