CPrimer 第11章泛型算法课后习题答案.docx

第11章-泛型算法1.algorithm头文件定义了一个名为count的函数，其功能类似于find。这个函数运用一对迭 代器和一个值做参数，返回这个值出现的次数的统计结果。编写程序读取一系列int型数据, 并将它们存储到vector对象中然后统计某个指定的值出现了多少次。/ ll.17_ll.l_int_to_vector_count.cpp :定义限制台应用程序的入口点。/#include "stdafx.h"#include <vector>#include <iostream>#include <algorithm>using namespace std;int _tmain(int argc, _TCHAR* argv)(cout « Utlnput some int numbers ( Ctrl + z to end):ntvector<int> iVec;int iVal;while ( cin » iVal)iVec.push_back( iVal);cout « "ntlnput a num to search in the iVec:cin.clear();cin »iVal;int iCnt = 0;if (iCnt = count( iVec.beginf), iVec.end(), iVal)cout« "ntThe value " « iVal « " occurs " « iCnt« " times." « endl;)system("pause");return 0;)/testing out iLstcout « "ntThe contents of iLst:nt"for (list<int>:iterator it = iLst.begin(); it != iLst.end(); +it)cout « *it « "cout« endl;vector<int> iVec;/ copy iLst's member to iVec;cout « un Using unique_copy, copy iLst's member to iVec:" « endl; unique_copy( iLst.begin(), iLst.end(), back_inserter( iVec);cout « "ntThe contents of iVec:nt"for ( vector<int>:iterator it = iVec.begin(); it != iVec.endf); +it)cout « *it « "cout« endl;system("pause");return 0;)c e: hhvhhvprogra>l 1. 18_11. 15_unique_copydebu；The contents of iLst： 1 2 3 4 100 100 5Using unique_copycopy iLstJ s nenber to iUec：The contents of iUec： 1 2 3 4 100 5 请按任意键继续.16.重写(1L3.2节第3小节)的程序，运用copy算法将一个文件的内容写到标准输出中。/ ll.20_ll.16_iostreamjertator.cpp :定义限制台应用程序的入口点。/运用copy算法将一个文件的内容写到标准输出中#include "stdafx.h"#include <iostream>#include <algorithm>#include <string>#include <iterator>#include <fstream> using namespace std;int _tmain(int argc, _TCHAR* argv)ostream_iterator<string> out_iter( cout, "n");ifstream inFile;in( "11.16.txt");if ( JinFile )cerr« " error file." « endl;return -1;)istream_iterator<string> in_ (inFile ), eof; copy( in_, eof, outjter);in()；cout« endl;system("pause");return 0;)c：' e: hhvhhvprogra> 11.2Hello buddy. This a test of11.16. dauy请按任意键继续. . . 17.运用一对istream_iterator对象初始化一个int型的vector对象。/ ll.20_ll.17_istreamjterator_vector.cpp :定义限制台应用程序的入口点。 /#include "stdafx.h"#include <iostream>#include <algorithm>#include <vector>#include <string>#include <iterator>using namespace std;int _tmain(int argc, _TCHAR* argv) (istream_iterator<int> cin_it( cin ), end;vector<int> iVec( cinjt, end );cout « "ntThe content of iVec:nt"for ( vector<int>:iterator it = iVec.begin(); it != iVec.end(); +it)cout« *it«cout« endl;system("pause");return 0; )c、e:hhvhhvprogra>11. 20_11.17* 2 3 4 5 6FzThe content of iUec：1 2 3 4 5 6情按任意键继续. . .18.编程运用istream_iterator对象从标准输入读入一些列整数。运用ostreamjterator对象将 偶数写到其次个文件，每个写入的值都存放在单独的行中。/ ll.20_ll.18_istreamjterator_ostreamjterator.cpp :定义限制台应用程序的入口点。/#include "stdafx.h"#include <iostream>#include <algorithm>#include <iterator>#include <fstream>using namespace std;int _tmain(int argc, _TCHAR* argv)(ofstream out, out;out.open( "out");out.open( "out");if ( !out 11 !out )cerr« "'t be open." « endl;return -1;)istreamjterator<int> injter( cin ), end;ostream_iterator<int> out_odd_iter( out,"");ostream_iterator<int> out_even_iter( out, "n");while (injter != end )(if ( *in_iter % 2 = 0 )*out_even_iter+ = *in_iter+;else*out_odd_iter+ = *in_iter+;)out.close();out.close();cout« endl;systemf'pause");return 0;)c、e:hhvhhvprogra>l1.1 2 3 4 5 6人Z请按任意键继续. . .t outFile_odd 记事本文件电）编辑圾）格式查看13 5t outFile_even 记事本文件9 翁辑 格式 查看219 .编写程序运用reversejterator对象以逆序输出vector容器对象的内容。/ ll.20_ll.19_reverse_iterator.cpp :定义限制台应用程序的入口点。/#include "stdafx.h"#include <iostream>#include <iterator>#include <vector>using namespace std;int _tmain(int argc, _TCHAR* argv) (int ia = 0,1, 2, 3,4);vector<int> iVec( ia, ia + 5 );for ( vector<int>:reverse_iterator rit = iVec.rbegin(); rit != iVec.rend(); +rit) (cout « *rit « ")cout« endl;system("pause");return 0;c：' e: hhvhhvprogra>4 3 2 1 0请按任意键继续. . .20 .现在，运用一般的迭代器逆序输出上题中的元素。/ 11.20_11.20_ iterator_reverse.cpp :定义限制台应用程序的入口点。 /#include "stdafx.h"#include <iostream>#include <iterator>#include <vector>using namespace std;int _tmain(int argc, _TCHAR* argv) (intia = 0,1, 2, 3,4;vector<int> iVec( ia, ia + 5 );for ( vector<int>:iterator it = iVec.end() -1; it > iVec.begin(); -it) (cout « *it « ")cout« *iVec.begin();cout« endl;system("pause");return 0;c：' e: hhvhhvprogra> 1 4 3 2 10清按任意键继续.21 .运用find在一个int型的list中需找值为0的最终一个元素。/ ll.20_ll.21Jist_find.cpp :定义限制台应用程序的入口点。/#include "stdafx.h"#include <iostream>#include <iterator>#include <list>#include <algorithm>using namespace std;int _tmain(int argc, _TCHAR* argv)int ia = l, 2, 3, 4, 0,6; list<int> iLst( ia, ia + 6 );for (list<int>:reverse_iterator rit = iLst.rbegin(); rit != iLst.rend(); +rit)cout « *rit « ")cout« endl;list<int>:reverse_iterator last_0_it = find( iLst.rbegin(), iLst.rend(), 0 );if (last_0Jt != iLst.rend()cout « "Get the last 0, it's value: " « *last_0Jt « endl; elsecout « "We can't find the last 0." « endl;cout« endl;system("pause");return 0;)c e:hhvhhvprogra>l1.20_11.6 0 4 3 2 1 Get the last itJ s ualue：0请按任意键继续. . . 22 .假设有一个存储了 10个元素的vector对象，将其中第3第7个位置上的元素以逆序复 制给list对象。/ 11.20_11.22_vector_reverseCopyToList.cpp :定义限制台应用程序的入口点。/include "stdafx.h"#include <iostream>#include <iterator>#include <list>#include <vector>using namespace std;int _tmain(int argc, _TCHAR* argv)int ia = l, 2, 3, 4, 5, 6,7, 8, 9,10 );vector<int> iVec( ia, ia + 10 );cout « "tThe original iVec's content is:n"for ( vector<int>:iterator it = iVec.begin(); it != iVec.end(); +it) cout « *it « "list<int> iLst( iVec.rbegin() + 3, iVec.rbegin() + 8 );cout « endl « "tAfter deal, list is:n"for (list<int>:iterator it = iLst.begin(); it != iLst.end(); +it)cout « *it « "cout« endl;system("pause");return 0;)3 e:hhvhhvprogra>11. 20_11. 22_vect iThe original iUecJ s content is： 123456789 10After deal, list is： 7 6 5 4 3 修按任意键继续. . 23冽出五种迭代器类型及其各自支持的操作。输入迭代器：=!=自减,* ->输出迭代器+*前向迭代器=!=*->双向迭代器=!=+*->-随机访问迭代器=!= +*-><<=>>=_+=24 .List容器拥有什么类型的迭代器？而vector呢？双向迭代器，vector拥有随机访问迭代器。25 .你认为copy算法须要运用哪种迭代器？而reverse和unique呢？ copy至少须要输入和输出迭代器； reverse算法至少须要双向迭代器； unique算法至少须要前向迭代器。26 .说明下列代码错误的缘由，指出哪些错误可以在编译时捕获。(a) string sa10;const vector<string> ( sa, sa+6 );(b) const vector<int> ivec;fill (ivec.begin(), ivec.end(), ival);(c) sort( ivec.begin(), ivec.rend();(d) sort( ivecl.begin(), ivec2.end();(a) const类型的vector<string>对象，不行以写入,错误。(b)错了，两个实参迭代器是cosnt迭代器，不能用来修改容器中的元素。(c)错了，用于算法的实参的两个迭代器必需是相同类型。(d)错了，用于算法参数的迭代器必需属于同一个迭代器。前三个错误均可以在编译时捕获。(d)不能在编译时捕获。27 .标准库定义了下面的算法：replace( beg, end, old_val, new_val);replacejf ( beg, end, pred, new_val);replace_copy( beg, end, de st, old_val, new_val);replace_copy_if ( beg, end, de st, pred, new_val);只依据这些函数的名字和形参，描述这些算法的功能。第一个：由beg和end指定的输入范围内值为old_val的元素用new_val替换。其次个：由beg和end指定的输入范围内使得谓词pred为真的元素用new_val替换。第三个：由beg和end指定的输入范围内的元素复制到dest,并将值为old_val的元素用 new_val 替换。第四个：由beg和end指定的输入范围内的元素复制到dest,并将使得谓词为真的元素用 new_val 替换。28 .假设1st是存储了 100个元素的容器，请说明下面的程序段，并修正你认为的错误。vector<int> vecl;reverse_copy (lst.begin(), lst.end(), vecl.begin();这段程序试图将1st中的元素以逆序的方式复制到vecl容器中。可能的错误为：lo vecl是一个空容器，尚未支配存储空间，可改为：vector<int> vecl(100);2o另外1st容器中存储的元素不愿定为int型。应当保证两种容器内存储的值的类型相同或 者可以进行转换。29 .用list容器取代vector重新实现节编写的解除重复单词的程序。/ ll.20_ll.29_list_wordCount.cpp :定义限制台应用程序的入口点。/#include "stdafx.h"#include <iostream>#include <list>#include <string>#include <algorithm>#include <numeric>using namespace std;bool isShorter( const string &sl, const string &s2 )return sl.size() < s2.size();bool GT4( const string &s )(return s.size() >= 4;)string make_plural( size_t i, const string &sl, const string &s2 )(return (i = 1) ? si: si + s2;)int _tmain(int argc, _TCHAR* argv)(cout « Utlnput some words to a list ( Ctrl + z to end):ntlist<string> strLst;string strVal;while ( cin » strVal) strLst.push_back( strVal);/ sortstrLst.sort();strLst.unique();list<string>:size_type wc = countjf ( strLst.begin(), strLst.end(), GT4 );cout « ,t"« wc « make_plural ( wc," word", "s") « " 4 letters or longer. *' « endl;cout « "nt Unique words:" « endl;for (list<string>:iterator it = strLst.begin(); it != strLst.end(); +it) cout « *it « "cout« endl;systemf'pause");return 0;。、e:hhvhhvprogra>l1. 20_l1. 29_list_<ordcountdebugl1Input sone words to a list < Ctrl + z to end>： hello dauv hello albert hello ZengKe4 v/ords4 letters or longer.words ：dauy helloUniqueZengKe albert懵按任意键继续.2.重复前面的程序，但是，将读入的值存储到一个string类型的list对象中。/ ll.17_ll.2_list_string_count.cpp :定义限制台应用程序的入口点。/#include "stdafx.h"#include <string>#include <list>#include <iostream>#include <algorithm> using namespace std;int _tmain(int argc, _TCHAR* argv)(cout « "tlnput some strings numbers ( Ctrl + z to end):nt list<string> strLst;string str;while ( cin » str)strLst.push_back( str);cout « "ntlnput a string to search in the strList: cin.clear();cin » str;size_t iCnt = 0;if (iCnt = count( strLst.begin(), strLst.end(), str)cout « "ntThe string '" « str« "' occurs " « iCnt « " times." « endl; ) system("pause");return 0;)c、 e:hhvhhvprogra>l1.17_11.2_1ist_string_countdebugInput sone strings numbers < Ctrl + z to end>： hello world hello dauy hello albert 人ZInput a string to search in the strList： helloThe string 9 hello 9 occurs 3 tines.请按任意键继续. . . 3.用accumulate统计vector<int>容器对象中的元素之和。/ ll.19_ll.3_accumulate_vector_int.cpp :定义限制台应用程序的入口点。 / #include "stdafx.h"#include <vector>#include <iostream>#include <algorithm>#include <numeric> using namespace std;int _tmain(int argc, _TCHAR* argv) (cout « "tlnput some int numbers ( Ctrl + z to end):nt vector<int> iVec;int iVal;while ( cin » iVal)(iVec.push_back( iVal);)cout « "ntlnput a int num for the first num: cin.clearf);cin »iVal;if (iVal= accumulate( iVec.begin(), iVec.end(), iVal)(cout « "ntThe sum of all the members and iVal is: " « iVal « endl; )system("pause");return 0;)c、 e:hhvhhvprogra>l1.19_11.3_accu>ulate_vector_inInput some int nunbers < Ctrl + z to end>： 1 2 3 4 5 6 rzInput a int nun for the first num： 10The sun of all the members and iUal is：31备按任意键继续. . .4 .假定 v 是 vector<double>类型的对象，则调用 accumulate( v.begin(), v.end(), 0 )是否有错？ 假如有的话，错在哪里？没有错，accumulate函数必需满足第三个实参的类型及容器内的意思匹配，或者可以转化为 第三个实参的类型。本题中double可以转化为int类型，但是会有较大误差。5 .对于本节调用find_first_of的例程,假如不给it加1,将会如何。(1)假如存在同时出现在两个list中的名字，则进入while循环，死循环；(2)不存在同时出现在两个list中的名字，循环不会被执行。6 .运用fill编写程序，将一系列int型值设为0。/ ll.18_ll.6_fill_n.cpp :定义限制台应用程序的入口点。/#include "stdafx.h"#include <iostream>#include <vector>#include <algorithm>#include <numeric>using namespace std;int _tmain(int argc, _TCHAR* argv)(cout « "tlnput some int numbers ( Ctrl + z to end):ntvector<int> iVec;int iVal;while ( cin » iVal)(iVec.push_back( iVal);)cout « untThe content of ivec is :nH;for ( vector<int>:iterator it = iVec.begin(); it != iVec.end(); +it)cout « *it « "fill_n( iVec.begin(), iVec.size(), 0 );cout « "ntAfter fill_n(), the content of ivec is :n"for ( vector<int>:iterator it = iVec.begin(); it != iVec.end(); +it)cout « *it « "cout« endl;system("pause");return 0;2 e:hh<hhwprogra>11.6_fill_ndebugl1.6_fill_n.Input sone int nunbers < Ctrl + z to end>： 1 2 3 4 5The content of iuec is ：12 3 4A 0 0 05After fill_n<>the content of ivec is ： &晴按任意键继续. . . 7 .推断下面的程序是否有错，假如有，请改正之：(a) vector<int> vec; list<int> 1st; int i;while ( cin » i)lst.push_back(i);copy( lst.begin(), lst.end(), vec.begin();(b) vector<int> vec;vec.reserve( 10);fill_n ( vec.begin(), 10, 0 );(a)有错，vec是一个空容器，试图往一个空容器里复制数据，发生错误，应改为：copy( lst.begin(), lst.end(), back_inserter( vec );(b)有错误，虽然为vec支配了内存，但是vec照旧是一个空容器，而在空vec上调用fill 会产生灾难，更正为：vector<int> vec;vec.resize(lO);fill_n( vec.begin(), 10, 0 );8 .前面说过，算法不变更它所操纵的容器的大小，为什么运用backjnserter也不能突破这个 限制?在运用backjnserter是，不是算法干脆变更它所操作的容器的大小，而是算法操作迭代器 backjnserter,迭代器的行为导致了容器的大小变更。9 .编写程序统计长度不小于4个单词，并输出输入序列中不重复的单词。在程序源文件上运 行和测试你自己的程序。/ ll.18_ll.9_wc_GT4.cpp :定义限制台应用程序的入口点。/#include "stdafx.h"#include <iostream>#include <vector>#include <string>#include <algorithm>#include <numeric>using namespace std;bool isShorter( const string &sl, const string &s2 )return sl.size() < s2.size();)bool GT4( const string &s )(return s.size() >= 4;)string make_plural( size_t i, const string &sl, const string &s2 )(return (i = 1) ? si: si + s2;)int _tmain(int argc, _TCHAR* argv)(cout « "tlnput some words ( Ctrl + z to end):ntvector<string> strVec;string strVal;while ( cin » strVal) strVec.push_back( strVal);/ sortsort ( strVec.begin(), strVec.end();vector<string>:iterator end_unique = unique ( strVec.begin()z strVec.end();strVec.erasef end_unique, strVec.end();stable_sort( strVec.begin(), strVec.end(), isShorter);vector<string>:size_type wc = countjf ( strVec.begin(), strVec.end(), GT4 );cout « wc « " " « make_plural ( wc, "word", "s") « " 4 letters or longer." « endl;cout « "nt Unique words:" « endl;for ( vector<string>:iterator it = strVec.begin(); it != strVec.end(); +it) cout « *it « "cout« endl;system("pause");return 0;c、 e:hhvhhvprogra>l1.18_11.9_>c_gt4debug11.18_11.Input some words < Ctrl + z to end>： hello world It is not good for this tine.人Z 5 words 4 letters or longer.Unique words：It is for not good this hello time. world请按任意键继续. . .10.标准库定义了一个find_if函数，及find 一样，find_if函数带有一对迭代器形参，指定 其操作的范围。及countJf一样，该函数还带有第三个形参，表明用于检查范围内每个元素 的谓词函数。findjf返回一个迭代器，指向第一个使为此函数返回非零值的元素。假如这 样的元素不存在，则返回其次个迭代器实参。运用findjf函数重写上述例题中统计长度大 于6的单词个数的程序部分。首先创建一个空的map容器m,然后再m中增加一个键为。的元素，并将其值赋值为1, 其次段程序将出现运行时错误，因为v为空的vector对象，其中下标为。的元素不存在。对 于vector容器，不能对尚不存在的元素干脆赋值，只能运用push_back、insert等函数增加 兀素。int iCnt = 0;vector<string>:iterator wit = strVec.begin();while ( wit = find_if( wit, strVec.end(), GT7 ) != strVec.end()(iCnt+;+wit;)cout« iCnt« " " « make_plural (iCnt, "word", "sH) « " with 6 more letters." « endl;c：' C: VINDO¥Ssyst e>32cMd. exeInput some words ( ctrl + z to end): hello davy hello world hello grandfather 71 word with 6 more letters.Un i que wo rds:davy hello world grandfather 请按任意键继续. 11 .你认为为什么算法不变更容器的大小？为了使得算法能够独立于容器，从而普适性更好，真正成为“泛型”算法。12 .为什么必需运用erase,而不是定义一个泛型算法来删除容器中的元素。 泛型算法的原则就是不变更容器的大小。13 .说明三种插入迭代器的区分。区分在于插入的元素的位置不同：backjnserter,运用push_back实现在容