[C++ Primer] : 第10章: 泛型算法

概述

泛型算法: 称它们为”算法“, 是因为它们实现了一些经典算法的公共接口, 如搜索和排序; 称它们是”泛型的“, 是因为它们可以用于不同类型的元素和多种容器类型, 不仅包括标准库类型, 还包括内置的数组类型.

大多数算法都定义在algorithm中, 标准库还在头文件numeric中定义了一组数值泛型算法.
一般情况下, 这些算法并不直接操作容器, 而是遍历有两个迭代器指定的一个元素范围来进行操作.
泛型算法本身不会执行容器的操作, 它们只会运行与迭代器之上, 执行迭代器的操作. 泛型算法运行于迭代器之上而不会执行容器操作的特性保证了: 算法可能改变容器中保存的元素的值, 但是算法永远不会改变底层容器的大小.
迭代器令算法不依赖于容器, 但是算法依赖于元素类型的操作. 大多数算法都使用了一个元素类型上的操作, 如==, !=等, 这些操作需要元素类型的支持. 不过大多数算法提供了一种方法, 允许我们使用自定义的操作来代替默认的运算符.

int val = 42;
vector<int> ivec{1, 2, 3, 42, 4};

// 返回第一个等于给定值元素的迭代器, 如果范围中无匹配元素, 则返回第二个参数来表示搜索失败.
auto result = find(ivec.cbegin(), ivec.cend(), val);

int ia[] = {1, 2, 3, 42, 4};
int *r2 = find(begin(ia), end(ia), val); // begin定义在iterator头文件中
int *r3 = find(ia+1, ia+4, val);

初识泛型算法

标准库提供的算法很多, 但是这些算法有一致的结构. 出少数例外, 标准库算法都对一个范围内的元素进行操作, 此元素范围称为输入范围.
只读算法:

int val = 42;
vector<int> ivec{1, 2, 3, 42, 4};
// accumulate定义在numeric头文件中, 对ivec中元素求和
int sum = accumulate(ivec.cbegin(), ivec.cend(), 0); // 第三个参数决定使用那个加法运算符以及返回值类型
vector<string> svec{"hello", "world"};
string sum2 = accumulate(svec.cbegin(), svec.cend(), string("")); // string定义了+操作, 所以可以用该函数把string连起来

vector<int> ivec{1, 2, 3, 42, 4};
list<int> ilst{1, 2, 3, 42, 5};
equal(ivec.cbegin(), ivec.cend(), ilst.cbegin()); // 用于确定两个序列是否保存相同的值. 前两个参数表示第一个序列的范围, 第三个参数表示第二个序列的首元素.

用单一迭代器表示第二个序列的算法都假定第二个序列至少与第一个一样长.
for_each(vec.begin(), vec.end(), 可调用对象) 对输入序列中的每个元素调用给定的可调用对象.

写容器元素的算法:

fill(vec.begin(), vec.end(), 0);   // 将第三个参数的值赋给指定范围内的元素.
fill(ivec.begin(), ivec.begin() + ivec.size()/2, 10); // 将前一半元素赋值10
fill_n(vec.begin(), vec.size(), 0) // 将所有元素重置为0
fill_n(ivec.begin(), 3, 24); // 前3个元素赋值24, 注意 3 <= ivec.size()
fill_n(dest, n, val)  // dest指向一个元素, 从dest开始写入n个值为val的元素

一些算法接受一个迭代器来指出一个单独的目的位置, 这些算法将新值赋予一个序列中的元素, 该序列从目的位置的迭代器指向的元素开始, 并假定目的位置足够大, 能容纳要写入的元素. 即算法不检查写操作.
transform(v.begin(), v.end(), v.begin(), 可调用对象)
接受3个迭代器, 前两个表示输入序列的范围, 第三个表示目的迭代器表示将结果写入的起始地址. 其作用是对输入序列中的每个元素调用可调用对象, 并将结果写入第三个目的迭代器所表示的位置.

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

vector<int> ivec;
auto it = back_inserter(ivec);
*it = 42;  // ivec现有1个元素, 值为42
fill_n(back_inserter(ivec), 10, 0); // 末尾添加10个元素到ivec

拷贝算法:

int a1[] = {1, 2, 3, 4};
int a2[sizeof(a1)/sizeof(*a1)]; // a2与a1大小一样
auto ret = copy(begin(a1), end(a1), begin(a2)); // ret指向拷贝到a2的尾元素之后的位置
// copy接受3个参数, 将输入范围中的元素拷贝到目的序列中. copy返回目的位置迭代器(递增后)的值. 即ret恰好指向拷贝到a2的尾元素之后的位置.

list<int> lst{0, 0, 1, 2};
replace(lst.begin(), lst.end(), 0, 42); // 将lst中所有0替换成42
// replace算法读入一个序列, 并将其中所有等于给定值的元素都改为另一个值. 此算法接受4个参数, 前两个是迭代器表示范围, 后两个一个是要搜的值, 一个是新值.

vector<int> ivec;
replace_copy(lst.cbegin(), lst.cend(), back_inserter(ivec), 0, 42); // lst保持不变, 将lst中所有0替换成42并添加到ivec中
// 保留原序列不变, 接收额外的第三个迭代器参数, 指出调整后序列的保存位置.

重排容器元素的算法:

vector<int> ivec{0, 0, 1, 2, 6, 4, 8, 3};
// 重排输入序列中的元素, 利用元素类型的 < 运算符来实现排序. 接受两个迭代器表示要排序的元素范围.
sort(ivec.begin(), ivec.end()); // 非降序, 注意list不支持
// 将相邻的重复项消除, 并返回一个指向不重复值范围末尾的迭代器. vec的大小并未改变, 仍然为原来的大小, unique并不删除任何元素, 它只是覆盖相邻的重复元素, 使得不重复元素出现在序列的开始部分. 此处体现了标准库算法对迭代器而不是容器操作的思想, 算法不能直接添加或删除元素.
auto end_unique = unique(ivec.begin(), ivec.end()); // end_unique指向最后一个不重复元素的下一个位置, 但是ivec.size()保持不变
ivec.erase(end_unique, ivec.end()); // 真正删除元素

定制操作

谓词: 是一个可调用的表达式, 其返回结果是一个能用作条件的值. 谓词有两类: 一元谓词, 只接受单一参数；二元谓词, 接受两个参数. 接受谓词参数的算法对输入序列中的元素调用谓词, 因此元素类型必须能转换成谓词的参数类型.
谓词只能接受一个或两个参数, 没有三个以上参数的谓词. 如果需要三个以上参数, 则可以使用lambda表达式.

bool isBigger(const int x, const int y)
{
    return x > y;
}
vector<int> ivec{0, 0, 1, 2, 6, 4, 8, 3};
sort(ivec.begin(), ivec.end(), isBigger);// 按从大到小的顺序排序, 而不是默认的从小到大的顺序.

lambda表达式
对于一个对象或表达式, 如果可以对其使用调用运算符, 则称它为可调用对象.
四种可调用对象: 函数, 函数指针, lambda表达式, 重载了函数调用运算符的类.
一个lambda表达式表示一个可调用的代码单元, 可以将其理解为一个未命名的内联函数. 一个lambda具有一个返回类型, 一个参数列表, 一个函数体. lambda可以定义在函数内部.
lambda表达式的一般形式:
[capture list] (parameter list) -> return type { function body }
捕获列表是一个lambda所在函数中定义的局部变量的列表, 其余几部分与普通函数一样.
与普通函数不同, lambda必须使用尾置返回来指定返回类型. lambda不能有默认参数.
参数列表和返回类型可以忽略, 但必须永远包含捕获列表和函数体.
捕获列表只用于局部非static变量, lambda可以直接使用局部static变量和它所在函数之外声明的名字.
如果lambda的函数体包含任何非return语句之外的内容, 且未指定返回类型, 则返回void.

auto f = [] { return 42; };
cout << f() << endl;

lambda捕获和返回
当定义一个lambda时, 编译器生成一个与lambda对应的新的未命名的类类型. lambda是未命名类的未命名对象, 所以只能用auto来推倒其类型.
lambda所捕获的变量对应于从lambda生成的类当中的数据成员, 与任何普通类的数据成员类似, lambda的数据成员也在lambda对象创建时被初始化.
值捕获
直接写变量名, 采用值捕获的前提是变量可以拷贝, 被捕获的变量的值是在lambda创建时拷贝, 而不是调用时拷贝, 因此随后对其修改不会影响到lambda内对应的值.
引用捕获
在变量名前加&来表示, 引用方式捕获的变量与其他任何类型的引用的行为类似, 当我们在lambda函数体内使用此变量时, 实际上使用的是引用所绑定的对象, 所以必须要确保被引用的对象在lambda执行时是存在的.
隐式捕获
& 采用引用方式的隐式捕获, = 采用值捕获方式的隐式捕获. 可混合使用隐式捕获和显示捕获. 当混合使用时, 捕获列表中的第一个元素必须是一个&或=用以指定隐式捕获的方式, 显示捕获的变量必须使用与隐式捕获不同的方式. 即若隐式捕获方式是引用的方式, 则显示捕获必须是值捕获的方式.
函数可以直接返回一个可调用对象, 或返回一个类对象, 该类含有可调用对象的数据成员. 如果函数返回一个lambda, 则与函数不能返回一个局部变量的引用类似, 此lambda不能包含引用捕获.
可变lambda
默认情况下, 一个值被拷贝的变量, lambda不能改变其值, 如果希望改变一个被捕获的变量的值, 就必须在参数列表后加上mutable关键字. 这可能是因为lambda中对应改变量的拷贝副本是一个const类型的.
而对于引用捕获的方式, 只要被引用对象是一个非const类型, lambda就可以改变其值.

vector<string> word{"aaa", "bb", "cccc", "d", "eeeee"};
// 按size()从小到大排序
stable_sort(word.begin(), word.end(), [](const string &s1, const string s2) { return s1.size() < s2.size(); });
int sz = 3;
// 查找第一个size > 3的元素
auto wc = find_if(word.begin(), word.end(), [sz](const string &s) { return s.size() > sz; });
// 遍历输出元素
for_each(wc, word.end(), [](const string &s) { cout << s << " "; });

指定lambda返回类型
对于lambda的返回类型, 书中是这样说的: 如果一个lambda体包含return之外的任何语句, 则编译器假定此lambda返回void. 经过上网查找得到的解释: 该限制在C++14中已被取消, 而且虽然标准是这样说的, 但是实际上很多编译器并未严格遵循这一标准, 如g++编译器可以编译通过如下代码:

int val = 10;
auto f = [val] ()mutable { val = 20; return val; }; // OK, 可以改变val的值
auto f = [=] (){ val = 20; return val; }; // Error, 不可改变val的值
auto f = [&] { val = 20; return val; };   // OK, 引用可以改变val的值
cout << f() << endl; // 输出20

// 将ivec中元素取绝对值
vector<int> ivec{1, 2, -2, -5};
transform(ivec.begin(), ivec.end(), ivec.begin(), [](int i) { return i < 0 ? -i : i; });
// 等价写法, 指明返回类型
transform(ivec.begin(), ivec.end(), ivec.begin(), [](int i) -> int { if(i > 0) return i; else return -i;});

参数绑定
对于捕获列表为空的lambda表达式, 通常可以很容易就用函数来代替, 但是对于捕获局部变量的lambda来说, 用函数来替代它就不是那么容易了. 此时可以使用bind函数来解决.
bind函数
可以看作一个通用的函数适配器, 接收一个可调用对象, 生成一个新的可调用对象来适应原对象的参数列表. 定义在functional头文件中.
bind一般形式为
auto newCallable = bind(callable, arg_list);
arg_list中的参数可能有形如_n的名字, n是整数, 这些参数是“占位符”, 表示newCallable的参数, 它们占据了传递给newCallable的参数的位置: _1为newCalllable的第一个参数, _2表示第二个参数. 然后arg_list被传递给callable.

bool checksize(const string &s, string::size_type sz)
{
	return s.size() >= sz;
}
// 此bind调用只有一个占位符, 表示check6只接受单一参数. check_size的第一个参数为_1即check6所接受的参数, 第二个参数为6.
auto check6 = bind(checksize, _1, 6);

bool checksize(const string &s, string::size_type sz)
{
	return s.size() >= sz;
}
// lambda表达式形式
auto wc = find_if(word.begin(), word.end(), [sz](const string &s) { return s.size() > sz; });
// bind形式
auto wc = find_if(word.begin(), word.end(), bind(checksize, std::placeholders::_1, sz));

名字_n都定义在一个名为placeholders的命名空间中, 而这个命名空间本身定义在std命名空间中. 为了使用这些名字, 两个命名空间都要写, 如_1对应的using声明为:

using std::placeholders::_1;
using namespace std::placeholders;

可以一次引入多有的命名: using namespace namespace_name；
bind也可以用来对可调用对象中的参数进行重新排序.

bool isBigger(const int x, const int y)
{
    return x > y;
}

vector<int> ivec{0, 0, 1, 2, 6, 4, 8, 3};
sort(ivec.begin(), ivec.end(), isBigger);// 按从大到小的顺序排序. 调用isBigger(A, B)
sort(ivec.begin(), ivec.end(), bind(isBigger, _2, _1));// 按从小到大的顺序排序. 调用isBigger(B, A)

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

ostream &print(ostream &os, const string &s, char c)
{
	os << s << c;
}
for_each(word.begin(), word.end(), bind(print, ref(cout), _1, ' '));

再探迭代器

除了为每个容器定义的迭代器之外, 标准库在头文件iterator中还定义了额外的几种迭代器:
插入迭代器: 插入器是一种迭代器适配器, 它接受一个容器, 生成一个迭代器, 可用来向容器插入元素.
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的迭代器, 此函数接收第二个参数, 指向一个容器的迭代器, 元素被插入到给定迭代器所表示的元素之前. 注意执行完后it仍指向原来的元素, 新插入的元素在它之前. 即: *it = val 和it = c.insert(it, val); ++it;的效果是一样的.

list<int> lst = {1, 2, 3, 4};
list<int> lst2, lst3;
// 拷贝完成之后, lst2包含 4 3 2 1
copy(lst.begin(), lst.end(), front_inserter(lst2));
// 拷贝完成之后, lst3包含 1 2 3 4
copy(lst.begin(), lst.end(), inserter(lst3, lst3.begin()));

流迭代器: 绑定到输入或输出流上, 可用来遍历所关联的IO流.
istream_iterator: 读取输入流.
ostream_iterator: 像一个输出流写数据.
这些迭代器将他们对应的流当作一个特定类型的元素序列来处理, 通过使用流迭代器, 我们可以使用泛型算法从流对象读取数据以及向其写入数据, 这是流迭代器的作用, 使得泛型算法可以处理流. 如
istream_iterator in(cin), eof;
cout << accumulate(in, eof, 0) << endl;
这段代码会计算从标准输入读取的值的和. 这使得泛型算法对流的处理和对容器的处理是一样的.

istream_iterator操作
当创建一个流迭代器时, 必须指定迭代器将要读写的对象类型, 一个istream_iterator使用>>来读取流, 因此, istream_iterator要读取的类型必须定义了输入运算符. 当创建一个istream_iterator时, 可以将其绑定到一个流. 也可以默认初始化迭代器, 这样就创建了一个可以当作尾后值使用的迭代器.
istream_iterator int_it(cin); //绑定到一个输入流, 从cin读取int
istream_iterator int_eof; //尾后迭代器
ifstream in("afile");
istream_iterator str_it(in); //从“afile”文件中读取字符串
下面是一个用istream_iterator从标准输入读取数据, 存入一个vector的例子:

vector<int> vec;
istream_iterator<int> in_iter(cin); //从cin读取int
istream_iterator<int> eof;          //istream尾后迭代器
while(in_iter != eof)               //当有数据可以读取时
    vec.push_back(*in_iter++);

// 等价操作
istream_iterator<int> in_iter(cin), eof;
vector<int> vec(in_iter, eof);

对于一个绑定到流的迭代器, 一旦其关联的流遇到文件尾或者遇到IO错误, 迭代器的值就与尾后迭代器相等.

istream_iterator in(is) in从输入流is读取类型为T的值
istream_iterator end; 读取类型为T的值的istream_iterator迭代器, 表示尾后位置
in1 == in2; in1和in2必须读取相同的类型, 如果它们都是尾后迭代器, 或绑定到相同的输入, 则两者相等.
in1 != in2;
*in 返回从流中读取的值
in->mem 与(*in).mem的含义相同
++in, in++ 使用元素类型所定义的>>运算符从输入流中读取下一个值, 和以往一样, 前置版本返回一个指向递增后迭代器的引用, 后置版本返回旧值.

ostream_iterator操作:
可以对任何具有输出运算符的类型定义ostream_iterator. 当创建一个ostream_iterator时, 可以提供第二个参数, 它是一个C风格的字符串, 在输出每个元素之后都会打印此字符串. 必须将ostream_iterator绑定到一个指定的流,
不允许空的或表示尾后位置的ostream_iterator.
ostream_iterator out(os)
ostream_iterator out(os, d) 将类型为T的值写到输出流os中, 每个值后面都输出一个d.
out = val 用<<运算符将val写入到out所绑定的ostream中, val的类型必须与out可写的类型兼容
*out, ++out, out++ 这些运算符存在, 但不会对out做任何事, 每个运算符返回out.
使用ostream_iterator的例子

vector<int> vec{1, 2, 3, 4};
ostream_iterator<int> out_iter(cout, " ");
for(auto e : vec)
    *out_iter++ = e;

由于对ostream_iterator的解引用和自增操作不做任何事, 所以循环还可以改写为如下的样子:

for(auto e : vec)
    out_iter = e;

但是推荐第一种写法, 这种写法中流迭代器的使用与其他迭代器的使用保持一致. 如果想将此循环改为其他迭代器类型, 则修改将会很容易.

可以通过调用copy来打印vec中的元素, 这比编写循环更为简单.

vector<int> vec{1, 2, 3, 4};
ostream_iterator<int> out_iter(cout, " ");
copy(vec.begin(), vec.end(), out_iter);
cout << endl;

反向迭代器: 这些迭代器向后而不是向前移动. 除了forwar_list之外的容器都有反向迭代器.
反向迭代器在容器中从尾元素向首元素反向移动的迭代器. 可以通过调用rbegin, rend, crbegin, crend成员函数来获得反向迭代器. 这些成员函数返回指向容器尾元素和首元素之前一个位置的迭代器.

vector<int> vec{1, 3, 2, 4};
sort(vec.begin(), vec.end());  // 从小到大
sort(vec.rbegin(), vec.rend());// 从大到小

反向迭代器与其他迭代器间的关系
反向迭代器的目的是表示元素范围, 而这些范围是不对称的! 当我们从一个普通迭代器初始化一个反向迭代器时, 或是给一个反向迭代器赋值时, 结果迭代器与元迭代器指向的不是相同的元素.

string line("abc,def,ghk"); // line保存的是以逗号分割的单词
// 查找并输出第一个单词
auto iter = find(line.cbegin(), line.cend(), ',');
cout << string(line.cbegin(), iter) << endl; // 输出abc
// 使用反向迭代器, 查找并输出最后一个单词
auto riter = find(line.crbegin(), line.crend(), ',');
cout << string(line.crbegin(), riter) << endl; // 输出khg
// 由反向迭代器得到一个正向迭代器, 且riter.base()的迭代器指向riter后一个位置
cout << string(riter.base(), line.cend()) << endl; // 输出ghk

移动迭代器: 不是拷贝而是移动它们. 移动迭代器的解引用返回一个右值引用, 可以通过调用标准库函数make_move_iterator将一个普通的迭代器转换为一个移动迭代器.

泛型算法结构

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);
所有算法都接受一个输入范围, 是否有其他参数依赖于要执行的操作.

接受单个目标迭代器的算法
dest参数是一个表示算法可以写入的目的位置的迭代器. 算法假定: 按其需要写入数据, 不管写入多少个元素都是安全的.
向输出迭代器写入数据的算法都假定目标空间足够容纳写入的数据. 更常见的情况是将dest绑定到一个插入迭代器或一个ostream_iterator迭代器, 插入迭代器会将新元素添加到容器中, 因而保证空间是足够的. ostream_iterator会将数据写入到一个输出流中, 同样不管要写入多少个数据都没有问题.
接受第二个输入序列的算法
接受单独的beg2或是接受beg2和end2的算法用这些迭代器表示第二个输入范围. 只接受单独的beg2的算法将beg2作为第二个输入范围中的首元素, 此范围的结束位置未定, 这些算法假定从beg2开始的范围与beg和end所表示的范围至少一样大.

算法命名规范:
一些算法使用重载形式传递一个谓词
接受谓词参数来代替 < 或 == 运算符的算法, 以及那些不接受额外参数的算法, 通常都是重载的函数. 函数的一个版本用元素类型的运算符来比较元素, 另一个版本接受一个额外的谓词参数来代替 < 或 == . 由于两个版本的函数在参数的个数上不相等, 因此具体调用那个版本不会产生歧义.

unique(beg, end);  // 使用 == 比较
unique(beg, end, comp);  // 使用 comp 比较

_if版本的算法
接受一个元素值的算法通常有另一个不同名的(不是重载的)版本, 该版本接受一个谓词代替元素值. 接受谓词参数的算法都有附加的_if前缀.

find(beg, end, val);   // 插到val第一次出现的位置
find(beg, end, pred);  // 查找第一个令pred为真的元素

区分拷贝元素的版本和不拷贝的版本
默认情况下, 重排元素的算法会将重排后的元素写回给定的输入序列中, 这些算法还提供了另一个版本, 将元素写到一个指定的输出目的位置.

reverse(beg, end);   // 翻转顺序
reverse_copy(beg, end, dest); // 逆序拷贝到dest

特定容器算法

链表类型定义的其他算法的通用版本可以用于链表, 但代价太高, 这些算法需要交换输入序列中的元素, 一个链表可以通过改变元素间的链接而不是真的交换它们的值来快速交换元素.
对于list和forward_list, 应该优先使用成员函数版本的算法而不是通用版本的算法.
lst.merge(lst2) 将来自lst2的元素合并入lst, lst和lst2必须是有序的. 元素将从lst2中删除, 在合并之后, lst2变为空, 第一个版本使用 < 运算符, 第二个版本使用给定的比较操作
lst.merge(lst2, comp)
lst.remove(val) 调用erase删除掉与给定值相等(==)或另一元谓词为真的每个元素
lst.remove_if(pred)
lst.reverse() 反转lst中的元素
lst.sort() 使用 < 或给定比较操作排序元素
lst.sort(comp)
lst.unique() 调用erase删除同一个值的连续拷贝, 第一个版本使用 == , 第二个版本使用给定的二元谓词.
lst.unique(pred)
上面这些操作都返回void.

splice成员