首页 > 代码库 > 《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章 泛型算法 读书笔记 习题答案