泛型算法----概述，初识泛型算法，定制操作

一、概述

　　标准库定义了一组泛型算法：称它们为“算法”，是因为它们实现了一些经典算法的公共接口，如排序和搜索；称它们是“泛型”，是因为它们可以用于不同类型的元素和多种容器类型（不仅包括标准库类型，如vector或list，还包括内置的数组类型）。

　　大多数算法都定义在头文件algorithm中。标准库还在头文件numeric中定义了一组数值泛型算法。

　　一般情况下，这些算法并不直接操作容器，而是遍历由两个迭代器指定的一个元素范围来进行操作。通常情况下，算法遍历范围，对其中每个元素进行一些处理。

　　泛型算法本身不会执行容器的操作，他们只会运行于迭代器之上，执行迭代器的操作。泛型算法运行于迭代器之上而不会执行容器操作的特性带来了一个令人惊讶但非常必要的编程假定：算法永远也不会改变底层容器的大小。算法可能改变容器中保存的元素的值，也可能在容器中移动元素，但永远不会直接添加或删除元素。

二、初识泛型算法

1、只读算法

　　一些算法只会读取其输入范围内的元素，而从不改变元素。常见的只读算法有：find、count、accumulate、equal。

1）find

　　find(beg, end, val)

find返回一个迭代器，指向输入序列中第一个等于val的元素。

2）count

　　count(beg, end, val)

count返回一个计数器，指出val出现了多少次

3）accumulate

　　accumulate(beg, end, val)

accumulate第三个参数是和的初值。第三个参数的类型决定了函数中使用哪个加法运算符以及返回值的类型。

4）equal

　　equal(beg1, end1, beg2)

equal用于确定两个序列是否保存相同的。它将第一个序列中的每个元素与第二个序列中的对应元素进行比较。如果所有元素对应都相等，则返回true，否则返回false。前两个迭代器表示第一个序列中的元素范围，第三个表示第二个序列的首元素。

　　注意：那些只接受一个单一迭代器来表示第二个序列的算法，都假定第二个序列至少与第一个序列一样长。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 
 7 int main()
 8 {
 9     std::vector<int> vec = { 1, 2, 3, 4, 5 };
10     auto res1 = find(vec.begin(), vec.end(), 5);
11     std::cout << "find:" << *res1 << std::endl;
12 
13     auto res2 = count(vec.begin(), vec.end(), 5);
14     std::cout << "count:" << res2 << std::endl;
15 
16     auto res3 = accumulate(vec.begin(), vec.end(), 0);
17     std::cout << "accumulate:" << res3 << std::endl;
18 
19     std::vector<int> vec2 = { 1, 2, 3, 4, 5, 6 };
20     auto res4 = equal(vec.begin(), vec.end(), vec2.begin());
21     std::cout << "equal:" << res4 << std::endl;
22     return 0;
23 }

View Code

2、写容器元素的算法

　　一些算法将新值赋予序列中的元素。当我们使用这类算法时，必须注意确保序列原大小至少不小于我们要求算法写入的元素数目。注意，算法不会执行容器操作，因此它们自身不可能改变容器的大小。

　　一些算法会自己向输入范围写入元素。这类算法本质上并不危险，它们最多写入与给定序列一样多的元素。

　　例如，算法fill接受一对迭代器表示一个范围，还接受一个值作为第三个参数。fill将给定的这个值赋予输入序列中的每个元素。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 
 7 int main()
 8 {
 9     std::vector<int> vec = { 1, 2, 3, 4, 5 };
10     fill(vec.begin(), vec.end(), 100);
11     for (auto iter = vec.begin(); iter != vec.end(); ++iter)
12     {
13         std::cout << *iter << " ";
14     }
15     std::cout << std::endl;
16     return 0;
17 }

View Code

1）算法不检查写操作

　　一些算法接受一个迭代器来指出一个单独的目的位置。这些算法将新值赋予一个序列中的元素，该序列从目的位置迭代器指向的元素开始。

　　注意：向目的位置迭代器写入数据的算法假定目的位置足够大，能容纳要写入的元素。

　　例如，函数fill_n接受一个单迭代器、一个计数值和一个值。它将给定值赋予迭代器指向的元素开始的指定个元素。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 
 7 int main()
 8 {
 9     std::vector<int> vec = { 1, 2, 3, 4, 5 };
10     fill_n(vec.begin(), 5, 100);
11     for (auto iter = vec.begin(); iter != vec.end(); ++iter)
12     {
13         std::cout << *iter << " ";
14     }
15     std::cout << std::endl;
16     return 0;
17 }

View Code

2）back_inserter

　　一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器。插入迭代器是一种向容器中添加元素的迭代器。通常情况，当我们通过一个迭代器向容器元素赋值时，值被赋予迭代器指向的元素。当我们通过一个插入迭代器赋值时，一个与赋值号右侧值相等的元素被添加到容器中。

　　back_inserter定义在头文件iterator中。back_inserter接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算符会调用push_back将一个具有给定值的元素添加到容器中。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 
 8 int main()
 9 {
10     std::vector<int> vec;
11     fill_n(back_inserter(vec), 5, 100);
12 
13     for (auto iter = vec.begin(); iter != vec.end(); ++iter)
14     {
15         std::cout << *iter << " ";
16     }
17     std::cout << std::endl;
18     return 0;
19 }

View Code

3）拷贝算法

　　拷贝算法是另一个向目的位置迭代器指向的输出序列中的元素写入数据的算法。此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列的起始位置。此算法将输入范围中的元素拷贝到目的序列中。传递给copy的目的序列至少要包含与输入序列一样多的元素。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 
 8 int main()
 9 {
10     std::vector<int> vec = { 1, 2, 3, 4, 5 };
11     std::vector<int> vec2(5);
12     // copy返回的是其目的位置迭代器（递增后），即ret指向vec2的尾元素之后的位置
13     auto ret = copy(vec.begin(), vec.end(), vec2.begin());
14     for (auto iter = vec2.begin(); iter != vec2.end(); ++iter)
15     {
16         std::cout << *iter << " ";
17     }
18     std::cout << std::endl;
19     return 0;
20 }

View Code

3、重排容器元素的算法

　　某些算法会重排容器中元素的顺序。

　　调用sort会重排输入序列中的元素，使之有序，他是利用元素类型的<运算符来实现排序的。

　　对于一个排完序的序列，我们可以使用unique来重排该序列，将相邻的重复项“删除”了，并返回一个指向不重复值范围末尾的迭代器。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 
 8 int main()
 9 {
10     std::vector<std::string> vec = { "the", "quick", "red", "fork", "jumps", "red" };
11 
12     sort(vec.begin(), vec.end());
13     auto end_unique = unique(vec.begin(), vec.end());
14     vec.erase(end_unique, vec.end());
15 
16     for (auto iter = vec.begin(); iter != vec.end(); ++iter)
17     {
18         std::cout << *iter << " ";
19     }
20     std::cout << std::endl;
21     return 0;
22 }

View Code

三、定制操作

　　很多算法都会比较输入序列中的元素。默认情况下，这类算法使用元素类型的<或==运算符完成比较。标准库还为这些算法定义了额外的版本，允许我们提供自己定义的操作来代替默认运算符。

1、向算法传递参数

　　谓词是一个可调用的表达式，其返回结果是一个能用作条件的值。标准库算法所使用的谓词分为两类：一元谓词（只接受单一参数）和二元谓词（接受两个参数）。接受谓词参数的算法对输入序列中的元素调用谓词。因此，元素类型必须能转换为谓词的参数类型。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 
 8 bool isShorter(const std::string &s1, const std::string &s2)
 9 {
10     return s1.size() < s2.size();
11 }
12 int main()
13 {
14     std::vector<std::string> vec = { "aaaa", "bb", "c", "ddd" };
15     sort(vec.begin(), vec.end(), isShorter);
16     for (auto iter = vec.begin(); iter != vec.end(); ++iter)
17     {
18         std::cout << *iter << " ";
19     }
20     std::cout << std::endl;
21     return 0;
22 }

View Code

2、lambda表达式

　　根据算法接受一元谓词还是二元谓词，我们传递给算法的谓词必须严格接受一个或两个参数。

　　我们可以向一个算法传递任何类别的可调用对象。对于一个对象或一个表达式，如果可以对其使用调用运算符，则称它为可调用的。

　　一个lambda表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。与任何函数类似，一个lambda具有一个返回类型、一个参数列表和一个个函数体。但与函数不同，lambda可能定义在函数内部。一个lambda表达式具有如下形式：

　　[capture list] (parameter list) -> return type { function body }

其中，capture list（捕获列表）是一个lambda所在函数定义的非static局部变量的列表；return type、parameter list和function body与任何普通函数一样，分别表示返回类型、参数列表和函数体。但是，与普通函数不同，lambda必须使用尾置返回来指定返回类型。

　　我们可以忽略参数列表和返回类型，但必须包含捕获列表和函数体。如果忽略返回类型，lambda根据函数体中的代码推断出返回类型。如果函数体只是一个return语句，则返回类型从返回的表达式的类型推断而来。否则，返回类型为void。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 
 8 int main()
 9 {
10     std::vector<std::string> vec = { "aaaa", "bb", "c", "ddd" };
11     sort(vec.begin(), vec.end(), [](const std::string &s1, const std::string &s2){
12         return s1.size() < s2.size();
13     });
14     for (auto iter = vec.begin(); iter != vec.end(); ++iter)
15     {
16         std::cout << *iter << " ";
17     }
18     std::cout << std::endl;
19     return 0;
20 }

View Code

1）向lambda传递参数

　　与一个普通函数类似，调用一个lambda时给定的实参被用来初始化lambda的形参。通常，实参和形参的类型必须匹配。但与普通函数不同，lambda不能有默认参数。

2）使用捕获列表

　　虽然一个lambda可以出现在一个函数中，使用其局部变量，但它只能使用那些明确指明的变量。一个lambda通过将局部变量包含在其捕获列表中来指出将会使用这些变量。捕获列表指引lambda在其内部包含访问局部变量所需的信息。

　　捕获列表只用于局部非static变量，lambda可以直接使用局部static变量和在它所在函数之外声明的名字。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 
 8 int main()
 9 {
10     std::vector<std::string> vec = { "aaaa", "bb", "c", "ddd" };
11     std::string::size_type sz = 2; // 局部非static
12     for_each(vec.begin(), vec.end(), [sz](const std::string &s){ 
13         if (s.size() > sz)
14             std::cout << s << std::endl;
15     });
16     return 0;
17 }

View Code

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 
 8 int main()
 9 {
10     std::vector<std::string> vec = { "aaaa", "bb", "c", "ddd" };
11     static std::string::size_type sz = 2; // 局部static
12     for_each(vec.begin(), vec.end(), [](const std::string &s){ 
13         if (s.size() > sz)
14             std::cout << s << std::endl;
15     });
16     return 0;
17 }

View Code

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 
 8 std::string::size_type sz = 2;
 9 
10 int main()
11 {
12     std::vector<std::string> vec = { "aaaa", "bb", "c", "ddd" };
13     for_each(vec.begin(), vec.end(), [](const std::string &s){ 
14         if (s.size() > sz)
15             std::cout << s << std::endl;
16     });
17     return 0;
18 }

View Code

3、lambda捕获和返回

　　当定义一个lambda时，编译器生成一个与lambda对应的新的（未命名的）类类型。可以这样理解，当向一个函数传递一个lambda时，同时定义了一个新类型和该类型的一个对象：传递的参数就是此编译器生成的类类型的未命名对象。类似的，当使用auto定义一个用lambda初始化的变量时，定义了一个从lambda生成的类型的对象。

　　默认情况下，从lambda生成的类型都包含一个对应该lambda所捕获的变量的数据成员。类似任何普通类的数据成员，lambda的数据成员也在lambda对象创建时被初始化。

1）值捕获

　　类似参数传递，变量的捕获方式也可以是值或引用。与传值参数类似，采用值捕获的前提是变量可以拷贝。与参数不同，被捕获的变量的值是在lambda创建时拷贝，而不是调用时拷贝。因此，随后对其修改不会影响到lambda内对应的值。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 
 8 int main()
 9 {
10     int v = 42;
11     auto f = [v] { return v; };
12     v = 0;
13     std::cout << f() << std::endl;
14     return 0;
15 }

View Code

2）引用捕获

　　定义lambda时可以采用引用方式捕获变量。一个以引用方式捕获的变量与其他任何类型的引用的行为类似。当我们在lambda函数体内使用此变量时，实际上使用的是引用所绑定的对象。

　　注意：当以引用方式捕获一个变量时，必须保证在lambda执行时变量是存在的。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 
 8 int main()
 9 {
10     int v = 42;
11     auto f = [&v] { return v; };
12     v = 0;
13     std::cout << f() << std::endl;
14     return 0;
15 }

View Code

　　我们可以从一个函数返回lambda。函数可以直接返回一个可调用对象，或者返回一个类对象，该类含有可调用对象的数据成员。如果函数返回一个lambda，则与函数不能返回一个局部变量的引用类似，此lambda也不能包含引用捕获。

3）隐式捕获

　　除了显示列出我们希望使用的来自所在函数的变量之外，还可以让编译器根据lambda体中的代码来推断我们要使用哪些变量。为了指示编译器推断捕获列表，应在捕获列表中写一个&或=。&告诉编译器采用捕获引用方式，=则表示采用值捕获方式。

　　如果我们希望对一部分变量采用值捕获，对其他变量采用引用捕获，可以混合使用隐式捕获和显示捕获。当我们混合使用隐式捕获和显示捕获时，捕获列表中的第一个元素必须是&或=，此符号指定了默认捕获方式为引用或值。当混合使用隐式捕获和显示捕获时，显示捕获的列表必须使用与隐式捕获不同的方式。

　　lambda捕获列表：

捕获列表	说明
[]	空捕获列表。lambda不能使用所在函数的变量。一个lambda只有捕获变量后才能使用它们
[names]	names是一个逗号分隔的名字列表，这些名字都是lambda所在函数的局部变量。默认情况下，捕获列表中的名字都被拷贝。名字前如果使用了&，则采用引用捕获方式
[&]	隐式捕获列表，采用引用捕获方式。lambda体中所使用的来自所在函数的实体都采用引用方式使用
[=]	隐式捕获列表，采用值捕获方式。lambda体将拷贝所使用的来自所在函数的实体的值
[&, identifier_list]	identifier_list是一个逗号分隔的列表，包含0个或多个来自所在函数的变量。这些变量采用值捕获方式，而任何隐式捕获的变量都采用引用方式捕获。 identifier_list中的名字前面不能使用&
[=, identifier_list]	identifier_list中的变量都采用引用方式捕获，而任何隐式捕获的变量都采用值方式捕获。identifier_list中的名字不能包括this，且这些名字之前必须使用&

4）可变lambda

　　默认情况下，对于一个值被拷贝的变量，lambda不会改变其值。如果我们希望能改变一个被捕获的变量的值，就必须在参数列表首加上关键字mutable。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 
 8 int main()
 9 {
10     int v = 42;
11     auto f = [v] ()mutable { return ++v; };
12     v = 0;
13     std::cout << f() << std::endl;
14     return 0;
15 }

View Code

　　一个引用捕获的变量是否可以修改依赖于此引用指向的是一个const类型还是一个非const类型。

5）指定lambda返回类型

　　如果未指定返回类型，默认情况下，如果一个lambda体包含return之外的任何语句，则编译器假定此lambda返回void。与其他返回void的函数类似，被推断返回void的lambda不能返回值。

4、参数绑定

1）标准库bind函数

　　标准库bind函数定义在头文件functional中。可以将bind函数看作一个通用的函数适配器，它接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表。

　　调用bind的一般形式为：

　　auto newCallable = bind(callable, arg_list)

其中，newCallable 本身是一个可调用对象，arg_list是一个逗号分隔的参数列表，对应给定的callable参数。即，当我们调用newCallable时，newCallable会调用callable，并传递给它arg_list中的参数。

　　arg_list中的参数可能包含形如_n的名字，其中n是一个整数。这些参数是“占位符”，表示newCallable 的参数，它们占据了传递给newCallable 的参数的“位置”。数值n表示生成的可调用对象中参数的位置：_1为newCallable 的第一个参数，_2为第二个参数，依次类推。

2）使用placeholders名字

　　名字_n都定义在一个名为placeholders的命名空间中，而这个命名空间本身定义在std命名空间中。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 #include <functional>
 8 
 9 void check_size(const std::string &s, std::string::size_type sz)
10 {
11     if (s.size() > sz)
12         std::cout << s << std::endl;
13 }
14 int main()
15 {
16     std::vector<std::string> vec = { "aaaa", "bb", "c", "ddd" };
17     auto newf = std::bind(check_size, std::placeholders::_1, 2);
18     for_each(vec.begin(), vec.end(), newf);
19     return 0;
20 }

View Code

3）绑定引用参数

　　默认情况下，bind的那些不是占位符的参数被拷贝到bind返回的可调用对象中。如果我们希望传递给bind一个对象而又不拷贝它，即以引用方式传递，就必须使用标准库ref函数。函数ref返回一个对象，包含给定的引用，此对象是可以拷贝的。标准库中还有一个cref函数，生成一个保存const引用的类。与bind一样，函数ref和cref也定义在头文件functional中。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>
 4 #include <numeric>
 5 #include <vector>
 6 #include <iterator>
 7 #include <functional>
 8 
 9 void check_size(const std::string &s,std::ostream &os, std::string::size_type sz)
10 {
11     if (s.size() > sz)
12         os << s << std::endl;
13 }
14 int main()
15 {
16     std::vector<std::string> vec = { "aaaa", "bb", "c", "ddd" };
17     auto newf = std::bind(check_size, std::placeholders::_1, std::ref(std::cout), 2);
18     for_each(vec.begin(), vec.end(), newf);
19     return 0;
20 }

View Code