C++ 深入介绍

C++ 语言教程

本教程的前两部分涵盖了最后两个单元中介绍的基本资料，并详细介绍了高级概念。本单元的重点内容是动态内存，以及有关对象和类的更多详细信息。 此外，还介绍了一些高级主题，例如继承、多态性、模板、异常和命名空间。我们稍后会在高级 C++ 课程中介绍这些内容。

面向对象的设计

这是一个关于面向对象的设计的绝佳教程。在本单元的项目中，我们会运用这里介绍的方法。

通过示例学习 3

本单元的重点是介绍如何使用指针、面向对象的设计、多维数组和类/对象进行更多练习。请完成以下示例。我们需要再次强调，要成为一名优秀的程序员，关键在于练习、练习、练习！

练习 1：使用指针进行更多练习

如果您需要有关指针的额外做法，请仔细阅读此资源，其中介绍了指针的所有方面，并提供了许多程序示例。

以下程序的输出是什么？请勿运行该程序，但应绘制内存图片以确定输出。 

void Unknown(int *p, int num);
void HardToFollow(int *p, int q, int *num);

void Unknown(int *p, int num) {
  int *q;

  q = #
  *p = *q + 2;
  num = 7;
}

void HardToFollow(int *p, int q, int *num) {
  *p = q + *num;
  *num = q;
  num = p;
  p = &q;
  Unknown(num, *p);
}

main() {
  int *q;
  int trouble[3];

  trouble[0] = 1;
  q = &trouble[1];
  *q = 2;
  trouble[2] = 3;

  HardToFollow(q, trouble[0], &trouble[2]);
  Unknown(&trouble[0], *q);

  cout << *q << " " << trouble[0] << " " << trouble[2];
}

手动确定输出后，运行程序以查看其是否正确。

练习 2：更多有关类和对象的练习

如果您需要对类和对象进行额外的练习，请参阅此处的资源，其中介绍了两个小类的实现。请花些时间做练习。

练习 3：多维数组

请考虑以下程序：

const int kStudents = 25;
const int kProblemSets = 10;

// This function returns the highest grade in the Problem Set array.
int get_high_grade(int *a, int cols, int row, int col) {
  int i, j;
  int highgrade = *a;

  for (i = 0; i < row; i++)
    for (j = 0; j < col; j++)
      if (*(a + i * cols + j) > highgrade)  // How does this line work?
        highgrade = *(a + i*cols + j);
  return highgrade;
}

int main() {
 int grades[kStudents][kProblemSets] = {
   {75, 70, 85, 72, 84},
   {85, 92, 93, 96, 86},
   {95, 90, 83, 76, 97},
   {65, 62, 73, 84, 73}
 };
 int std_num = 4;
 int ps_num = 5;
 int highest;

 highest = get_high_grade((int *)grades, kProblemSets, std_num, ps_num);
 cout << "The highest problem set score in the class is " << highest << endl;

 return 0;
}

此程序中有一行标记为“How does this line work?”（此行的工作原理是什么？） - 您能明白吗？ 点击此处可查看我们的说明。

编写一个程序，它会初始化一个三维数组，并使用所有三个索引的总和填充第三个维度值。 点击此处查看我们的解决方案。

练习 4：广泛的 OO 设计示例

下面详细介绍了面向对象的设计示例，该示例完整介绍了整个流程。最终代码是用 Java 编程语言编写的，但您可以根据已经取得的进展进行阅读。

请花些时间浏览整个示例。此图很好地说明了相关流程以及支持该流程的设计工具。

单元测试

简介

测试是软件工程流程的关键环节。单元测试是一种特殊的测试，它会检查单个小源代码模块的功能。单元测试始终由工程师完成，并且通常在他们为模块编写代码的同时完成。用于测试 Composer 和 Database 类的测试驱动程序是单元测试的示例。

单元测试具有以下特征。他们...

  • 单独测试组件
  • 是确定性的
  • 通常会映射到单个类
  • 避免依赖外部资源，例如数据库、文件、网络
  • 快速执行
  • 可以按任意顺序运行

有自动化框架和方法可为大型软件工程组织中的单元测试提供支持和一致性。 有一些复杂的开源单元测试框架，我们稍后会在本课程中加以介绍。

下面显示了在单元测试过程中进行的测试。

在理想情况下，我们会测试以下内容：

  1. 对模块接口进行测试，以确保信息正确进出。
  2. 系统会检查本地数据结构，以确保其正确存储数据。
  3. 系统会测试边界条件，以确保模块在限制处理的边界处正常运行。
  4. 我们会测试模块中的独立路径，以确保每条路径都能确保模块中的每条语句都至少执行一次。 
  5. 最后，我们需要检查错误是否得到正确处理。

代码覆盖率

实际上，我们无法通过测试实现完整的“代码覆盖率”。代码覆盖率是一种分析方法，用于确定测试用例套件已执行（覆盖）软件系统的哪些部分以及尚未执行的部分。如果我们尝试实现 100% 的覆盖率，那么编写单元测试所花费的时间比编写实际代码要多！请考虑针对以下所有独立路径编写单元测试。这很快就会变成一个指数问题。

在此图中，红线未测试，无色线则进行测试。

我们并没有尝试实现 100% 覆盖率，而是专注于通过测试来提高对模块正常运行的信心。我们会测试以下内容：

  • Null 情况
  • 范围测试，例如正值/负值测试
  • 边缘用例
  • 失败情况
  • 测试大多数情况下最有可能执行的路径

单元测试框架

大多数单元测试框架在路径执行期间使用断言来测试值。断言是用于检查条件是否成立的语句。断言的结果可能是成功、非严重失败或严重失败。在执行断言后，如果结果为成功或非严重失败，则程序会继续正常运行。如果发生严重故障，当前函数会被取消。

测试由设置状态或操纵模块的代码与用于验证预期结果的断言组成。如果测试中的所有断言都成功（即返回 true），则表示测试成功；否则测试失败。

一个测试用例包含一个或多个测试。我们会将测试划分为多个测试用例，以反映所测试代码的结构。在本课程中，我们将使用 CPPUnit 作为单元测试框架。有了此框架，我们就可以使用 C++ 编写单元测试并自动运行这些测试，并提供有关测试成功或失败的报告。

CPPUnit 安装

从 SourceForge 下载 CPPUnit 代码。 找到合适的目录并将 tar.gz 文件放在其中。然后，输入以下命令（在 Linux、Unix 中），将相应的 cppunit 文件名替换为相应的 cppunit 文件名： 

gunzip filename.tar.gz
tar -xvf filename.tar

如果您使用的是 Windows，则可能需要找到用于解压缩 tar.gz 文件的实用程序。下一步是编译库。切换到 cppunit 目录。里面有提供具体说明的 INSTALL 文件。通常，您需要运行以下命令：

./configure
make install

如果您遇到问题，请参阅 INSTALL 文件。这些库通常位于 cppunit/src/cppunit 目录中。要检查编译是否正常运行，请转到 cppunit/examples/simple 目录并输入“make”。如果一切正常，说明一切就绪。

此处提供了一个出色的教程。 请浏览本教程，并创建复数类及其关联的单元测试。cppunit/examples 目录中还有几个其他示例。

我为什么一定要这样做？？？

单元测试在业界至关重要，原因有很多。您应该已经熟悉了一个原因：在开发代码时，我们需要某种方法来检查我们的工作。即使我们正在开发一个非常小的程序，我们也会本能地编写某种检查工具或驱动程序，以确保我们的程序可以按预期运行。

从长期的经验来看，工程师们知道，一个程序在第一次尝试时成功的几率很小。单元测试就是在这一理念的基础上构建的，使测试计划能够自检且可重复。断言会取代手动检查输出。而且，由于结果易于解读（测试通过或失败），因此测试可以反复运行，从而提供一个安全网，使代码在更改时更具弹性。

具体而言：当您首次将完成后的代码提交到 CVS 时，效果会非常好。而且在一段时间内，它仍会继续完美运行。然后，有一天，其他人更改了您的验证码。迟早会有人破坏您的代码。你觉得他们会自行发现吗？不太可能。但是，当您编写单元测试时，有一些系统可以每天自动运行它们。 这些系统称为“持续集成”系统。因此，当工程师 X 破坏您的代码时，系统会向其发送讨厌的电子邮件，直到他们加以修复。即使 X 工程师就是你！

除了帮助您开发软件，并确保该软件在面对变化时保持安全，您还会进行单元测试：

  • 创建可执行规范以及与代码保持同步的文档。也就是说，您可以通过阅读单元测试来了解模块支持的行为。
  • 帮助您将要求与实现分离。由于您声明了外部可见的行为，因此您有机会明确地思考这种行为，而不是混淆如何实施这种行为的想法。
  • 支持实验。如果您有安全网可以在您破坏模块行为时向您发出提醒，您更有可能尝试新设计并重新配置设计。
  • 改进您的设计。若要编写全面的单元测试，您通常需要提高代码的可测试性。可测试代码的模块化程度通常比不可测试的代码更高。
  • 保持高质量。关键系统中的一个小错误就可能导致公司损失数百万美元，甚至可能导致用户的幸福感或信任度下降。单元测试提供的安全网降低了这种可能性。通过尽早发现错误，质量检查团队还可以将时间花在更复杂、更难以处理的故障场景中，而不是报告明显的故障。

请花些时间为 Composer 数据库应用编写 CPPUnit 单元测试。 如需帮助，请参阅 cppunit/examples/ 目录。

Google 的运作方式

简介

想象一下，中世纪的一位僧侣正在查看其寺院档案中的数千份手稿。“那是 Aristotle 的那首...”

修道院图书馆

幸运的是，这些手稿按内容整理，上面刻有特殊符号，以方便检索每份手稿中包含的信息。如果没有这样的整理，就很难找到相关的手稿。

存储和检索大型集合中的书面信息的活动称为信息检索 (IR)。几个世纪以来，这种活动变得越来越重要，尤其是纸张和印刷机等发明。过去只有少数人在家。然而，如今有数以亿计的用户每天在使用搜索引擎或在桌面上进行搜索时，都会参与信息检索。

信息检索入门

戴帽子的猫

苏斯博士在 30 年的时间里撰写了 46 本儿童图书。他的书里讲述了猫、牛和大象，以及谁、咧嘴笑和大笑。你还记得哪个故事出过哪些生物吗？除非您是家长，否则只有孩子可以告诉您苏斯博士的哪一组故事里有这些生物：

（COW 和 BEE）或 CROWS

我们将应用一些经典的信息检索模型来帮助解决这一问题。

一种显而易见的方法就是暴力：阅读全部 46 名苏斯博士的故事，然后开始阅读。对于每本图书，请记下哪本图书包含 COW 和 BEE 字样，同时查找包含 CROWS 一词的图书。在这方面，计算机要比我们快得多。如果我们以数字形式保存了苏斯博士著的所有文字（比如文本文件），我们就可以通过 grep 查找这些文件。对于像苏斯博士的书这样的小藏书，这种方法很有效。

不过，在很多情况下，我们还需要更多功能。例如，当前在线的所有数据的集合过大，grep 无法处理。此外，我们不仅仅想要符合我们条件的文档，已经习惯于按相关性对文档进行排名。

除 grep 之外，另一种方法是在执行搜索之前为集合中的文档创建索引。IR 中的索引类似于教科书背面的索引。我们制作了一个列表，列出苏斯博士的每篇故事中的所有字词（即“字词”），去掉“the”“and”等字词以及其他连接词、介词等（这些字词称为“停用词”）。然后，我们会采用适当的方式呈现这些信息，以便于查找相关术语和识别其所属的故事。

一种可能的表示形式是使报道在顶部、每行列出的术语的矩阵。某列中若为“1”，则表示该字词出现在与该列对应的故事中。

书和词表

我们可将每一行或各列视为一个位矢量。行的位矢量表示相应字词出现在哪些报道中。列的位矢量表示故事中出现的字词。

回到我们最初的问题：

（COW 和 BEE）或 CROWS

我们获取这些项的位矢量，首先执行按位 AND，然后对结果执行按位 OR。

（100001 和 010011）或 000010 = 000011

答案是：“张杰先生！“Can You?”和“The Lorax”。此图显示了布尔检索模型，它是一个“完全匹配”模型。

假设我们要扩展矩阵，以包含苏斯博士的所有故事以及故事中的所有相关术语。该矩阵会显著增长，重要的观察结果是大多数条目为 0。矩阵可能不是索引的最佳表示法。我们需要找到一种方法来存储 1 标记。

一些增强功能

IR 中用于解决此问题的结构称为“反转索引”。我们保存了一个术语字典，然后针对每个术语，我们有一个记录这些术语所在的文档的列表。此列表称为帖子列表。单链接列表可以很好地表示这种结构，如下所示。

如果您不熟悉链接列表，只需在 Google 上搜索“C++ 中的链接列表”，即可找到大量资源，其中介绍了如何创建链接列表以及如何使用链接列表。我们将在后续单元中更详细地介绍这一点。

请注意，我们使用文档 ID (DocIDs) 代替故事名称。我们还会对这些 DocID 进行排序，因为这有利于处理查询。

我们如何处理查询？对于原始问题，我们首先找到 COW 帖子列表，然后找到 BEE 帖子列表。然后，我们会将它们“合并”在一起：

  1. 将标记置于两个列表中，并同时浏览两个帖子列表。
  2. 在每一步中，比较两个指针指向的 DocID。
  3. 如果它们相同，请将该 DocID 放入结果列表中，否则将指针指向较小的 docID。

下面展示了如何构建倒排索引：

  1. 为每个相关文档分配一个 DocID。
  2. 对于每个文档，确定其相关术语（词元化）。
  3. 对于每个术语，创建一条记录，该记录由该术语、出现该术语的 DocID 以及该文档中的频率。请注意，如果特定字词出现在多个文档中，则可能有多个记录。
  4. 按术语对记录进行排序。
  5. 创建字典和帖子列表，方法是处理某个术语的单个记录，以及合并出现在多个文档中的术语的多条记录。创建一个 DocID 链接列表（按排序顺序）。每个术语还具有一个频率，该频率是某个术语的所有记录中发生频率的总和。

项目

找到几个可以试验的较长的明文文档。该项目是使用上述算法根据文档创建倒排索引。您还需要创建一个用于查询输入的接口和一个用于处理查询的引擎。您可以在论坛上找到项目合作伙伴。

完成此项目的可能流程如下：

  1. 首先要定义一个用于在文档中识别术语的策略。列出您能想到的所有无效搜索字词，并编写一个函数来读取文件中的字词、保存字词并消除无效搜索字词。在查看迭代中的术语列表时，您可能需要向列表中添加更多无效搜索字词。
  2. 编写 CPPUnit 测试用例来测试您的函数，并编写 makefile 来整合 build 所需的一切。请将您的文件签入 CVS，尤其是在与合作伙伴合作时。您可能需要研究如何向远程工程师开放您的 CVS 实例。
  3. 添加处理以包含位置数据，即，字词位于哪个文件以及该文件中的哪个位置？您可能需要进行计算，以定义页码或段落编号。
  4. 编写 CPPUnit 测试用例来测试此附加功能。
  5. 创建一个倒排索引，并将位置数据存储在每个字词的记录中。
  6. 编写更多测试用例。
  7. 设计一个可让用户输入查询的界面。
  8. 使用上述搜索算法处理倒排索引，并将位置数据返回给用户。
  9. 请务必也为最后这部分添加测试用例。

正如我们在所有项目中所做的那样，您可以在论坛中聊天并寻找项目合作伙伴，并相互分享想法。

额外功能

许多 IR 系统中的常见处理步骤称为“词干提取”。词干提取背后的主要理念是，搜索“检索”相关信息的用户也将对包含“检索”“已检索”“正在检索”等信息的文档感兴趣。系统可能会因词干不畅而容易出错，因此这有点棘手。例如，对“信息检索”感兴趣的用户可能会因词干提取而收到标题为“金毛检索器信息”的文档。Porter 算法是一种实用的词干提取算法。

应用：Go Anywhere！

如需查看这些概念的应用，请访问 Panoramas.dk。