[数据结构与算法]c++primer第十章（习题解答）：泛型算法

前言

这些大部分都是自己做出来的，还有一些是参考答案写的，可供大家参考

10.1节练习

10.1:头文件algorithm中定义了一个名为count的函数，它类似find，接受一对迭代器和一个值作为参数。count返回给定值在序列中出现的次数。编写程序，读取int序列存入vector中，打印有多少个元素的值等于给定值。
答：

#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;
int main() {
    vector<int>ans{ 1,2,3,4,5,6 };
    cout << count(ans.begin(), ans.end(), 2);
    return 0;
}

10.2:重做上一题，但读取string序列存入list中
答：

#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<deque>
#include<algorithm>
#include<list>
using namespace std;
int main() {
    vector<int>ans{ 1,2,3,4,5,6 };
    list<string>list1 = { "hello","world" };
    cout << count(ans.begin(), ans.end(), 2);
    cout << count(list1.begin(), list1.end(), "hello");
    return 0;
}

10.2.1节练习

10.3：用accmulate求一个vector< int >中的元素之和
答：

#include<iostream>
#include<string>
#include<stack>
#include<vector>
#include<deque>
#include<algorithm>
#include<list>
#include<numeric>
using namespace std;
int main() {
    vector<int>ans{ 1,2,3,4,5,6 };
    cout << accumulate(ans.begin(), ans.end(),0);
    
    return 0;
}

10.4：假定v是一个vector< double >，那么调用accumulate(v.cbegin(),v.cend(),0)有何错误（如果存在的话）？
答：c.begin()是尾后迭代器，没有指向元素
10.5:在本节对名册（roster)调用equal的例子中，如果两个名册中保存的都是c风格字符串而不是string，会发生什么？
答: 正常运行
10.6：编写程序，使用fill_n将一个序列中的int值都设为0
答：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    vector<int> ans(10);
    fill_n(ans.begin(), ans.size(), 0);
    for(auto num:ans)
        cout << num << " ";
    getchar();
    getchar();
    return 0;
}

10.7：下面的程序是否错误？如果有，请改正

(a)vector<int>vec;list<int>lst;it i;
while(cin>>i)
	lst.push_back(i);
copy(lst.cbegin(),lst.cend(),vec.begin());
(b)vector<int>vec;
vec.reserve(10);
fill_n(vec.begin(),10,0);

答：(a):copy只负责复制，不负责申请空间，这样有误，改正：

#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
int main(){
    vector<int> ans = {1, 2, 3};
    vector<int> ret;
    copy(ans.begin(), ans.end(), back_inserter(ret));
    for(auto num:ret)
        cout << num<< " ";
    getchar();
    getchar();
    return 0;
}

(b):reserve仅影响vector预先分配多大的内存，并不是已经分配内存。改正：

#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
int main(){
    vector<int> ans = {1, 2, 3};
    vector<int> ret;
    copy(ans.begin(), ans.end(), back_inserter(ret));
    for(auto num:ret)
        cout << num<< " ";
    cout << endl;
    vector<int> vec;
    vec.resize(10);
    fill_n(vec.begin(), 10, 10);
    for(auto num:vec)
        cout << num << " ";
    getchar();
    getchar();
    return 0;
}

10.8：本节提到过，标准库算法不会改变他们所操作的容器的大小。为什么使用back_inserter不会使这断言失效。
答：back_inserter相当于push_back操作类似的效果

10.2.3节练习

10.9:实现你自己的elimDups.测试你自己的程序，分别在读取输入后，调用unique后以及调用erase后打印vector中的内容。
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
void elimDups(vector<string>&word){
    sort(word.begin(), word.end());
    auto end_iter=unique(word.begin(),word.end());
    word.erase(end_iter, word.end());
}
int main(){
    vector<string> str = {"a", "a", "b", "b", "c"};
    elimDups(str);
    for(auto s:str)
        cout << s << " ";
    getchar();
    getchar();
    return 0;
}

10.10：你认为算法不改变容器的原因是什么？
答：其算法根本不该知道容器的存在

10.3.1节练习

10.11：编写程序，使用stable_sort和isShorter将传递给你的elimDups版本的vector排序，打印vector中的内容，验证你的正确性。
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include<iterator>
using namespace std;
void elimDups(vector<string>&word){
    sort(word.begin(), word.end());
    auto end_iter=unique(word.begin(),word.end());
    word.erase(end_iter, word.end());
}
bool isShorter(const string &a,const string &b){
    return a.size() < b.size();
}
int main(){
    vector<string> str = {"aa", "aaaa", "b", "b", "c"};
    elimDups(str);
    for(auto s:str)
        cout << s << " ";
    cout << endl;
    stable_sort(str.begin(),str.end(), isShorter);
    for(auto s:str)
        cout << s << " ";
    getchar();
    getchar();
    return 0;
}

10.12：编写一个名为compareIsbn的函数，比较两个Sales_data对象的isbn成员。使用这个函数排序一个保存Sales_data对象的vector.
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include"sales_data.h"
using namespace std;
bool compareIsbn(sales_data a,sales_data b){
    return a.isbn()<b.isbn();
}
int main(){
   sales_data book1("aook",1,2);
   sales_data book2("gs",3,4);
   sales_data book3("bes",23,4);
   vector<sales_data>ans={book1,book2,book3};
   stable_sort(ans.begin(),ans.end(),compareIsbn);
   for(auto num:ans)cout<<num.isbn()<<" ";
   return 0;
}

10.13:标准库定义了一个名为partition的算法，它接受一个谓词，对容器中内容进行划分，使得谓词为true的值会被排到容器中的前半部分，而使谓词为false的值会被排到后半部分。算法返回一个迭代器，指向最后一个使谓词为true的元素之后的位置。编写程序，接受一个bool值，指出string是否有5个或者更多字符。使用此函数划分words。打印出长度大于等于5的元素。
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include"sales_data.h"
using namespace std;
bool com(string s){
    return s.size()<5;
}
int main(){
   vector<string>ans={"1234","82347218","237891756","12","2341"};
   vector<string>::iterator iter=partition(ans.begin(),ans.end(),com);
   for(vector<string>::iterator ie=iter;ie!=ans.end();++ie)cout<<*ie<<endl;
   return 0;
}

10.3.2节练习

10.14：编写一个lambda，接受两个int，返回它们的和
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include"sales_data.h"
using namespace std;
int main(){
   int a=1,b=3;
   auto f=[](const int a,const int b){return a+b;};
   cout<<f(a,b)<<endl;
   return 0;
}

10.15:编写一个lambda，捕获它所在的函数的int，并接受一个int参数。lambda应该返回捕获的int和int的值。
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include"sales_data.h"
using namespace std;
void add1(int a){
    auto f=[a](int b){return a+b;};
    cout<<f(2)<<endl;
}
int main(){
   int a=1,b=3;
   add1(1);
   return 0;
}

10.16：使用lambda编写自己的版本的biggies
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include"sales_data.h"
using namespace std;
void add1(int a){
    auto f=[a](int b){return a+b;};
    cout<<f(2)<<endl;
}
void elimDups(vector<string>&words){
    sort(words.begin(),words.end());
}
string make_plural(int count,string s1,string s2){
    if(count>1)return s1+s2;
    else return s1;
}
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;
    cout<<count<<" "<<make_plural(count,"word","s")<<" of length "<<sz<<" or longer "<<endl;
    for_each(wc,words.end(),[](const string &s){cout<<s<<" ";});
    cout<<endl;
}
int main(){
   vector<string>words={"hello","hwllos slfj"};
   biggies(words,words.size());
   return 0;
}

10.17：重写一个345页的程序，在对sort的调用中使用lambda来代替函数compareIsbn
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include"sales_data.h"
using namespace std;
int main(){
   vector<string>words={"hello","awllos slfj"};
   stable_sort(words.begin(),words.end(),[](const string&a,const string&b){return a<b;});
   for(auto num:words)cout<<num<<endl;
   return 0;
}

10.18:重写biggies,用partition代替find_if。
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include"sales_data.h"
using namespace std;
void elimDups(vector<string>&words){
    sort(words.begin(),words.end());
}
string make_plural(int count,string s1,string s2){
    if(count>1)return s1+s2;
    else return s1;
}
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=partition(words.begin(),words.end(),[sz](const string&a){return a.size()>=sz;});
   auto count=wc-words.begin();
    cout<<count<<" "<<make_plural(count,"word","s")<<" of length "<<sz<<" or longer "<<endl;
    for_each(words.begin(),wc,[](const string &s){cout<<s<<" ";});
    cout<<endl;
}
int main(){
   vector<string>words={"hello","awllos slfj"};
   biggies(words,words.size());
   stable_sort(words.begin(),words.end(),[](const string&a,const string&b){return a<b;});
   for(auto num:words)cout<<num<<endl;
   return 0;
}

10.19：用stable_partition重写上一题的程序，与stable_sort类似，在划分后的序列中维持原有序列的顺序。
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include"sales_data.h"
using namespace std;
void elimDups(vector<string>&words){
    sort(words.begin(),words.end());
}
string make_plural(int count,string s1,string s2){
    if(count>1)return s1+s2;
    else return s1;
}
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=stable_partition(words.begin(),words.end(),[sz](const string&a){return a.size()>=sz;});
    auto count=wc-words.begin();
    cout<<count<<" "<<make_plural(count,"word","s")<<" of length "<<sz<<" or longer "<<endl;
    for_each(words.begin(),wc,[](const string &s){cout<<s<<" ";});
    cout<<endl;
}
int main(){
   vector<string>words={"hello","awllos slfj"};
   biggies(words,words.size());
   stable_sort(words.begin(),words.end(),[](const string&a,const string&b){return a<b;});
   for(auto num:words)cout<<num<<endl;
   return 0;
}

10.3.3节练习

10.20：标准库定义了一个名为count_if的算法。类似find_if,此函数接受一对迭代器，表示一个输入范围，还接受一个谓词，会对输入范围每个元素执行。count_if返回一个计数值，表示谓词有多少此为真。使用count_if重写我们的程序中统计有多少单词长度超过6的部分
答:

#include<iostream>
#include<vector>
#include<algorithm>
#include"sales_data.h"
using namespace std;
bool com(string s){
    return s.size()>6;
}
int main(){
   vector<string>words={"hello","awllos slfj","adf"};
   cout<<count_if(words.begin(),words.end(),com);
   return 0;
}

10.21:编写一个lambda，捕获一个int变量，并递减变量值，直至它变为0.一旦变量变为0，再调用lambda应该不再递减变量。lambda应该返回一个bool值，指出捕获的变量是否为0
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include"sales_data.h"
using namespace std;
bool com(string s){
    return s.size()>6;
}
void f(int &b){
    auto fun=[&b]()->bool {
        if(b){
        while(b)
            --b;
        return true;
    }else
        return false;
    };
    cout<<fun()<<endl;
}
int main(){
   //vector<string>words={"hello","awllos slfj","adf"};
   //cout<<count_if(words.begin(),words.end(),com);
   int b=5;
   f(b);
   f(b);
   //cout<<f(b)<<endl;
   return 0;
}

10.3.4节练习

10.22：重写统计长度小于等于6单词数量的程序，使用函数代替lambda
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include"sales_data.h"
using namespace std;
using namespace std::placeholders;
bool com(string s){
    return s.size()>6;
}
int main(){
   vector<string>words={"hello","I am a student","yes ys s"};
   cout<<count_if(words.begin(),words.end(),bind(com,_1));
   return 0;
}

10.23:bind接受几个参数？
答：小于等于其绑定的函数的参数个数
10.24:给定一个string,使用bind和check_size在一个int的vector中查找第一个大于string长度的值。
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include"sales_data.h"
using namespace std;
using namespace std::placeholders;
bool check_size(const string &s,string::size_type sz){
    return s.size()>=sz;
}
int main(){
   vector<int>num={1,2,3,4,5,6};
   string s="hello";
   for(auto nums:num){
        auto check=bind(check_size,_1,nums);
        if(!check(s)){
            cout<<nums<<endl;
            break;
        }
   }
   return 0;
}

10.25:在249页中编写一个使用partition的biggies版本。使用check_size和·bind重写这个函数。
答：

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include"sales_data.h"
using namespace std;
using namespace std::placeholders;
void elimDups(vector<string>&words){
    sort(words.begin(),words.end());
}
string make_plural(int count,string s1,string s2){
    if(count>1)return s1+s2;
    else return s1;
}
bool check_size(const string s,string::size_type sz){
    return s.size()>sz;
}
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 check=bind(check_size,_1,sz);
    int count=0;
    for(auto num:words){
        if(check(num))++count;
    }
    cout<<count<<" "<<make_plural(count,"word","s")<<" of length "<<sz<<" or longer "<<endl;
    cout<<endl;
}
int main(){
   vector<string>words={"hello","awllos slfj"};
   biggies(words,6);
   return 0;
}

10.4.1节练习

10.26:解释三种插入迭代器的不同之处？
答：不同之处在于插入的位置不同
10.27:除了unique之外，标准库还定义了名为unique_copy的函数，它接受第三个迭代器，表示拷贝不重复元素的目的位置。编写一个程序，使用unique_copy将一个vector中不重复的元素拷贝到一个初始化为空的list中
答:

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<list>
#include"sales_data.h"
using namespace std;
int main(){
   vector<string>words={"hello1","hello1","hello2","hello2"};
   list<string>ans;
   unique_copy(words.begin(),words.end(),back_inserter(ans));
   for(auto num:ans){
        cout<<num<<" ";
   }
   return 0;
}

10.28:一个vector中保存1到9，将其拷贝到三个其他容器中。分别使用inserter、back_inserter和front_inserter将元素添加到三个容器中。对每种inserter,估计输出序列是怎样的，运行程序验证你的估计是正确的。
答：

#include<iostream>
#include<iterator>
#include<vector>
#include<algorithm>
#include<functional>
#include<list>
#include"sales_data.h"
using namespace std;
int main(){
   vector<int>nums={1,2,3,4,5,6,7,8,9};
   vector<int>nums1,nums2;
   list<int>nums3;
   copy(nums.begin(),nums.end(),inserter(nums1,nums1.begin()));
   copy(nums.begin(),nums.end(),back_inserter(nums2));
   copy(nums.begin(),nums.end(),front_inserter(nums3));
   for(int i=0;i<nums.size();++i){
        cout<<nums1[i]<<" "<<nums2[i]<<" "<<endl;
   }
   for(auto num:nums3)cout<<num<<" ";
   return 0;
}

10.4.2节练习

10.29:编写程序，使用流迭代器读取一个文本文件，存入一个vector中的string里

#include<iostream>
#include<fstream>
#include<iterator>
using namespace std;
int main(){
    ifstream file("E:\\text.txt");
    istream_iterator<string>init_it(file);
    istream_iterator<string>eof;
    while(init_it!=eof)cout<<*init_it++<<" ";
    return 0;
}

10.30:使用流迭代器、sort和copy从表准输入中读取一个整数序列，将其排序，并将其结果写到标准出

#include<iostream>
#include<iterator>
#include<vector>
using namespace std;
int main(){
    istream_iterator<int>iter(cin),eof;
    vector<int>num(iter,eof);
    ostream_iterator<int>out(cout," ");
    copy(num.begin(),num.end(),out);
    return 0;

}

10.31:修改上一题的程序，使其只打印不重复的元素。你的程序应该使用unique_copy
答：

#include<iostream>
#include<iterator>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    istream_iterator<int>iter(cin),eof;
    vector<int>num(iter,eof);
    sort(num.begin(),num.end());
    ostream_iterator<int>out(cout," ");
    unique_copy(num.begin(),num.end(),out);
    return 0;

}

10.32：重写1.6节书店程序，使用一个vector保存交易记录，使用不同的算法完成处理。使用sort和compareIsbn函数来排序交易记录，然后使用find和accmulate求和

#include<iostream>
#include<algorithm>
#include<vector>
#include<iterator>
#include"Sales_item"
using namespace std;
int main(){
	vector<Sales_item>vs;
istream_iterator<Sales_item>in_iter(cin);
istream_iterator<Sales_item>eof;
vs(in_iter,eof);
if(vs.empty()){
	cerr<<"No data"<<endl;
	return -1;
}
sort(vs.begin(),vs.end(),compareIsbn);
auto l=vs.begin();
while(l!=vs.end()){
	auto item=*l;
	auto r=find_if(l+1,vs.end(),[item](const Sales_item &item1){return item1.isbn()!=item.isbn();}
cout<<accumulate(l+1,r,item)<<endl;
l=r;
}
return 0;
}

10.33:编写程序，接受三个参数：一个输入文件和两个输入文件的文件名。输入文件保存的应该是整数，使用istream_iterator读取输入文件。使用ostream_iterator将奇数写入第一个输入文件，每个值之后都跟一个空格。将偶数写入到第二个输入文件，每个值都独占一行。

#include<iostream>
#include<iterator>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
void f(ifstream& in_file,const char* out_file1,const char* out_file2){
    istream_iterator<int>iter(in_file),eof;
    ofstream file1(out_file1);
    ofstream file2(out_file2);
    ostream_iterator<int>out1(file1," ");
    ostream_iterator<int>out2(file2,"\n");
    vector<int>nums(iter,eof);
    for(auto num:nums){
        if(num&1){
            *out1++=num;
        }else{
            *out2++=num;
        }
    }
}
int main(){
    ifstream in("E:\\text.txt");
   // string b="E:\\a.txt",c="E:\\c.txt";
    f(in,"E:\\a.txt","E:\\c.txt");
    return 0;

}

10.4.3节练习

10.34：使用reverse_iterator逆序打印一个vector
答：

#include<iostream>
#include<iterator>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
   vector<int>num={1,2,3,4,5};
   for(auto iter=num.rbegin();iter!=num.rend();iter++)cout<<*iter<<" ";
    return 0;

}

10.35:使用普通迭代器逆序打印一个vector
答：

#include<iostream>
#include<iterator>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
   vector<int>num={1,2,3,4,5};
   //for(auto iter=num.rbegin();iter!=num.rend();iter++)cout<<*iter<<" ";
   for(auto iter=num.cend();iter!=num.cbegin();)cout<<*(--iter)<<" ";
    return 0;

}

10.36:使用find在一个int的list中查找一个最后值为0的元素
答：

#include<iostream>
#include<iterator>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
   vector<int>num={1,2,0,3,4,5,0,0,0,0};
   //for(auto iter=num.rbegin();iter!=num.rend();iter++)cout<<*iter<<" ";
   //for(auto iter=num.cend();iter!=num.cbegin();)cout<<*(--iter)<<" ";
    auto list=find(num.rbegin(),num.rend(),0);
    int p=1;
    list++;
    for(auto l=num.begin();l!=list.base();l++){
        p++;
    }
    cout<<p<<endl;
    return 0;

}

10.37：给定一个包含10个元素的vector,将位置3到7之间的元素按排序拷贝到一个list中
答：

#include<iostream>
#include<iterator>
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
   vector<int>num={1,2,0,3,4,5,0,0,0,0};
   //for(auto iter=num.rbegin();iter!=num.rend();iter++)cout<<*iter<<" ";
   //for(auto iter=num.cend();iter!=num.cbegin();)cout<<*(--iter)<<" ";
    //auto list=find(num.rbegin()+3,num.rend(),0);
    //int p=1;
    //list++;
    for(auto l=num.rbegin()+3;l!=num.rend()-2;l++){
        cout<<*l<<" ";
    }
  //  cout<<p<<endl;
    return 0;

}

10.5.1节练习

10.38：列出5个迭代器，以及每类迭代器支持的操作
答
输入迭代器：只读，不写，单遍扫描，还支持相等运算符，解引用运算符和箭头运算符
输出迭代器：只写，不读，单遍扫描，只能递增，支持解引用运算符
前向迭代器：可读写，多遍扫描，只能递增，支持所有输入，输出迭代器的操作
双向迭代器：可读写，多遍扫描，可递增递减，支持所有前向迭代器操作
随机访问迭代器：可读写，多遍扫描，支持全部迭代器运算，处理上述迭代器类型支持的操作外，还有比较两个迭代器相对位置的关系运算符。
10.39list上的迭代器输入哪一类？vector
答：
list上是双向迭代器，vector上是随机访问迭代器
10.40：你认为copy要求支持那类迭代器？reverse和unique
答：
输入迭代器，双向迭代器，前向迭代器
10.41：仅根据算法和参数的名字，描述下面标准库执行什么操作？

replace(beg,end,old_val,new_old)
replace_if(beg,end,pred,new_val)
replace_copy(beg,end,dest,old_val,new_val)
replace_copy_if(beg,end,dest,pred,new_val)

答：1.将范围[beg,end)间值等于old_val的元素替换为new_val
2.将范围[beg,end)间满足谓词pred的元素替换为new_val
3.将范围[beg,end)间的元素拷贝到目的序列dest中，将其中值等于old_val的元素替换为new_val
4.将范围为[beg,end)间的元素拷贝到目的序列dest中，将其中满足谓词的元素替换为new_val
10.42:使用list代替vector重新实现343页的去除重复单词的程序
答：

#include<iostream>
#include<iterator>
#include<fstream>
#include<vector>
#include<algorithm>
#include<list>
using namespace std;
void elimDups(list<int>&words){
    words.sort();
    auto end_unique=unique(words.begin(),words.end());
    words.erase(end_unique,words.end());
}
int main(){
   list<int>num={1,2,0,3,4,5,0,0,0,0};
   elimDups(num);
   for(auto nums:num)cout<<nums<<" ";
   //for(auto iter=num.rbegin();iter!=num.rend();iter++)cout<<*iter<<" ";
   //for(auto iter=num.cend();iter!=num.cbegin();)cout<<*(--iter)<<" ";
    //auto list=find(num.rbegin()+3,num.rend(),0);
    //int p=1;
    //list++;
    /*for(auto l=num.rbegin()+3;l!=num.rend()-2;l++){
        cout<<*l<<" ";
    }*/

  //  cout<<p<<endl;
    return 0;

}