C++Primer笔记——第十章：泛型算法

作者: 吃远 | 来源:发表于2018-12-14 15:45 被阅读0次

一、本章学习总结

【待总结】

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<<"~";});
 }

注意：
1. unique算法返回一个指向不重复区域之后一个位置的迭代器。（一般不用关心该迭代器之后位置的值。因为不同的编译器有不同处理方法。比如我的可能是通过交换的方式。）
1. unique之后要删除序列后半部分，涉及到容器元素删减操作，还是需要用容器自己的成员函数。
1. stable_sort先整体按新的谓词进行排序，局部位置保持原来的顺序。
1. 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;
}

C++Primer笔记——第十章：泛型算法

一、本章学习总结

10.1 泛型算法的特点

10.2 初始泛型算法

10.2.1 只读算法

10.2.2 写容器元素的算法

10.2.3 重排容器元素的算法

10.3 lambda表达式和bind参数绑定

10.3.1 lambda表达式

10.3.2 参数绑定

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读