[C++知识库]C++ Primer 学习笔记（第十章 泛型算法）

目录

前言

10.1 概述

10.2 初识泛型算法

10.3 定制操作

10.4 再探迭代器

10.5 泛型算法结构

10.6 特定容器算法

第十章 泛型算法

前言

用户可能还希望对容器做很多其他操作，标准库并没有给每个容器定义成员函数来实现这些操作，而是定义了一组泛型算法。泛型是指它们可以用于不同类型的元素和多种容器类型，以及其他类型序列。

10.1 概述

一般情况下，这些算法不能直接操作容器，而是遍历由两个迭代器指定的一个元素范围来进行操作。例如对于算法find的使用：

int val = 42;                                            // 调用标准库算法find：在vec中查找想要的元素
auto result = find(vec.c.begin(), vec.end(), val);
cout << "The value " << val << (result == vec.cend() ? "is not present" : "is present") << endl;                                                    

                                                         // 调用标准库算法find：在一个string的list中查找一个给定值
string val = "a value";
auto result = find(lst.cbegin(), lst.cend(), val);       // 用find在数组中查找值
int ia[] = {27, 210, 12, 47, 109, 83};
int val;
int* result = find(begin(ia), end(ia), val);                                                            
auto result = find(ia + 1, ia + 4, val);                 // 在序列的子范围中查找，只需要将指向子范围首元素和尾元素之后位置的迭代器（指针）传递给find

注意：迭代器令算法不依赖于容器，但算法依赖于元素类型的操作。泛型算法本身不会执行容器的操作，它们只会运行于迭代器之上，执行迭代器的操作。因此，算法永远不会改变容器的大小，只可能改变容器中保存的元素的值或顺序。

10.2 初识泛型算法

Ⅰ）只读算法：只会读取其输入范围内的元素，而从不改变元素。

?accumulate：求和算法。

int sum = accumulate(vec.cbegin(), vec.cend(), 0);
// 对vec中的元素求值，和的初值是0。第三个参数的类型决定了函数中使用哪个加法运算以及返回值的类型。
string sum = accumulate(v.cbegin(), v.cend(), string(""));    // 将vector中所有string元素连接
string sum = accumulate(v.cbegin(), v.cend(), "");            // 错误，传递的是字符串字面值，用于保存和的对象的类型将是const char*，没有定义+运算符。

equal：用于确定两个序列是否保存相同的值，相同返回true，否则返回false。?

equal(roster1.cbegin(), roster1.cend(), roster2.cbegin());
// 将第一个序列中的每个元素与第二个序列中的对应元素比较，元素类型不是必须一样，如可以是vector<string>和list<const char*>
// 接受3个迭代器，前两个接受第一个序列中的元素范围，第三个表示第二个序列的首元素。

注意：对于只读取不改变元素的算法，通常最好使用cbegin()和cend()。但是，如果使用算法返回的迭代器改变元素的值，就需要使用begin()和end()。

Ⅱ）写容器元素的算法

fill(vec.begin(), vec.end(), 0);                    // 将每个元素重置为0
fill(vec.begin(), vec.begin() + vec.size/2, 10);    // 将容器的一个子序列设置为10
                                                    // 迭代器表示范围，第三个参数用于接受一个值赋予输入序列中的每个元素

注意：①?序列原大小至少不小于要求算法写入的元素数目。② 操作两个序列的算法之间的区别在于我们如何传递第二个序列。③ 用一个单一迭代器表示第二个序列的算法都假定第二个序列至少与第一个一样长。

// 用fill_n将一个新值赋予vector中的元素
vector<int> ivec;                        // 空vector
fill_n(ivec.begin(), ivec.size(), 0);    // 所有元素重置为0，调用形式：fill_n(dest, n, val);

// 注意：假定dest指向一个元素，dest开始的序列至少包含n个元素
vector<int> ivec;                        // 空vector
fill_n(ivec.begin(), 10, 0);             // 错误！想要写入10个元素，但ivec中实际没有元素，语句未定义

插入迭代器 back_inserter：接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器，我们可以通过此迭代器赋值，将一个具有给定值的元素添加到容器中。

vector<int> ivec;                    // 空向量
auto it = back_inserter(ivec);       // 将元素添加到ivec中
*it = 42;                            // ivec中现在有一个元素：42

vector<int> vec;                     // 空向量
fill_n(back_inserter(vec), 10, 0);   // 使用back_inserter创建一个迭代器，作为算法的目的位置使用，向vec的末尾添加了10个元素0。

拷贝算法：将输入范围内的元素拷贝到目的序列中。

// 使用copy实现内置数组的拷贝
int a1[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int a2[sizeof(a1)/sizeof(*a1)];                // 确保a2和a1大小一样
auto ret = copy(begin(a1), end(a1), a2);       // ret指向拷贝到a2的尾元素之后的位置

// replace读入一个序列，并将其中所有等于给定值的元素都改为另一个值
replace(ilst.begin(), ilst.end(), 0, 42)     // 将所有值为0的元素改为42

// ilst并未改变，ivec包含ilst的一份拷贝，不过原来在ilst中的值为0的元素在ivec中都变成42
replace_copy(ilst.cbegin(), ilst.cend(), back_inserter(ivec), 0, 42);

Ⅲ）重排容器元素的算法

void elimDups(vector<string> &words) {
    sort(words.begin(), words.end());                        
// 按字典序排序
    auto end_unique = unique(words.begin(), words.end());   
// unique重排输入范围，使得每个单词只出现一次
// 将出现一次的单词排列在范围的前部，返回指向不重复区域之后一个位置的迭代器
    words.erase(end_unique, words.end()); 
// 删除重复元素，end_unique到容器尾部保存重复的单词。注意：即使没有重复元素也可以。
}

注意：标准库算法对迭代器而不是容器进行操作。因此，算法不能添加或删除元素。?

10.3 定制操作

Ⅰ）向算法传递函数

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

bool isShorter(const string &s1, const string &s2) {
    return s1.size() < s2.size();
}
// 按长度由短至长排序words
short(words.begin(), words.end(), isShorter);


elimDups(words);                // 将words按字典序排序，并消除重复单词。
// 按长度重新排序，长度相同的单词维持字典序
stable_sort(words.begin(), words.end(), isShorter);
for (const auto &s : words)
    cout << s << " ";
cout << endl;

Ⅱ）lambda表达式

可调用对象：对于一个对象或一个表达式，如果可以对其使用调用运算符，则称它是可调用的。可调用对象有：函数和函数指针、重载了函数调用运算符的类以及lambda表达式。

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

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

其中，capture list 是一个lambda所在函数中定义的局部变量的捕获列表（局部变量列表，通常为空），与普通函数不同，lambda必须使用尾置返回来指定返回类型。

auto f = [] { return 42; };
cout << f() << endl;
/*
* 可以忽略参数列表和返回类型，但是必须永远包含捕获列表和函数体。
* 调用方式和普通函数的调用方式相同。
*/

?向lambda传递参数：lambda不能有默认参数。?

#include<iostream>
using namespace std;

void biggies(vector<string> &words, vector<string>::size_type sz) {
    elimDups(words);     // 将words按字典序排序，删除重复单词
    stable_sort(words.begin(), words.end(), [](const string &a, const string &b) { return a.size() < b.size(); }); // 按长度排序，当stable_sort需要比较两个元素时，它就会调用给定的这个lambda表达式。
    auto wc = find_if(words.begin(), words.end(), [sz](const string &a) { return a.size() >= sz; }) // 利用捕获列表将sz给lambda表达式。获取一个迭代器，指向第一个满足size() >= sz的元素
    auto count = words.end() - wc; //计算满足size >= sz 的元素的数目
    cout << count << " " << make_plural(count, "word", "s") << "of length" << sz << "or longer" << endl;
    for_each(wc, words.end(), [](const string &s) { cout << s << " "; });
    cout << endl;
}
int main() {
    vector<string> words = {"the", "quick", "red", "fox", "jumps", "over", "the", "slow", "red", "turtle"};
    biggies(words, 4);
}

使用捕获列表（局部变量列表）： 向函数传递lambda时，同时定义了一个未命名的新类型和该类型的一个对象。默认情况下，新类型包括了捕获的变量，作为数据成员。

// 值捕获
void fcn() {
    size_t v1 = 42;                // 局部变量
    auto f = [v1]{ return v1; }    // 将v1的值拷贝到名为f的可调用对象
    v1 = 0;
    auto j = f();                  // j为42，f在上面存储了v1的值
}
// 引用捕获
void fcn2() {
    size_t v1 = 42;
    auto f2 = [&v1]{ return v1; }  // f2是对v1的引用，不对值进行存储。注意：必须保证在lambda表达式执行时v1已经存在。
    v1 = 0;
    auto j = f2();                 // j的值为v1的最新值
}
// 隐式捕获:让编译器根据lambda体中的代码来判断需要使用哪些变量。&：隐式引用捕获；=：隐式拷贝捕获。
wc = find_if(words.begin(), words.end(), [=](const string &s) { return s.size() >= sz; })
// 混合使用隐式捕获和显式捕获
void biggies(vector<string> &words, vector<string>::size_type sz, ostream &os = out, char c = ' ') {
    for_each(words.begin(), words.end(), [&, c](const string &s) { os << s << c; });
    for_each(words.begin(), words.end(), [=, &os](const string &s) { os << s << c; });
}
// 可变 lambda
void fcn3() {
    size_t v1 = 42;
    auto f3 = [v1]() mutable { return ++v1; }  // 对于值拷贝的变量，如果函数体里面需要修改它的值，必须加上关键字mutable。先拷贝，再改变。
    v1 = 0;
    auto j = f3();                 // j的值为v1在函数体内的最新值 43
}
void fcn4() {
    size_t v1 = 42;
    auto f4 = [v1]{ return ++v1; }
    v1 = 0;
    auto j = f4();                 // 对于非const变量的引用，可以通过f4中的引用修改，上一条语句v1=0，这里加一变为1
}

Ⅳ）参数绑定?

• ?标准库bind函数：定义在头文件functional中，接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表：

auto newCallable = bind(callable, arg_list)

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

arg_list中的参数可以包含形如_n的名字，其中n是一个整数。这些参数是“占位符”，表示newCallable的参数，它们占据了传递给newCallable的参数的位置。

using namespace std;
using namespace std::placeholders;

vector<string> words = {"string1", "abcde"}
bool check_size(const string&s, string::size_type sz) {
    return s.size() >= sz;
}
int main() {
    auto check6 = bind(check_size, _1, 6); // 只有一个占位符，表示check6只接受单一参数。
    string s = "hello";
    bool b1 = check6(s); // check6(s)会调用check_size(s, 6)
    auto wc = find_if(words.begin(), words.end(), bind(check_size, _1, 6));
    auto wc2 = find_if(words.begin(), words.end(), check6);    
}

• bind的参数?

auto g = bind(f, a, b, _2, c, _1);
// g是一个有两个参数的可调用对象。g(X, Y)的调用会映射到f(a, b, Y, c, X)

• ?用bind重排参数顺序

sort(words.begin(), words.end(), isShorter); // 单词由长至短排序
sort(words.begin(), words.end(), bind(isShorter, _2, _1)); // 单词由短至长排序

• ?绑定引用参数

for_each(words.begin(), words.end(), bind(print, os, _1, ' '));
for_each(words.begin(), words.end(), bind(print, ref(os), _1, ' '));
// 对于ostream对象，不能拷贝。

10.4 再探迭代器

Ⅰ）插入迭代器

• back_inserter：创建一个使用push_back的迭代器。
• front_inserter：创建一个使用push_front的迭代器。
• inserter：创建一个使用insert的迭代器。

// it是由insert生成的迭代器
*it = val;
// 这两条代码效果一样
it = c.insert(it, val); // it指向新插入的元素
++it;                   // 递增it使得它指向原来的元素

list<int> lst = {1, 2, 3, 4};
list<int> lst2, lst3;
copy(lst.cbegin(), lst.cend(), front_inserter(lst2));          // lst2包含4，3，2，1
copy(lst.cbegin(), lst.cend(), inserter(lst3, lst3.begin));    // lst3包含1，2，3，4

Ⅱ）iostream迭代器

istream_iterator<int> int_iter(cin);        // 绑定一个流，从cin读取int
istream_iterator<int> eof;                  // 默认初始化迭代器，尾后迭代器
while(in_iter != eof)
    vec.push_back(*in_inter++);             // 解引用迭代器获得从流读取的前一个值
// 可以将程序重写为下面的形式
istream_iterator<int> int_iter(cin), eof;
vector<inter> vec(in_iter, eof);            // 从迭代器范围构造vec

ifstream in("afile");
istream_iterator<string> str_it(in);        // 从“afile”读取字符串

使用算法操作流迭代器：?

istream_iterator<int> in(cin), eof;
cout << accumulate(in, eof, 0) << endl; // 计算从标准输入读取的值的和，如果输入为1 2 5，输出为8

Ⅲ）反向迭代器：反向迭代器需要递减运算符。

10.5 泛型算法结构

Ⅰ）5类迭代器

Ⅱ）算法参数模型

大多数算法具有如下4种形式之一：?

alg(beg, end, other args);
alg(beg, end, dest, other args);
alg(beg, end, beg2, other args);
alg(beg, end, beg2, end2, other args);
// alg表示算法名，beg和end表示算法所操作的输入范围
// dest、beg2、 end2都是迭代器参数，dest参数是一个表示算法可以写入的目的位置的迭代器

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

Ⅲ）算法命名规范

• ?一些算法使用重载形式传递一个谓词：

  unique(beg, end);            // 使用==运算符比较元素
  unique(beg, end, comp);      // 使用comp比较元素

• _if版本的算法：

  find(beg, end, val);            // 查找输入范围中val第一次出现的位置
  find_if(beg, end, pred);        // 查找第一个令pred为真的元素

• 拷贝元素和不拷贝元素：

  reverse(beg, end); // 反转输入范围中元素的顺序
  reverse_copy(beg, end, dest); // 将元素逆序拷贝到dest
  remove_if(v1.begin(), v1.end(), [](int){ return i % 2; }); // 从v1中删除奇数元素
  remove_copy_if(v1.begin(), v1.end(), back_inserter(v2), [](int){ return i % 2; }); // 将偶数元素从v1拷贝到v2，v1不变

10.6 特定容器算法

注意：对于list和forword_list，应该优先使用成员函数版本的算法，而不是通用算法，因为代价太大。?

链表还定义了splice算法，是链表数据结构所特有的，因此不需要通用版本。

注意：链表特有的操作会改变容器。

参考教程：C++模板与标准模板库