CPrimer 泛型算法課后習(xí)題答案

1、第11章-泛型算法1.algorithm頭文件定義了一個名為count的函數(shù)，其功能類似于find。這個函數(shù)使用一對迭代器和一個值做參數(shù)，返回這個值出現(xiàn)的次數(shù)的統(tǒng)計(jì)結(jié)果。編寫程序讀取一系列int型數(shù)據(jù)，并將它們存儲到vector對象中然后統(tǒng)計(jì)某個指定的值出現(xiàn)了多少次。/ 11.17_11.1_int_to_vector_count.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include <vector>#include <iostream>#include <algorithm>using nam

2、espace std;int _tmain(int argc, _TCHAR* argv)cout << "tInput some int numbers ( ctrl + z to end):nt "vector<int> iVec;int iVal;while ( cin >> iVal )iVec.push_back( iVal );cout << "ntInput a num to search in the iVec: "cin.clear();cin >> iVal; int iCn

3、t = 0;if ( iCnt = count( iVec.begin(), iVec.end(), iVal )cout << "ntThe value " << iVal << " occurs " << iCnt << " times." << endl;system("pause");return 0;2.重復(fù)前面的程序，但是，將讀入的值存儲到一個string類型的list對象中。/ 11.17_11.2_list_string_cou

4、nt.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include <string>#include <list>#include <iostream>#include <algorithm>using namespace std;int _tmain(int argc, _TCHAR* argv)cout << "tInput some strings numbers ( ctrl + z to end):nt "list<string> str

5、Lst;string str;while ( cin >> str )strLst.push_back( str );cout << "ntInput 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 <<

6、" ' occurs " << iCnt << " times." << endl;system("pause");return 0;3.用accumulate統(tǒng)計(jì)vector<int>容器對象中的元素之和。/ 11.19_11.3_accumulate_vector_int.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include <vector>#include <iostream>#incl

7、ude <algorithm>#include <numeric>using namespace std;int _tmain(int argc, _TCHAR* argv)cout << "tInput some int numbers ( ctrl + z to end):nt "vector<int> iVec;int iVal;while ( cin >> iVal )iVec.push_back( iVal );cout << "ntInput a int num for the f

8、irst num: "cin.clear();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;4.假定v是vector<double>類型的對象，則調(diào)用accumulate( v.begin(), v.end()

9、, 0 )是否有錯？如果有的話，錯在哪里？沒有錯，accumulate函數(shù)必須滿足第三個實(shí)參的類型與容器內(nèi)的意思匹配，或者可以轉(zhuǎn)化為第三個實(shí)參的類型。本題中double可以轉(zhuǎn)化為int類型，但是會有較大誤差。5.對于本節(jié)調(diào)用find_first_of的例程，如果不給it加1，將會如何。(1) 如果存在同時出現(xiàn)在兩個list中的名字，則進(jìn)入while循環(huán)，死循環(huán)；(2) 不存在同時出現(xiàn)在兩個list中的名字，循環(huán)不會被執(zhí)行。6.使用fill_n編寫程序，將一系列int型值設(shè)為0 。/ 11.18_11.6_fill_n.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "st

10、dafx.h"#include <iostream>#include <vector>#include <algorithm>#include <numeric>using namespace std;int _tmain(int argc, _TCHAR* argv)cout << "tInput some int numbers ( ctrl + z to end):nt "vector<int> iVec;int iVal;while ( cin >> iVal )iVec.

11、push_back( iVal );cout << "ntThe content of ivec is :n"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 (

12、vector<int>:iterator it = iVec.begin(); it != iVec.end(); +it )cout << *it << " "cout << endl;system("pause");return 0;7.判斷下面的程序是否有錯，如果有，請改正之：(a) vector<int> vec; list<int> lst; int i;while ( cin >> i )lst.push_back(i);copy( lst.begin(),

13、lst.end(), vec.begin() );(b) vector<int> vec;vec.reserve( 10 );fill_n ( vec.begin(), 10, 0 );(a) 有錯，vec是一個空容器，試圖往一個空容器里復(fù)制數(shù)據(jù)，發(fā)生錯誤，應(yīng)改為：copy( lst.begin(), lst.end(), back_inserter( vec ) );(b) 有錯誤，雖然為vec分配了內(nèi)存，但是vec仍然是一個空容器，而在空vec上調(diào)用fill_n會產(chǎn)生災(zāi)難，更正為：vector<int> vec;vec.resize(10);fill_n( vec.

14、begin(), 10, 0 );8.前面說過，算法不改變它所操縱的容器的大小，為什么使用back_inserter也不能突破這個限制？在使用back_inserter是，不是算法直接改變它所操作的容器的大小，而是算法操作迭代器back_inserter, 迭代器的行為導(dǎo)致了容器的大小改變。9.編寫程序統(tǒng)計(jì)長度不小于4個單詞，并輸出輸入序列中不重復(fù)的單詞。在程序源文件上運(yùn)行和測試你自己的程序。/ 11.18_11.9_wc_GT4.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include <iostream>#includ

15、e <vector>#include <string>#include <algorithm>#include <numeric>using namespace std;bool isShorter( const string &s1, const string &s2 )return s1.size() < s2.size();bool GT4( const string &s )return s.size() >= 4;string make_plural( size_t i, const string &

16、amp;s1, const string &s2 )return ( i = 1 ) ? s1 : s1 + s2;int _tmain(int argc, _TCHAR* argv)cout << "tInput some words ( ctrl + z to end):nt "vector<string> strVec;string strVal;while ( cin >> strVal )strVec.push_back( strVal );/ sortsort ( strVec.begin(), strVec.end(

17、) );vector<string>:iterator end_unique = unique ( strVec.begin(), strVec.end() );strVec.erase( end_unique, strVec.end() );stable_sort( strVec.begin(), strVec.end(), isShorter );vector<string>:size_type wc = count_if ( strVec.begin(), strVec.end(), GT4 );cout << wc << " &

18、quot; << 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 << " &

19、quot;cout << endl;system("pause");return 0;10.標(biāo)準(zhǔn)庫定義了一個 find_if 函數(shù)，與find一樣，find_if 函數(shù)帶有一對迭代器形參，指定其操作的范圍。與count_if一樣，該函數(shù)還帶有第三個形參，表明用于檢查范圍內(nèi)每個元素的謂詞函數(shù)。find_if 返回一個迭代器，指向第一個使為此函數(shù)返回非零值的元素。如果這樣的元素不存在，則返回第二個迭代器實(shí)參。使用find_if函數(shù)重寫上述例題中統(tǒng)計(jì)長度大于6的單詞個數(shù)的程序部分。首先創(chuàng)建一個空的map容器m，然后再m中增加一個鍵為0的元素，并將其值賦值為1，第二段程

20、序?qū)⒊霈F(xiàn)運(yùn)行時錯誤，因?yàn)関為空的vector對象，其中下標(biāo)為0的元素不存在。對于vector容器，不能對尚不存在的元素直接賦值，只能使用push_back、insert等函數(shù)增加元素。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 (

21、iCnt, "word", "s" ) << " with 6 more letters. " << endl;11.你認(rèn)為為什么算法不改變?nèi)萜鞯拇笮?？為了使得算法能夠?dú)立于容器，從而普適性更好，真正成為“泛型”算法。12.為什么必須使用erase, 而不是定義一個泛型算法來刪除容器中的元素。泛型算法的原則就是不改變?nèi)萜鞯拇笮　?3. 解釋三種插入迭代器的區(qū)別。區(qū)別在于插入的元素的位置不同：back_inserter，使用push_back實(shí)現(xiàn)在容器末端插入。front_inserter, 使用push_fro

22、nt實(shí)現(xiàn)在容器前端插入。inserter，使用insert實(shí)現(xiàn)插入，它還帶有第二個實(shí)參：指向插入起始位置的迭代器。14.編程使用replace_copy將一個容器中的序列復(fù)制給另一個容器，并將前一個序列中給定的值替換為指定的新值。分別使用inserter、back_inserter和front_inserter實(shí)現(xiàn)這個程序。討論在不同情況下輸出序列如何變化。/ 11.18_11.14_replace_copy.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include <iostream>#include <algor

23、ithm>#include <vector>#include <list>using namespace std;int _tmain(int argc, _TCHAR* argv)/vector< int > iVec;int ia = 1, 2, 3, 4, 100, 5, 100 ;vector< int > iVec( ia, ia+7 );/ testing out iVeccout << "ntThe contents of iVec: "for ( vector<int>:itera

24、tor it = iVec.begin(); it != iVec.end(); +it )cout << *it << " "cout << endl; list<int> iLst; / copy iVec's member to iLst; cout << "n Using inserter: " << endl;replace_copy( iVec.begin(), iVec.end(), inserter( iLst, iLst.begin() ), 100, 0

25、);cout << "tThe contents of iLst: "for ( list<int>:iterator it = iLst.begin(); it != iLst.end(); +it )cout << *it << " "cout << endl;cout << "n Using back_inserter: " << endl;iLst.clear();replace_copy( iVec.begin(), iVec.end(),

26、back_inserter( iLst ), 100, 0 );cout << "tThe contents of iLst: "for ( list<int>:iterator it = iLst.begin(); it != iLst.end(); +it )cout << *it << " "cout << endl;cout << "n Using front_inserter: " << endl;iLst.clear();replace_c

27、opy( iVec.begin(), iVec.end(), front_inserter( iLst ), 100, 0 );cout << "tThe contents of iLst: "for ( list<int>:iterator it = iLst.begin(); it != iLst.end(); +it )cout << *it << " "cout << endl;system("pause");return 0;15.算法標(biāo)準(zhǔn)庫定義了一個名為uniqu

28、e_copy的函數(shù)，其操作與unique類似，唯一的區(qū)別在于：前者接受第三個迭代器實(shí)參，用于指定復(fù)制不重復(fù)元素的目標(biāo)序列。編寫程序使用unique_copy將一個list對象中不重復(fù)的元素復(fù)制到一個空的vector對象中。/ 11.18_11.15_unique_copy.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include <iostream>#include <algorithm>#include <vector>#include <list>using namespace st

29、d;int _tmain(int argc, _TCHAR* argv)/vector< int > iVec;int ia = 1, 2, 3, 4, 100, 100, 5 ;list<int> iLst( ia, ia+7 );/ testing out iLstcout << "ntThe contents of iLst:nt"for ( list<int>:iterator it = iLst.begin(); it != iLst.end(); +it )cout << *it << &q

30、uot; "cout << endl;vector<int> iVec;/ copy iLst's member to iVec;cout << "n 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 ( v

31、ector<int>:iterator it = iVec.begin(); it != iVec.end(); +it )cout << *it << " "cout << endl;system("pause");return 0;16. 重寫（11.3.2節(jié)第3小節(jié)）的程序，使用copy算法將一個文件的內(nèi)容寫到標(biāo)準(zhǔn)輸出中。/ 11.20_11.16_iostream_iertator.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/ 使用copy算法將一個文件的內(nèi)容寫到標(biāo)準(zhǔn)輸出中#include "

32、;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;inFile.open( "11.16.txt&

33、quot; );if ( !inFile )cerr << " error file. " << endl;return -1;istream_iterator<string> in_file_iter ( inFile ), eof;copy( in_file_iter, eof, out_iter );inFile.close();cout << endl;system("pause");return 0; 17.使用一對istream_iterator對象初始化一個int型的vector對象。/ 11

34、.20_11.17_istream_iterator_vector.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#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

35、), end;vector<int> iVec( cin_it, 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;18.編程使用istream_iterator對象從標(biāo)準(zhǔn)輸入讀入一些列整

36、數(shù)。使用ostream_iterator對象將偶數(shù)寫到第二個文件，每個寫入的值都存放在單獨(dú)的行中。/ 11.20_11.18_istream_iterator_ostream_iterator.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include <iostream>#include <algorithm>#include <iterator>#include <fstream>using namespace std;int _tmain(int argc, _TCHAR* argv

37、)ofstream outFile_even, outFile_odd;outFile_even.open( "outFile_even.txt" );outFile_odd.open( "outFile_odd.txt" );if ( !outFile_even | !outFile_odd )cerr << " File can't be open. " << endl;return -1;istream_iterator<int> in_iter( cin ), end;ostream

38、_iterator<int> out_odd_iter( outFile_odd, " " );ostream_iterator<int> out_even_iter( outFile_even, "n" );while ( in_iter != end )if ( *in_iter % 2 = 0 ) *out_even_iter+ = *in_iter+;else *out_odd_iter+ = *in_iter+ ;outFile_odd.close();outFile_even.close();cout <<

39、 endl;system("pause");return 0; 19.編寫程序使用reverse_iterator對象以逆序輸出vector容器對象的內(nèi)容。/ 11.20_11.19_reverse_iterator.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include <iostream>#include <iterator>#include <vector>using namespace std;int _tmain(int argc, _TCHAR* argv)int

40、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;20.現(xiàn)在，使用普通的迭代器逆序輸出上題中的元素。/ 11.20_11.20_ iterator_reverse.c

41、pp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#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>:iterator it = iVec.end() - 1; it > i

42、Vec.begin(); -it )cout << *it << " "cout << *iVec.begin(); cout << endl;system("pause");return 0;21.使用find在一個int型的list中需找值為0的最后一個元素。/ 11.20_11.21_list_find.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include <iostream>#include <iterator>

43、#include <list>#include <algorithm>using namespace std;int _tmain(int argc, _TCHAR* argv)int ia = 1, 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 <

44、;< endl ;list<int>:reverse_iterator last_0_it = find( iLst.rbegin(), iLst.rend(), 0 );if ( last_0_it != iLst.rend() )cout << "Get the last 0, it's value: " << *last_0_it << endl;else cout << "We can't find the last 0. " << endl;cout

45、<< endl;system("pause");return 0;22.假設(shè)有一個存儲了10個元素的vector對象，將其中第3第7個位置上的元素以逆序復(fù)制給list對象。/ 11.20_11.22_vector_reverseCopyToList.cpp : 定義控制臺應(yīng)用程序的入口點(diǎn)。/#include "stdafx.h"#include <iostream>#include <iterator>#include <list>#include <vector>using namespace

46、 std;int _tmain(int argc, _TCHAR* argv)int ia = 1, 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 << " " lis

47、t<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;23.列出五種迭代器類型及

48、其各自支持的操作。輸入迭代器： = != 自減, * ->輸出迭代器 + *前向迭代器 = != * ->雙向迭代器 = != + * -> - 隨機(jī)訪問迭代器 = != + * -> < <= > >= _ +=24.List容器擁有什么類型的迭代器？而vector呢？雙向迭代器，vector擁有隨機(jī)訪問迭代器。25.你認(rèn)為copy算法需要使用哪種迭代器？而reverse和unique呢？copy 至少需要輸入和輸出迭代器；reverse算法至少需要雙向迭代器；unique算法至少需要前向迭代器。26. 解釋下列代碼錯誤的原因，指出哪些錯誤可以

49、在編譯時捕獲。(a) string sa10;const vector<string> file_names( sa, sa+6 );(b) const vector<int> ivec;fill ( ivec.begin(), ivec.end(), ival );(c) sort( ivec.begin(), ivec.rend() );(d) sort( ivec1.begin(), ivec2.end() );(a) const 類型的vector<string>對象，不可以寫入，錯誤。 (b) 錯了，兩個實(shí)參迭代器是cosnt迭代器，不能用來修改容

50、器中的元素。(c) 錯了，用于算法的實(shí)參的兩個迭代器必須是相同類型。(d) 錯了，用于算法參數(shù)的迭代器必須屬于同一個迭代器。 前三個錯誤均可以在編譯時捕獲。(d) 不能在編譯時捕獲。27.標(biāo)準(zhǔn)庫定義了下面的算法：replace( beg, end, old_val, new_val );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 );只根據(jù)這些函數(shù)的名字和形參，描述這些算法的功能。第一個：由beg和end指定的輸入范