首页 > 代码库 > 《C++primer》v5 第10章 泛型算法 读书笔记 习题答案

《C++primer》v5 第10章 泛型算法 读书笔记 习题答案

10.1

using namespace std;int main(){    vector<int> vec;    int a;    cin>>a;    int v;    while(cin>>v)        vec.push_back(v);    cout<<a<<" : "<<count(vec.begin(),vec.end(),a)<<endl;    return 0;}

10.2

using namespace std;int main(){    list<string> l;    string a;    cin>>a;    string v;    while(cin>>v)        l.push_back(v);    cout<<a<<" : "<<count(l.begin(),l.end(),a)<<endl;    return 0;}

10.3

#include<numeric>using namespace std;int main(){    vector<int> vec;    int sum=100;    int a;    while(cin>>a)        vec.push_back(a);    sum=accumulate(vec.cbegin(),vec.cend(),0);    cout<<sum<<endl;    return 0;}

该操作需要该元素类型定义+运算。

10.4

#include<numeric>using namespace std;int main(){    vector<double> vec;    double sum=0;    double a;    while(cin>>a)        vec.push_back(a);    cout<<accumulate(vec.cbegin(),vec.cend(),0)<<endl;    return 0;}

输入

1.5

2

将得到3

原因是第三个参数是int的,因此每个元素都被转化成了int。

正解:

#include<numeric>using namespace std;int main(){    vector<double> vec;    double sum=0;    double a;    while(cin>>a)        vec.push_back(a);    cout<<accumulate(vec.cbegin(),vec.cend(),0.0)<<endl;    return 0;}

10.5

编译错误。因为c风格的字符串没有重载==

10.6

算法永远不会执行容器操作,永远不会直接改变容器大小。

using namespace std;int main(){    vector<int> vec(10,5);    fill_n(vec.begin(),vec.size(),0);    for(auto i:vec)        cout<<i<<endl;    return 0;}

向输入范围写入元素,最多写入和给定序列一样多的元素。

10.7

(a)算法不会改变容器大小。此处要求vec至少和lst一样大。显然这样是不合规定的。

(b)reserve仅影响容器容纳元素的大小,不改变当前容器内元素的个数。故这里vec还是空的,下面的fill_n中没有10个元素。而且这个错误是灾难的!

10.8

back_inserter是迭代器,改变容器大小是它实现的并非算法。

10.9

using namespace std;int main(){    vector<string> vec;    string s;    while(cin>>s)        vec.push_back(s);    sort(vec.begin(),vec.end());    auto end_unique=unique(vec.begin(),vec.end());    for(auto s:vec)        cout<<s<<endl;    cout<<"==="<<endl;    vec.erase(end_unique,vec.end());    for(auto s:vec)        cout<<s<<endl;    return 0;}

10.10

标准库对迭代器进行操作而非容器。

10.11

using namespace std;bool isShorter(const string &s1,const string &s2){    return s1.size()<s2.size();}void elimDups(vector<string> &word){    stable_sort(word.begin(),word.end(),isShorter);    auto end_unique=unique(word.begin(),word.end());    word.erase(end_unique,word.end());}int main(){    vector<string> vec;    string s;    while(cin>>s)        vec.push_back(s);    elimDups(vec);    for(auto s:vec)        cout<<s<<endl;    return 0;}

10.12

using namespace std;struct Sales_data{    string bookNo;//isbn编号    unsigned units_sold=0;//该书的销量    double revenue=0.0;//该书的总销售收入    Sales_data(const string &s):bookNo(s),units_sold(0),revenue(0){}    string isbn()const {return bookNo;}    Sales_data& combine(const Sales_data &rhs)    {        units_sold+=rhs.units_sold;        revenue+=rhs.revenue;        return *this;    }    double avg_price() const    {        if(units_sold)            return revenue/units_sold;        else            return 0;    }};bool compareIsbn(const Sales_data &a,const Sales_data &b){    return a.isbn()<b.isbn();}int main(){    string s;    vector<Sales_data> vec;    while(cin>>s)        vec.push_back(Sales_data(s));    sort(vec.begin(),vec.end(),compareIsbn);    for(auto i:vec)        cout<<i.isbn()<<endl;    return 0;}

10.13

#include<algorithm>using namespace std;bool part(const string& s){    return s.size()>=5;}int main(){    string s;    vector<string> vec;    while(cin>>s)        vec.push_back(s);    auto end_true=partition(vec.begin(),vec.end(),part);    for(auto i=vec.begin();i!=end_true;++i)        cout<<*i<<endl;    return 0;}

partition接受一对迭代器和一个一元谓词。根据跟一元谓词进行划分,使其为true的位于前半部分,false的位于后半部分。返回一个指向最后一个为true的元素的后一个位置的迭代器。

 

find_if将返回第一个使得谓词为true的位置的迭代器。

int main(){    vector<string> vec;    string s;    while(cin>>s)        vec.push_back(s);    int sz=5;    auto end_true=find_if(vec.begin(),vec.end(),[sz](const string &s){return s.size()>=sz;});    for(auto it=vec.begin();it!=end_true;++it)        cout<<*it<<endl;    return 0;}

10.14

    auto f=[](const int &a,const int &b){return a+b;};

10.15

    auto f=[a](const int &b){return a+b;};

10.16

void elimDups(vector<string> &word){    stable_sort(word.begin(),word.end());    auto end_unique=unique(word.begin(),word.end());    word.erase(end_unique,word.end());}void biggies(vector<string> &words,vector<string>::size_type sz){    elimDups(words);    stable_sort(words.begin(),words.end(),[](const string &a,const string &b){return a.size()<b.size();});    auto wc=find_if(words.begin(),words.end(),[sz](const string &a){return a.size()>=sz;});    auto count=words.end()-wc;    for_each(wc,words.end(),[](const string &s){cout<<s<<" ";});    cout<<endl;}int main(){    vector<string> vec;    string s;    while(cin>>s)        vec.push_back(s);    biggies(vec,5);    return 0;}

10.17

int main(){    string s;    vector<Sales_data> vec;    while(cin>>s)        vec.push_back(Sales_data(s));    sort(vec.begin(),vec.end(),[](const Sales_data &a,const Sales_data &b )    {        return a.isbn()<b.isbn();    });    for(auto i:vec)        cout<<i.isbn()<<endl;    return 0;}

10.18

#include<algorithm>using namespace std;void elimDups(vector<string> &word){    stable_sort(word.begin(),word.end());    auto end_unique=unique(word.begin(),word.end());    word.erase(end_unique,word.end());}void biggies(vector<string> &words,vector<string>::size_type sz){    elimDups(words);    auto wc=partition(words.begin(),words.end(),[sz](const string &a)    {        return a.size()>=sz;    });    for_each(words.begin(),wc,[](const string &s)    {        cout<<s<<" ";    });    cout<<endl;}int main(){    vector<string> vec;    string s;    while(cin>>s)        vec.push_back(s);    biggies(vec,5);    return 0;}

10.19

#include<algorithm>using namespace std;void elimDups(vector<string> &word){    stable_sort(word.begin(),word.end(),[](const string &a,const string &b){return a.size()>b.size();});    auto end_unique=unique(word.begin(),word.end());    word.erase(end_unique,word.end());}void biggies(vector<string> &words,vector<string>::size_type sz){    elimDups(words);    auto wc=stable_partition(words.begin(),words.end(),[sz](const string &a)    {        return a.size()>=sz;    });    for_each(words.begin(),wc,[](const string &s)    {        cout<<s<<" ";    });    cout<<endl;}int main(){    vector<string> vec;    string s;    while(cin>>s)        vec.push_back(s);    biggies(vec,5);    return 0;}

10.20

int main(){    vector<string> vec;    string s;    while(cin>>s)        vec.push_back(s);    int sz=6;    int n=count_if(vec.begin(),vec.end(),[sz](const string &a){return a.size()>=sz;});    cout<<n<<endl;    return 0;}

10.21

    int v=10;    auto f=[&v] {return v==0?true:v--==0;};    for(int i=0; i<=10; ++i)        cout<<f()<<endl;

注意要用引用捕获

10.22

lambda适用于只在一两个地方调用的简单操作,对于复杂操作应该使用函数。而这些算法只能接受一元或二元谓词,对于有多个参数的函数无法调用。因此引入新标准的bind函数来解决传递长度参数的问题。它接受一个可调用对象,生成一个新的可调用对象来适应原对象的参数列表。

bool check_size(const string &a,int sz){    return a.size()<=sz;}int main(){    vector<string> vec;    string s;    while(cin>>s)        vec.push_back(s);    int sz=6;    int n=count_if(vec.begin(),vec.end(),bind(check_size,_1,sz));    cout<<n<<endl;    return 0;}

auto g=bind(可调用函数名f,a,b,_2,c,_1)

a表示f的第一个参数绑定到a上,b表示f的第二个参数绑定到b上,c表示f的第四个参数绑定到b上。

_2表示新可调用对象g将自己的第2个参数作为f的第三个参数传递给f。

_1表示新可调用对象g将自己的第1个参数作为f的第五个参数传递给f。

占位符在using namespace placeholders;这个命名空间内。

bind在#include<functional>这个头文件内。

10.23

bind接受的参数等于原可调用对象接受参数个数+1。

10.24

bool check_size(int a,int sz){    return a>sz;}int main(){    string s;    cin>>s;    vector<int> vec;    int v;    while(cin>>v)        vec.push_back(v);    auto i=find_if(vec.begin(),vec.end(),bind(check_size,_1,s.size()));    cout<<*i<<endl;    return 0;}

10.25

#include<algorithm>using namespace std;void elimDups(vector<string> &word){    stable_sort(word.begin(),word.end());    auto end_unique=unique(word.begin(),word.end());    word.erase(end_unique,word.end());}bool part(const string &a,int sz){     return a.size()>=sz;}void biggies(vector<string> &words,vector<string>::size_type sz){    elimDups(words);    auto wc=partition(words.begin(),words.end(),bind(part,_1,sz));    for_each(words.begin(),wc,[](const string &s)    {        cout<<s<<" ";    });    cout<<endl;}int main(){    vector<string> vec;    string s;    while(cin>>s)        vec.push_back(s);    biggies(vec,5);    return 0;}

 10.26

front_inserter创建一个使用push_front的迭代器

back_inserter创建一个使用push_back的迭代器

inserter接受两个参数,第一个为容器,第二个为迭代器,元素将被插入到给定迭代器表示的元素之前。

10.27

#include<algorithm>using namespace std;void solve(vector<int> &word,list<int> &l){    stable_sort(word.begin(),word.end());    auto end_pos=unique_copy(word.begin(),word.end(),l.begin());    for(auto i=l.begin();i!=end_pos;++i)        cout<<*i<<endl;}int main(){    vector<int> vec;    int a;    while(cin>>a)        vec.push_back(a);    list<int> l(vec.size());    solve(vec,l);    return 0;}

注意算法不改变容器大小,因此一定要预先分配好list的大小。

或者这样。

using namespace std;void solve(vector<int> &word,list<int> &l){    stable_sort(word.begin(),word.end());    auto end_pos=unique_copy(word.begin(),word.end(),back_inserter(l));    for(auto i=l.begin();i!=l.end();++i)        cout<<*i<<endl;}int main(){    vector<int> vec;    int a;    while(cin>>a)        vec.push_back(a);    list<int> l;    solve(vec,l);    return 0;}

10.28

int main(){    vector<int> vec;    for(int i=1; i<10; ++i)        vec.push_back(i);    deque<int> a,b,c;    copy(vec.begin(),vec.end(),front_inserter(a));    copy(vec.begin(),vec.end(),back_inserter(b));    copy(vec.begin(),vec.end(),inserter(c,c.begin()));    cout<<"======="<<endl;    for(auto i:a)        cout<<i<<endl;    cout<<"======="<<endl;    for(auto i:b)        cout<<i<<endl;    cout<<"======="<<endl;    for(auto i:c)        cout<<i<<endl;    return 0;}

inserter中给定的迭代器在传入后就不会变了,即始终是该位置前插入。

10.29

必须使用的头文件#include<iterator>

int main(){    ifstream in("read.txt");    istream_iterator<string> sit(in),seof;    vector<string> vec;    while(sit!=seof)        vec.push_back(*sit++);    for(auto i:vec)        cout<<i<<endl;    return 0;}

 10.30

int main(){    istream_iterator<int> sit(cin),seof;    vector<int> vec;    while(sit!=seof)        vec.push_back(*sit++);    sort(vec.begin(),vec.end());    ostream_iterator<int> oit(cout, " ");    copy(vec.begin(),vec.end(),oit);    return 0;}

10.31

int main(){    istream_iterator<int> sit(cin),seof;    vector<int> vec;    while(sit!=seof)        vec.push_back(*sit++);    sort(vec.begin(),vec.end());    ostream_iterator<int> oit(cout, " ");    unique_copy(vec.begin(),vec.end(),oit);    return 0;}

10.32

暂略

10.33

int main(){    ifstream in("read.txt");    ofstream out1("out1.txt"),out2("out2.txt");    istream_iterator<int> it(in),eof;    ostream_iterator<int> ot1(out1," "),ot2(out2,"\n");    while(it!=eof)    {        if(*it%2)            ot1=*it;        else            ot2=*it;        ++it;    }    return 0;}

10.34

int main(){    vector<int> vec{1,3,5,2,6};    for(auto it=vec.rbegin();it!=vec.rend();++it)        cout<<*it<<endl;    return 0;}

10.35

int main(){    vector<int> vec{1,3,5,2,6};    for(auto it=vec.end()-1;it>=vec.begin();--it)        cout<<*it<<endl;    return 0;}

10.36

int main(){    vector<int> vec{1,3,0,5,2,6,0,5};    auto pos=find(vec.rbegin(),vec.rend(),0);    cout<<(pos.base()-vec.begin())<<endl;    return 0;}

对于find传入反向迭代器将返回一个反向迭代器,使用.base则返回它对应的普通迭代器。

10.37

int main(){    vector<int> vec{1,2,3,4,5,6,7,8,9,10};    list<int> l;    copy(vec.rbegin()+3,vec.rbegin()+8,back_inserter(l));    for(auto i:l)        cout<<i<<endl;    return 0;}

10.38

输入迭代器:只读不写,单遍扫描,只能递增

输出迭代器:只写不读,单遍扫描,只能递增

前向迭代器:可读写,多遍扫描,只能递增

双向迭代器:可读写,多遍扫描,可递增可递减

随机访问迭代器:可读写,多遍扫描,支持全部迭代器运算

10.39

list的迭代器属于双向迭代器

vector的迭代器属于随机访问迭代器

10.40

copy要求输出迭代器

reverse要求双向迭代器

unique要求前向迭代器?

10.41

在beg,end范围内用newVal取代oldVal

在beg,end范围内对于使pred为真的元素替换为newVal

在beg,end范围内将其拷贝到以dest为首地址的容器中,并用newVal取代oldVal

在beg,end范围内将其拷贝到以dest为首地址的容器中,对于使pred为真的元素替换为newVal

对于第四个函数的测试:

int main(){    vector<int> vec{1,2,3,4,5,6,7,8,9,10};    vector<int> aa;    replace_copy_if(vec.begin(),vec.end(),back_inserter(aa),[](int a){return a>=4;},99);    for(auto i:aa)        cout<<i<<endl;    return 0;}

10.42

using namespace std;void solve(list<int> &l){    l.sort();    auto end_pos=unique(l.begin(),l.end());    l.erase(end_pos,l.end());    for(auto i=l.begin();i!=l.end();++i)        cout<<*i<<endl;}int main(){    list<int> l;    int a;    while(cin>>a)        l.push_back(a);    solve(l);    return 0;}

 

《C++primer》v5 第10章 泛型算法 读书笔记 习题答案