原创 C++ 程序设计四——库算法、关联容器

一、实验目的

l        
熟悉库算法；

l        
熟悉关联容器；

二、实验环境

P4 1.7G计算机一台，Windows XP操作系统，Microsoft Visual C++ 2005编程环境。

三、实验内容及分析

（一）

1.        
题意描述：习题6-1。

Reimplement the frame and hcat
operations from §5.8.1 and §5.8.3 to use iterators.

2.        
问题分析与解决

用iterators转换一下，用begin和end处理iterators的开始和结尾即可。

3.        
调试、测试运行情况及结果分析

（1）      
实验中碰到的问题及解决方法

ostream_iterator比较难于理解，是输出适配器，据MSDN介绍——Constructs an ostream_iterator that is initialized and delimited to
write to the output stream.

（2）       测试数据及运行结果

（3）       结果分析与结论

用iterators转换比较简单，体现了STL的容易操作性。

（二）男女学生成绩分析

1.        
题意描述：将学生按照性别分类（需自行修改Student_info结构体的定义，增加表示学生性别的成员变量），同一性别的学生再按照是否完成全部作业进行分类。仿照课本第六章中的例子，对分类后的学生分别用三种计算总成绩的方法分析其成绩。

2.        
问题分析与解决

修改Student_info结构体的定义，增加表示学生性别的string类型的成员变量，当输入性别的第一个字母出现m(ale)或者是b(oy)时，判断该学生为男性，否则该学生为女生，再分别对以性别分类的学生按照是否完成全部作业进行分类，共分成四类，最后对分类后的学生分别用三种计算总成绩的方法分析其成绩。

3.        
调试、测试运行情况及结果分析

（1）      
实验中碰到的问题及解决方法

（2）       测试数据及运行结果

（3）       结果分析与结论

只要仿照课本第六章中的例子，即可轻松将女生分离出来，比较麻烦之处在于涉及多个程序，需要从不同的章节将源代码添加。

（三）

1.        
题意描述：习题6-9

 Use a library algorithm to
concatenate all the elements of a vector<string>.

提示：使用accumulate函数

2.        
问题分析与解决

不就是使用accumulate这个重载函数罢了，靠的是传入的第三个参数决定使用哪个函数。

3.        
调试、测试运行情况及结果分析

（1）      
实验中碰到的问题及解决方法

不能使用””作为accumulate的第三个参数，编译器不会聪明的将它转换成支持+重载运算的string，解决方案：使用string()作为第三个参数。

（2）       测试数据及运行结果

（3）       结果分析与结论

不同的第三个参数，得出的最后结果是不同的，对于自定义类型，应当重载加法以实现吧。

（四）

1.        
题意描述：习题7-1。

Extend the program from §7.2 to produce its
output sorted by occurrence count. That is, the output should group all the
words that occur once, followed by those that occur twice, and so on.

2.        
问题分析与解决

先使用map进行strings的统计，再使用set容器，key值为pair<string, int>, set的第二个参数为sortForInt<pair<string, int> >，这个类有个成员函数bool operator()(const Pr& lhs, const
Pr& rhs)，以实现先对第二个参数排序，如果第二个参数相同的话则对第一个参数string进行二级排序的目的。

3.        
调试、测试运行情况及结果分析

（1）      
实验中碰到的问题及解决方法

对sortForInt<pair<string,
int> >这个类，开始时毫无头绪，解决方法：上网寻找相关资料，并研读struct less : public binary_function<_Ty, _Ty,
bool>的代码，进行编写sortForInt类。

不知道使用set关联容器快，还是将map的处理后的结果存储到vector里再使用sort排序快，解决方案：从网上搜索《contact》（《超时空接触》影片）的英文资料，比较两种方案的结果，如下图：

结果令人大开眼界，都不知道为什么set数据结构会比vector加上sort快那么多倍了。

（2）       测试数据及运行结果

（3）       结果分析与结论

实现中使用set容器，并自定义第二个参数，充分利用了set的特点：key值为pair<string,
int>, set的第二个参数为sortForInt<pair<string,
int> >（即为先按照key值中的int排序）。实现结果挺理想的，有增加了知识。

（五）

1.            
题意描述：习题7-3。

The cross-reference program from  7.3 could be improved: As it stands, if a word
occurs more than once on the same input line, the program will report that line
multiple times. Change the code so that it detects multiple occurrences of the
same line number and inserts the line number only once.

2.            
问题分析与解决

使用map<string, set<int> >替代map<string, vector<int> >，由于set容器里的元素只出现一次，故能不费多大功夫就能解决问题。

3.            
调试、测试运行情况及结果分析

（1）      
实验中碰到的问题及解决方法

容器set的插入不能用push_back，解决方法：改用insert。

（2）       测试数据及运行结果

（3）       结果分析与结论

用容器set后，一切都好办了，如果要记录的除了行号还有改行出现的次数，则可用map。

（六）

1.        
题意描述：习题7-5

Reimplement the grammar program using a list as the
data structure in which we build the sentence.

2.        
问题分析与解决

由于list不能实现随机访问也即是不能使用[]operate进行操作，要想得到第nth个元素，只能从一个到下一个这样访问。故特设计一个函数其中使用++operate，实现返回第nth个元素的功能。

3.        
调试、测试运行情况及结果分析

（1）      
实验中碰到的问题及解决方法

对于Grammar的类型不是很熟悉，写出的函数返回类型和传入参数的类型不匹配，解决方案：认真分析Grammar的结构，了解iterator所指的内容以及各引用的类型。

每次运行都得到相同的句子，解决方案：传入随机种子。

（2）       测试数据及运行结果

（3）       结果分析与结论

在本题中，如果使用重载operate，如有需要自己写个类的话，就会清晰很多。