泛型算法

发表于 | 分类于 |
字数统计: 4.3k 字 | 阅读时长 ≈ 17 分钟

一、初识泛型算法

1、只读算法

一些算法只会读取其输入范围内的元素，而不改变元素。

find 函数

1
2
int val = 42;
auto result = find(vec.cbegin(), vec.cend(),val);

传递给 find 的前两个参数是表示元素范围的迭代器，第三个参数是一个值。find 将范围中每个元素与给定值进行比较。他返回指向第一个等于给定值的元素的迭代器。如果范围中无匹配元素，则 find 返回第二个参数来表示搜索失败。

accumulate 函数

1
int sum = accumulate(vec.cbegin(), vec.cend(), 0);

accumulate 函数定义在 numeric 中，accumulate 函数接受三个参数。前两个指出了需要求和的元素的范围，第三个参数是和的初值。

注意：accumulate 函数指定的序列中的元素必须与第三个参数匹配，或者能够转换为第三个参数的类型：

1
2
3
// v 是 vector<string> 类型。
string sum = accumlate(v.cbegin(), v.cend(), string(""));   // 正确
string sum = accumlate(v.cbegin(), v.cend(), "");   // 错误

equal 函数

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

1
equal(roster1.cbegin(),roster1.cend(),roster2.cbegin());

2、写容器元素的算法

算法不会执行容器操作，因此它们自身不可能改变容器大小。

fill 函数
fill 算法接受一对迭代器表示一个范围，还接受一个值作为第三个参数。

1
fill(vec.begin(), vec.end(), 0);

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

1
fill_n(vec.begin(), vec.size(), 0);         // 将所有元素重置为 0

介绍 back_inserter

一种保证算法有足够元素空间来容纳输出数据的方法是使用插入迭代器。

插入迭代器是一种向容器中添加元素的迭代器。

back_inserter 接受一个指向容器的引用，返回一个与该容器绑定的插入迭代器。

1
2
3
vector<int> vec;        // 空向量
auto it = back_inserter(vec);       // 绑定了 vec 的插入迭代器
*it = 42;

拷贝算法

拷贝(copy)算法是另一个向目的位置迭代器指向的输出序列中写入数据的算法。此算法接受三个迭代器，前两个表示一个输入范围，第三个表示目的序列起始位置。

1
2
3
4
int a1[] = {0,1,2,3,4,5,6,7,8,9};
int a2[sizeof(a1)/sizeof(*a1)];
copy(begin(a1),end(a1),begin(a2));

replace 算法
replace 算法读入一个序列，并将其中所有等于给定值的元素都改为另一个值。
此算法接受 4 个参数：前两个是迭代器，表示输入序列，后两个一个是要搜索的值，另一个是新值。它将所有等于第一个值的元素替换为第二个值：

1
replace(begin(a1), end(a1), 5, 15);     // 将 a1 中所有值为 5 的元素 替换为 15

replace_copy 算法

如果我们希望保留原序列不变，可以调用 replace_copy 。此算法接受额外第三个迭代器参数，指出调整后序列的保存位置：

1
2
int a3[sizeof(a1)/sizeof(*a1)];
replace_copy(begin(a1), end(a1), begin(a3), 5, 15);

3、重排容器元素的算法

sort 算法

sort 算法接受两个迭代器，表示要排序的范围。

1
2
vector<string> s_vec{"the","quick","red","jumps","fox","over","the","slow","red","turle"};
sort(s_vec.begin(), s_vec.end());   // 此时，s_vec为{"fox","jumps","over","quick","red","red","slow","the","the","turle"}

unique 算法
unique 算法重排输入序列，将相邻的重复项“消除”，并返回一个指向不重复范围末尾的迭代器。

1
2
auto end_unique = unique(s_vec.begin(),s_vec.end());
s_vec.erase(end_unique, s_vec.end());       // 删除多余的重复元素

二、定制操作

1、向算法传递函数

谓词

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

sort 函数

接受一个二元谓词参数的 sort 函数用这个谓词代替 < 来比较元素。

1
2
3
4
5
// 比较函数，用来按长度排序
bool isShorter(const string &s1, const string &s2) {
    return s1.size() < s2.size();
}
sort(s_vec.begin(), s_vec.end(), isShorter);

stable_sort 函数
在我们使用谓词重排的同时，还希望具有相同长度的元素维持原有顺序。（即相同长度的字符串按照大小排序）

1
stable_sort(s_vec.begin(), s_vec.end(), isShorter);

2、lambda 表达式

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

到目前为止，我们使用过的仅有的两种可调用对象是函数和函数指针。

一个 lambda 表达式表示一个可调用的代码单元。我们可以将其理解为一个未命名的内联函数。

lambda 表达式具有如下形式：

1
2
3
[capture list](parameter list) -> return type {function body}
// capture list （捕获列表）是一个 lambda 所在函数中定义的局部变量的列表；
// return type 、parameter list 和 function body 与普通函数一样，分别是返回类型、参数列表和函数体；

我们可以忽略参数列表和返回值类型，但必须永远包含捕获列表和函数体：

1
2
auto f = []{return 42;};
cout << f() << endl;    // 打印 42

在 lambda 中忽略括号和参数列表等价于指定一个空参数列表。
如果忽略返回类型，lambda 根据函数体中的代码推断出返回类型。如果函数体只是一个 return 语句，则返回类型从返回的表达式的类型推断而来。否则，返回类型为 void。

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

1
2
3
4
5
auto isShorter = [](const string &s1, const string &s2){
    return s1.size() < s2.size();
};

stable_sort(s_vec.begin(), s_vec.end(), isShorter);

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

1
2
3
4
string::size_type sz = 3;
auto f = [sz](const string &s) -> bool{
    return s.size()<=3;
};

find_if 函数
find_if 算法对输入序列中的每个元素调用给定的这个谓词。它返回第一个使谓词返回非 0 值的元素，如果不存在，这样的元素，则返回尾后迭代器。

1
2
3
4
5
6
7
vector<string> s_vec{"hello", "world", "c++", "program"};
string::size_type sz = 3;
auto f = [sz](const string &s) -> bool{
    return s.size()<=sz;
};
// 调用 find_if 返回一个迭代器，指向第一个长度小于等于 sz 的元素。如果这样的元素不存在，则返回 s_vec.end()。
auto wc = find_if(s_vec.begin(), s_vec.end(), f);

for_each 函数
for_each 算法接受一个可调用对象，并对输入序列中每个元素调用此对象：

1
2
for_each(wc, s_vec.end(), [](const string &s){cout << s << " ";});
// 打印 c++ program

3、lambda 捕获和返回

值捕获
与传值参数类似，采用值捕获的前提是变量可以拷贝。与参数不同，被捕获的变量是在 lambda 创建时拷贝，而不是调用时拷贝：

1
2
3
4
5
6
7
8
void fcn2() {
    size_t v1 = 32;     // 局部变量
    auto f2 = [v1] {return v1};
    v1 = 0;
    auto j = f2();      // j 为42，
    
    // 由于被捕获变量的值是在 lambda 创建时拷贝，因此随后对其修改不会影响到 lambda 内对应的值。
}

引用捕获
我们定义 lambda 时可以采用引用方式捕获变量：

1
2
3
4
5
6
7
8
void fcn2() {
    size_t v1 = 32;     // 局部变量
    auto f2 = [&v1] {return v1};
    v1 = 0;
    auto j = f2();      // j 为0，
    
    // f2 保存 v1 的引用，而非拷贝。
}

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

隐式捕获

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

1
2
// sz 为隐式捕获，值捕获方式
wc = find_if(s_vec.begin(),s_vec.end(),[=](const string &s){return s.size() <= sz;});

如果我们希望对一部分变量采用值捕获，对其他变量采用引用捕获，可以混合使用隐式捕获和显示捕获：

1
2
3
4
5
6
7
8
9
10
11
12
void biggers(vector<string> &words,vector<string>::size_type sz, ostream &os = cout, char c =' ') {
    
    // os 隐式捕获，引用捕获方式； c 显式捕获，值捕获方式
    for_each(words.begin(), words.end(), [& ,c](const string &s) {
        os << s << c;
    });
    
    // os 显式捕获，引用捕获方式； c 隐式捕获，值捕获方式
    for_each(words.begin(), words.end(), [= ,&os](const string &s) {
        os << s << c;
    });
}

当我们混合使用隐式捕获和显式捕获时，捕获列表中的第一个元素必须是一个 & 或 = 。此符号指定了默认捕获方式。

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

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

1
2
3
4
5
6
7
8
9
void fcn3() {
    size_t v1 = 42;
    auto f = [v1]() mutable {return ++v1;};
    
    v1 = 0;
    
    auto j = f();   // j = 43;
    
}

指定 lambda 返回类型

如果一个 lambda 体只包含单一的 return 语句，那么我们无需指定返回类型，因为可以根据返回值类型推断出来。
如果一个 lambda 体包含 return 之外的任何语句，那么编译器假定此 lambda 返回 void。

与其他返回 void 的函数类似，被推断返回 void 的 lambda 不能返回值。

当我们需要为一个 lambda 定义返回类型时，必须使用尾置返回类型：

1
2
3
4
5
6
7
transform(vi.begin(), vi.end(), vi.begin(),[](int i) -> int {
    if (i < 0) {
        return -i;
    } else {
        return i;  
    }
});

4、参数绑定

标准库 bind 函数

bind 函数接受一个可调用对象，生成一个新的可调用对象来“适应”原对象的参数列表。

调用 bind 的一般形式为：

1
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 为第二个参数，以此类推。

1
2
3
4
5
6
7
8
9
bool check_size(const string &s, string::size_type sz) {
    return s.size() >= sz;
}

auto check_f = bind(check_size, _1, 6);

check_f(string("Hello world!"));

//调用 check_f(s) 相当于 调用 check_size(s, 6);

使用 bind，我们可以将原来基于 lambda 的 find_if 调用：

1
auto wc = find_if(s_vec.begin(),s_vec.end(),[=](const string &s){return s.size() <= sz;});

替换为：

1
wc = find_if(s_vec.begin(),s_vec.end(),bind(check_size, _1, sz));

bind 的参数

我们可以用 bind 修正参数的值，也可以用 bind 绑定给定可调用对象中的参数或重新安排其参数：

1
2
auto g = bind(f, a, b, _2, c, _1); 
g(X, Y);            // 等价于 f(a, b, Y, c, X);

下面是用 bind 重排参数顺序的具体例子：

1
2
3
4
5
// 按单词长度由短到长排序
sort(words.begin(), words.end(), isShorter);

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

绑定引用参数

默认情况下，bind 的那些不是占位符的参数被拷贝到 bind 返回的可调用对象中。但是，与 lambda 类似，有时对有些绑定的参数我们希望以引用方式传递，或是要绑定参数的类型无法拷贝。

1
2
3
4
5
6
7
ostream &print(ostream &os, const string &s, char c) {
    return os << s << c;
}

// 错误： 无法拷贝 os 对象
for_each(words.begin(), words.end(), bind(print, cout, _1, ' '));

如果我们希望传递给 bind 一个对象而不是拷贝它，就必须使用标准库 ref 函数：

1
for_each(words.begin(), words.end(), bind(print, ref(cout), _1, ' '));

函数 ref 返回一个对象，包含给定的引用，此对象是可以拷贝的。标准库中还有一个 cref 函数，生成一个保存 const 引用的类。

三、再探迭代器

除了为每个容器定义的迭代器之外，标准库在头文件 iterator 中还定义了额外几种迭代器。这些迭代器包括以下几种：

  • 插入迭代器： 这些迭代器被绑定到一个容器上，可用来向容器插入元素。
  • 流迭代器： 这些迭代器被绑定到输入或输出流上，可用来遍历所关联的 IO 流。
  • 反向迭代器： 这些迭代器向后而不是向前移动，除了 forward_list 之外的标准容器都有反向迭代器。
  • 移动迭代器： 这些专用的迭代器不是拷贝其中的元素，而是移动它们。

1、插入迭代器

插入迭代器是一种迭代器适配器，他接受一个容器，生成一个迭代器，能实现向给定容器添加元素。当我们通过一个插入迭代器进行赋值时，该迭代器调用容器操作来向给定容器的指定位置插入一个元素。

插入迭代器操作
it = t 在 it 指定的当前位置插入值 t 。假定 c 是 it 绑定的容器，依赖于插入迭代器的不同种类，此赋值会分别调用 c.push_back(t)、 c.push_front(t) 或 c.insert(t, p)，其中 p 为传递给 inserter 的迭代器位置
*it,++it,it++ 这些操作虽然存在，但不会对 it 做任何操作。每个操作都返回 it

插入迭代器有三种类型，差异在于元素插入的位置：

  • back_inserter 创建一个使用 push_back 的迭代器。
  • front_inserter 创建一个使用 push_front 的迭代器。
  • inserter 创建一个使用 insert 的迭代器。此函数接受第二个第二个参数，这个参数必须是一个指向给定容器的迭代器。元素将被插入到给定迭代器所表示的元素之前。

2、iostream 迭代器

虽然 iostream 类型不是容器，但标准库定义了可以用于这些IO类型对象的迭代器。istream_iterator 读取输入流，ostream_iterator 向一个输出流写数据。

istream_iterator 操作
当创建一个流迭代器时，必须指定迭代器将要读写的对象类型。