第3章感受（一）——3.14. Hello STL 算法篇

以你之姓@ 2022-08-24 01:29 111阅读 0赞

[\[回到目录\]][Link 1]

白话C++

3.14. Hello STL 算法篇

前一小节，在输出成绩时，我们从students中得到每个学生的学号，然后，通过for循环，在一个list中查找符合“学号等于指定值”的元素。代码如下（为了方便说明，行号进行了重排）：

001 for (list<Score>::const_iterator iter = scores.begin(); 
                iter != scores.end(); ++iter) { 005 if (iter->number == number) { 
                    found = true; //找到了                 
                    cout << "成绩：" << iter->mark << endl; break; } }

有 一个“容器”无序地存储了一些元素，我们希望于其中找到某个符号特定条件的元素，这个过程称为“查找/find”。写程序时，“查找/find”是一个经 常用到的算法。比如，假设李老师要求我们提供一个新功能：输入学生姓名，找出学生学号，这时候，我们就又必须通过一个for循环，取出students中 的每一个“学生元素”，比较他的姓名和我们要找的姓名是否相等……

可见，查找过程通常都是一个循环结构，然后取出每一个元素，对这个元素做一个“判断”，如果“判断”成立，就返回这个元素位置上的迭代器；否则继续下一个元素——这中间变化的因素是那个“判断”方式，在C++术语中，“判断”方式也称为“predicate/谓语”。

你肯定知道“我吃饭”中的动词“吃”，是一个“谓语”；但我要特别提醒：“我是一个男人”中的“是”，也是一个谓语。同样，C++中的“谓语/predicate”通常是用来做一个“是什么吗？”的判断，比如：“是大于number吗”，或“是等于number吗”。

要想减少一次次写重复的代码，函数是我们最早学会的方法，还记得那个一直点头“Hello”的早晨吗？针对当前的查找工作，我们大致可以写这样一个函数：

list<Score>::iterator find (list< Score> scores, XXXX) { for (list<Score>::iterator iter = scores.begin(); iter != scores.end(); ++iter) { 006 if (XXX(iter->number)) { return iter; } } //没找到,返回end() return scores.end(); }

这是一段充满问题的代码，但它代表了我们此时的思路。我们希望把全班的分数列表(scores)传给这个函数，更为精采的是，我们想传一个“谓语”给这个函数，希望在006行能用上它来实现“判断”。只是，我们现在不知道如何传一个“谓语”。

有一些读者特别有编程“慧根”，他们想到了“谓语”其实就是一个“动作”。而他们又想到“函数”就是用来表示一个“动作”的，那么，可不可以把“某个函数”做一个参数传入find，然后在006行处调用这个传入的函数用以判断呢？

没错，C语言就是采用这种方法，C语言允许采用一种被称为“函数指针”的数据作为参数，实现上述过程。

C++语言对C语言有良好的兼容，所以也存在“函数指针”这类数据。然而函数指针至少存在这些缺点：不直观、不安全、不够灵活……C++提供此类问题“面向对象”对解决方法，这项技术的名字就叫做“函数对象”。

![hint_icon.PNG][]〖小提示〗：错不在“函数指针”

我罗列函数指针的几个“不”以后，顿时脸红心跳，像做了一件志亏心事。其实，函数指针非常很强大，问题是它也确实很难以学习和使用，除了C++这个铁哥们还保留了之外，后来的Java或C\#都从语言中完全移除函数指针的概念。但不管如何，这不是函数指针的错，

3.14.1. 函数对象

函数对象，英文为“function object”；有时也称为“仿函数/functor”。综合这两种叫法，倒是说出它的一个功能：“通过对象来模仿函数”。

还记得vector中的\[\]操作符吗？当时我们说过，C++允许把操作符当成一个函数来设计，比如vecotr类型中，其实存在了一个名为“operator \[\] ”的成员函数。我们还说：

manyBeauties\[0\]

其实相当于：

manyBeauties.**operator \[\]** (0)

今天，我们要“设计”的操作符，是方括号\[\]的兄弟：圆括号()。假设有这样一个类型：Dog，它存在一个成员函数：Bark：

struct Dog { 003 void Bark() const { cout << “Wang~Wang~” << endl; } };

既然强大的C++允许我们用“操作符”来作为函数的名字，“()”也是一种操作符，所以我想用它来替换Bark，那么，让我们把“Bark”替换成“()”，结果是——

struct Dog { 003 void ()() const //噢，这是什么？（错误代码） { cout << “Wang~Wang~” << endl; } };

噢，正经一点，我们是在学习编程，而不是在创造“火星文”。此时的004行存在错误的：记住，用“操作符”来作来函数时，名字要加上前缀：“operator”。那么，正确写法应该是：

struct Dog { 003 void operator() () const //operator () 是本类的一个成员函数 (正确) { cout << “Wang~Wang~” << endl; } };

这一次正确了，接下来，如何使用这个函数呢？根据之前operator\[\]的经验，我们很快可以得出，使用方法有两种：

001 Dog doggie; 002 doggie.operator(); //方法一 003 doggie(); //方法二

明显，方法二比较简单，这也正是C++提供将操作符函数的目的。不过，此时，我们的目光应该再次盯着方法二

003 doggie (); //方法二

天，这多么像是在调用一个名为“doggie”的函数啊。C++语言确实像是一位擅长搞“障眼法”的大师，别被它骗了，请认清。

假相：

doggie(); //调用一个函数，函数名：doggie

真相:

doggie(); //调用一个函数，函数名：operator()。doggie是一个对象，即： // doggie.operator()

doggie是001行定义的一个类型为Dog的对象，而()是它的一个成员函数。

很有意思的C++语言，不是吗？

![laugth_icon.PNG][]〖轻松一刻〗：诗一首：《咏函数对象》 （梨花体）

是

一个函数？

还是

一个对象？

我认真地看了，

原来——

是一个对象，

在调用一个函数，一个

叫做“operator ()”的函数。

operator () 函数可以有参数，也可以有返回值。比如：

struct Add { int operator () (int n2) const //参数：n2, 返回值类型：int { return n1 + n2; } int n1; };

然后，我们可这样使用：

001 Add s; 002 s.n1 = 1; 003 int r = s(2); cout << r << endl; //输出3

001行：定义了一个Add类型的对象，名称为s。

002行：将对象s的成员数据n1赋值为1。

003行：调用s的成员函数：“operator ()”，等同：s.operator()(2)；并得到返回值。

3.14.2. 自定义查找算法

有了“函数对象”这样技术，我们就可以完成find函数。

*   *  定义函数对象

struct CompareByNumber_Equal { unsigned int number; //学号 005 bool operator () (int current_number) const { return (current_number == number); } };

005行的“operator()”函数用以实现比较。该函数会得到当前学号（current\_number），然后返回current\_number是否等于指定（待查找）的number。

代码“(current\_number == number) ”执行的运行是判断==两边的值是否相等，它的结果只有两种可能“真(相等)”或“假(不等)”。因此，代码

return (current_number == number);

等效于：

if (current_number == number) { return true; } else { return false; }

*   *  使用函数对象

下面，我们用这个“函数对象”类型，来代替那段未完成的代码中的XXXX：

list<Score>::iterator find (list< Score> scores, CompareByNumber_Equal cmp) { for (list<Score>::iterator iter = scores.begin(); iter != scores.end(); ++iter) { 006 if (cmp (iter->number)) { return iter; } } //没找到,返回endl() return scores.endl(); }

乍一看006行还是有些摸不着头脑？“cmp”很明显是表达“比较”的意思，它在C++里被当成一个“谓语”，这也不难理解，因为“比较”确实是一个动词——不过，“比较”至少需要两个对象吧？比如cmp(a, b)，用来比较a和b，然而代码：

006 if (cmp (iter->number))

cmp只接受一个参数，这不太好理解啊？

cmp只接受了一个学号：iter->number，拿它和谁比呢？答案是：“函数对象”其实是一个“对象”，而对象可以拥有“成员数据”。用来和iter->number 比较的另外一方，我们可以事先将它保存为“成员数据”。

cmp.number = 5;

![一比多][tu42.PNG]

（图 42 “一对多”的比较过程）

如图所示，在连续的比较过程中，其中一方“指定学号”保持不变，既然如此，我们何必每次都重新获得呢？

有了CompareByNumber\_Equal和find函数，在输出成绩时，我们需要查找其学号“等于指定学号”的成绩时，其查找代码简化成如下：

void StudentScoreManager::OutputScores() const { for (unsigned int i=0; i<students.size(); ++i) { unsigned int number = students[i].number; //学号 //......此处代码略去...... //在scores中查找成绩: CompareByNumber_Equal cmp; cmp.number = number; //指定要查找的学号 list<Score>::const_iterator iter = find(scores, cmp); //......此处代码略去...... } }

![xczy.png][]〖课堂作业〗：使用自定义查找函数

请新建一个控制台项目，取名为“HelloSTL\_ScoreManageVer1\_01”。然后，请使用本节实现的查找函数，重新实现1.0版本中的功能。

3.14.3. 标准库查找算法

前一小节，我们自力更生实现了可用于“学号”查找的算法，不过，和标准库的查找算法比起来，我们的算法还有很多不足。

第一、只能针对“list<Score>”的内容查找。意思是，不能针对“list<Beauty>”查找，也不能对“vector<Score>”查找。为什么？你看我们的find函数如何声明的：

list<Score>::iterator find (list< Score> scores, CompareByNumber\_Equal cmp);

入参是list<Score>，返回值是list<Score>，所以这个函数只适用于在Score的列表中查询。

第二、 只能通过既定的“谓语”：CompareByNumber\_Equal比较。一旦有新的查找需求，比如想查找“成绩为100分”，就得重新写一个比较器，并且find函数也需要重写。

真让人沮丧……

标准库的查找算法可以解决这两个问题，因为它采用了“泛型”技术。其实我们不必自己去实现，标准库已经提供更为强大的查找算法：一个名为“find\_if”的成员函数。

001 template<typename InputIterator, typename Predicate> 002 InputIterator find_if ( InputIterator first, InputIterator last, Predicate pred ) { //查找过程具体实现…… }

先不去管001行，直接看002行代码，类似在定义一个函数：

*   *  **函数名：**find\_if
     *  **参数：**三个，前两个参数类型为“InputIterator”，后一个参数类型为“Predicate”。
     *  **返回值：**类型为“InputIterator”。

但 是，“InputIterator”和“Predicate”都不是真实的数据类型。它们只是一些“类型代号”。事实上，find\_if在此时是一个“函 数模板”。和“类模板”一样，仅当在调用时，用一些实际类型替换了这些“类型代号”，“函数模板”才会变成一个真正的函数。

“函数模板”需要通过一些语法，来指出它将用到“类型代号”。001行的作用在此。具体语法与含义，不在“感受”篇学习。

正因为采用了此类“泛型技术”写成，因此find\_if能适用于多种容器的查找。同时，它也支持各种未知的“比较器”，而不用改写函数本身。尝试一下它的神奇吧！

**步骤 1：**请新建一个控制台应用项目，取名为“HelloSTL\_ScoreManageVer1\_02”。修改其main.cpp文件编码为“系统默认”，然后复制原“HelloSTL\_ScoreManageVer1\_01”项目的main.cpp文件的内容。

**步骤 2：**删除源代码中的find函数实现，我们不再需要自己去实现find。

**步骤 3：**在头文件包含位置，追加一行以下内容，因为我们所要使用的find\_if来自该文件。algorithm的意思是“算法”。

\#include <algorithm>

步骤 4： struct CompareByNumber\_Equal修改成如下：

struct Compare { int number; //学号 bool operator () (Score current_score) const { return current_score.number == number; } };

步骤 5： 输出成绩时所用到的查找代码，替换为：

//......此处代码略去...... //查找成绩: Compare cmp; cmp.number = number; //指定学号 cmp.flag = cfEqual; //指定按 == 比较 list<Score>::const_iterator iter = find_if(scores.begin(), scores.end(), cmp); //......此处代码略去......

变 化在最后一行：find函数替换为“find\_if”。第一个入参，原本是”scores”，现在拆分成两个迭代器位置：scores.begin(), 和scores.end()。find\_if将从begin()开始，一起找到end()，当然，不包含end()。最后一个参数仍然是“谓语”。

![xczy.png][]〖课堂作业〗：完成HelloSTL\_ScoreManageVer1\_02

请依据本节代码，完成HelloSTL\_ScoreManageVer1\_02项目的编译与运行。

3.14.4. 标准库排序算法

除 了“查找”以外，“排序”也是一个非常经常用到的算法。比如在前例录入学生成绩时，由于学生交考卷时是无序的，但我们又希望成绩录入后，能够按 “学号从小排到大”的次序排列；于是我们相当费力地在每一笔成绩录入时，找到合适的位置插入。如果有一个排序算法，我们就可尽管录入，只在录入完成后，一 次性地按座号重排一下次序，那多简单啊……

“如果有一个排序算法……”，门外传来老当益壮的声音：“为什么不给这套系统添加一个成绩排名的功能呢？”

丁小明知道谁来了，急忙迎上去：“可是，教育部不是反对给学生排名次吗？”

李老师：“排名数据我们只在内部使用，并不公开。你知道的，它有利于老师更加准确地了解学生情况”。

“那么，好吧。我会在下一节课实现管理系统的2.0版本，加入这个功能”。

![important.png][]〖重要〗： 算法学习

丁 小明必须在一天之内学会“排序/sort”算法——这既可能又不可能。如果我们要在一天之内学会各种排序算法的具体实现，那是不可能的；但如果我们仅仅是 学会使用“排序”算法，那么半天足矣。尽管我们曾经亲手完成find的实现，但对于“排序/sort”算法，以及后面可能遇上的更多的算法，我们多数仅教 你如何“使用”，而不是“实现”。

那么什么时候学习各类 “算法”的实现呢？表面上，“算法”可以独立于编程语言；然而算法需要语言来表达，因此，你在熟练掌握一门至少编程语言以后，再开始学习“算法”。

在 和find\_if平行的位置，STL提供通用版本的sort算法。然而list容器也提供了自己的“成员函数”版本的sort算法。STL的原则是：当一 个容器有自定义的某个算法时，那么你应该使用容器自定义的版本。有时是因为自定义版本性能更好些，有时候则是“通用版本”虽然通用，但仍然会对某些容器失 灵。sort算法与list容器的关系正是如此：通用版本的sort，要求容器必须支持对元素的“随机访问”——比如vector，而list则不支持。

template <typename Compare> void list::sort ( Compare cmp ) { //具体实现…… }

使用sort确实很简单，我们只需要提供正确的“比较器”就可以了。对于“学生成绩”，我们现在有两种排序需求，其一是按学号“从低排到高”；其二是按成绩“从高排到低”。我们这回分开写两个“比较器”。

*   *  “排序比较器”基本特点

当我们在排序时，排序算法不断地取容器中的两个元素进行比较，不同的查找算法的实现，这两个元素的变换过程也互不相同。

![tu43.PNG][]

（图 43排序过程中的比较）

上 图演示在排序过程中，可能的比较过程：第二次参与比较的是元素1和2；第二次是元素2和3；第三次则是是2和4……可见比较的双方都会在不断变换，不存在 一个固定的比较方。这一点“查找”过程中的比较有所不同：在容器中“查找”某一元素时，会有一个“固定”的比较方，即查找目标。

结论是，用于“查找”的“比较器”只需一个参数，但用于“排序”的“比较器”，需要两个参数。所以，一个排序比较器，大致长这个样子：

struct Compare4Sort { bool operator () (T t1, T t2) const; };

〖小提示〗：“4”是什么意思

英文中，“4”的读音等同于“for”，为了让代码中的某些名称变短一点，常用“4”代表“for”。同样的还有“2”代表“to”，比如用于表示将一个整数转换为字符串：“int2str”。

除了需要两个参数以外，这个operator ()同样返回一个“真假类型”的值。排序过程比较t1和t2两个元素，如果返回的值是“真”，那么，就把t1放在t2之前；如果返回“假”，则把t1放在t2之后。

*   *  按成绩排序的“比较器”

struct CompareByMarkBigger { bool operator () (Score s1, Score s2) const { return (s1.mark > s2.mark); } };

函数operator() 得到两个参数：s1和s2，然后返回s1的分数是否大于s2的分数，如果是，那么返回“真”，于是s1将被排在前面；如果“假”，那么说明s1的分数“小于或等于”s2的分数，此时s2将被排在前面。

“(s1.mark > s2.mark) ”的运算结果，不是“真”就是“假”。所以:

return (s1.mark > s2.mark);

相当于：

if (s1.mark > s2.mark) { return true; // s1分数高，返回true，将被排前面 } else { return false; // s2分数高（或相等），返回false，s2 将被排前面 }

*   *  使用“比较器”

现在我们可以通过list的sort成员函数，和前述的两个“比较器”，来分别实现将学生成绩按分数进行排序：

//按分数高低排： CompareByMarkBigger cmp; scores.sort(cmp);

![hint_icon.PNG][]〖小提示〗：几种排序算法

仅仅是写了“比较器”（函数对象），我们可以轻松在做到为一个容器内的元素进行排序。一方面这体现了C++标准库的便捷，另一方面，它也让我们避免了在学习一门语言的同时，要同时要学习复杂的算法，但这并不表明我们可以永远不去了解算法的实现。

教学上，经常用到的排序算法有：“冒泡排序/bubble sort”、“插入排序/insert sort”、“快速排序/Quick sort”等。而STL的sort通常是快速排序算法的实现。

3.14.5. 实例：成绩管理系统2.0

2.0版管理系统将实现以下功能：

第一、新增(+)：新增主菜单功能，允许用户反复执行选择的功能。菜单项有：

*   *  录入学生基本信息
     *  按学号，查找学生
     *  按姓名，查找学生
     *  录入学生考试成绩
     *  清空学生考试成绩
     *  按学号，显示成绩
     *  按排名，显示成绩
     *  帮助
     *  关于
     *  退出

第二、保留(.)：学生基本信息（姓名、学号）录入功能。其中学号自动按次序产生。该功能已经在1.0版实现；本版基本不用改动。

第三、新增(+)：提供输入单个学生学号，输出其学号、姓名，成绩的功能。

第四、新增(+)：提供输入单个学生姓名，输出其学号、姓名、成绩的功能。如果有同名学生，则全部输出。

第五、改进(\*)：学生考试成绩（分数、学号）录入功能。在用户输入学号后，增加立即输出学生姓名的功能，再提示用户输入成绩。如果对应的学号找不到学生，则提示出错信息。

第六、保留(.)：依据学号次序，从小到大输出学号、姓名、分数的功能，如果找不到成绩，则提示。

第七、新增(+)：在录入完成绩后，立即按成绩高低排序。在此基础上，提供新功能：根据按分数由高至低，输出成绩。

第八、新增(+)：提供各个菜单项的简单帮助。

第九、新增(+)：“About”功能，显示软件版权、作者等信息。

第十、新增(+)：提供退出功能，也结束程序主体循环。

第十一、改进(\*)：加入用户输入错误的处理，以解决原版本中，用户在该输入数字时输入其它字符会造成程序死循环的BUG。

![hint_icon.PNG][]〖小提示〗：功能清单上的符号

我习惯于用“.”、“+”、“-”、“\*”符号来对应表示以下性质的功能改变：“保留原有功能”、“新增一个功能”、“去除某原有功能”、“改进某原有功能（包括解决BUG）”。有些人还会用“\#”表示“对某一功能的重大增强”

请 新建一个控制台应用项目，命名为“HelloSTL\_ScoreManage\_Ver2”。打开向导自动生成的main.cpp文件，并通过菜单“编辑- 文件编码/Edit-File encoding”修改其编码为“系统默认/System default”。不用复制原有的代码到新工程，我们将从头编写整个工程。

我 们将根据代码在main.cpp中的出现次序，完整地写出全部代码，并逐段加以说明。要求读者此时应该已经学习完前面的课程，并且正确完成 “HelloSTL\_ScoreManage\_Ver1\_01”及“HelloSTL\_ScoreManage\_Ver1\_02”两个项目。

*   *  头文件与名字空

include <iostream> #include <list> #include <vector> #include <string> #include <algorithm> using namespace std;

*   *  学生、成绩的类型定义

//学生 struct Student { unsigned int number; //学号 string name; //姓名 }; //成绩 struct Score { unsigned int number; //学号 float mark; //分数 };

*   *  成绩管理系统类型定义
    
        //学生成绩管理类 class StudentScoreManager { public: void InputStudents(); //录入学生基本信息（录入前自动清空原有数据） void InputScores(); //录入成绩（录入前不清空原有数据） void ClearScores(); //清空成绩数据 void OutputScoresByNumber() const; //以学号次序，输出每个学生信息，包括成绩 void OutputScoresByMark() const; //以分数排名，输出每个成绩，包括学生基本信息 void FindStudentByNumber() const; //通过学号，查找学生，显示姓名，学号，成绩 void FindStudentByName() const; //通过姓名，查找学生，显示姓名，学号，成绩 private: //内部调用的函数: //给定一个学号，在scores中查找，并输出其分数 void FindScoreByNumber(unsigned int number) const; vector<Student> students; list<Score> scores; };
    
     *  特定函数：检查控制台输入出错
    
        //检查是否输入有误，如有，则清除出错状态，并返回“真”. bool CheckInputFail() { if (cin.fail ()) //检查 cin是不是出错了？ { //出错了... cin.clear(); //清除cin当前可能处于错误状态 cin.sync(); //再清除当前所有未处理的输入 cout << "输入有误，请重新处理。" << endl; return true; } return false; }

任何可视字符都可以组成字符串，因此如果在需要从cin中读入字符串时，通常不会有什么问题。然而如果是想读入一个整数，比如：

int number; cin >> number;

就必须考虑当用户输入类似“abc”字符时，cin无法将abc转换成合法的数字，此时cin处于“出错状态”——表现之一就是不再接受任何输入！CheckInputFail()函数将在代码中多处需要输入数值的地方被调用。

*   *  录入学生成绩

//输入学生成绩 void StudentScoreManager::InputStudents() { //检查是否已经有数据: if (students.empty() == false) { cout << "确信要重新录入学生基本信息吗？(y/n)"; char c; cin >> c; if (c != 'y') { return; } cin.sync(); //吃掉回车键. } //因为允许用户重新录入，所以现在需要清除原有数据 students.clear(); unsigned int number = 1; //学号从1开始 while(true) { cout << "请输入学生姓名(输入x表示结束), " << number << "号："; string name; getline(cin, name); if (name == "x") { break; } Student student; student.number = number; student.name = name; students.push_back(student); ++number; } }

函数一开始，首先检查students是否为空，如果不为空，说明之前已经有录入过学生基本信息，于是提示是否真的重新录入……

*   *  用于查找的比较器

//比较器：比较姓名是否相等 //用于在students中查找指定姓名的学生 struct CompareByName4Find { bool operator () (Student student) const { return student.name == name; } //待查找的姓名 string name; }; //比较器：比较成绩中的学号是否相等 //用于在 scores中查找指定学号的成绩 struct CompareByNumber_Equal4Find { bool operator () (Score s) const { return (s.number == number); } unsigned int number; };

两个比较器的名称，都以4Find为后缀，暗示这两个比较器都将用于查找。再分别看“operator ()”的参数的类型，第一个是Student，第二个Score，这暗示了它们分别用于查找什么。

*   *  根据学号，查找分数
    
        //内部调用的函数: //给定一个学号，在scores中查找，并输出其分数 void StudentScoreManager::FindScoreByNumber(unsigned int number) const { CompareByNumber_Equal4Find cbne; cbne.number = number; list<Score>::const_iterator itScore = find_if(scores.begin(), scores.end(), cbne); if (itScore == scores.end()) { //找不到成绩： cout << "，成绩：查无成绩。"; } else { //查到成绩了，显示： cout << "，成绩：" << itScore->mark; } }

这里是本项目中第一次调用到“find\_if”。它在scores中查找指定学号的成绩。在输出成绩时，我们首先输出一个“逗号”，这说明什么呢？

*   *  通过学号查找学生
    
        //通过学号查到详细信息 void StudentScoreManager::FindStudentByNumber() const { cout << "请输入要查找的学号："; unsigned int number; cin >> number; //用户输入非数字字符时，此时检查出错误 if (CheckInputFail()) { return; } //检查是不是在合法范围内的学号: unsigned int maxNumber = students.size(); if (number > maxNumber) { cout << "学号只允许在 1~" << maxNumber << " 之间！" << endl; return; } cout << "学号：" << number; cout << "，姓名：" << students[number - 1].name; //继续查：用学号查分数: FindScoreByNumber(number); cout << endl; }

这里调用了FindScoreByNumber函数，在调用该函数以输出成绩之前，我们已经在屏幕上输出学号和姓名了，并且你可能也发现了，这一次我们将信息尽量在同一行输出，因此采用逗号分隔，而不是换行。

学号(number)从1开始，而vector的索引从0开始，所以number换算成studentes的下标时，需要减1。

![caution.png][]〖危险〗： 数组越界

如 果你不小心将students\[number - 1\]写成students\[number\]，那么不仅在逻辑上，所有学员的信息都对不上位，而且当输出最后一个学员信息时，程序可能会因为数组越界（比 如，students中只有0~9个元素，而你访问了第11个），而崩溃。

*   *  通过姓名查找学生

//通过姓名查找到学生基本信息，然后再通过学号找到学生成绩。 //逐步显示查到的结果。如果有多个同名学生，则全部输出。 void StudentScoreManager::FindStudentByName() const { cout << "请输入待查找的学员姓名："; string name; getline(cin, name); CompareByName4Find cmp; cmp.name = name; int foundCount = 0; //已经查找到几个人了？ vector<Student>::const_iterator itStu = students.begin(); //从哪里查起 while(itStu != students.end()) { //查找学生，注意查找范围为: itStu ~ students.end() itStu = find_if(itStu, students.end(), cmp); if (itStu == students.end()) { break; //找不到人了...结束循环 } //查到该学生了... ++foundCount; //找到的人数加1。 //显示学生基本信息： cout << "姓名：" << name; cout << "，学号：" << itStu->number; //继续查：用学号查分数: FindScoreByNumber(itStu->number); cout << endl; //重要：将itStu前进到下一个位置， //意思是：下次查找时，将从当前找到的那学生的下一个位置开始找起 itStu++; } cout << "总共查到" << foundCount << "位学生，名为：" << name << endl; }

学生重名的现象并不少见。本函数相对复杂的逻辑，在于需要查出所有同名同姓的学生。假设学生的姓名列表是：

“①张一、②李二、③吴三、④李二、⑤王五、⑥end”，而我们查找的是“李二”。那么，连续查找过程为：

第1次查找范围：①~⑥,查询结果是②；

第2次查找范围：③~⑥,即从第一个李二的下一个位置开始，查询结果是④。

第3次查找范围：⑤~⑥，查询结果是⑥；

第4次尝试范围：⑥~⑥，于是结束while循环。

这个函数，也调用了FindScoreByNumber函数。

![xczy.png][]〖课堂作业〗：while循环转换成for循环

请考虑本函数中的while循环，如果要换成for表达，该如何写代码？

*   *  按学号显示成绩

//根据学号的次序输出学生成绩，没有成绩的学员，显示“查无成绩” void StudentScoreManager::OutputScoresByNumber() const { for (unsigned int i=0; i<students.size(); ++i) { unsigned int number = students[i].number; //学号 cout << "学号：" << number; cout << "，姓名：" << students[i].name; //查找成绩: CompareByNumber_Equal4Find cmp; cmp.number = number; list<Score>::const_iterator iter = find_if(scores.begin(), scores.end(), cmp); if (iter != scores.end()) { cout << "，成绩：" << iter->mark << endl; } else //没找到 { cout << "，成绩：" << "查无成绩。" << endl; } } }

再次用到find\_if。在scores全部范围内查找指定学号的成绩。

*   *  用于排序的比较

//比较器：比较成绩中的分数高低 //在InputScores()中，录入成绩之后，会立即使用本比较对成绩进行排序 struct CompareByMarkBigger { bool operator () (Score s1, Score s2) const { return (s1.mark > s2.mark); } };

虽然没有4Sort的后缀，但两个参数版本的operator()函数，在此处暗示了它用途。如果把比较时的“大于号”改成“小于号”，那么得“鸭蛋”的人将铁定得第一。

*   *  录入成绩

除了两次调用CheckInputFail，本版本这个函数最大的改进，就是在循环结束后，立即调用排序函数。

//录入学生成绩，录入完成后即行排序 void StudentScoreManager::InputScores() { while(true) { unsigned int number; cout << "请输入学号（输入0表示结束）："; cin >> number; //检查用户输入是不是合法的数字 if (CheckInputFail()) { continue; } if (number == 0) { break; } //判断学号大小是否在合法的范围内： if (number > students.size()) { cout << "错误：学号必须位于: 1 ~ " << students.size() << " 之间。" << endl; continue; } float mark; cout << "请输入成绩(" << students[number-1].name << ")："; //本版新增姓名提示 cin >> mark; //检查用户输入是不是合法的浮点数 if (CheckInputFail()) { continue; } Score score; score.number = number; score.mark = mark; scores.push_back(score); } //本版新增功能：录入成绩后，立即按分数高低排序 //保证scores中的元素永远是有序的 CompareByMarkBigger cmp; scores.sort(cmp); }

除了两次调用CheckInputFail，本版本这个函数最大的改进，就是在循环结束后，立即调用排序函数。

*   *  清空成绩

//清空成绩 void StudentScoreManager::ClearScores() { cout << "您确信要清空全部成绩数据？ (y/n)"; char c; cin >> c; if (c == 'y') { scores.clear(); cout << "成绩数据清除完毕！" << endl; } cin.sync(); }

清除前要求用户输入‘y’以确认不是误操作。在要求用户输入单个字符时，我们总不忘了在最后调用cin.sync()，以确保清除回车键。

*   *  按名次输出成绩

//按分数高低，输出每个成绩，包括学生姓名，没有参加考试学员，将不会被输出 void StudentScoreManager::OutputScoresByMark() const { //在每次录入成绩之后，我们都会调用sort立即为所有成绩进行排序 //所以scores中的所有成绩，已经是按高低分排序了 //问题是：分数相同时必须处理“名次并列”的情况。 int currentIndex = 1; //当前名次,排名从1开始 int sameMarkCount = 0; //相同分数个数 double lastMark= -1; //上一次分数，刚开始时，初始化为一个不可能的分数 for (list<Score>::const_iterator it = scores.begin(); it != scores.end(); ++it) { if (lastMark!= it->mark) { lastMark= it->mark; currentIndex += sameMarkCount; sameMarkCount = 1; } else //分数相同 { ++sameMarkCount; } cout << "名次：" << currentIndex; cout << "，姓名：" << students[it->number - 1].name; //通过学号得到名字 cout << "，学号：" << it->number; cout << "，成绩：" << it->mark << endl; } }

这段处理“并列名次”的代码，算得上本项目中最复杂的一段逻辑了。假设当前成绩排列如下：

“100、100、99、95、95、80”。

处 理逻辑是，当成绩出现变化时，比如从100变到99，此时当前名次（currentIndex）必须开始变化，变化的涨幅是前面有几个并列的100，这个 并列数目由sameMarkCount负责计数。为了能知道何时出现分数变化，我们需要lastMark来负责记住上一次的成绩，然后取它和当前分数相 比。

不 过，得到第一个成绩时，lastMark该是什么呢？我们用了一个不可能的分数，这样，第一次出现分数变化时，其实并不是从100到99，而是第一个 100。请仔细考虑，你会发现currentIndex、sameMarkCount和lastMark的初始值是互相配合的，没有谁可以单独变化。

*   *  关于

*   *  帮助
     *

void Help() { system("cls"); /*本函数通过cout输出本程序的基本使用方法 具体代码请查看配套光盘中的实际项目。 这里仅列出最后三项.*/ cout << "8#关于：关于本软件的一些信息。" << endl << endl; cout << "9#帮助：显示本帮助信息。" << endl << endl; cout << "0#退出：输入0，退出本程序。" << endl << endl; }

*   *  菜单

int Menu() { cout << "---------------------------" << endl; cout << "----学生成绩管理系统 Ver2.0----" << endl; cout << "---------------------------" << endl; cout << "请选择：(0~1)" << endl; cout << "1--#录入学生基本信息" << endl; cout << "2--#录入成绩" << endl; cout << "3--#清空成绩" << endl; cout << "---------------------------" << endl; cout << "4--#按学号次序显示成绩" << endl; cout << "5--#按分数名次显示成绩" << endl; cout << "---------------------------" << endl; cout << "6--#按学号查找学生" << endl; cout << "7--#按姓名查找学生" << endl; cout << "---------------------------" << endl; cout << "8--#关于" << endl; cout << "9--#帮助" << endl; cout << "---------------------------" << endl; cout << "0--#退出" << endl; int sel; cin >> sel; if (CheckInputFail()) { return -1; } cin.sync(); //清掉输入数字之后的回车键 return sel; }

*   *  主函数/框架

int main() { StudentScoreManager ssm; while(true) { int sel = Menu(); if (sel == 1) { ssm.InputStudents(); } else if (sel == 2) { ssm.InputScores(); } else if (sel == 3) { ssm.ClearScores(); } else if (sel == 4) { ssm.OutputScoresByNumber(); } else if (sel == 5) { ssm.OutputScoresByMark(); } else if (sel == 6) { ssm.FindStudentByNumber(); } else if (sel == 7) { ssm.FindStudentByName(); } else if (sel == 8) { About(); } else if (sel == 9) { Help(); } else if (sel == 0) { break; } else //什么也不是.. { cout << "请正确输入选择：范围在 0 ~ 9 之内。" << endl; } system("Pause"); } cout << "bye~bye~" << endl; return 0; }

我们用来到一个来自C标准库的函数：system()；它可以执行当前操作系统的控制台命令。这里用到的是“pause”。你可以试着在操作系统内打开一个控制台，然后输入pause再回车，看看屏幕上显示的是什么？

![caution.png][]〖危险〗： “Pause”命令的平台依赖性

注意不同的操作系统，其控制台命令并不兼容。“pause”在Linux下就无法执行，所以，很遗嘱，由于这一行代码，我们的这套“学生成绩管理系统”，居然就无法跨平台了。对付这种情况，c++也有很好的方法，不过，这不是我们此时需要关注的内容。

[\[回到目录\]][Link 1]

[Link 1]: http://blog.csdn.net/nanyu/archive/2008/10/03/3014022.aspx
[hint_icon.PNG]: http://www.d2school.com/bhcpp_book/images/common/hint_icon.PNG
[laugth_icon.PNG]: http://www.d2school.com/bhcpp_book/images/common/laugth_icon.PNG
[tu42.PNG]: http://www.d2school.com/bhcpp_book/images/3_14/tu42.PNG
[xczy.png]: http://www.d2school.com/bhcpp_book/images/common/xczy.png
[important.png]: http://www.d2school.com/bhcpp_book/images/common/important.png
[tu43.PNG]: http://www.d2school.com/bhcpp_book/images/3_14/tu43.PNG
[caution.png]: http://www.d2school.com/bhcpp_book/images/common/caution.png