一、本章学习总结
【待总结】
10.1 泛型算法的特点
大多数算法都定义在头文件algorithm中，标准库还在头文件numeric中定义了一组数值泛型算法。
泛型算法的特点：
- “泛型”是指它们可以用于不同类型的元素和多种容器类型，还包括内置数组类型。
比如下面的例子通过find_if算法来查找数组中的特定元素：
//char *str_arr[] = {"ths","is","a","string"}; //C++11好像不支持这种写法，以前的版本貌似支持？
int ia [] = {0,3,2,4,5,7,8,9};
auto it=begin(ia); //注意：内置数组的begin和end函数包含在头文件iterator中
auto ed = end(ia);
while(it!=ed)
{
it = find_if(it, ed, [thresh](int a){return a>thresh;});
//find_if返回第一个符合条件的元素对应的迭代器
if(it!=ed)
cout<<*it<<", ";
else
{
cout<<"elem not present."<<endl;
return 1;
}
++it; //别忘了移动迭代器
}
- 不直接操作容器（不依赖容器）
算法永远不会改变容器的大小：算法可能改变容器的值，也可能在容器内移动元素，但不会直接添加或删除元素。 - 而依赖于算法使用的迭代器。算法可以通过标准库定义的特殊迭代器，如插入器（inserter）来间接实现在容器中添加元素等操作。
10.2 初始泛型算法
10.2.1 只读算法
-
accumulate(输入迭代器，单次扫描序列)
举例：将一个vector<string>中的所有字符连接在一起，组成一个“句子”：
string sum = accumulate(vs.cbegin(), vs.cend(), string(""));
注意：
①accumulate函数不是在algorithm头文件中，而是在numeric头文件中.
②accumulate函数最后接收一个累加的初始值，该初始值决定了保存的和的对象是什么数据类型。假如这里不加string，只使用""，则默认和的初值为const char 类型。然而const cahr*类型不支持+运算，string类型支持+运算符，故强制转换类型
*equal算法
许多算法操作两个序列，如 equal。这类算法的前两个参数通常是第一个序列的范围，接着是第二个序列的范围。有时候可以只用一个参数代表第二个序列的开始位置，这时候编译器会假定第二个序列至少与第一个一样长。故程序员需要自己确保这一点。
10.2.2 写容器元素的算法
-
fill和fill_n
fill(vec.begin(), vec.end()+vec.size()/2, val);
//fill_n:
vector<string> vec;
fill_n(vec.begin(), 10, "HaHa"); //将保错：因为此时vec为空容器。无法进行写操作
fill_n(back_inserter(vec), 10, "HaHa");
-
back_inserter：用于保证算法有足够元素空间来容纳输出数据
当对一个容器调用back_inserter时，会返回一个与容器绑定的插入迭代器。当我们通过此迭代器赋值时，赋值运算会调用push_back将一个具有给定值的元素添加到容器中。如下图：
Fig. 1通过给插入迭代器赋值，实现push_back
back_inserter也定义在iterator头文件中。 -
replace_copy：
保持原容器元素不变，将replace之后的容器元素另存到新容器中
vector<int> v1={1,2,3,4,0};
vector<int> v2;
//下面写法将会报错：v2虽然容量给定，但是实际元素数量仍是0.
v2.reserve(20);replace_copy(v1.begin(), v1.end(),v2, 0, 42);
//正确写法：
replace_copy(v1.begin(), v1.end(), back_inserter(v2), 0, 42);
10.2.3 重排容器元素的算法
- 例子： 将元素按字母表顺序排列并去重，然后再按长短排序
void print(const vector<string> &vs, ostream_iterator<string> &out)
{
copy(vs.cbegin(), vs.cend(), out);
cout<<endl;
}
int main()
{
ifstream in("story");
istream_iterator<string> it(in), eof;
ostream_iterator<string> out_it(cout, " ");
if (!in)
{
cout<<"fail to read story!"<<endl;
exit(0);
}
vector<string> vs;
copy(it, eof, back_inserter(vs));
cout<<"Original story: "<<endl;
print(vs, out_it);
sort(vs.begin(), vs.end());
auto end_unique = unique(vs.begin(), vs.end());
vs.erase(end_unique, vs.end());
//print vec:"
cout<<"after unique: "<<endl;
print(vs, out_it);
stable_sort(vs.begin(), vs.end(), [](const string &s1, const string &s2){return s1.size()>s2.size();});
cout<<"after stable_sorted: "<<endl;
print(vs, out_it);
//for_each:
cout<<"for_each print: "<<endl;
for_each(vs.cbegin(), vs.cend(), [](const string &s){if (s.size()>4) cout<<s<<"~";});
}
- 注意：
- unique算法返回一个指向不重复区域之后一个位置的迭代器。（一般不用关心该迭代器之后位置的值。因为不同的编译器有不同处理方法。比如我的可能是通过交换的方式。）
- unique之后要删除序列后半部分，涉及到容器元素删减操作，还是需要用容器自己的成员函数。
- stable_sort先整体按新的谓词进行排序，局部位置保持原来的顺序。
- for_each很好用，可以接收一个带判断的谓词，直接过滤输出，顺便还可以指定输出的格式。
10.3 lambda表达式和bind参数绑定
很多算法，如sort，除了提供一个使用默认元素类型的<或==运算符进行比较的版本之外，还会提供一个重载的版本，可接收一个谓词作为第三个参数。这里的谓词可用于自定义比较的标准。可以类比python中sorted的'key'参数来理解：
# 按文件名中的数字顺序排列
img_lst = sorted(img_lst, key = lambda x: int(re.findall('\d+', x)[0]))
10.3.1 lambda表达式
直接通过一个例子来学习：
void print(vector<string> vs, std::ostream &os=cout, char ch = ' ')
{
for_each(vs.cbegin(), vs.cend(), [&os, ch](const string &s){os<<s<<ch;});
}
该函数用于打印vector对象，其中os和ch需要传递给lambda表达式。由于ostream对象不允许拷贝和赋值， 故当需要作为参数传递给函数时只能使用ostream对象的引用。（注意这个例子其实涉及到两次传递ostream对象，都使用了引用）。
注意，捕获列表还支持隐式捕获，让编译器去推断捕获的变量。比如上面的lambda可写成: [&os, =]或者[&, c]（就是如果有多个捕获变量，不能所有变量都隐式捕获）。
- 可变lambda： mutable
int a = 5;
auto f = [a] () mutable -> bool
{cout<<"Inner lambda: a= "<<a<<endl; if (a>0) --a; return (a==0? true:false);};
// 正确写法： auto f = [&a] () -> bool {if (a>0) --a; return (a==0? true:false);};
while(!f())
{cout<<"Outer: a= "<<a<<endl;}
输出
Inner lambda: a= 5
Outer: a= 5
Inner lambda: a= 4
Outer: a= 5
Inner lambda: a= 3
Outer: a= 5
Inner lambda: a= 2
Outer: a= 5
Inner lambda: a= 1
注意：区分mutable和引用捕获。mutable传给lambda表达式的参数，可以被表达式修改，并且将修改后的状态“暂存”在表达式中（不严格的理解）。且某个参数被拷贝到捕获列表之后，就和原来的参数完全独立了。虽然不是很理解这个具体是怎么实现的，不过有点类似python中的yield函数, 也是在调用函数之后有一个暂存局部变量的机制（复习下yield中的中断）。然后下次调用函数会从上一次的状态开始。
而引用捕获则将参数和lambda表达式绑定在一起，会随着表达式的修改而修改。
-
指定lambda的返回类型：
如果lambda的函数体部分不是只包含单一的return语句，除了return语句还包含任何其他语句，则编译器假定此lambda返回void。故这种情况下要指明返回类型。
Fig. 2 指定lambda表达式的返回类型
10.3.2 参数绑定
lambda表达式虽然好用，但是适用于只有一两个地方调用的场景。如果很多地方要使用相同操作，最好还是定义一个函数。这时候就要用到bind函数将普通函数处理成可以传递给算法作为谓词的形式。
接下来通过一个小练习来复习本章主要内容：
- 练习：在一个文件夹中放置了许多图像数据，格式为
img_xxx.jpg，其中xxx代表不同的数字，如img_0023.jpg,img_256.jpg。现在要求获取文件夹下的所有图片列表，对该列表按数字排序，然后将数字大于20的图像名称写入一个单独的data_test.txt.
【遗留：获取文件夹下特定文件的cpp脚本有待研究】
#include "review.h"
#include<functional> //placeholders 定义在functional中！！
#include<cctype> //string的处理方法定义在cctype头文件中！！
using namespace std;
using namespace std::placeholders;
string find_digits(string &s)
{
if (islower(s[0]))
s[0] = toupper(s[0]);
#ifndef NDEBUG
cout<<"file name: "<<s<<endl;
#endif
auto get_num = [](const char c) -> bool {if (isdigit(c)) return true;else return false;};
auto loc = stable_partition(s.begin(), s.end(), get_num);
s.erase(loc, s.end());
auto it = s.begin();
// 0013 -> 13
while(it!=s.end())
{
if (*it=='0')
//s.erase(*it);
it = s.erase(it); //返回一个指向被删元素之后元素的迭代器
else
break;
}
return s;
}
bool islarger(const string &num1, const string &num2)
{
//const char *num1_ch = num1.c_str(); //????这样会报错，不知道为啥
auto num1_ch = num1.c_str();
auto num2_ch = num2.c_str();
return atoi(num1_ch)>atoi(num2_ch); //注意：atoi接收的参数是char *，不是string. 比如atoi("1995") -> 1995; 此处输入为Const char *
}
void format_print(vector<string>::iterator i1, vector<string>::iterator i2, ostream &out=cout)
{
//格式化输出字符串到指定输出流, c++中将字符写入文件还是很方便的，只需创建输出流对象
for_each(i1, i2, [&out](const string &s){out<<"img_"<<s<<".jpg"<<endl;});
}
int main(int argc, char *argv[])
{
if (argc<3)
{
cout<<"参数数目不够！要求输入 3 个，实际输入 "<<argc<<" 个"<<endl;
exit(0);
}
ifstream in(argv[1]);
istream_iterator<string> it(in), eof;
ofstream outfile(argv[2], ofstream::app); //data_test.txt, 以append模式打开
ostream_iterator<string> out_it(outfile, "; ");
vector<string> img_list(it, eof);
cout<<"Original img_list: "<<endl;
print(img_list);
cout<<endl;
#ifndef NDEBUG
string s1 = "img_recon";
string s2 = s1 + "_0023.jpg";
s1 = find_digits(s1);
s2 = find_digits(s2);
cout<<"s1="<<s1<<endl; //s1中不含数字，返回一个空值。该空值是什么类型的对象？？
cout<<"s2="<<s2<<endl;
if (s1==" ")
cout<<"s1 == ' '";
else cout<<"s1 != \" \""<<endl; //打印双引号时需要反斜杠转义
cout<<"s1.empty(): "<<s1.empty()<<endl; //or string.size()==0;
#endif
//初步筛选出文件名
transform(img_list.begin(), img_list.end(), img_list.begin(), find_digits);
//去除名字中不包含数字的文件
auto loc_par = partition(img_list.begin(), img_list.end(), [](const string &s){return !s.empty();});
img_list.erase(loc_par, img_list.end());
//按照文件名中包含的数字大小排序
sort(img_list.begin(), img_list.end(), bind(islarger, _2, _1)); // bind调整参数顺序，将使得序列按照islarger相反的顺序排列
cout<<"按照数字大小排序之后："<<endl;
print(img_list);
//将图像文件后缀数字大于某个值的文件放入data_test.txt中
//再次调用islarger函数，不过这次相当于一个一元谓词加捕获参数的形式
string thresh_test = "20";
auto loc_test = find_if(img_list.begin(), img_list.end(), bind(islarger, _1, thresh_test));
if (loc_test == img_list.end())
cout<<"test_img not found!"<<endl;
else cout<<"*loc_test = "<<*loc_test<<endl;
cout<<endl;
//将序列后一部分输出到文件中
copy(loc_test, img_list.end(), out_it); //第一种写入方法：使用ostream_iterator + copy (无法格式化输出)
format_print(loc_test, img_list.end(), outfile); //第二种写入方法：使用for_each 格式化输出到指定输出流~
cout<<"测试文件已写入 "<<argv[2]<<endl;
img_list.erase(loc_test, img_list.end());
cout<<"去除测试数据之后："<<endl;
print(img_list);
outfile.close();
return 0;
}
网友评论