[toc]

前言

• 相比于《C++ Primer》，这是一本轻量级作品，适用于有编程基础的人快速入门C++。

  • 精细度：本书的精细度调降了相当程度。
  • 语言核心：介绍程序语言本身的特性，藉此来为不同问题提供解决之道。
  • 范例的数量：习题解答置于附录A。”

• 本书的结构与组织：七章，两附录

  • 第一章：C++语言预先定义的部分。内建数据类型，运算符，标准库中的vector和string类，条件语句和循环语句，输入输出程序库iostream。
  • 第二章：函数的设计与使用。inline函数，重载函数overloaded，函数模板function template，函数指针。
  • 第三章：标准模板库Standard Template Library/STL。容器类vector/list/set/map，作用于容器的泛型算法sort/copy/merge，附录B常用泛型算法。
  • 第四章：类机制的设计与使用。类class，面向对象的类层次体系，建立专属数据类型。
  • 第五章：扩展类，多个相关类形成族系，面向对象的类层次体系，继承、动态绑定dynamic binding
  • 第六章：类模板class template。类的先行描述，将类用于多个数据类型，抽离并参数化。二叉树类模板。
  • 第七章：异常处理机制exception handling facility。标准程序库异常体系。
  • 附录A：习题解答。
  • 附录B：常用泛型算法的讨论和使用。

1 C++编程基础

• C++程序语言的基本组成

  • 基础数据类型：布尔值Boolean，字符character，整数integer，浮点数floating point

  • 运算符：操作基础数据类型

  • 算术运算符：加法+，累加++
    • 关系运算符：等号==，小于等于<=
    • 逻辑运算符
    • 赋值运算符：赋值=，复合赋值+=
    • 条件运算符：?:

  • 控制流：条件分支if，循环控制while，改变程序控制流程

  • 复合类型：指针，数组

  • 标准程序库：字符串string，向量vector

1.1 如何撰写C++程序

• 每个C++程序都是从main函数开始。

• 关键字：所谓关键字（keyword），就是程序语言预先定义的一些具有特殊意义的名称。int用来表示语言内置的整数数据类型。

• 函数：函数（function）是一块独立的程序代码序列（code sequence），能够执行一些运算。它包含四个部分：返回值类型（return type）、函数名称、参数列表（parameter list），以及函数体（function body）。

• 返回值：函数的返回值通常用来表示运算结果。main（）函数返回整数类型。main（）的返回值用来告诉调用者，这个程序是否正确执行。习惯上，程序执行无误时我们令main（）返回零。若返回一个非零值，表示程序在执行过程中发生了错误。
  • 函数名：函数的名称由程序员选定。函数名最好能够提供某些信息，让我们容易了解函数实际上在做些什么。函数的名称由程序员选定。函数名最好能够提供某些信息，让我们容易了解函数实际上在做些什么。main并非是程序语言定义的关键字。但是，执行我们这个C++程序的编译系统，会假设程序中定义有main（）函数。如果我们没有定义，程序将无法执行。
  • 参数列表：函数的参数列表（parameter list）由两个括号括住，置于函数名之后。空的参数列表，如main（），表示函数不接受任何参数。参数列表用来表示“函数执行时，调用者可以传给函数的类型列表”。列表之中以逗号隔开各个类型。
  • 函数体：函数的主体（body）由大括号（{}）标出，其中含有“提供此函数之运算”的程序代码。双斜线（//）表示该行内容为注释，也就是程序员对程序代码所做的某些说明。注释的撰写是为了便于阅读者更容易理解程序。编译过程中，注释会被忽略掉。双斜线之后直至行末的所有内容，都会被当作程序注释。

• 数据的输入与输出：并非C++程序语言本身定义的一部分，而是由 C++的一套面向对象的类层次体系（classes hierarchy）提供支持，并作为C++标准库（standard library）的一员。

• 类（class）：是用户自定义的数据类型（user-defineddata type）。面向对象的类层次体系（classhierarchy）定义了整个家族体系的各相关类型。

• 基础数据类型：布尔值（Boolean）、字符（character）、整数（integer）、浮点数（floatingpoint）。

• class机制，赋予了我们“增加程序内之类型抽象化层次”的能力。class的定义，一般来说分为两部分，分别写在不同的文件中。其中之一是所谓的“头文件（header file）”，用来声明该 class 所提供的各种操作行为（operation）。另一个文件，程序代码文件（program text），则包含了这些操作行为的实现内容（implementation）。

• 欲使用class，我们必须先在程序中包含其头文件。头文件可以让程序知道class的定义。C++标准的“输入/输出库”名为iostream，其中包含了相关的整套class，用以支持对终端和文件的输入与输出。我们必须包含iostream库的相关头文件，才能够使用它。

• 利用已定义好的cout（读作see out）对象，将信息写到用户的终端中。output运算符（＜＜）可以将数据定向到cout。

• 语句（statement）：语句是C++程序的最小独立单元。就像自然语言中的句子一样。语句以分号作为结束。

• 声明语句（declaration statement）：读取之前，我们必须先定义一个对象，用以储存数据。欲定义一个对象，必须指定其数据类型，再给定其标识符。还必须让程序知道string class的定义。因此还必须在程序中包含string class的头文件。

• 利用已定义好的cin（读作see in）对象来读取用户在终端上的输入内容。通过input运算符（＞＞）将输入内容定向到具有适当类型的对象身上。

• 字符常量：所谓字符常量（character literal）系由一组单引号括住。字符常量分为两类：第一类是可打印字符，例如英文字母（’a’、’A’，等等）、数字、标点符号（’；’、’-‘，等等）。另一类是不可打印字符，例如换行符（’\n’）或制表符（tab，’\t’）。由于不可打印字符并无直接的表示法（这表示我们无法使用单一而可显示的字符来独立表示），所以必须以两个字符所组成的字符序列来表示。

• 将换行（newline）字符常量写至cout。一般而言，所有内置数据类型都可以用同样的方式来输出——也就是说，只需换掉output运算符右方的值即可。

• 我们在自己的应用程序中定义了新的class时，也应该为每一个class提供它们自己的output运算符（第4章会告诉你如何办到这件事情）。这么一来便可以让那些class的用户得以像面对内置类型一样地以相同方式输出对象内容。如果嫌连续数行的输出语句太烦人，也可以将数段内容连成单一输出语句。

• return语句：我们以return语句清楚地表示main（）到此结束。return是C++中的关键字。此例中的0是紧接于return之后的表达式（expression），也就是此函数的返回值。先前我曾说过，main（）返回0即表示程序执行成功。

• 命名空间：using和namespace都是C++中的关键字。std是标准库所驻之命名空间（namespace）的名称。标准库所提供的任何事物（诸如string class以及cout、cin这两个iostream类对象）都被封装在命名空间std内。所谓命名空间（namespace）是一种将库名称封装起来的方法。通过这种方法，可以避免和应用程序发生命名冲突的问题（所谓命名冲突是指在应用程序内两个不同的实体〔entity〕具有相同名称，导致程序无法区分两者。命名冲突发生时，程序必须等到该命名冲突获得解析〔resolve〕之后，才得以继续执行）。命名空间像是在众多名称的可见范围之间竖起的一道道围墙。

• 若要在程序中使用string class以及cin、cout这两个iostream类对象，我们不仅需要包含＜string＞及＜iostream＞头文件，还得让命名空间std内的名称曝光。using指令便是让命名空间中的名称曝光的最简单方法。

• 练习
  • 1.1：输入名字，输出欢迎语

    #include <iostream>
    #include <string>
    using namespace std;
    int main(void)
    {
      string user;    
      cout << "Please enter your name: ";    
      cin >> user;    
      cout << "\nHello, " << user << " ... and goodbye!\n";    
      return 0; 
    }
    

  • 1.4：输入姓名，输出欢迎语 ```cpp #include #include using namespace std;

  int main(void) { string first_name, last_name; cout « “Please enter your first name: “; cin » first_name; cout « “Please enter your last name: “; cin » last_name; cout « “Hello, “ « first_name « ‘ ‘ « last_name « ” … and goodbye!\n”;

  return 0; } ```
  

1.2 对象的定义与初始化

• 对象命名：为了定义对象，我们必须为它命名，并赋予它数据类型。对象名称可以是任何字母、数字、下画线（underscore）的组合。大小写字母是有所区分的。对象名称不能以数字开头。当然，任何命名都不能和程序语言本身的关键字完全一致。例如 delete 是语言关键字，就不可以用于程序内的命名。

• 数据类型：每个对象都属于某个特定的数据类型。对象名称如果设计得好，可以让我们直接联想到该对象的属性。数据类型决定了对象所能持有的数值范围，同时也决定了对象应该占用多少内存空间。

• 内置数据类型：所谓 class，便是程序员自行定义的数据类型。除此之外，C++还提供了一组内置的数据类型，包括布尔值（Boolean）、整数（integer）、浮点数（floatingpoint）、字符（character）。每一个内置数据类型都有一个相应的关键字，用于指定该类型。

• 定义对象：在单一声明语句中一并定义多个对象，其间以逗号分隔。

• 对象初始化：一般来说，将每个对象初始化，是个好主意——即使初值只用来表示该对象尚未具有真正有意义的值。

• 另外还有一种不同的初始化语法，称为“构造函数语法（constructor syntax）”。
  • 用 assignment运算符（=）进行初始化”这个操作系沿袭自C语言。如果对象属于内置类型，或者对象可以单一值加以初始化，这种方式就没有问题。
  • 但是如果对象需要多个初值，这种方式就没有办法完成任务了。于是便引入了用来处理“多值初始化”的构造函数初始化语法（constructor initialization syntax）。

• 模板类：出现于complex之后的尖括号，表示complex是一个template class（模板类）。template class允许我们在“不必指明data member类型”的情况下定义class。

• template class机制使程序员得以直到使用template class时才决定真正的数据类型。程序员可以先插入一个代名，稍后才绑定至实际的数据类型。

• 浮点数：C++支持三种浮点数类型，分别是以关键字 float 表示的单精度（single precision）浮点数，以关键字 double 表示的双精度（double precision）浮点数，以及连续两个关键字long double表示的长双精度（extended precison）浮点数。

• 字符类型：关键字char表示字符（character）类型。单引号括住的字符代表所谓的字符常量，例如’a’、’7’、’；’。此外还有一些特别的内置字符常量（有时也称为“转义字符〔escape sequence〕”），我们常常会在字符串常量中使用这些特殊字符。

• 换行符\n，制表符\t，null字符\0，单引号'，双引号"，反引号\

• 布尔类型：C++提供了内置的Boolean类型，用以表示真假值（true/false）。Boolean对象系由关键字bool指出。其值可为true或false（两者都是常量）。

• 常量：截至目前我们所定义出来的对象，其值都会在程序执行过程中改变。但有时候我们需要一些用来表示常量的对象，被定义为const的对象，在获得初值之后，无法再有任何变动。如果你企图为const对象指定新值，会产生编译期错误。

1.3 撰写表达式

• 运算符：内置数据类型都可运用这样一组运算符，其中包括算术运算符、关系运算符、逻辑运算符、复合赋值（compound assignment）运算符。

• 算术运算符：Arithemetic Operator

• 加法运算：a + b
  • 减法运算：a - b
  • 乘法运算：a * b
  • 除法运算：a / b。两个整数相除会产生另一个整数（商）。小数点之后的部分会被完全舍弃；也就是说，并没有四舍五入。
  • 余数运算：a % b

• 条件运算符：conditional operator

• 形式：expr ? 表达式1 : 表达式2
  • 如果expr的运算结果为true，那么紧接在’？’之后的表达式会被执行。如果expr的运算结果为false，那么’：’之后的表达式会被执行。
  • 条件表达式的值如果为零，会被视为false，其他非零值则一律被视为true。

• 复合赋值运算符：compound assignment。是一种简便的表达方法。在对象身上使用某个运算符，然后将结果重新赋值给该对象

• 复合赋值运算符可以和每个算术运算符结合，形成+=、-=、＊=、/=和%=。

• 递增/递减运算符：increment，decrement。使对象值递增或递减。

• 递增运算符和递减运算符都有前置（prefix）和后置（postfix）两种形式。前置形式中，原值先递增（或递减），之后才被拿来使用。至于后置形式写法，对象原值会先供给表达式进行运算，然后才递增（或递减）。

• 关系运算符：任何一个关系运算符（relational operator）的求值结果不是true就是false。关系运算符包括以下六个：

  • ==相等：a==b
  • !=不等：a!=b
  • ＜小于：a ＜ b
  • ＞大于：a ＞ b
  • ＜=小于等于：a ＜=b
  • ＞=大于等于：a ＞=b

• if语句：if语句之后的表达式运算结果为true时，条件成立，于是紧接其后的语句便会被执行。加上else子句，如果条件不成立，那么便开始对接下来的else子句求值。

• 逻辑运算符：

  • 逻辑或运算符

    ：只需左右两个表达式中的一个为true，OR逻辑运算符的求值结果便为true。左侧表达式会先被求值，如果其值为 true，剩下的另一个表达式就不需要再被求值（此所谓短路求值法）。

  • 逻辑与运算符&&：在左右两个表达式的结果皆为 true时，其求值结果方为 true。第一个表达式结果若为false，则AND运算符的求值结果即为false，其余表达式不会（不需要）再被求值。
  • 逻辑非运算符!：如果有一个表达式的运算结果为false，那么将NOT逻辑运算符用于其上，结果为true。

• 运算符的优先级：如果同一个表达式中使用多个运算符，其求值（evaluate）顺序是由每一个运算符事先定义的优先级来决定。

• 如果想要改变内置的运算符优先级，可利用小括号。我们应该明确地加上小括号，来实现我们希望的运算优先级。

• 运算符优先级简列于下。位置在上者的优先级高于位置在下者。同一行的各种运算符具有相同的优先级，其求值次序取决于它在该表达式中的位置（由左至右）。

  • 逻辑运算符NOT
  • 算术运算符（＊，/，%）
  • 算术运算符（+，-）
  • 关系运算符（＜，＞，＜=，＞=）
  • 关系运算符（==，!=）
  • 逻辑运算符AND
  • 逻辑运算符OR
  • 赋值（assignment）运算符

*1.4 条件语句和循环语句

• 语句：基本上，从 main（）的第一行语句（statement）开始，程序里的每行语句都只会被依序执行一次。

• 控制流：

• if语句让我们依据某个表达式的结果（视为真假值）来决定是否执行一条或多条连续的语句。可有可无的else子句，更可让我们连续检验多个测试条件。
  • 循环（loop）语句，可以让我们根据某个表达式结果（视为真伪条件），重复执行单一或连续多条语句。

• 条件语句：

• if语句：

  • if语句中的条件表达式（condition expression）必须写在括号内。如果此表达式的运算结果为true，那么紧接在if之后的那一条语句便会被执行。如果想执行多条语句，那么必须在if之后以大括号将这些语句括住（这样便称为一个语句块）。
    • if语句也可以配合else子句来使用。else子句用以表示一旦if语句的测试条件不成立，我们所希望执行的单行语句或语句块。
    • 使用 else子句的第二种方式，便是将它和两条（或更多）if语句结合。如果其中一条 if语句为 true，其他两者必为false。因此我们可以结合一连串的else-if子句，来反映这些if语句间的关系。第一条if语句会先被求值。如果其值为true，紧接在后的语句便会被执行，接下来的所有else-if子句都不会被求值。但如果第一条 if语句的求值结果为 false，便会接着对下一条 if语句求值，直到其中有某一个条件成立为止。如果所有条件都不成立，那么最末的else子句会被执行。
    • 嵌套的（nested）if-else子句有个很容易令人困惑的地方，那就是要正确组织其逻辑其实是比较难的一件事。

if (expr) { // expr is ture, statement 1 } else { // expr is false, statement 2 }

• switch语句：如果测试条件值属于整数类型，我们还可以改用switch语句来取代一大堆的if-else-if子句。

  • 关键字switch之后紧接着一个由小括号括住的表达式（是的，对象名称也可视为表达式），该表达式的值必须是整数形式。关键字switch之后是一组case标签，每一个标签之后都指定有一个常量表达式。在switch之后的表达式值被计算出来后，便依次和每个case标签的表达式值相比较。如果找到相符的case标签，便执行该case标签之后的语句。如果找不到吻合者，但有default标签，便执行default标签之后的语句。如果default标签也没有，就不执行任何操作。
    • 向下穿越：为什么我在每个case标签的最末加上break语句呢？要知道，每个case标签的表达式值都会依次和switch表达式值相比较，不吻合者便依次跳过。若某个case标签的表达式值吻合，便开始执行该case标签之后的语句——这个操作会一直执行到switch语句的最下面。当某个标签和switch的表达式值吻合时，该case标签之后的所有case标签也都会被执行，除非我们明确使用break来结束执行。这也正是break语句的用途。

switch (int_expr) { case 1: // statement 1 break; case 2: // statement 2 break; default: // default statement break; }

• 循环语句：只要条件表达式不断成立（亦即其运算结果为 true），循环语句便会不断地执行单一语句或整个语句块。

• while循环：

  • while循环即将开始之际，会先对括号内的条件表达式求值。如果其值为true，则紧接在while循环之后的语句或语句块便会被执行。执行完毕之后，条件表达式会被重新求值。这种求值/执行的工作模式不断循环，直到条件表达式的值变成 false。通常，语句块在某种状态下会将该条件表达式的值设置为 false。如果条件表达式的值永远不为 false，我们便陷入了一个无穷循环之中——这样的程序逻辑当然不正确。
    • 如果在执行循环内的语句时遇上break语句，循环便会结束。
    • 我们也可以利用 continue 语句来遽然终止循环的当前迭代（current iteration）。执行continue语句，于是结束循环的当前迭代，也就是说，while循环中的剩余部分便不会被执行。循环会重新来过，而条件表达式会被再一次求值。

// intial statement while (condition_expr) { // body statement // condition iteration }

1.5 如何运用Array和Vector

• 容器：使用可存放连续整数值的容器（container）类型。这种类型不仅允许我们以名称（name）取用容器中的元素，也允许我们以容器中的位置来取用元素。C++允许我们以内置的array（数组）类型或标准库提供的vector类来定义容器。一般而言，我建议使用vector甚于array。不过，大量现存的程序代码都使用array。

• 数组：要定义array，我们必须指定array的元素类型，还得给予array一个名称，并指定其尺度大小——亦即array所能储存的元素个数。array的大小必须是个常量表达式（constant expression），也就是一个不需要在运行时求值的表达式。

• int arr[18];

• 向量：至于定义vector object，我们首先必须包含vector头文件。vector是个classtemplate，所以我们必须在类名之后的尖括号内指定其元素类型，其大小则写在小括号中；此处所给予的大小并不一定得是个常量表达式。

• vector seq(18);

• 访问：无论 array 或 vector，我们都可以指定容器中的某个位置，进而访问该位置上的元素。索引操作（indexing）系通过下标运算符（[]）达成。这里必须注意的小技巧是，容器的第一个元素位置为0而非1。因此，容器的最后一个元素必须以容器的大小减一加以索引。

• for循环：要依次迭代vector或array中的多个元素时，通常会使用C++中的另一种重要的循环语句，for循环。for循环包含以下几个组成部分：

• 其中的init-statement会在循环开始执行前被执行一次。

  • condition用于循环控制，其值会在每次循环迭代之前被计算出来。如果condition为true，statement便会被执行。statement可以是单一语句，也可以是个语句块。如果condition第一次求值即为false，那么statement一次也不会执行。
  • expression 会在循环每次迭代结束之后被求值。通常它用来更改两种对象的值。一个是在 init-statement 中被初始化的对象，另一个是在 condition 中被检验的对象。
  • 如果我们愿意，也可以在init-statement或expression甚至condition处（较罕见）留空，不写任何东西。其中的分号是必要的，因为必须利用它来表示init-statement留空。

for (init_statement; condition; expression) statement;

• 初始化：

• 如果是array，我们可以指定初始化列表（initialization list），借由逗号分隔每一个要指定的值，这些值便成为array的全部或部分元素。初始化列表内的元素个数，不能超过array的大小。如果前者的元素数量小于array的大小，其余的元素值会被初始化为0。初始化列表内的元素个数，不能超过array的大小。如果前者的元素数量小于array的大小，其余的元素值会被初始化为0。

  • int arr[5] = {1, 2, 3, 4, 5};

  • vector不支持上述这种初始化列表。有个冗长的写法可以为每个元素指定其值。另一个方法是利用一个已初始化的array作为该vector的初值。传入两个值给vector。这两个值都是实际内存位置。它们标示出了“用以将vector初始化”的元素范围。

  • vector seq(3); seq[0] = 1; seq[1] = 2; seq[2] = 3;

    • int arr[3] = {1, 2, 3}; vector seq(arr, arr+3);

• 使用vector：array和vector之间存在一点差异，那就是vector知道自己的大小是多少。

for (int i = 0; i < seq.size(); i++) cout « seq[i] « ’ ‘;

1.6 指针带来弹性

• 指针的作用：我们将通过使用指针（pointer），舍弃以名称指定的方式，间接地访问每个vector，借此达到透明化的目的。指针为程序引入了一层间接性。我们可以操作指针（代表某特定内存地址），而不再直接操作对象。

• 在我们的程序中，我定义了一个可以对整数vector寻址的指针。每一次循环迭代，便更改指针值，使它定位到不同的vector。随后的指针操作行为不需要更改。
  • 在我们的程序中，指针主要做两件事情。它可以增加程序本身的弹性，但同时也增加了直接操作对象时所没有的复杂度。

• 指针：

• 定义：指针内含某特定类型对象的内存地址。当我们要定义某个特定类型的指针时，必须在类型名称之后加上＊号。

  • int *p;

  • 初始化：可以使用取址运算符&，获取对象所在的内存地址，并将指针的初值设置为对象的内存地址。

  • int x = 1; int *p = &x;

  • 访问：如果要访问一个由指针所指的对象，我们必须对该指针进行提领（dereference）操作——也就是取得“位于该指针所指内存地址上”的对象。在指针之前使用＊号，便可以达到这个目的。

  • int y = *p + 1;

  • 指针所具有的双重性质：既可以让我们操作指针包含的内存地址，也可以让我们操作指针所指的对象值。

  • 指针可能并不指向任何对象。如果指针定位到某个对象，则对指针进行提领（dereference）操作没有错误。但如果指针指向任何对象，则提领指针导致未知的执行结果。这意味着，在使用指针时，必须在提领之前先确定它的确指向某对象。

  • 空指针：一个未指向任何对象的指针，其地址值为0。有时候我们称之为null指针。任何指针都可以被初始化，或是令其值为0。只有在pi持有一个非零值时，其求值结果才会是true。

  • int *p = 0;

• vector对象指针：

• 当我们需要一个指针，指向一个“元素类型为int”的vector时。由于我们所要的指针系用来指向vector＜int＞，因此我把它命名为pv，并给定初值0。

  • vector *pv = 0;

  • 我们也可以明确地将向量vector的内存地址赋值给它。但这种赋值方式会牺牲程序的透明性。另一种方案是将每个数列的内存地址存入某个数组中，这样我们就可以通过索引的方式，透明地访问这些向量。

  • pv = &seq;

    • vector *pvs[3] = {&seq1, &seq2, &seq3};

• 随机化：可以通过C语言标准库中的rand（）和srand（）两个函数达成。rand（）和srand（）都是标准库提供的所谓伪随机数（pseudo-randomnumber）生成器。

• srand（）的参数是所谓随机数生成器种子（seed）。
  • 每次调用rand（），都会返回一个介于0和“int所能表示的最大整数”间的一个整数。
  • 这两个函数的声明位于cstdlib头文件。

#include srand(seed); rand_idx = rand() % cnt;

• 使用对象指针：使用对象指针，和使用内置类型的指针略有不同。这是因为classobject关联了一组我们可以调用（invoke）的操作（operation）。

• 调用对象方法：dot成员选择运算符（member selection operator）, ，用来选择我们想要进行的操作。

  • seq.size();

  • 指针调用方法：如果要通过指针来选择操作，必须改用arrow成员选择运算符。由于指针可能并未指向任何对象，所以在调用empty（）之前，应该先检验指针是否为非零值。

  • pv->size();

  • 下标运算符：如果要使用下标运算符（subscript operator），我们必须先提领pv。由于下标运算符的优先级较高，因此指针提领操作的两旁必须加上小括号。

  • (*pv)[1] = 2;

*1.7 文件的读写

• 数据持久化：用户可能会一再执行这个程序。我们应该让用户的数据可以在不同的“会话（session）”累计使用。为了达到这个目的，我们必须：（1） 每次执行结束，将用户的姓名及会话的某些数据写入文件，（2） 在程序开启另一个会话时，将数据从文件中读回。

• 文件写入：

• 头文件：要对文件进行读写操作，首先得包含fstream头文件。

  • #include

  • 打开文件：为了打开一个可供输出的文件，我们定义一个ofstream（供输出用的file stream）对象，并将文件名传入。如果指定的文件并不存在，便会有一个文件被产生出来并打开供输出使用。如果指定的文件已经存在，这个文件会被打开用于输出，而文件中原有的数据会被丢弃。如果文件已经存在，但我们并不希望丢弃其原有内容，而是希望将新数据增加到该文件中，那么我们必须以追加模式（append mode）打开这个文件。为此，我们提供第二个参数 ios_base::app给ofstream对象。

  • ofstream outfile(“data.txt”); // 以写入模式打开文件
    • ofstream outfile(“data.txt”, ios_base::app); // 以追加模式打开文件

  • 打开检验：文件有可能打开失败。在进行写入操作之前，我们必须确定文件的确打开成功。最简单的方法便是检验class object的真伪。如果文件未能成功打开，则该ofstream对象的求值结果为false。

  • 本例中我们将信息写入cerr，告知用户这个状况。cerr代表标准错误设备（standard error）。和cout一样，cerr将其输出结果定向到用户的终端。两者的唯一差别是，cerr的输出结果并无缓冲（bufferred）情形——它会立即显示于用户终端中。

  • 写入文件：如果文件顺利打开，我们便将输出信息定向到该文件，就像将信息写入 cout 及cerr 这两个ostream对象一样。

  • endl是事先定义好的所谓操纵符（manipulator），由iostream library提供。操纵符并不会将数据写到iostream，也不会从中读取数据，其作用是在iostream上执行某些操作。endl会插入一个换行符，并清除输出缓冲区（output buffer）的内容。
    • 除了endl，另有一些事先定义好的操纵符，例如hex（以十六进制显示整数）、oct（以八进制显示整数）、setprecision（n）（设定浮点数显示精度为n）。

if (!outfile) cerr « “Open file failure!\n”; else outfile « data « endl; // write data to file

• 文件读取：

• 打开文件：如果要打开一个可供读取的文件，我们就定义一个ifstream（供输入的filestream）对象，并将文件名传入。如果文件未能成功打开，该ifstream对象就为false。如果成功，该文件的写入位置会被设定在起始处。

  • ifstream infile(“data.txt”); // 以读取模式打开文件

  • 读取文件：while循环的每次迭代都会读取文件的下一行内容。这样的操作会持续到文件末才结束。这条语句的返回值就是从infile读到的class object。一旦读到文件末尾，对读入class object的求值结果就会是false。因此我们可以在while循环的条件表达式中，以此作为结束条件。

  • while (infile » name)

ifstream infile(“data.txt”); if (!infile) // fail to open else { // open success string name; int n1, n2; while (infile » name) // read each line { infile » n1 » n2; // process } }

• 文件同时读写：如果想要同时读写同一个文件，我们得定义一个fstream对象。为了以追加模式（append mode）打开，我们得传入第二参数值ios_base::in

  ios_base::app。

• 当我们以追加模式来打开档案，文件位置会位于末尾。如果我们没有先重新定位，就试着读取文件内容，那么立刻就会遇上“文件结束”的状况。seekg（）可将iofile重新定位至文件的起始处。由于此文件是以追加模式开启，因此任何写入操作都会将数据添加在文件末尾。

• 练习：

• 1.5：输入用户名字，根据名字长度产生相应输出

/* 1.5 Input a user’s name, respond according to name length. */ # include # include using namespace std; int main(void) { string name; cout << "Please enter your name: "; cin >> name; switch (name.size()) { case 0: cout << "hello, user with no name\n"; break; case 1: cout << "hello, " << name << " with 1-character name\n"; break; default: cout << "hello, " << name << endl; break; } return 0; }

• 1.6：输入整数序列，输出和与平均值。

/* 1.6 Input integer sequence, output sum and average. */ # include # include using namespace std; int main(void) { vector vec; int i, x; // input integers while (cin >> x) vec.push_back(x); // sum and average int total = 0; double avg = 0.0; for (i = 0; i < vec.size(); i++) total += vec[i]; avg = total / (double) vec.size(); // output cout << endl; cout << "sum: " << total << ", average: " << avg << endl; return 0; }

• 1.7：读取文本文件中的词到vector中，排序后将结果写入到另一个文件。

/* 1.7 Read text file, sort words and write to another file. */ #include #include #include #include #include using namespace std; int main(void) { ifstream infile("data.txt"); ofstream outfile("sort.txt"); if (!infile || !outfile) { cerr << "Fail to open file" << endl; return -1; } // read file string word; vector words; while (infile >> word) words.push_back(word); // print words int i; for (i = 0; i < words.size(); i++) cout << words[i] << ' '; cout << endl; // sort sort(words.begin(), words.end()); // write file for (i = 0; i < words.size(); i++) outfile << words[i] << ' '; outfile << endl; return 0; }

2 面向过程的编程风格

• 函数：通常我们会抽取通用的操作，例如计算Fibonacci数列元素、产生随机数，等等，将它们实现为独立函数。将函数独立出来的做法可带来三个主要好处：

• 第一，以一连串函数调用操作，取代重复编写相同的程序代码，可使程序更容易读懂。
  • 第二，我们可以在不同的程序中使用这些函数。
  • 第三，我们可以更容易地将工作分配给协作开发团队。
• 本章涵盖了独立函数的众多基本编写原则，并简要讨论了所谓的重载（overloaded）以及function template，同时也说明了函数指针的运用技巧。

*2.1 如何编写函数

• 函数定义：每一个函数必须定义以下四个部分：

• 返回类型。函数如果没有返回值，其返回类型为void。
  • 函数名。好名称可以帮助我们理解函数操作的实际内涵
  • 参数列表（parameterlist）。函数参数扮演着占位符（placeholder）的角色，它让用户在每次调用函数时，将要传入的值放在其中，以便函数使用。也就是说，参数所代表的值随每次调用操作而有所不同。参数的指定包括类型及名称。函数的参数列表可以是空的。
  • 函数体。此即操作本身的工作逻辑的实现内容。通常它会使用函数的参数值。函数体紧接在参数列表之后，由大括号括起来。

• 函数声明：函数必须先被声明，然后才能被调用（被使用）。函数的声明让编译器得以检查后续出现的使用方式是否正确——是否有足够的参数、参数类型是否正确，等等。函数声明不必提供函数体，但必须指明返回类型、函数名，以及参数列表。此即所谓的函数原型（function prototype）。

• 声明并未写出其两个参数的名称。这没有问题，因为参数名称只有在函数内使用参数时才是必要的。有些人建议不论如何都指定参数名称，以作为一种文档使用。
  • int fibo(int pos); // 函数声明

• 函数体：函数的定义则包括函数原型及函数体。成对的/＊、＊/是多行注释，/＊和＊/之间的所有内容都会被视为注释。函数以return语句将值返回。

• 错误处理：

• 如果用户输入错误，程序应该怎么处理呢？最极端的做法就是终止整个程序。标准库的exit（）函数可派上用场。我们必须传一个值给exit（），此值将成为程序结束时的状态值。为了能使用exit（），必须先包含cstdlib头文件。

  • #include exit(-1);

  • 另一个方式是抛出异常。

• 返回值：函数只能返回一个值。如果需要多个返回值，做法之一（如上）是加入第二个参数：一个referenceto int。这使我们得以从这个函数中返回两个值。

• 如果函数的返回类型不为 void，那么它必须在每个可能的退出点上将值返回。函数中的每条return语句都被用来明确表示该处就是函数的退出点。如果函数体的最后一条语句不是 return，那么最后一条语句之后便是该函数的隐式退出点。函数可能无法正确编译，因为其隐式退出点并未返回任何数值。

• 溢出：每个值类型都只能表示其值域（domain）中的最小至最大值间的某个值。int是个有符号（signed）类型。我们的实现代码必须设置一个终点。该如何决定这个终点值呢？这和用户的需求有关。

• 练习：

• 2.1：输入位置，输出对应位置的斐波拉契数。

/* 2.1 Input position, output whose fibonacci number. */ # include using namespace std; int fibo(int pos) { // fibonacci number of given position if (pos <= 0 || pos >= 1024) return -1; int n1 = 1, n2 = 1; int i, t; for (i = 3; i <= pos; i++) { t = n1 + n2; n1 = n2; n2 = t; } return n2; } int main(void) { int pos, elem; bool flag = true; char ch; // try more times while (flag) { // input cout << "Please enter a position: "; cin >> pos; // compute elem = fibo(pos); // output if (elem == -1) cout << "Computation error"; else cout << "Element is " << elem; cout << endl; // whether continue cout << "Continue? (Y/N): "; cin >> ch; if (ch != 'Y' && ch != 'y') flag = false; } return 0; }

*2.2 调用函数

• 参数传递：两种参数传递方式：传址（by reference）及传值（by value）。

• 冒泡排序法（bubble sort）：主要的想法是，当外层的for循环每次迭代完成，由ix索引出来的元素便已被放置在适当位置。当ix为0时，vector中的最小元素会被找到，并被置于位置0处。当ix的值为1时，次小的元素会被找到并放在正确位置，以此类推。放置元素的操作由内层的for循环完成。jx从ix+1依次递增至size-1；它比较位于ix处及jx处的两个元素，如果jx处的元素比较小，就将两元素互换。（选择排序？）

• 调试：如果有调试器（debugger），接下来最好是一步一步地执行程序，依次检查程序中各个对象在执行过程中的值，并观察for循环和if语句的实际流程。但是在当前环境下，更实际的方法是加上打印语句，来跟踪控制流程的逻辑并显示对象的状态。

• 程序堆栈：当我们调用一个函数时，会在内存中建立起一块特殊区域，称为“程序堆栈（program stack）”。这块特殊区域提供了每个函数参数的储存空间。它也提供了函数所定义的每个对象的内存空间——我们将这些对象称为local object（局部对象）。一旦函数完成，这块内存就会被释放掉，或者说是从程序堆栈中被pop出来。

• 参数传递：

• 传值：当我们将 vec[ix]这样的对象传入函数，默认情形下其值会被复制一份，成为参数的局部性定义（local definition）。这种方式称为pass byvalue（传值）。
  • 传址：为了让程序正确工作，我们必须通过某种方法，令函数参数和传入的实际对象产生关联。此即所谓的pass by reference（传址）。要达成这个目的，最简单的做法便是将参数声明为一个reference。

• 传址语义：

• 引用：reference扮演着外界与对象之间一个间接手柄的角色。只要在类型名称和reference名称之间插入&符号，便是声明了一个reference。

  • int ival = 1; int &rval = ival;

  • C++不允许我们改变reference所代表的对象，它们必须从一而终。注意，重点是，面对reference的所有操作都和面对“reference所代表的对象”所进行的操作一般无二。当我们以reference作为函数参数，亦复如此。

  • 当我们以by reference方式将对象作为函数参数传入时，对象本身并不会复制出另一份——复制的是对象的地址。函数中对该对象进行的任何操作，都相当于是对传入的对象进行间接操作。

  • 好处：

  • 将参数声明为reference的理由之一是，希望得以直接对所传入的对象进行修改。这个理由极为重要，因为就像我们在前面的例子中所见，不这么做的话，程序无法正确工作。
    • 将参数声明为reference的第二个理由是，降低复制大型对象的额外负担。这个理由相比较起来不是那么重要，因为对程序而言不过是效率问题罢了。

  • 指针和引用：如果我们愿意，也可以将vector以pointer形式传递。这和以reference传递的效果相同：传递的是对象地址，而不是整个对象的副本。唯一差别在于reference和pointer的用法不同。

  • pointer参数和reference参数之间更重要的差异是，pointer可能（也可能不）指向某个实际对象。当我们提领pointer时，一定要先确定其值并非0。至于reference，则必定会代表某个对象，所以不需要做此检查。

  • 一般来说，除非你希望在函数内更改参数值，否则我建议在传递内置类型时，不要使用传址方式。传址机制主要用于传递class object。

• 作用域及范围：

• 除了一个必要的例外（意指static，见2.4节），函数内定义的对象，只存在于函数执行期间。如果将这些所谓局部对象（local object）的地址返回，会导致运行时错误。

  • 函数是暂时位于程序堆栈（内存内的一块特殊区域）之上。局部对象就放在这块区域中。当函数执行完毕，这块区域的内容便会被弃置。于是局部对象不复存在。一般而言，对根本不存在的对象进行寻址操作，是很不好的习惯。

  • 局部性范围：为对象分配的内存，其存活时间称为储存期（storage duration）或范围（extent）。每次函数执行，都会为对象分配内存，每当函数结束便会加以释放。我们称此对象具有局部性范围（local extent）。函数参数（如上例的size）便具有局部性范围。

  • 作用域：对象在程序内的存活区域称为该对象的scope（作用域）。

  • 局部作用域：我们说size和elems在函数内拥有local scope。如果某个对象仅具有local scope（局部作用域），其名称在local scope之外便不可见。
    • 文件作用域：对象如果在函数以外声明，具有所谓的file scope。对象如果拥有file scope，从其声明点至文件末尾都是可见的。file scope内的对象也具备所谓的静态范围static extent，意即该对象的内存在 main（）开始执行之前便已经分配好了，可以一直存在至程序结束。
  • 初始化：内置类型的对象，如果定义在file scope之内，必定被初始化为0。但如果它们被定义于local scope之内，那么除非程序员指定其初值，否则不会被初始化。

• 动态内存管理：

• 动态范围：不论local scope或file scope，对我们而言，都是由系统自动管理。第三种储存期形式称为dynamic extent（动态范围）。其内存系由程序的空闲空间（free store）分配而来，有时也称为heap memory（堆内存）。这种内存必须由程序员自行管理，其分配系通过new表达式来完成，而其释放则通过delete表达式完成。

  • new表达式：此处的Type可为任意内置类型，也可以是程序知道的class类型。默认情形下，由heap分配而来的对象，皆未经过初始化。new表达式的另一种形式允许我们指定初值。C++没有提供任何语法让我们得以从heap分配数组的同时为其元素设定初值。

  • int *pi = new Type(initial_value);
    • int *arr = new int[24]; // 从heap中分配数组

  • delete表达式：从heap分配而来的对象，被称为具有dynamic extent，因为它们是在运行时通过new表达式分配来的，因此可以持续存活，直到以delete表达式加以释放为止。delete表达式会释放指针所指的对象。如果要删除数组中的所有对象，必须在数组指针和 delete 表达式之间，加上一个空的下标运算符。

  • delete pi;
    • delete [] arr;
    • 注意，无须检验指针是否非零。编译器会自动进行这项检查。如果因为某种原因，程序员不想使用delete表达式，由heap分配而来的对象就永远不会被释放。这称为memory leak（内存泄漏）。

• 示例：

• 2.2：冒泡排序。

/* Eg.2.2 Buble sort. */ # include # include using namespace std; void display(vector &vec) { for (int i = 0; i < vec.size(); i++) cout << vec[i] << ' '; cout << endl; } void swap(int &v1, int &v2) { int t = v1; v1 = v2; v2 = t; } void bubble_sort(vector &vec) { for (int i = 0; i < vec.size(); i++) for (int j = i + 1; j < vec.size(); j++) if (vec[j] < vec[i]) swap(vec[j], vec[i]); } int main(void) { int arr[8] = {8, 34, 3, 13, 1, 21, 5, 2}; vector vec(arr, arr + 8); cout << "Vector before sort:" << endl; display(vec); bubble_sort(vec); cout << "Vector after sort:" << endl; display(vec); return 0; }

2.3 提供默认参数值

• 一般的程序编写法则是，以“参数传递”作为函数间的沟通方式，比“直接将对象定义于file scope”更适当。理由之一是，函数如果过度依赖定义于file scope内的对象，就比较难以在其他环境中重用，也比较难以修改——我们不仅需要了解该函数的工作逻辑，也必须了解定义于file scope中的那些对象的工作逻辑。

• 默认参数值：C++允许我们为全部或部分参数设定默认值。

• 参数声明为对象的一个pointer而非reference。我们必须做这样的改变，才可以为它设定默认值0，表示并未指向任何ofstream对象。reference不同于pointer，无法被设置为0。因此，reference一定得代表某个对象。

  • void bubble_sort(vector &vec, ofstream *outfile = 0)

  • 一般情形下输出至cout当然很好，但是有时候用户可能会希望提供一个不同的目的地，例如文件。我们必须能够在main（）之中同时支持这两种使用方式。解决之道就是让 cout成为默认的 ostream参数。

  • void display(const vector &vec, ostream &os = cout)

  • 关于默认参数值的提供，有两个不很直观的规则。

  • 第一个规则是，默认值的解析（resolve）操作由最右边开始进行。如果我们为某个参数提供了默认值，那么这一参数右侧的所有参数都必须也具有默认参数值才行。
    • 第二个规则是，默认值只能够指定一次，可以在函数声明处，亦可以在函数定义处，但不能够在两个地方都指定。

  • 头文件：通常，函数声明会被放在头文件，每个打算使用该函数的文件，都会包含对应的头文件。函数的定义通常被放在程序代码文件，该文件只被编译一次，当我们想要使用该函数时，会将它链接（link）到我们的程序来。也就是说，头文件可为函数带来更高的可见性（visiblity）。为了更高的可见性，我们决定将默认值放在函数声明处而非定义处。

  • void display(const vector &vec, ostream &os = cout); // 默认值放在函数声明处

2.4 使用局部静态对象

• 在函数内声明局部（local）vector对象并不能解决上述问题。因为局部对象会在每次调用函数时建立，并在函数结束的同时被弃置。如果将vector对象定义于file scope之中，又过于冒险。是的，为了节省函数间的通信问题而将对象定义于file scope内，永远都是一种冒险。通常，file scope对象会打乱不同函数间的独立性，使它们难以理解。

• 局部静态对象（local static object）：和局部非静态对象不同的是，局部静态对象所处的内存空间，即使在不同的函数调用过程中，依然持续存在。现在我们可以安全地将对象的地址返回。

• const vector* fibo(int size) { static vector elems; /…/ return &elems; }

  • push_back（）会将数值放在vector末端。vector class提供有内存自动管理机制。

2.5 声明 inline函数

• 函数分解：我们可以将各个小工作分解为独立函数，以求更简化。如果其执行性能不够理想，只好再将三个函数重新组合为一个。然而C++还提供了另一个解决办法，就是将这些函数声明为inline。

• inline函数：将函数声明为inline，表示要求编译器在每个函数调用点上，将函数的内容展开。面对一个inline函数，编译器可将该函数的调用操作改为以一份函数代码副本代替。这将使我们获得性能改善。

• 只要在函数前面加上关键字inline，便可将该函数声明为inline。

  • inline bool fibo_elem(int pos, int &elem)

  • 将函数指定为inline，只是对编译器提出的一种要求。编译器是否执行这项请求，需视编译器而定。

  • 一般而言，最适合声明为inline的函数：体积小，常被调用，所从事的计算并不复杂。

  • inline函数的定义，常常被放在头文件中。由于编译器必须在它被调用的时候加以展开，所以这个时候其定义必须是有效的。

*2.6 提供重载函数

• 函数重载：传入不同类型甚至不同数量的参数给函数，必须通过所谓的函数重载（function overloading）机制。参数列表（parameter list）不相同（可能是参数类型不同，可能是参数个数不同）的两个或多个函数，可以拥有相同的函数名称。

• 重载声明：

  • void display(char ch);
    • void display(const string &);
    • void display(const string &, int);
    • void display(const string &, int, int);

  • 重载调用：既然名称相同，编译器如何知道应该调用哪一个函数呢？它会将调用者提供的实际参数拿来和每个重载函数的参数比对，找出其中最适合的。这也就是每个重载函数的参数列表必须和其他重载函数的不同的原因。

  • 编译器无法根据函数返回类型来区分两个具有相同名称的函数。为什么返回类型不足以将函数重载呢？因为返回类型无法保证提供给我们一个足以区分不同重载函数的语境。

• 重载的好处：将一组实现代码不同但工作内容相似的函数加以重载，可以让函数用户更容易使用这些函数。如果没有重载机制，我们就得为每个函数提供不同的名称。

*2.7 定义并使用模板函数

• 函数模板：需要一种机制，让我们得以将单一函数的内容与希望显示的各种vector类型绑定（bind）起来。所谓function template（函数模板）便提供了这样的机制。

• function template 将参数列表中指定的全部（或部分）参数的类型信息抽离了出来。这样就可以定义出一份不需要再有任何更改的模板（template）。不过，这样还不完整，因为我们遗漏了抽离出来的类型信息。这份类型信息系由用户提供——当他决定采用function template的某个实例时提供。

  • 定义函数模板：function template以关键字template开场，其后紧接着以成对尖括号（＜＞）包围起来的一个或多个标识符。这些标识符用以表示我们希望推迟决定的数据类型。用户每次利用这一模板（template）产生函数，都必须提供确实的类型信息。这些标识符事实上扮演着占位符的角色，用来放置函数参数列表及函数体中的某些实际数据类型。

  • 关键字typename表示，elemType在函数中是一个暂时放置类型的占位符。elemType只是个任意名称，我们也可以选用foobar或T之类的名称。由于在这个例子中我们希望推迟指定要显示的vector的元素类型，因此把elemType放在vector的尖括号内。
    • template void display_message(const string &msg, const vector &vec)
    • function template的参数列表通常都由两种类型构成，一类是明确的类型，另一类是暂缓决定的类型。

  • 使用函数模板：使用方式看起来和普通函数极为相似。

  • vector vec; display_message(msg, vec);
    • 编译器会将elemType绑定（bind）为int类型，然后产生一份函数实例，于是其第二参数的类型即变成 vector＜int＞。函数体内的局部对象的类型同样也变成了 int。
    • function template扮演的角色如同处方一般，我们可以通过它产生无数函数，其elemType可以被绑定为内置类型或用户自定义类型。

• 函数重载和函数模板：一般而言，如果函数具备多种实现方式，我们可将它重载（overload），其每份实例提供的是相同的通用服务。如果我们希望让程序代码的主体不变，仅仅改变其中用到的数据类型，可以通过function template达到目的。

• 当然，function template同时也可以是重载函数。

  • template void display( string &msg, vector &vec);
    • template void display( string &msg, list <);

2.8 函数指针带来更大的弹性

• 函数指针：所谓函数指针（pointer to function），其形式相当复杂。它必须指明其所指函数的返回类型及参数列表。此外，函数指针的定义必须将＊放在某个位置，表示这份定义所表现的是一个指针。当然，最后还必须给予一个名称。

• 定义函数指针：为了让seq_ptr被视为一个指针，我们必须以小括号改变运算优先级。现在，seq_ptr 可以指向“具有所列返回类型及参数列表”的任何一个函数。

  • const vector* (*seq_ptr) (int);

  • 使用函数指针：由函数指针指向的函数，其调用方式和一般函数相同。会间接调用seq_ptr所指向的函数。我们不知道（或者不在乎）它所指向的函数是哪一个。

  • int seq_elem( int pos, vector* (*seq_ptr) (int) ) { seq_ptr(pos) }

  • 初值：

  • 我们可以给予函数指针初值。如果初值为0，表示并未指向任何函数。

    • 也可以拿某个函数的地址作为函数指针的初值。问题是，如何取得函数的地址呢？这是C++中最不复杂的操作了，只要提供函数名称即可。

• 函数指针数组：

• 首先定义一个数组，内放函数指针。

  • vector* (*seq_arr[]) (int) = { fibo_seq, lucas_seq, pell_seq };

• 枚举类型：关键字 enum 之后是一个可有可无的标识符，如本例的 ns_type。借此便定义出所谓枚举类型（enumerated type）。大括号里头是以逗号分隔的列表，其中的每个项称为枚举项（enumerator）。默认情形下，第一个枚举项的值为0，接下来的每个枚举项都比前一个多1。

• 以ns_type为例，ns_fis的值为0，ns_lucas的值为1，ns_pell的值为2，以此类推，ns_pent的值为5。

  • enum ns_type { ns_fibo, ns_lucas, ns_pell };

  • 为了以明确指定的方式取用函数指针，我们使用对应的枚举项作为数组索引值。

  • seq_ptr = seq_arr[ ns_pell ];

2.9 设定头文件

• 函数声明：调用函数之前，必须先声明它，以使程序知道它的存在。如果它被五个程序文件调用，就必须进行五次声明操作。为了不用分别在五个文件中声明函数，我们把函数声明放在头文件中，并在每个程序代码文件内包含（include）这些函数声明。

• 使用这种编写习惯，我们只需为函数维护一份声明即可。如果其参数列表或返回类型需要改变，也只需更改这份声明即可——函数用户会包含更新后的函数声明。

• 头文件的编写：头文件的扩展名，习惯上是.h。标准库例外，它们没有扩展名。

• 我们的头文件命名为NumSeq.h，并将与数列处理有关的所有函数的声明都放在该文件中。

  • 函数的定义只能有一份。不过倒是可以有许多份声明。我们不把函数的定义放入头文件，因为同一个程序的多个代码文件可能都会包含这个头文件。

  • “只定义一份”的规则有个例外：inline函数的定义。为了能够扩展inline函数的内容，在每个调用点上，编译器都得取得其定义。这意味着我们必须将 inline 函数的定义放在头文件中，而不是把它放在各个不同的程序代码文件中。

  • 在file scope内定义的对象，如果可能被多个文件访问，就应该被声明于头文件中。因为如果我们没有在程序中声明某个对象，便无法加以访问。就像函数一样，一个对象只能在程序中被定义一次。对象的定义，就像函数定义一样，必须放在程序代码文件中。只要在上述seq_array定义前加上关键字extern，它便成为一个声明。

  • extern const vector* (*seq_arr[seq_cnt]) (int);

  • const object就和inline函数一样，是“一次定义”规则下的例外。const object的定义只要一出文件之外便不可见。这意味着我们可以在多个程序代码文件中加以定义，不会导致任何错误。（读者可能会疑惑：刚才讨论的seq_array不也是一个const object吗？不，它不是，它是一个“指向const object”的指针，它本身并不是const object。）

  • const int seq_cnt = 6;

  • 我们希望编译器在我们的数组声明中使用这一 const object，并且在其他需要用到常量表达式（constant expression）的场合中（那可能会跨文件）也能够使用。

• 头文件的使用：

• 任何需要用到函数的文件，在它们第一次使用函数名称时，都必须包含对应的头文件。

  • #include “NumSeq.h” int main(void) { int x = seq_elem(1); }

  • 为什么我们使用双引号而非尖括号（＜ ＞）将NumSeq.h括起来呢？下面是个简略的回答：如果头文件和包含此文件的程序代码文件位于同一个磁盘目录下，我们便使用双引号。如果在不同的磁盘目录下，我们便使用尖括号。

  • 更有技术含量的回答是，如果此文件被认定为标准的或项目专属的头文件，我们便以尖括号将文件名括住；编译器搜索此文件时，会先在某些默认的磁盘目录中寻找。如果文件名由成对的双引号括住，此文件便被认为是一个用户提供的头文件；搜索此文件时，会由要包含此文件的文件所在的磁盘目录开始找起。

• 练习：

• 2.2：产生并打印Pentagonal数列，公式为P(n) = n * (3n - 1) / 2。

/* 2.2 Generate and display pentagonal numeric sequence. */ # include # include using namespace std; bool pentagonal_elements(vector &vec, int n) { // generate elements if (n <= 0 || n > 64) return false; for (int i = vec.size() + 1; i <= n; i++) vec.push_back(i * (3 * i - 1) / 2); return true; } void display(vector &vec, ostream &os = cout) { for (int i = 0; i < vec.size(); i++) os << vec[i] << ' '; os << endl; } int main(void) { vector vec; if (pentagonal_elements(vec, 8)) display(vec); return 0; }

• 2.4：使用静态局部vector存储pentagonal数列，并返回给定位置的元素。

/* 2.4 Compute pentagonal element of given position. */ # include # include using namespace std; const vector* pent_seq(int n) { // sequence static vector vec; if (n <= 0 || n > 64 || n <= vec.size()) return &vec; for (int i = vec.size() + 1; i <= n; i++) vec.push_back(i * (3 * i - 1) / 2); return &vec; } int pent_elem(int pos) { // element if (pos <= 0 || pos > 64) return 0; const vector* p = pent_seq(pos); if (p != NULL) return (*p)[pos - 1]; else return 0; } int main(void) { cout << pent_elem(8) << endl; return 0; }

• 2.6：使用template实现重载的max函数，支持不同参数列表。

/* 2.6 Overloaded max function with template. */ # include # include # include using namespace std; template T my_max(T a, T b) { return a > b ? a : b; } template T my_max(vector &vec) { T m = vec[0]; for (int i = 1; i < vec.size(); i++) if (vec[i] > m) m = vec[i]; return m; } template T my_max(T vec[], int size) { T m = vec[0]; for (int i = 1; i < size; i++) if (vec[i] > m) m = vec[i]; return m; } int main(void) { string s1 = "world", s2 = "hello"; float f1 = 1.2, f2 = 0.3; int arri[3] = {1, 2, 3}; vector veci(arri, arri + 3); float arrf[3] = {0.1, 1.2, 0.3}; vector vecf(arrf, arrf + 3); string arrs[3] = {"hello", "world", "robert"}; vector vecs(arrs, arrs + 3); cout << my_max(2, 3) << endl; cout << my_max(f1, f2) << endl; cout << my_max(s1, s2) << endl; cout << my_max(veci) << endl; cout << my_max(vecf) << endl; cout << my_max(vecs) << endl; cout << my_max(arri, 3) << endl; cout << my_max(arrf, 3) << endl; cout << my_max(arrs, 3) << endl; return 0; }

3 泛型编程风格

• 标准模板库：Standard Template Library（STL）主要由两种组件构成：

• 容器：一是容器（container），包括vector、list、set、map等类；
  • 泛型算法：另一种组件是用以操作这些容器的所谓泛型算法（generic algorithm），包括find（）、sort（）、replace（）、merge（）等。

• 容器

• 顺序性容器：vector和list这两种容器是所谓的顺序性容器（sequential container）。顺序性容器会依次维护第一个、第二个……直到最后一个元素。我们在顺序性容器身上主要进行所谓的迭代（iterate）操作。
  • map和set这两种容器属于关联容器（associative container）。关联容器可以让我们快速查找容器中的元素值。

• map：所谓map乃是一对对的key/value组合。key用于查找，value用来表示我们要储存或取出的数据。

• 举例来说，电话号码即可以map轻松表示，电话用户名便是key，而value与电话号码产生关联。

• set：所谓set，其中仅含有key。我们对它进行查询操作，为的是判断某值是否存在于其中。

• 在让某个字眼进入索引表之前，我们要先查询excluded_word这么一个set，如果这个字眼在里面，我们便忽略它不再计较；反之则将它加入索引表。

• 泛型算法：泛型算法提供了许多可作用于容器类及数组类型上的操作。这些算法之所以被称为泛型（generic），是因为它们和它们想要操作的元素类型无关。举个例子，它们和元素类型究竟是int、double或string全然无关。它们同样也和容器类彼此独立（不论容器是vector、list或array）。

• 泛型算法系通过function template技术，达到“与操作对象的类型相互独立”的目的。
  • 而实现“与容器无关”的诀窍，就是不要直接在容器身上进行操作。而是借由一对iterator（first和 last），标示我们要进行迭代的元素范围。如果first等于last，算法便只作用于first所指元素。如果first不等于last，算法便会首先作用于first所指元素身上，并将first递增，指向下一个位置，然后再比较first和last是否相等，如此持续进行，直到first等于last为止。

3.1 指针的算术运算

• 泛型函数：

• 想办法让这个函数不仅可以处理整数，更可以处理任何类型——前提是该类型定义有equality（相等）运算符。这个任务其实就是要求我们将泛型算法find（）以function template的形式呈现。
  • 下一个任务，便是要让这个函数同时可以处理vector与array内的任意类型元素——当然该类型的equality运算符皆已定义。本例我们并不建议使用重载方式来解决。

• 数组作为函数参数：

• 当数组被传给函数，或是由函数中返回，仅有第一个元素的地址会被传递。

  • 指向array开头的指针，使我们得以开始对array进行读取操作。接下来我们必须设法告诉函数，应该在何处停止对array的读取。

  • 解法之一是：增加一个参数，用来表示array的大小。

    • 解法之二则是传入另一个地址，指示array读取操作的终点。（我们将此值称为“标兵”。）这种解法最让人感兴趣的地方便是，array从参数列表中彻底消失了。

• 访问数组元素：虽然array是以第一个元素的指针传入函数中，但我们看到，仍然可以通过subscript（下标）运算符访问array的每个元素，就如同此array是个对象（而非指针形式）一般。为什么呢？因为事实上所谓下标操作就是将 array 的起始地址加上索引值，产生出某个元素的地址，然后该地址再被提领（dereference）以返回元素值。

• 指针算术运算：在指针算术运算中，会把“指针所指的类型”的大小考虑进去。假设array所储存的元素类型为int。array+2便是array的地址加上两个整数元素的大小。有些机器的int长度是4 byte，那么这个指针算术运算的答案便是1008。
  • 取得元素的地址后，还必须提领（dereference）该地址，以得到元素值。当我们写下 array[2]，指针的算术运算以及提领操作都会自动进行。

• 泛型算法实现：

• 以下是find（）的另一种实现，其中通过指针来进行每个元素的定位。为了能够依次定位array的每个元素，我们在循环的每次迭代中，都会将 array的值递增1。为了读取它所指出的元素，我们必须提领指针。也就是说，程序代码中如果出现array，获得的是元素地址，如果出现＊array，则获得的是元素值。

  • template T* find( const T *arr, int size, const T &value )

  • 下一个版本，我们使用第二个指针来取代参数size。此指针扮演着标兵的角色。这个版本可以让我们将array的声明从参数列表中完全移除。

  • template T* find( const T *first, const T *last, const T &value )

• 使用泛型算法：

• 数组：我们传入第二个地址，标示出数组最后一个元素的下一个地址。这合法吗？是的，不过倘若我们企图对此地址进行读取或写入操作，那就不合法。如果我们仅仅是将该地址拿来和其他元素的地址进行比较，那就完全不会有任何问题。数组最后一个元素的下一个地址，扮演着我们所说的标兵角色，用以指示我们的迭代操作何时完成。

  • int arr[8]; int *p = find(arr, arr + 8, arr[3]);

  • vector：不论 vector 的元素类型是什么，都能一一访问vector内的每个元素。要知道，vector和array相同，都是以一块连续内存储存其所有元素，所以我们可以使用和array一样的处理方式，将一组用来表示“启始地址/结束地址”的参数传入find（）。

  • 但是，切记，vector可以是空的，array则不然。对find（）的调用操作，如果svec为空，便会产生一个运行时错误。
    • 通常我们会将“取用第一个元素的地址”的操作包装为函数。其对应函数end（），会返回0或是vector最后元素的下一个地址。采用这种方式，我们便有了安全的、放之四海而皆准的方式，使find（）应用于任意vector之上
    • template T* begin( const vector &vec) { return vec.empty() ? 0 : &vec[0]; }

  • 这同时也解决了我们最原始的任务。我们已实现出 find（），只需这一份 find（），便可同时处理vector或array。

  • find( begin(vec), end(vec), search_value);

• 扩展泛型：现在让我们扩展 find（）的功能，令它也能支持标准库所提供的 list 类别。

• list也是一个容器。不同的是，list的元素以一组指针相互链接（linked）：前向（forward）指针指向下一个（next）元素，后向（backward）指针指向上一个（preceding）元素。
  • 因此，指针的算术运算并不适用于list，因为指针的算术运算必须首先假设所有元素都储存在连续空间里，然后才能根据当前的指针，加上元素大小之后，指向下一个元素。这是先前find（）的实现之中最基本的假设。不幸的是，当我们想要取得list的下一个元素时，这一假设并不成立。
  • 我们不需要提供另一个find（）函数来支持list。事实上，除了参数列表之外，find（）的实现内容一点也不需要改变。
  • 解决这个问题的办法是，在底层指针的行为之上提供一层抽象，取代程序原本的“指针直接操作”方式。我们把底层指针的处理通通放在此抽象层中，让用户无须直接面对指针操作。这个技巧使得我们只需提供一份find（）函数，便可以处理标准库所提供的所有容器类。

• 示例：

• 3.1：给定一个储存整数的vector或array，以及一个整数值。如果此值存在于vector内，我们必须返回一个指针指向该值；反之则返回0，表示此值并不在vector内。使用指针实现。

/* Eg.3.1 Find element in a vector or array, with generic pointer. */ # include # include using namespace std; template T* find(const T *first, const T *last, T &value) { if (first == NULL || last == NULL) return NULL; for (T *p = (T *) first; p != last; p++) if (*p == value) return p; return NULL; } int main(void) { int arr[8] = {8, 34, 3, 13, 1, 21, 5, 2}; int *p = NULL; p = find(arr, arr + 8, arr[3]); cout << (*p) << endl; return 0; }

*3.2 了解 Iterator（泛型指针）

• iterator类：我们需要一组对象，可提供有如内置运算符（++，＊，==，！=）一般的运算符，并允许我们只为这些运算符提供一份实现代码即可。我们可以利用C++的类机制来达到目的。接下来我要设计一组iterator class，让我们得以使用“和指针相同的语法”来进行程序的编写。

• 这就好像把first和last当作指针一样。唯一的差别在于其dereference（提领，＊）运算符、inequality （不等，！=）运算符、increment（递增，++）运算符乃是由iterator class内相关的inline函数提供。
  • 对list iterator而言，其递增函数会沿着list的指针前进到下一个元素，对vector iterator而言，其递增函数前进至下一个元素的方式，是将目前的地址加上一个元素的大小。

• 定义并使用标准容器的iterator

• 每个标准容器都提供有一个名为begin（）的操作函数，可返回一个iterator，指向第一个元素。另一个名为end（）的操作函数会返回一个iterator，指向最后一个元素的下一位置。

  • 对iterator进行赋值（assign）、比较（compare）、递增（increment）、提领（dereference）操作

  • for (it = vec.begin(); it != vec.end(); it++) cout « *it « ’ ‘;

• 定义iterator：

• 定义应该提供的信息：（1） 迭代对象（某个容器）的类型，这可用来决定如何访问下一元素；（2）iterator所指的元素类型，这可决定iterator提领操作的返回值。

  • 定义：此处iter被定义为一个iterator，指向一个vector，后者的元素类型为string。其初值指向svec的第一个元素。（双冒号〔：：〕表示此iterator乃是位于string vector定义内的嵌套〔nested〕类型。）

  • vector::iterator it = vec.begin();

  • 面对const vector，我们使用const_iterator来进行遍历操作：const_iterator允许我们读取vector的元素，但不允许任何写入操作。

  • const vector vec; vector::const_iterator it = vec.begin();

• 使用iterator：

• 取得元素：欲通过iterator取得元素值，我们可以采用一般指针的提领方式。同样道理，如果要通过iter调用底部的string元素所提供的操作，我们可以使用arrow（箭头）运算符。以iterator取代了原先使用的subscript（下标）运算符。

  • cout « *it « it->size() « endl;

  • 现在我要重新实现find（），让它同时支持两种形式：一对指针，或是一对指向某种容器的iterator。我们让find（）有了更大的通用性。

  • template IT find( IT first, IT last, const T &value )

• 提升泛型算法弹性

• find（）的实现使用了底部元素所属类型的equality（相等）运算符。如果底部元素所属类型并未提供这个运算符，或如果用户希望赋予equality运算符不同的意义，这个find（）的弹性便嫌不足了。如何才能增加其弹性？解法之一便是传入一个函数指针，取代原本固定使用的 equality 运算符。第二种解法则是运用所谓的functionobject（这是一种特殊的class）。我们会在第4章看到如何设计function objects。
  • 下一个要努力的目标，是将现有的find（）版本演化为泛型算法。（标准库提供的find_if（），能够接受函数指针或function object，取代底部元素的equality运算符，大大提升弹性。）

• 泛型算法：总共有超过60个的泛型算法（事实上几近75个）。以下列出一部分。完整列表以及每个算法的使用范例，可于附录B找到。

• 排序（sorting）及次序整理（ordering）算法：merge（），partial_sort（），partition（），random_shuffle（），reverse（），rotate（），sort（）。

• 复制（copy）、删除（deletion）、替换（substitution）算法：copy（），remove（），remove_if（），replace（），replace_if（），swap（），unique（）。
  • 关系（relational）算法：equal（），includes（），mismatch（）。
  • 生成（generation）与质变（mutation）算法：fill（），for_each（），generate（），transform（）。
  • 数值（numeric）算法：accmulate（），adjacent_difference（），partial_sum（），inner_product（）。
  • 集合（set）算法：set_union（），set_difference（）。

• 示例：

• 3.2：查找容器中的元素，使用iterator实现。

/* Eg.3.2 Find element in a vector or array or list, with generic iterator. */ # include # include # include using namespace std; template <typename IT, typename T> IT find(IT first, IT last, T &value) { for (IT it = first; it != last; it++) if (*it == value) return it; return last; } int main(void) { int arr[8] = {8, 34, 3, 13, 1, 21, 5, 2}; vector vec(arr, arr + 8); list lt(arr, arr + 8); int *p = NULL; // array p = find(arr, arr + 8, arr[3]); cout << (*p) << endl; // vector vector::iterator it; it = find(vec.begin(), vec.end(), arr[3]); if (it != vec.end()) cout << (*it) << endl; // list list::iterator it2; it2 = find(lt.begin(), lt.end(), arr[3]); if (it2 != lt.end()) cout << (*it2) << endl; return 0; }

3.3 所有容器的共通操作

• 所有容器类（以及string类）的共通操作：

• equality（==）和inequality（！=）运算符，返回true或false。
  • assignment（=）运算符，将某个容器复制给另一个容器。
  • empty（）会在容器无任何元素时返回true，否则返回false。
  • size（）返回容器内目前持有的元素个数。
  • clear（）删除所有元素。

• 每个容器都提供了 begin（）和 end（）两个函数，分别返回指向容器的第一个元素和最后一个元素的下一位置的iterator：通常我们在容器身上进行的迭代操作都是始于begin（）而终于end（）。

• begin（）返回一个iterator，指向容器的第一个元素。
  • end（）返回一个iterator，指向容器的最后一个元素的下一位置。

• 所有容器都提供insert（）用以插入元素，以及erase（）用以删除元素。insert（）和erase（）的行为视容器本身为顺序性（sequential）容器或关联（associative）容器而有所不同。

• insert（）将单一或某个范围内的元素插入容器内。
  • erase（）将容器内的单一元素或某个范围内的元素删除。

*3.4 使用顺序性容器

• 顺序性容器：顺序性容器用来维护一组排列有序、类型相同的元素，其中有第一、第二……以此类推，乃至最后一个元素。vector和list是两个最主要的顺序性容器。

• vector：vector以一块连续内存来存放元素。对vector进行随机访问（random access）颇有效率；vector内的每个元素都被储存在距离起始点的固定偏移位置上。如果将元素插入任意位置，而此位置不是vector的末端，那么效率将很低，因为插入位置右端的每个元素，都必须被复制一份，依次向右移动。同样道理，删除vector内最后一个元素以外的任意元素，同样缺乏效率。

  • vector 比较适合表示数列。因为我们会有许多随机访问的机会。此外，我们并不需要删除其中元素，只需要将元素插入vector末尾。

  • list：list系以双向链接（double-linked）而非连续内存来储存内容，因此可以执行前进或后退操作。list中的每个元素都包含三个字段：value、back指针（指向前一个元素）、front指针（指向下一个元素）。在list的任意位置进行元素的插入或删除操作，都颇具效率，因为list本身只需适当设定back指针和front指针即可。但是如果要对list进行随机访问操作，则效率不彰。例如，要依次访问其第5个元素、第17个元素、第9个元素，都必须遍历介于其中的所有元素。

  • 每当我们读入一个分数，便可能需要将它随机插入到容器内。这种情况下list比较适当。

  • deque：第三种顺序性容器是所谓的deque（读作deck）。deque的行为和vector颇为相似——都以连续内存储存元素。和 vector 不同的是，deque 对于最前端元素的插入和删除操作，效率更高；末端元素亦同。如果我们需要在容器最前端插入元素，并执行末端删除操作，那么 deque 便很理想。（标准库的queue便是以deque实现，也就是说，以deque作为底部储存元素。）

• 头文件：要使用顺序性容器，首先必须包含相关的头文件，也就是以下三者之一：

• #include
  • #include
  • #include

• 定义顺序性容器：定义顺序性容器对象的方式有五种。

• 1.产生空的容器

  • list lt;
    • vector vec;

  • 2.产生特定大小的容器。每个元素都以其默认值作为初值（还记得吗，int和double这类语言内置的算术类型，其默认值为0）。

  • list lt(1024); // 括号中为大小
    • vector vec(32);

  • 3.产生特定大小的容器，并为每个元素指定初值

  • vector vec(10, -1);
    • list lt(16, “assigned”);

  • 4.通过一对iterator产生容器。这对iterator用来标示一整组作为初值的元素的范围：

  • int arr[3] = {1, 2, 3}; vector vec(arr, arr + 3);

  • 5.根据某个容器产生出新容器。复制原容器内的元素，作为新容器的初值

  • list lt1; list lt2(lt1);

• 容器操作函数：

• 末端插入/删除：

  • push_back（）会在末端插入一个元素，pop_back（）会删除最后一个元素。
    • 除此之外，list和deque（但不包括vector）还提供了push_front（）和pop_front（）。
    • pop_back（）和pop_front（）这两个操作函数并不会返回被删除的元素值。

  • 读取末端：如果要读取最前端元素的值，应该采用front（）。如果要读取末端元素的值，应该采用back（）。

  • 插入：push_front（）和push_back（）都属于特殊化的插入（insertion）操作。每个容器除了拥有通用的插入函数insert（），还支持四种变形。

  • iterator insert（iterator position，elemType value）：可将value插入position之前。它会返回一个iterator，指向被插入的元素。
    • void insert（iterator position，int count，elemType value）：可在position之前插入count个元素，这些元素的值都和value相同。
    • void insert（iterator1 position，iterator2 first，iterator2 last）：可在position之前插入[first，last）所标示的各个元素。
    • iterator insert（iterator position）：可在position之前插入元素。元素的初值为其所属类型的默认值。

  • 删除：pop_front（）和pop_back（）都属于特殊化的删除（erase）操作。每个容器除了拥有通用的删除函数erase（），还支持两种变形。上述两个erase（）函数返回的iterator，皆指向被删除之最后一个元素的下一位置。

  • iterator erase（iterator posit）：可删除posit所指的元素。
    • iterator erase（iterator first，iterator last）：可删除[first，last）范围内的元素。
    • list并不支持iterator的偏移运算。不能写：lt.erase( it1, it1 + size)，而必须将it1和it2传入erase（）。

3.5 使用泛型算法

• 头文件：欲使用泛型算法，首先得包含对应的algorithm头文件

• #include

• 泛型搜索算法：

• find（）：用于搜索无序（unordered）集合中是否存在某值。搜索范围由iterator [first，last）标出。如果找到目标，find（）会返回一个iterator指向该值，否则返回一个iterator指向last。

  • binary_search（）：用于有序（sorted）集合的搜索。如果搜索到目标，就返回true；否则返回false。binary_search（）比find（）更有效率。（因为find（）属于linear search，效率较binary search差。）

  • binary_search（）要求，其作用对象必须经过排序（sorted），这一责任由程序员承担。如果我们不确定是否已排序，可以将容器先复制一份。然后，先对新容器执行排序操作，再调用binary_search（）。

  • count（）：返回数值相符的元素数目。

  • search（）：比对某个容器内是否存在某个子序列。例如给定序列{1，3，5，7，2，9}，如果搜索子序列{5，7，2}，则search（）会返回一个iterator指向子序列起始处。如果子序列不存在，就返回一个iterator指向容器末尾。

• 最大/最小：

• max_element（）：将一对 iterator 传给max_element（），它会返回该范围内的最大值。

• 复制：

• copy（）：接受两个iterator，标示出复制范围。第三个iterator指向复制行为的目的地（也是个容器）的第一元素，后续元素会被依次填入。

  • 确保“目标容器”拥有足够空间以放置每个即将到来的元素，这是程序员的责任。如果我们不确定这件事，可以使用所谓的inserter，以插入模式（insertion）取代默认的assignment行为。3.9节对此另有讨论。

• 泛型算法：附录B有每一个泛型算法的运用范例。

*3.6 如何设计一个泛型算法

• 过滤元素filter：

• “比较操作”参数化：以函数调用来取代less-than运算符。加入第三个参数pred，用它来指定一个函数指针，其参数列表有两个整数，返回值为bool。为方便起见，我们同时定义了许多可传给 filter（）的关系（relational）比较函数，调用 filter（）时，用户亦可传入上述函数，或其他自定义的关系比较函数。

  • vector filter ( const vector &vec, int filter_value, bool (*pred) (int, int) );
    • bool greater_than (int v1, int v2) { return v1 > v2; }

• 泛型算法 find_if（）：将find_if（）反复作用于数列身上，找出符合条件的每一个元素——所谓“条件”则由用户指定的函数指针定义。

• 泛型算法find（）接受三个参数：两个iterator标示出检测范围，第三个参数是我们想要寻找的数值。

• 我们在 while 循环之内将 find（）的返回值设给 iter。find（）返回一个iterator，指向元素值为val的元素。如果没有找到任何符合条件的元素，就返回一个等同于vec.end（）的iterator。一旦iter等同于vec.end（），循环即终止。
  • while循环之所以运行正确，是因为我们在每次循环迭代中，找到符合条件的元素后便将iter加1。

• 函数对象Function Object：

• 定义：所谓function object，是某种class的实例对象，这类class对function call运算符做了重载操作，如此一来可使function object被当成一般函数来使用。

  • 目的：function object实现了我们原本可能以独立函数加以定义的事物。但又何必如此呢？主要是为了效率。我们可以令call运算符成为inline，从而消除“通过函数指针来调用函数”时需付出的额外代价。

  • 标准库：标准库事先定义了一组function object，分为算术运算（arithmetic）、关系运算（relational）和逻辑运算（logical）三大类。以下列表中的type在实际使用时会被替换为内置类型或class类型：

  • 六个算术运算：plus＜type＞，minus＜type＞，negate＜type＞，multiplies＜type＞，divides＜type＞，modules＜type＞。

• • 六个关系运算：less＜type＞，less_equal＜type＞，greater＜type＞，greater_equal＜type＞，equal_to＜type＞，not_equal_to＜type＞。

    • 三个逻辑运算，分别对应于&&、

      、！运算符：logical_and＜type＞，logical_or＜type＞，logical_not＜type＞。

  • 欲使用事先定义的function object，首先得包含相关头文件：

  • #include

  • 示例1：默认情形下，sort（）会使用底部元素的类型所提供的less-than运算符，将元素升序排序。如果我们传入greater_than function object，元素就会以降序排序。其中greater()会产生一个未命名的class template object，传给sort（）。

  • sort( vec.begin(), vec.end(), greater() );

  • 示例2：binary_search（）期望其搜索对象先经过 less-than 运算符排序。为了正确搜索 vector，我们现在必须传给它某个function object object，供vector排序使用。

  • binary_search ( vec.begin(), vec.end(), elem, greater() );

  • 泛型算法transform（）：我们必须传给transform（）：（1） 一对iterator，标示出欲转换的元素范围，（2） 一个iterator，所指元素将应用于转换操作上，（3） 一个iterator，所指位置（及其后面的空间）用来存放转换结果，（4） 一个function object，表现出我们想要应用的转换操作。

  • transform ( fib.begin(), fib.end(), pell.begin(), fib_plus_pell.begin(), plus() );

• 函数对象适配器Function Object Adapter：

• 适配器adapter：function object adapter会对function object进行修改操作。所谓binder adapter（绑定适配器）会将function object的参数绑定至某特定值，使binary（二元）function object转化为unary（一元）function object。

  • function object less＜type＞期望外界传入两个值，如果第一个值小于第二个值就返回true。本例中，每个元素都必须和用户所指定的数值进行比较。理想情形下，我们需要做的就是将less＜type＞转化为一个一元（unary）运算符。这可通过“将其第二个参数绑定（bind）至用户指定的数值”完成。这么一来less＜type＞便会将每个元素拿出来一一与用户指定的数值比较。真的可以做到这样吗？是的。标准库提供的所谓adapter（适配器）便应此而生。

  • 绑定适配器binder adapter：标准库提供了两个binder adapter：bind1st会将指定值绑定至第一操作数，bind2nd则将指定值绑定至第二操作数。以下是修改后的filter（），使用了bind2nd adapter。

  • vector filter (const vector &vec, int val, less <) { iter = find_if( iter, vec.end(), bind2nd(lt, val) ); }

  • 消除函数和元素类型、容器类型的依赖：使 filter（）更加泛型化。为了消除它和元素类型间的依赖性，我们将 filter（）改为 function template，并将元素类型加入 template的声明中。为了消除它和容器类型间的依赖性，我们传入一对iteartor [first，last），并在参数列表中增加另一个iterator，用以指定从何处开始复制元素。

  • template OI filter ( II first, II last, OI at, const T &val, Comp pred)

  • insert iterator adapter：我们各需两种容器的两份实例：其中之一储存即将被过滤（filter）的元素，另一个用来储存过滤后的元素。我们令后者的容量与前者相同。3.9节有另一种解决方法：利用了所谓的insert iterator adapter。

  • 取反适配器negator：另一种adapter是所谓的negator，它会对function object的真伪值取反。not1可对unary function object的真伪值取反，not2可对binary functionobject的真伪值取反。

  • 举个例子，要找出所有大于或等于10的元素，我们可以将function object less＜int＞（）的运算结果取反。

    • findif ( iter, vec.end(), not1( bind2nd(less, 10) ) );

• 另一种实现过滤器filter的方法：另一种截然不同的方法是，先对vector排序，再以find_if（）找出第一个大于指定值的元素位置，然后再删除该位置之后至vector末尾的所有元素。通常我们会在vector的副本上进行排序，因为用户可能不愿意我们改变vector。

• 小结：

• 过滤器函数：可以找出 vector 内小于 10 的所有元素。然而函数过于死板，没有弹性。
  • 数值参数：为函数加上了一个数值参数，让用户得以指定某个数值，以此和vector中的元素做比较。
  • 函数指针：又加上了一个新参数：一个函数指针，让用户得以指定比较方式。
  • 函数对象：引入function object的概念，使我们得以将某组行为传给函数，此法比函数指针的做法效率更高。简短地检阅了标准库提供的function object。（第4章会告诉各位如何编写自己的function object。）
  • 泛型算法：最后，我将函数以function template的方式重新实现。为了支持多种容器，我传入了一对iterator，标示出一组元素范围；为了支持多种元素类型，我将元素类型参数化，也将应用于元素上的“比较操作”参数化，以便得以同时支持函数指针和function object两种方式。现在，我们的函数和元素类型无关，也和比较操作无关，更和容器类型无关。简单的说，我们已经将最初的函数转化为一个泛型算法了。

• 示例：

• 3.6：实现一个过滤器filter泛型算法，能够返回满足过滤条件的所有元素。

/* Eg.3.6 Filter as generic algorithm. */ # include # include # include # include using namespace std; template <typename InIter, typename OutIter, typename Comp> OutIter filter (InIter first, InIter last, OutIter at, Comp pred) { InIter it = first; while ((it = find_if(it, last, pred)) != last) { *at = *it; at++; it++; } return at; } template void display(InIter first, InIter last, ostream &os = cout) { for (InIter it = first; it != last; it++) os << *it << ' '; os << endl; } int main(void) { int arr[8] = {8, 34, 3, 13, 1, 21, 5, 2}; vector vec(arr, arr + 8); vector vo(vec.size()); display(vec.begin(), vec.end()); filter( vec.begin(), vec.end(), vo.begin(), bind2nd(less(), 10) ); display(vo.begin(), vo.end()); return 0; }

*3.7 使用Map

• map：map 被定义为一对（pair）数值，其中的 key 通常是个字符串，扮演索引的角色，另一个数值是value。字典便是map的一个不错实例。

• 插入：插入key/value的最简单方式是，map[key] = value

• #include map mp; mp[“vermeer”] = 1;

• 取值：map[key]，会取出与key相应的value。如果key不在map内，它便会因此被放到map内，并获得默认值0。

• 遍历：可以使用iterator遍历map的每个元素。map对象有一个名为first的member，对应于key。另有一个名为second的member，对应于value。

• map::iterator it = mp.begin(); for(; it != mp.end(); it++) cout « it->first « ’,’ « it->second « ’ ‘;

• 查找：欲查询map内是否存在某个key，有三种方法。

• 最直觉的做法就是把key当成索引使用。这种写法的缺点是，如果我们用来索引的key并不存在于map内，这个key会自动被加入map中，而其相应的value会被设置为所属类型的默认值。

  • if ( mp[key] )

  • 第二种map查询法是利用map的find（）函数（不要和泛型算法find（）搞混了）。我们将key传入find（）并调用。如果key已放在其中，find（）会返回一个iterator，指向key/value形成的一个pair（pair class是标准库的一员）。反之则返回end（）。

  • if ( mp.find(“vermeer”) != mp.end() )

  • 第三种map查询法是利用map的count()函数。count()会返回特定项在map内的个数。

  • if ( mp.count( string(“vermeer”) ) != 0)

• 唯一key：任何一个 key 值在 map 内最多只会有一份。如果我们需要储存多份相同的 key 值，就必须使用multimap。本书并不讨论multimap。

*3.8 使用Set

• set：Set由一群key组合而成。如果我们想知道某值是否存在于某个集合内，就可以使用set。

• 定义：

  • #include set st;

  • 对于任何key值，set只能储存一份。（如果要储存多份相同的key值，必须使用multiset。本书并不讨论multiset）

  • 默认情形下，set元素皆依据其所属类型默认的less-than运算符进行排列。

  • set st( vec.begin(), vec.end() ); // 1, 3, 5

• 查找：查找set中是否存在某个key。

• if ( st.count(key) )

• 插入：

• 如果要为set加入单一元素，可使用单一参数的insert（）

  • st.insert( val );

  • 如果要为set加入某个范围的元素，可使用双参数的insert（）

  • st.insert( vec.begin(), vec.end() );

• 迭代：在set身上进行迭代，其形式为iterator引用每个元素

• set::iterator it; for ( it = st.begin(); it != st.end(); it++ ) cout « *it « ’ ‘;

• 泛型算法：泛型算法中有不少和set相关的算法：

• set_intersection（），set_union（），set_difference（）和set_symmetric_difference（）。

3.9 如何使用 Iterator Inserter

• 目的端容器的大小：我们将源端（容器）中每一个符合条件的元素一一赋值（assign）至目的端（容器）。这种形式下，目的端的容器必须够大，以储存被赋值进来的每个元素。filter（）没有办法知道每次对at递增之后，at是否仍指向一个有效的容器位置。“确保at所指目的端容器的空间够大”，这是程序员的责任。

• 我们设定了目的端容器的大小，使它等于源端容器的大小，借此方式来确保以上条件。这个解法的问题在于，大部分情形下，目的端容器的大小显然太大了。
  • 另一种解法是先定义一个空容器，而后每当有元素被插入进来，再加以扩展。

• 所有“会对元素进行复制行为”的泛型算法：例如copy（）、copy_backwards（）、remove_copy（）、replace_copy（）、unique_copy（），等等，都和filter（）的实现极为相似。每个算法都接受一个iterator，标示出复制的起始位置。每复制一个元素，都会被赋值（assigned），iterator则会递增至下个位置。我们必须保证在每一次复制操作中，目的端容器都足够大，可以储存这些被赋值进来的元素。

• 插入适配器：标准库提供了三个所谓的insertion adapter，这些adapter让我们得以避免使用容器的 assignment运算符。

• back_inserter（）：会以容器的push_back（）函数取代assignment运算符。对vector来说，这是比较适合的inserter。传入back_inserter的参数，应该就是容器本身。

  • unique_copy ( vec.begin(), vec.end(), back_inserter(result_vec) );

  • inserter（）：会以容器的insert（）函数取代assignment运算符。inserter（）接受两个参数：一个是容器，另一个是iterator，指向容器内的插入操作起点。

  • unique_copy ( vec.begin(), vec.end(), inserter(result_vec) );

  • front_inserter（）：会以容器的push_front（）函数取代assignment运算符。这个inserter只适用于list和deque。

  • copy ( ilist.begin(), ilist.end(), front_inserter(olist) );

  • 欲使用上述三种adapter，首先必须包含iterator头文件

  • #include

  • 然而这些adapter并不能用在array上。array并不支持元素插入操作。

• 示例：filter（）会依次将每个元素赋值（assign）给目的端vector——本例为ivec2。由于本例并未设定ivec2的大小，所以赋值操作会产生运行时错误。但是一旦将ivec2传给inserter adapter，元素的赋值操作（assignment）即被替换为插入操作。如果只在vector的末端插入元素，效率会比较高，因此我们选用back_inserter。

• 3.9：使用inserter适配器，调用filter泛型函数，使得赋值时可以自动插入新元素。

/* Eg.3.9 Filter with inserter, which automatically inserts element when assigment. */ # include # include # include # include # include using namespace std; template <typename InIter, typename OutIter, typename Comp> OutIter filter (InIter first, InIter last, OutIter at, Comp pred) { InIter it = first; while ((it = find_if(it, last, pred)) != last) { *at = *it; at++; it++; } return at; } template void display(InIter first, InIter last, ostream &os = cout) { for (InIter it = first; it != last; it++) os << *it << ' '; os << endl; } int main(void) { int arr[8] = {8, 34, 3, 13, 1, 21, 5, 2}; vector vec(arr, arr + 8); vector vo; display(vec.begin(), vec.end()); filter( vec.begin(), vec.end(), back_inserter(vo), bind2nd(less(), 10) ); display(vo.begin(), vo.end()); return 0; }

3.10 使用 iostream Iterator

• 输入输出迭代器：标准库定义有供输入及输出使用的 iostream iterator 类，称为 istream_iterator和 ostream_iterator，分别支持单一类型的元素读取和写入。

• 头文件：使用这两个iteratorclass之前，先得包含iterator头文件。

  • #include

• istream_iterator：从标准输入设备中读取元素。

• 就像所有的iterator一样，我们需要一对iterator：first和last，用来标示元素范围。

  • first iterator：它将is定义为一个“绑至标准输入设备”的istream_iterator。

  • istream_iterator is( cin );

  • last iterator：表示“要读取的最后一个元素的下一位置”。对标准输入设备而言，end-of-file即代表last。只要在定义istream_iterator时不为它指定istream对象，它便代表了end-of-file。

  • istream_iterator eof;

  • 使用istream_iterator：将它们和储存字符串元素的vector，一起传给泛型算法copy（）。由于不知道该为vector保留多少空间，所以我选用了back_inserter。

  • copy ( is, eof, back_inserter(vec) );

• ostream_iterator：标示元素的输出位置。一旦不再有任何元素需要输出，我就停止输出操作。

• 定义：将os定义为一个“绑至标准输出设备”的ostream_iterator。此标准输出设备供我们输出类型为string的元素。上述第二个参数可以是C-style字符串，也可以是字符串常量。它用来表示各个元素被输出时的分隔符。默认情形下，输出的各个元素之间并无任何分隔符。本例我选择在各输出字符串之间以空格加以分隔。

  • ostream_iterator os (cout, “ “);

  • 使用ostream_iterator：opy（）会将储存在 text中的每个元素一一写到由 os所表示的ostream上。每个元素皆以空格分隔开来。

  • copy ( vec.begin(), vec.end(), os );

• 读写文件：我们常常并不是要从标准输入设备读数据，也不是要写到标准输出设备去，而是希望从文件中读取，写到文件去。这该如何办到？啊，只需将istream_iterator绑定至ifstream object，将ostream_iterator绑定至ofstreamobject即可。

• 示例：

• 3.10：使用iostream iterator从文件中读取单词，排序后，写入文件中。

/* Eg.3.10 Use iostream iterator to read file, sort and write to file. */ # include # include # include # include # include using namespace std; int main(void) { ifstream infile("./in.txt"); ofstream outfile("./out.txt"); if (!infile || !outfile) { cout << "Fail to open file" << endl; return -1; } // read vector vec; istream_iterator is(infile); istream_iterator eof; copy( is, eof, back_inserter(vec) ); // sort sort( vec.begin(), vec.end() ); // write ostream_iterator os(outfile, " "); copy( vec.begin(), vec.end(), os); return 0; }

• 练习：

• 3.1：使用map记录文件中词的次数，并打印出来。

/* 3.1 Use map to compute word frequency and show. */ # include # include # include # include # include # include <map> # include using namespace std; int main(void) { ifstream infile("./in.txt"); if (!infile) { cout << "Fail to open file" << endl; return -1; } // read istream_iterator is(infile); istream_iterator eof; // word map string arr[6] = {"a", "an", "or", "the", "and", "but"}; set excluded(arr, arr + 6); map<string, int> word_freq; for (; is != eof; is++) { string t = *is; if (excluded.find(t) != excluded.end()) // exclude continue; word_freq[t]++; } // show map map<string, int>::iterator it; for (it = word_freq.begin(); it != word_freq.end(); it++) cout << it->first << ',' << it->second << endl; return 0; }

• 3.3：读取文件中的map，其中每个key有多个对应值，根据key查询，并打印map。

/* 3.3 Read family map, query and display. */ #include #include #include #include #include #include <map> using namespace std; void populate_map(istream &is, map<string, vector > &mp) { // read map string line; while ( getline(is, line) ) { stringstream ss(line); vector vals; string k; ss >> k; string val; while (ss >> val) vals.push_back(val); if (mp.find(k) == mp.end()) mp[k] = vals; } } void display_map(map<string, vector > &mp, ostream &os = cout) { map<string, vector >::iterator it; for (it = mp.begin(); it != mp.end(); it++) { os << it->first << ": "; for (int i = 0; i < (it->second).size(); i++) os << (it->second)[i] << ' '; os << endl; } } void query_map(map<string, vector > &mp) { bool flag = true; while (flag) { string k; cout << "Please enter a family name or q to quit: "; cin >> k; if (k == "q") break; if (mp.find(k) == mp.end()) { cout << "Key not existed" << endl; continue; } cout << k << ": "; for (int i = 0; i < mp[k].size(); i++) cout << mp[k][i] << " "; cout << endl; } } int main(void) { ifstream infile("in.txt"); if (!infile) { cout << "Fail to open file" << endl; return -1; } // read map map<string, vector > families; populate_map(infile, families); // query map query_map(families); // display map display_map(families); return 0; }

• 3.4：使用iostream iterator读写整数。

/* 3.4 Read and write integer using iostream iterator. */ #include #include #include #include #include using namespace std; int main(void) { // read integer istream_iterator is( cin ); istream_iterator eof; vector vec; copy( is, eof, back_inserter(vec) ); // write odd int i; ostream_iterator os( cout , " " ); for (i = 0; i < vec.size(); i++) if (vec[i] % 2 == 1) os++ = vec[i]; cout << endl; // write even ostream_iterator os2( cout , "\n" ); for (i = 0; i < vec.size(); i++) if (vec[i] % 2 == 0) os2++ = vec[i]; cout << endl; return 0; }

4 基于对象的编程风格

• 使用类：这一章，我们会设计并实现属于我们自己的class。在使用class之前，由于它并非程序语言本身内置，所以我们必须先让程序知道它。通常我们会包含某个头文件来完成这件事。

• #include

• 类名：class名称被视为一个类型（type）名称，就像内置类型int、double一样。

• 对象初始化：Class object的初始化做法有很多种。

• vector vec( 4 );
  • vector vec(4, 0);
  • vector vec(arr, arr + 4);

• 操作函数：每个 class 都会提供一组操作函数，让我们作用于其 object 上。这些操作函数包括具名函数，如size（）和empty（），以及重载运算符，如equality和assignment运算符，等等

• vec1 != vec2; vec3 = vec2;
  • vec.empty(); vec.size();

• 类组成：通常我们并不知道class的实现内容。一般而言，class由两部分组成：一组公开的（public）操作函数和运算符，以及一组私有的（private）实现细节。

• public：这些操作函数和运算符称为class的member function（成员函数），并代表这个class的公开接口。身为class的用户，只能访问其公开接口。这也就是我们使用string、vector的方式。针对string的member function，我们只知其原型声明（prototype）。

  • private：Class的private实现细节可由member function的定义以及与此class相关的任何数据组成。

  • 如果string class object欲储存其字符串长度，就必须在每个class object中定义private data member（私有的数据成员），并在size（）定义中将该值返回。每当字符串长度有所变动，这份data member都必须同步更新。

• 封装：Class用户通常不会关心此等实现细节。身为一个用户，我们只利用其公开接口来进行编程。这种情形下，只要接口没有更改，即使实现细节重新打造，所有的应用程序代码也不需要变动。

• 实现类：这一章，我们的境界将从class的使用提升至class的设计与实现。这正是C++程序员的主要工作。

*4.1 如何实现一个 Class

• 抽象：一般来说，我们会从所谓的抽象（abstraction）开始。

• stack：stack是计算机科学中十分基础的一个抽象概念，它允许我们叠放许多数值，并以后进先出（last-in，first-out，LIFO）的顺序取出。

• 我们以pushing方式将新数值叠放到堆栈内，并以popping方式取出stack内最后一个被pushed的数值。用户通常还会要求其他操作行为，像是询问stack的空间是否已满（full），或是否为空（empty），或询问 stack 的元素个数（size）。stack 也可能提供查看（peeking）能力，观察stack内最后一个被pushed的数值。
  • 通用型stack应该可以存放各种类型元素。如果把stack定义为class template，便可以达到这个目的。不过，class template是第6章讨论的课题。

• 类class：

• 前置声明：Class的声明以关键字class开始，其后接一个class名称（可任意命名）。此句只是作为Stack class的前置声明（forward declaration），将class名称告诉编译器，并未提供此class的任何其他信息（像是class支持的操作行为及所包含的datamember等）。前置声明使我们得以进行类指针（class pointer）的定义，或以此class作为数据类型。

  • class Stack; //前置声明
    • Stack *p = 0;

• 定义类：接下来，在定义实际的Stack class object或访问Stack的任何一个member之前，必须先定义class本身。

• Class 定义由两部分组成：class 的声明，以及紧接在声明之后的主体。主体部分由一对大括号括住，并以分号结尾。主体内的两个关键字public和private，用来标示每个块的“member访问权限”。Public member可以在程序的任何地方被访问，private member只能在member function或是class friend内被访问。稍后我会解释friend在C++语言中的意义。

  • class Stack { public: /public接口/ private: /private实现/}

  • 所有member function都必须在class主体内进行声明。至于是否要同时进行定义，可自由决定。如果要在 class 主体内定义，这个 member function 会自动地被视为 inline函数。

  • 要在class主体之外定义member function，必须使用特殊的语法，目的在于分辨该函数究竟属于哪一个class。如果希望该函数为inline，应该在最前面指定关键字inline。告诉编译器（或程序读者）说，empty（）是 Stack class（而非 vector或 string）的一个member。class名称之后的两个冒号（Stack：：）即所谓的class scope resolution（类作用域解析）运算符。

  • inline bool Stack::empty() { return _stack.empty(); }

  • 对inline函数而言，定义于class主体内或主体外，并没有什么分别。然而就像non-member inline function一样，它也应该被放在头文件中。class定义及其inline member function通常都会被放在与class同名的头文件中。例如Stack class的定义和其empty（）函数定义都应该放在Stack.h头文件中。此即用户想要使用Stack时应该包含的文件。

  • non-inline member function应该在程序代码文件中定义，该文件通常和class同名，其后接着扩展名.C、.cc、.cpp或.cxx（x代表横放的+）。

• Stack member function 的定义。

• full（）会将目前的元素个数拿来和底层vector 的max_size（）数值（此即vector的大小）做比较。
  • push（）则是在_stack未满的前提下将元素插入。
  • 虽然我们已经提供给用户一整组操作行为，但还未能完成Stack的完整定义。下一节我们会看到如何提供极为特殊的所谓初始化函数和终止函数，它们分别被称为constructor（构造函数）和destructor （析构函数）。

• 练习：

• 4.1：编写Stack.h头文件和Stack.cpp程序代码文件，并编写main()函数，练习操作Stack的所有公开接口。程序代码文件和main（）都必须包含Stack.h。

  • Stack.h：

/* 4.1 Head file for stack. */ # include using namespace std; class Stack { public: // Stack(/* args */); // ~Stack(); void push(int x) { if (!full()) _stack.push_back(x); } void pop(void) { if (!empty()) _stack.pop_back(); } int peek(void) { if (empty()) return -1; return _stack.back(); } bool full(void) { return _stack.size() == _stack.max_size(); } bool empty(void) { return _stack.empty(); } private: vector _stack; };

• • main.cpp：

/* 4.1 Main fucntion for stack. */ # include # include "Stack.h" using namespace std; int main(void) { int i; Stack st; // push for (i = 0; i < 10; i++) st.push(i); // show while (!st.empty()) { cout << st.peek() << ' '; st.pop(); } cout << endl; return 0; }

• 4.2：扩展Stack的功能，以支持find（）和count（）两个操作。find（）会查看某值是否存在而返回true或false。count（）返回某字符串的出现次数。

/* 4.2 Expand stack to find and count function. */ # include # include # include using namespace std; class Stack { public: // Stack(/* args */); // ~Stack(); void push(int x) { if (!full()) _stack.push_back(x); } void pop(void) { if (!empty()) _stack.pop_back(); } int peek(void) { if (empty()) return -1; return _stack.back(); } bool full(void) { return _stack.size() == _stack.max_size(); } bool empty(void) { return _stack.empty(); } bool find(int x) { return std::find(_stack.begin(), _stack.end(), x) != _stack.end(); } int count(int x) { return std::count(_stack.begin(), _stack.end(), x); } int size(void) { return _stack.size(); } private: vector _stack; }; int main(void) { int i; Stack st; // push for (i = 0; i < 10; i++) st.push(i); // find cout << st.find(10) << endl; cout << st.find(5) << endl; // size cout << st.size() << endl;; // count st.push(2); cout << st.count(2) << endl; // pop while (!st.empty()) { cout << st.peek() << ' '; st.pop(); } cout << endl; return 0; }

*4.2 什么是构造函数和析构函数

• 构造函数：data member不会被自动初始化。如果我们提供一个或多个特别的初始化函数，编译器就会在每次class object被定义出来时，调用适当的函数加以处理。这些特别的初始化函数称为constructor（构造函数）。

• Constructor的函数名称必须与class名称相同。语法规定，constructor不应指定返回类型，亦不用返回任何值。它可以被重载（overloaded）。例如，class可能有三个constructor。

  • Triangular ();
    • Triangular (int len);
    • Triangular (int len, int beg_pos);

  • class object定义出来后，编译器便自动根据获得的参数，挑选出应被调用的constructor。

  • 因为C++必须兼容于C。对C而言，t3之后带有小括号，会使 t3被视为函数。正确（符合我们意图）的声明方式，应该和t0一样。
    • Triangular t1 = 8; // 调用constructor
    • Triangular t2(10, 3);
    • Triangular t3(); // 无法成功定义object
    • Triangular t0; // 可以定义object

  • 最简单的constructor是所谓的default constructor。它不需要任何参数（argument）。这意味着两种情况。由于我们为两个整数提供了默认值，所以这个default constructor同时支持原本的三个constructor。

  • 第一，它不接受任何参数。 Triangular () { _length = 1; }
    • 第二，它为每个参数提供了默认值。这种情况更为常见。Triangular ( int len = 1, int bp = 1 )

• 成员初始化列表：Constructor定义的第二种初始化语法，是所谓的member initialization list（成员初始化列表）。

• 成员初始化列表紧接在参数列表最后的冒号后面，是个以逗号分隔的列表。其中，欲赋值给member的数值被放在member名称后面的小括号中；这使它们看起来像是在调用constructor。

  • Triangular ( int len, int bp ) : _length(len), _beg_pos(bp) { } // 空函数体

  • 成员初始化列表主要用于将参数传给member class object的constructor。

• 析构函数：和constructor对立的是destructor。所谓destructor乃是用户自定义的一个classmember。一旦某个class提供有destructor，当其object结束生命时，便会自动调用destructor处理善后。Destructor主要用来释放在constructor中或对象生命周期中分配的资源。

• Destructor的名称有严格规定：class名称再加上’～’前缀。它绝对不会有返回值，也没有任何参数。由于其参数列表是空的，所以也绝不可能被重载（overloaded）。

  • 若constructor使用new表达式从heap中分配double数组所需空间。其destructor则负责释放这些内存。class的用户不需要知道内存管理细节。这种写法有点类似标准库的容器（container）设计。

  • ~Matrix() { delete [] _pmat; }

  • Destructor并非绝对必要。三个data member皆以储值（by value）方式来存放，这些member在class object被定义之后便已存在，并在class object结束其生命时被释放。因此，Triangular destructor没有什么事好做。我们没有义务非得提供destructor。事实上，C++编程的最难部分之一，便是了解何时需要定义destructor而何时不需要。

• Memberwise Initialization（成员逐一初始化）：默认情形下，当我们以某个class object作为另一个object的初值。class data member会被依次复制。此即所谓的default memberwise initialization（默认的成员逐一初始化操作）。

• 通常default memberwise initialization会正确复制所有的data member，我们不必特意做其他事。

  • Triangular t2 = t1;

  • 但对于有内存分配的class而言，default memberwise initialization并不适当。

  • 这会使得两个对象的_pmat都指到heap内的同一个数组。当Matrix destructor应用于mat2上，该数组空间便被释放。不幸的是，此时mat的_pmat仍指向那个数组，而你知道，对空间已被释放的数组进行操作，是非常严重的错误行为。

  • 可以通过“另一个copy constructor”，改变这种“成员逐一初始化”的默认行为模式。copy constructor唯一参数是一个constreference，指向（代表）一个Matrix object。其内容可以产生一个独立的数组复本，这样便可以使某个对象的析构操作不致于影响到另一个对象。

  • Matrix( const Matrix &rhs) : _row(rhs._row), _col(rhs._col) { _pmat = new double[_row*_col]; _pmat[i] = rhs._pmat[i] }

  • 当我们设计class时，必须问问自己，在此class之上进行“成员逐一初始化”的行为模式是否适当？如果答案肯定，我们就不需要另外提供copy constructor。但如果答案是否定的，我们就必须另行定义copy constructor，并在其中编写正确的初始化操作。

  • 如果有必要为某个class编写copy constructor，那么同样有必要为它编写copyassignment operator （参阅4.8节）。

4.3 何谓mutable（可变）和 const（不变）

• const成员函数：trian是个const reference对象，因此编译器必须保证对象不会被修改。但是，调用的任何一个member function都有可能更改trian的值。编译器必须确保成员函数都不会更改其调用者。class设计者必须在member function身上标注 const，以此告诉编译器：这个member function不会更改class object的内容。

• const修饰符紧接于函数参数列表之后。凡是在class主体以外定义者，如果它是一个const member function，那就必须同时在声明与定义中指定const。

  • const Triangular &trian;
    • int length() const { return _length; }

  • 虽然编译器不会为每个函数进行分析，决定它究竟是 const还是non-const，但它会检查每个声明为const的member function，看看它们是否真的没有更改class object内容。

  • bool next( int &val) const { _next++; } // 错误：更改了_next的值

  • 返回一个 non-const reference 指向_val，实际上等于将_val开放出去，允许程序在其他地方加以修改。由于member function可以根据const与否而重载，因此有个方法可以解决这个问题：提供两份定义，一为const版本，一为non-const版本。Non-const class object会调用non-const版的val（）（于是对象内容被改变也没有关系），const class object则会调用const版的val（）（那就不可能改变对象的内容）。这样就完全没有问题了。

  • const BigClass& val() const { return _val; }
    • BigClass& val() { return _val; }
  • 设计class时，鉴定其const member function是一件很重要的事。如果你忘了这么做，要知道，没有一个const reference class参数可以调用公开接口中的non-const成分（但目前许多编译器对此情况都只给警告）。用户也许会因此大声咒骂。将const加到class内并非易事，特别是如果某个member function被广泛使用之后。

• Mutable Data Member（可变的数据成员）：

• trian是个const object，而next_reset（）和next（）都会更改_next值，它们都不是const memberfunction。但它们却被trian调用，于是造成错误。

  • const Triangular trian;
    • trian.next(val);

  • mutable：_next只是用来让我们得以实现出iterator机制，它本身不属于数列抽象概念的一环。改变_next的值，从意义上来说，不能视为改变class object的状态，或者说不算是破坏了对象的常量性（constness）。关键字mutable可以让我们做出这样的声明。只要将_next标示为mutable，我们就可以宣称：对_next所做的改变并不会破坏class object的常量性。

  • mutable int _next;

  • 现在，next（）和next_reset（）既可以修改_next的值，又可以被声明为const member function。这么一来，前述的sum（）实现就没有问题了。

*4.4 什么是this指针

• copy（）成员函数：以Triangular class object作为另一个Triangular class object的初值。copy（）必须返回被复制出来的对象。

• 本例中，tr1不仅是复制的目标，也用来接收复制的结果。

  • tr1.copy(tr2);
    • Triangular& copy( const Triangular &rhs) { _length = rhs._length; return *this; }

• this指针：我们还需要一种可以指向 tr1整个对象的方法。所谓 this指针便扮演了这样的角色。this指针系在member function内用来指向其调用者（一个对象）。

• 内部工作过程是，编译器自动将this指针加到每一个member function的参数列表，于是copy（）被转换为以下形式：

  • Triangular& copy(Triangular *this, const Triangular &rhs)

  • 在member function内，this指针可以让我们访问其调用者的一切。如果想在copy（）中返回tr1，只要简单地提领this指针即可。

  • return *this;

  • 欲以一个对象复制出另一个对象，先确定两个对象是否相同是个好习惯。这必须再次运用this指针。

  • if (this != &rhs)

4.5 静态类成员

• 静态数据成员：static（静态）data member用来表示唯一的、可共享的member。它可以在同一类的所有对象中被访问。

• 我们声明_elems是Triangular class的一个static datamember。对class而言，static data member只有唯一的一份实体，因此我们必须在程序代码文件中提供其清楚的定义。这种定义看起来很像全局对象（global object）的定义。唯一的差别是，其名称必须附上class scope运算符。也可以为它指定初值。

  • static vector _elems;
    • vector Triangular::_elems;
    • int Triangular::_initial_size = 8;

  • 如果要在class member function内访问static data member，其方式有如访问一般（non-static）数据成员。像buf_size这类的const static int data member，可以在声明时为其明确指定初值。

  • static const in _buf_size = 1024;

• Static Member Function（静态成员函数）：

• 一般情形下，member function 必须通过其类的某个对象来调用。这个对象会被绑定至该 member function的this指针。通过储存于每个对象中的this指针，member function才能够访问储存于每个对象中的non-static data member。

  • 上述的 is_elem（）并未访问任何non-static data member。它的工作和任何对象都没有任何关联，因而应该可以很方便地以一般non-member function的方式来调用。class scope运算符可以解决这种令人混淆的问题。

  • static bool is_elem(int val);
    • if ( Triangular::is_elem(8) )

  • 于是static member function便可以在这种“与任何对象都无瓜葛”的情形之下被调用。注意，member function只有在“不访问任何non-static member”的条件下才能够被声明为static，声明方式是在声明之前加上关键字static。

  • 当我们在class主体外部进行member function的定义时，无须重复加上关键字static（这个规则也适用于static data member）

  • bool Triangular::is_elem(int val)

• 示例：

• 4.5：使用静态成员的Triangular class。

/* eg.4.5 Triangular Class with static member. */ #include #include #include #include using namespace std; class Triangular { public: static bool is_elem(int val) { if (_elems.size() < 1 || _elems.back() < val) gen_elems_to_value(val); return std::find(_elems.begin(), _elems.end(), val) != _elems.end(); } static void gen_elems_to_value(int val) { int i; while ( _elems.size() == 0 ||(_elems.size() < _elems.max_size() && _elems.back() < val) ) { i = _elems.size() + 1; _elems.push_back(i * (i + 1) / 2); } } private: static vector _elems; }; vector Triangular::_elems; int main(void) { int val; bool flag = true; char ch; while (flag) { cout << "Enter value: "; cin >> val; cout << Triangular::is_elem(val) << endl; cout << "Continue? Y/N: "; cin >> ch; if (ch != 'Y' && ch != 'y') flag = false; } return 0; }

*4.6 打造一个 Iterator Class

• iterator class：为了说明如何对class进行运算符重载操作，让我们体验一下如何实现一个iterator class。

• 运算符重载：我们必须为此iterator class定义！=、＊、++等运算符。我们可以像定义memberfunction那样来定义运算符。运算符函数看起来很像普通函数，唯一差别是它不用指定名称，只需在运算符前加上关键字operator即可。

  • bool operator==( const Triangular_iterator & rhs) const;
    • int operator*() const;
    • Triangular_iterator& operator+ (); // 前置版
    • Triangular_iterator operator++(int); // 后置版

  • Triangular_iterator维护一个索引值，用以索引Triangular中用来储存数列元素的那个static data member，也就是_elems。为了达到这个目的，Triangular 必须赋予 Triangular_iterator 的member function特殊的访问权限。我们会在4.7节看到如何通过friend机制给予这种特殊权限。

  • 如果两个Triangular_iterator对象的_index相等，我们便说这两个对象相等。

  • bool operator==( const T &rhs ) const { return _index == rhs._index; }

  • 所谓运算符，可以直接作用于其class object。如果我们希望将运算符作用于指针所指的对象，就得先提领该指针，取出其所指对象。

  • if (*it1 == *it2)

  • 任何运算符如果和另一个运算符性质相反，我们通常会以后者实现出前者。

  • bool operator!=( const T &rhs ) const { return !( *this == rhs ); }

• 运算符重载的规则：

• 不可以引入新的运算符。除了.、.＊、：：、？：四个运算符，其他的运算符皆可被重载。

  • 运算符的操作数（operand）个数不可改变。每个二元运算符都需要两个操作数，每个一元运算符都需要恰好一个操作数。因此，我们无法定义出一个equality运算符，并令它接受两个以上或两个以下的操作数。

  • 运算符的优先级（precedence）不可改变。例如，除法的运算优先级永远高于加法。

  • 运算符函数的参数列表中，必须至少有一个参数为 class 类型。也就是说，我们无法为诸如指针之类的non-class类型，重新定义其原已存在的运算符，当然更无法为它引进新运算符。运算符的定义方式，就像member function一样。但也可以像non-member function一样。Non-member运算符的参数列表中，一定会比相应的member运算符多出一个参数，也就是 this指针。对member运算符而言，这个this指针隐式代表左操作数。

  • int opeator*() const { return Triangular::_elems[_index]; }

    • int operator*( const Iter &rhs ) { return Triangular::_elems[_index]; }

• check_integrity（） member function 可以确保_index 不大于_max_elems，并确保_elems储存了必要的元素。

• 递增运算符：我们必须提供increment（递增）运算符的前置（++trian）和后置（trian++）两个版本。

• 前置版的参数列表是空的：

  • Triangular_iterator& operator++() { ++_index; return *this; }

  • 后置版的参数列表原本也应该是空的，然而重载规则要求，参数列表必须独一无二。因此，C++语言想出一个变通办法，要求后置版得有一个int参数：

  • Triangular_iterator operator++() { Triangular_iterator tmp=*this; ++_index; return tmp; }

  • increment（递增）或decrement（递减）运算符的前置及后置版本都可直接作用于其class object。编译器会自动为后置版产生一个int参数（其值必为0）。用户不必为此烦恼。

• 接下来我们要做的，便是为Triangular提供一组begin（）/end（）member function，并支持前述iterator定义。这需要用到稍后才讨论到的所谓嵌套类型（nested type）。

• Triangular_iterator begin() const { return Triangular_iterator(_beg_pos); }
  • Triangular_iterator end() const { return Triangular_iterator(_beg_pos+_length); }

• 嵌套类型（Nested Type）：

• typedef：typedef可以为某个类型设定另一个不同的名称。其中的 existing_type 可以是任何一个内置类型、复合类型或 class 类型。在我们的例子中，我令iterator等同于Triangular_iterator，以简化其使用形式。

  • typedef existing_type new_name;
    • class Triangular { public typedef Triangular_iterator iterator };

  • 定义一个iterator object：我们得使用class scope运算符来指引编译器，让它在面对iterator这个字眼时，查看Triangular内部提供的定义。

  • Triangular::iterator it = trian.begin();

  • 如果将iterator嵌套放在每个“提供iterator抽象概念”的class内，我们就可以提供有着相同名称的多个定义。但是这样的声明语法有些复杂。

4.7 合作关系必须建立在友谊的基础上

• 朋友：任何 class 都可以将其他function或class指定为朋友（friend）。而所谓friend，具备了与class member function相同的访问权限，可以访问class的private member。

• 为了让operator＊（）通过编译，不论Triangular或Triangular_iterator都必须将operator＊（）声明为“朋友”。

  • friend int operator*( const Triangular_iterator &rhs) { return Triangular::_elems[rhs._index]; }

  • 只要在某个函数的原型（prototype）前加上关键字friend，就可以将它声明为某个class的friend。这份声明可以出现在class定义的任意位置上，不受private或public的影响。如果你希望将数个重载函数都声明为某个class的friend，你必须明确地为每个函数加上关键字friend。

  • Triangular_iterator内的operator＊（）和check_integrity（）都需要直接访问Triangular的private member，因此我们将两者都声明为Triangular的friend。

  • class Triangular
    • friend int Triangular_iterator::operator*();

  • 为了让上述定义成功通过编译，我们必须在上述两行之前，先提供Triangular_iterator的定义让 Triangular 知道。否则编译器就没有足够的信息可以确定上述两个函数原型是否正确，也无法确定它们是否的确是Triangular_iterator的member function。

  • 我们也可以令class A与class B建立friend关系，借此让class A的所有member function都成为class B的friend。如果以这种形式来声明class间的友谊，就不需要在友谊声明之前先显现class的定义。

  • class Triangular
    • friend class Triangular_iterator;

• 如果Triangular提供一个public member function来访问_max_elems，以及另一个public member function来返回_elems的当前大小，那么check_integrity（）就不再需要主动建立友谊。

• public: static int max_elems() { return _max_elems; }
  • if ( _index >= Triangular::max_elems() )

• 友谊的建立，通常是为了效率考虑。例如在某个non-member运算符函数中进行Point和Matrix的乘法运算。如果我们只是希望进行某个data member的读取和写入，那么，为它提供具有public访问权限的inline函数，就是建立友谊之外的一个替代方案。

• 示例：

• 4.7：利用friend实现Triangular类的iterator class。

/* eg.4.7 Iterator Class with friend. */ #include #include #include #include using namespace std; class Triangular_iterator { public: Triangular_iterator& operator=(const Triangular_iterator &rhs) { _index = rhs._index; return *this; } Triangular_iterator(int idx = 0): _index(idx) {} bool operator!=(const Triangular_iterator &rhs) { return _index != rhs._index; } Triangular_iterator& operator++(int x) { _index++; return *this; } int operator*(); private: int _index; void check_integrity(); }; class Triangular { public: typedef Triangular_iterator iterator; friend class Triangular_iterator; Triangular (int len = 0): _length(len), _beg_pos(1) {} static bool is_elem(int val) { if (_elems.size() < 1 || _elems.back() < val) gen_elems_to_value(val); return std::find(_elems.begin(), _elems.end(), val) != _elems.end(); } static void gen_elems_to_value(int val) { int i; while ( _elems.size() == 0 ||(_elems.size() < _elems.max_size() && _elems.back() < val) ) { i = _elems.size() + 1; _elems.push_back(i * (i + 1) / 2); } } static void gen_elems(int len) { int i = 0; while (_elems.size() < len && _elems.size() < _elems.max_size()) { i = _elems.size() + 1; _elems.push_back(i * (i + 1) / 2); } } iterator begin() { return iterator(_beg_pos - 1); } iterator end() { return iterator(_beg_pos + _length - 1); } private: static vector _elems; int _length; int _beg_pos; }; vector Triangular::_elems; inline int Triangular_iterator::operator*() { check_integrity(); return Triangular::_elems[_index]; } void Triangular_iterator::check_integrity() { if (_index + 1 > Triangular::_elems.max_size()) throw "Iterator Overflow"; else if (_index + 1 > Triangular::_elems.size()) Triangular::gen_elems(_index + 1); } int main(void) { Triangular tri(20); Triangular::iterator it; for (it = tri.begin(); it != tri.end(); it++) cout << *it << ' '; cout << endl; return 0; }

4.8 实现一个 copy assignment operator

• 复制赋值运算符：默认情况下，当我们将某个class object赋值给另一个，class data member会被依次复制过去。这称为defaultmemberwise copy（默认的成员逐一复制操作）。

• 但是面对4.2节的Matrix class，这种defaultmemberwise copy行为便不正确。Matrix需要一个 copy constructor 和一个 copy assignment operator。

  • 只要class设计者明确提供了 copy assignment operator（像上面那样），它就会被用来取代default memberwise copy行为。严格说来，这种做法并非exception-safe（异常发生时保持安全）。

  • Matrix& operator=( const Matrix &rhs )

    • _pmat = new double[ _row * _col ]; _pmat[ix] = rhs._pmat[ix];

*4.9 实现一个 function object

• 函数对象：我们已经在 3.6 节看到了标准库事先定义的 function object。本节教你如何实现自己的 function object。所谓function object乃是一种“提供有function call运算符”的class。

• 当编译器在编译过程中遇到函数调用，lt可能是函数名称，可能是函数指针，也可能是一个提供了functioncall运算符的function object。如果lt是个class object，编译器便会在内部将此语句转换。

  • lt( val );
    • lt.operator( val );

  • function call运算符可接受任意个数的参数：零个、一个、两个或更多。举个例子，它可被用来支持Matrix的多维度下标（subscripting）操作，因为语言所提供的subscript运算符仅能接受一个参数。

  • 定义function object的方式和定义一般对象并没有两样，对其函数调用运算符operator()进行重载。

  • class LessThan
    • bool operator(int a, int b) { return a < b; }

  • 将function call运算符应用于对象身上，便可以调用function call运算符。通常我们会把function object当作参数传给泛型算法。附录B提供有更多function object的定义实例。

  • LessThan lt;
    • sort( vec.begin(), vec.end(), lt );

• 示例：

• 4.9：实现function object并传给泛型函数。

/* eg.4.9 Function object. */ #include #include #include using namespace std; class GreaterThan { public: bool operator()(int a, int b) { return a > b; } }; int main(void) { int arr[5] = {1, 2, 3, 4, 5}; vector vec(arr, arr+5); GreaterThan gt; sort( vec.begin(), vec.end(), gt ); for (int i = 0; i < vec.size(); i++) cout << vec[i] << ' '; cout << endl; return 0; }

4.10 重载 iostream运算符

• 重载io运算符：我们常常会希望对某个class object进行读取和写入操作。

• 我们必须另外提供一份重载的output运算符。传入函数的ostream对象又被原封不动地返回。如此一来我们便得以串接多个output运算符。参数列表中的两个对象皆以传址（byreference）方式传入。其中的ostream对象并未声明为const，因为每个output操作都会更改ostream对象的内部状态。至于rhs这种将被输出的对象，就会被声明为const——因为这里之所以使用传址方式，是基于效率考虑而非为了修改其对象内容。

  • ostream& operator«( ostream &os, const Triangular &rhs ) { os « rhs.length(); return os; }
    • cout « tri « endl;

  • 为什么不把output运算符设计为一个member function呢？因为作为一个member function，其左操作数必须是隶属于同一个class的对象。如果output运算符被设计为tri class member function，那么triobject就必须被放在output运算符的左侧，这种奇怪的形式必定对class用户造成困惑！

  • input 运算符只读取和 Triangular有关的前四个成分。

  • istream& operator»( istream &is, Triangular &rhs ) { is » len; rhs.length(len); return is; }

  • 一般而言，input运算符的实现比较复杂。因为读入的数据可能有问题。在这里，我并没有考虑错误的检验。

• 示例：

• 4.10：重载对象的io运算符。

/* eg.4.10 Overload iostream operator. */ #include #include using namespace std; class MyClass { public: int length() { return _length; } void length(int len) { _length = len; } private: int _length; }; ostream& operator<<( ostream &os, MyClass &rhs ) { os << rhs.length(); return os; } istream& operator>>( istream &is, MyClass &rhs ) { int len; is >> len; rhs.length(len); return is; } int main(void) { MyClass obj; cin >> obj; cout << obj << endl; return 0; }

4.11 指针，指向 Class Member Function

• 本节讨论的重点在于实现出一个通用的数列类num_sequence，使其对象可同时支持上述六种数列。

• 其中的 ns便是一个通用型数列对象。在 for循环每次迭代过程中，我们利用 set_sequence（），根据ns_type（）返回的不同数列的代码，将ns重新设值。num_of_sequences（）返回目前支持的数列种类个数。num_of_sequence（）和ns_type（）皆为inline staticmember function。elem（）会返回特定位置的元素值。

• 指向成员函数的指针：num_sequence的设计关键在于，pointer to member function（指向成员函数的指针）机制的运用。这种指针看起来和pointer to non-member function（2.8节介绍过）极为相似。两者皆需指定其返回类型和参数列表。不过，pointer to member function还得指定它所指的究竟是哪一个class。

• 将pm声明为一个指针，指向num_sequence的memberfunction，后者的返回类型必须是void，并只接受单一参数，参数类型为int。pm的初始值为0，表示它目前并不指向任何memberfunction。

  • void (NumSeq::*pm) (int) = 0;

  • 如果这样的语法过于复杂，我们可以通过typedef加以简化。将PtrType声明为一个指针，指向num_sequence的member function，后者的返回类型是void，只接受一个int参数。这种声明方式和先前的完全相同。

  • typedef void (NumSeq::*PtrType) (int);
    • PtrType pm = 0;

  • num_sequence提供以下六个member function，每一个都可由PtrType指针加以定位。为了取得某个member function的地址，我们对函数名称应用address-of（取址）运算符。注意，函数名称前必须先以class scope运算符加以限定，至于返回类型和参数列表皆不必指明。

  • PtrType pm = &NumSeq::fibonacci;

• 每当调用set_sequence（），我们便指定_pmf值，令其指向前述六个member functions之一。为求简化，我们可以将这六个member function的地址储存在一个static array中。为了避免重复计算每个数列元素，我们还维护一个static vector，内放六个vector，分别储存各个数列。

• seq是个vector，其中每个元素又是一个vector（代表一个数列），用来存放int元素。如果我们忘了在两个＞之间加上空白，就无法编译成功。这是基于所谓的 maximal munch 编译规则。此规则要求，每个符号序列（symbol sequence）总是以“合法符号序列”中最长的那个解释。因为＞＞是个合法的运算符序列，因此如果两个＞之间没有空白，这两个符号必定会被合在一起看待。

  • static vector > seq;

  • 我们还必须提供每个 static data member 的定义。由于PtrType 是个嵌套类型，所以在num_sequence之外对它所做的任何访问操作，都必须以class scope运算符加以限定。至于num_seq的值，已经在class定义中指定好了，这里不需要重复指定。如果你对嵌套类型的语法感到困惑，可以利用typedef加以隐藏。

  • vector > NumSeq::seq( num_seq );
    • NumSeq::PtrType NumSeq::func_tbl[ num_seq ] = { 0, &NumSeq:fibonacci };
  • _elem和_pmf在set_sequence（）内一起被设定。设定好后，_elem指向存有数列元素的vector，_pfm则指向产生数列元素的memberfunction。set_sequence（）的实际做法，要到5.3节才介绍。

• 调用函数：Pointer to member function和pointer to function的一个不同点是，前者必须通过同一类的对象加以调用，而该对象便是此member function内的this指针所指之物。

• 为了调用指针所指向的成员函数，其中的.＊符号是个pointer to member selection运算符，系针对class object工作。我们必须为它加上外围小括号，才能正确工作。

  • NumSeq ns;
    • PtrType pm = &NumSeq::fibonacci;
    • (ns.*pm)( pos ) // 调用fibonacci成员函数

  • 至于针对pointer to class object工作的pointer to member selection运算符，其符号是-＞＊：

  • NumSeq *pns = &ns;
    • (pns->*pm) ( pos )
  • elem（）的实现内容。如果用户所指定的位置是个合理值，而目前所储存的元素并未包含这个位置，那么就调用_pmf所指函数，产生新元素。

• 以上便是截至目前所讨论的实现方法。第 5 章有更多设计细节，谈到如何让每个 num_sequence对象在其生命期的任意时刻，都能知晓自身的数列究竟是什么类型。然后我们会看到如何通过面向对象（object-oriented）编程风格，将多重类型的操作方式更加简化。

• 练习：

• 4.5：实现一个matrix class，并重载其运算符。

/* 4.5 Matrix class. */ #include #include using namespace std; typedef float ElemType; class Matrix { public: Matrix (ElemType *arr) { int i, j; for (i = 0; i < 4; i++) for (j = 0; j < 4; j++) _mat[i][j] = arr[4*i+j]; } Matrix () {}; Matrix operator+( Matrix &rhs ) { Matrix m; int i, j; for (i = 0; i < 4; i++) for (j = 0; j < 4; j++) m._mat[i][j] = (this->_mat)[i][j] + rhs._mat[i][j]; return m; } Matrix operator*( Matrix &rhs ) { Matrix m; int i, j, k; for (i = 0; i < 4; i++) for (j = 0; j < 4; j++) for (k = 0, m._mat[i][j] = 0; k < 4; k++) m._mat[i][j] += (this->_mat)[i][k] * rhs._mat[k][j]; return m; } void print(ostream &os) { int i, j; for (i = 0; i < 4; i++) { for (j = 0; j < 4; j++) os << _mat[i][j] << ' '; os << endl; } } void operator+=( Matrix &rhs ) { int i, j; for (i = 0; i < 4; i++) for (j = 0; j < 4; j++) (this->_mat[i][j]) += rhs._mat[i][j]; } ElemType operator()( int row, int col ) const { return _mat[row][col]; } ElemType& operator()( int row, int col ) { return _mat[row][col]; } private: ElemType _mat[4][4]; }; ostream& operator<<( ostream &os, Matrix &rhs ) { rhs.print(os); return os; } int main(void) { ElemType ar[16] = { 1., 0., 0., 0., 0., 1., 0., 0., 0., 0., 1., 0., 0., 0., 0., 1. }; ElemType ar2[16] = { 1.3, 0.4, 2.6, 8.2, 6.2, 1.7, 1.3, 8.3, 4.2, 7.4, 2.7, 1.9, 6.3, 8.1, 5.6, 6.6 }; Matrix m1(ar); cout << m1 << endl; Matrix m2(ar2); cout << m2 << endl; Matrix m3 = m1 + m2; m3 += m1; cout << m3 << endl; Matrix m4 = m1 * m2; cout << m4 << endl; return 0; }

5 面向对象编程风格

• 类的实现：class的主要用途在于引入一个崭新的数据类型，能够更直接地在我们所设计的程序系统中，表现我们想表现的实体。

• 类间关系：

• 当我们的应用系统布满许多类，其间有着“是一种（is-a-kind-of）”的关系时，以对象为基础（object-based）的编程模型反而会拖累我们的程序设计工作。每个类可能会共享data member及member function，也可能增加额外的特殊数据，用以表示其自身状态。

  • 第4章所谈的“基于对象（object-based）”的类机制无法轻松针对这四个“are-a-kind-of（隶属同类）”的Book类的共通性质进行系统化的划分。因为这种模型无法让我们更进一步地指出类间的关系。类间的关系有赖“面向对象编程模型（object-oriented programming model）”加以设定。

*5.1 面向对象编程概念

• 面向对象编程：面向对象编程概念的两项最主要特质是：继承（inheritance）和多态（polymorphism）。前者使我们得以将一群相关的类组织起来，并让我们得以分享其间的共通数据和操作行为，后者让我们在这些类之上进行编程时，可以如同操控单一个体，而非相互独立的类，并赋予我们更多弹性来加入或移除任何特定类。

• 继承：继承机制定义了父子（parent/child）关系。父类（parent）定义了所有子类（children）共通的公有接口（public interface）和私有实现（private implementation）。每个子类都可以增加或覆盖（override）继承而来的东西，以实现其自身独特的行为。

• 基类/派生类：在C++中，父类被称为基类（base class），子类被称为派生类（derived class）。父类和子类之间的关系则称为继承体系（inheritance hierarchy）。

  • 抽象基类：继承体系中最根本的类乃是一个抽象基类（abstract base class）：LibMat。LibMat用来定义图书馆借阅管理系统中所有馆藏的共通操作行为。LibMat并不代表图书馆借阅管理系统中实际存在的任何一个馆藏，仅仅是为了我们设计上的需要而存在。但事实上这个抽象十分关键。我们称之为“抽象基类（abstract base class）”。

  • 在面向对象应用程序中，我们会间接利用“指向抽象基类”的pointer或reference来操作系统中的各对象，而不直接操作各个实际对象。这让我们得以在不更动旧有程序的前提下，加入或移除任何一个派生类。

  • 我们的程序中并不存在LibMat对象，每当loan_check_in（）被调用，mat必定得指向我们程序中的某个实际对象。此外，被调用的 check_in（）函数也势必得被解析（ resolved）为 mat 所代表的实际对象所拥有的那个check_in（）函数。这便是整个进行过程。

    • void loan_check_in (LibMat &mat) { mat.check_in(); }

• 多态：面向对象编程风格的第二个独特概念是多态（polymorphism）：让基类的pointer或reference得以十分透明地（transparently）指向其任何一个派生类的对象。

• mat总是指向（代表）LibMat的某个派生对象。但究竟是哪一个？答案是除非程序实际执行的当下，否则无法确定。而且，loan_check_in（）的每次执行情况都可能不同。

• 动态绑定：动态绑定（dynamic binding）是面向对象编程风格的第三个独特概念。

• 静态绑定：在非面向对象的编程风格中，编译器在编译时就依据 mat 所属的类决定究竟执行哪一个 check_in（）函数。由于程序执行之前就已解析出应该调用哪一个函数，所以这种方式被称为静态绑定（static binding）。
  • 动态绑定：但在面向对象编程方法中，编译器无法得知究竟哪一份 check_in（）函数会被调用。每次loan_check_in（）执行时，仅能在执行过程中依据mat所指的实际对象来决定调用哪一个check_in（）。“找出实际被调用的究竟是哪一个派生类的check_in（）函数”这一解析操作会延迟至运行时（run-time）才进行。此即我们所谓的动态绑定（dynamic binding）。
• 复用性：如果图书馆决定不再出借交互式书籍，我们只需将此类从继承体系中移除即可。loan_check_in（）实现无须任何变动。同样道理，如果图书馆决定为特定的有声书收取额外的出租费用，我们可以做出另一个派生类AudioRentalBook。loan_check_in（）仍旧无须任何更改。

*5.2 漫游：面向对象编程思维

• 类体系：实现一个三层的类体系，并借此引入C++语言中的基本组成和支持面向对象编程方法的语法元素。我以 LibMat这个抽象基类作为类体系中的最根本的类。我从 LibMat派生出 Book，并从Book派生出AudioBook。我们先限定接口只有一个constructor、一个destructor和一个print（）函数。

• 基类：默认情形下，member function的解析（resolution）皆在编译时静态地进行。若要令其在运行时动态进行，我们就得在它的声明前加上关键字virtual。LibMat的声明表示，其destructor和print（）皆为virtual（虚函数）。

  • class LibMat
    • LibMat() { cout « “LibMat constructor\n”; }
    • virtual ~LibMat() { cout « “LibMat destructor.\n”; }
    • virtual void print() const { cout « “LibMat print function.\n”; }

  • 调用虚函数：在main（）程序中重复调用display（），并依次将LibMat对象、Book对象、AudioBook对象当作参数传递给它。每次display（）被执行，都会依据mat实际所指的对象，在LibMat、Book、AudioBook三者之间挑选正确的print（）member function加以调用。

  • void display( const LibMat &mat ) { mat.print(); }
    • LibMat mat;
    • display(mat);

  • 虚拟调用：将Book对象传入display（），通过mat.print（）所进行的虚拟调用（virtual invocation）操作的确有效。被调用的函数是Book：：print（）而非LibMat：：print（）。第二件令人感兴趣的事是，当程序定义出一个派生对象，基类和派生类的constructor都会被执行。（当派生对象被销毁，基类和派生类的destructor也都会被执行〔但次序颠倒〕。）

  • Book b(“The Castle”, “Franz Kafka”);
    • display(b);

• 实现派生类：

• 为了清楚标示这个新类乃是继承自一个已存在的类，其名称之后必须接一个冒号（：），然后紧跟着关键字public和基类的名称。

  • class Book : public LibMat {
    • Book ( const string &title, const string &author ) : _title(title), _author(author) {}
    • virtual void print() const {}
    • const string& title() const { return _title; }
    • protected: string _title;

  • 覆盖：Book中的print（）覆盖（override）了LibMat的print（）。这也正是mat.print（）所调用的函数。

  • 访问函数：title（）和author（）是两个所谓的访问函数（accessfunction），都是non-virtual inline函数。

  • protected成员：过去我们不曾介绍关键字protected，被声明为protected的所有成员都可以被派生类直接访问，除此（派生类）之外，都不得直接访问protected成员。

  • 继续派生：从Book类派生出一个更特殊的AudioBook类。AudioBook除了拥有标题和作者，还有播讲者。我们只需要把焦点放在AudioBook与其基类Book的不同之处——也就是 print（）——即可。当然，我们还必须提供AudioBook 播讲者姓名，以及这个类的constructor和 destructor。至于Book类所提供的各项数据及操作函数，均可被AudioBook直接使用，仿佛它们本来便是由AudioBook定义似的。

  • class AudioBook : public Book
    • AudioBook (const string &title, const string &author, const string &narrator)
    • virtual void print() const {}
    • protected: string _narrator;

  • 使用派生类时不必刻意区分“继承而来的成员”和“自身定义的成员”。两者的使用完全透明。

  • AudioBook ab( “Snow White”, “Anderson”, “Robert”);
    • cout « ab.title() « ‘\n’ « ab.narrator() « endl;

• 示例：

• 5.2：实现LibMat类体系，派生一个Book类，定义一个Book对象并调用display()。

/* Eg.5.2 Implement a class hierarchy. */ # include # include using namespace std; class LibMat { public: LibMat () { cout << "LibMat constructor" << endl; } ~LibMat () { cout << "LibMat destructor" << endl; } virtual void print() { cout << "LibMat print function" << endl; } }; class Book : public LibMat { public: Book (const string &title): _title(title) { cout << "Book constructor" << endl; } ~Book () { cout << "Book destructor" << endl; } virtual void print() { cout << "Book print function" << endl; cout << "Title: " << _title << endl; } string& title() { return _title; } protected: string _title; }; void display(LibMat &mat) { mat.print(); } int main(void) { Book b("Snow White"); display(b); return 0; }

5.3 不带继承的多态

• 模拟多态：num_sequence class模拟了多态行为。该类的每一个对象皆能在程序执行过程中的任一时间点，通过member functionset_sequence（），摇身一变为六个数列之一。

• 这种改变ns数列类型的能力，乃是通过编程技巧获得，不是由程序语言先天赋予。该类的每一个对象都含有data member _isa，用以记录它目前代表的数列类型。

  • ns.set_sequence( num_sequence::nstype(ix) );
    • ns_type _isa;

  • 所有数列类型名称被放在一个名为ns_type的枚举类型（enumerated type）中。

  • nstype（）函数会检验其整数参数是否代表某一有效数列。如果参数有效，nstype（）就返回对应的enumerator（枚举项），否则返回ns_unset。这里用到的 static_cast 是个特殊转换记号，可将整数 num 转换为对应的 ns_type 枚举项。

  • static_cast< ns_type > (num);

  • nstype（）的结果再被我们传给set_sequence（）。于是，set_sequence（）将当前数列的_pfm、_isa、_elem等datamember设定妥当。

  • 为了让外界查询此对象目前究竟代表何种数列，我还提供了一个what_am_i（）操作函数，返回一个表示数列类型的字符串。what_am_i（）系利用_isa对一个静态字符串数组进行索引操作，此数组按照ns_type枚举项的顺序，列出本程序支持的所有数列名称。

  • const char* what_am_i() const { return names[_isa]; }

• 这么做当然极费功夫，尤其事后的维护更是工程浩大。每当我们希望加入或删除某个数列类型，以下所有事物都必须正确地予以更新：（1）“用以储存数列元素”的那些vector群聚而成的那个vector，（2） pointer to member function 所形成的数组，（3）what_am_i（）字符串数组，（4） set_sequence（）的switch语句，（5） num_seq的值，等等。面向对象编程模式消除了这种极为明显的编程负担，使我们的程序得以更精简，更具扩展性。

• 示例：

• 5.3：不使用继承，实现能支持多个数列的广义数列类num_sequence。

/* eg.5.3 Sequence class without inheritance. */ #include #include using namespace std; template ostream& operator<<(ostream& os, vector &vec) { for(int i = 0; i < vec.size(); i++) cout << vec[i] << ' '; return os; } class NumSequence { public: enum ns_type { ns_unset, ns_fibonacci, ns_pell, ns_lucas, ns_triangular, ns_square, ns_pentagonal }; typedef void (NumSequence::*PtrType) (int pos); static int num_of_sequence() { return num_seq; } static ns_type nstype( int i ) { return i <= 0 || i >= num_seq ? ns_unset : static_cast(i); } void set_sequence ( ns_type nt ) { _func_pointer = _func_tables[nt]; _seq_idx = nt; } void fibonacci (int n) { vector& vec = _elems[_seq_idx]; int m = vec.size(); for (int i = m + 1; i <= n; i++) { if (i < 3) vec.push_back(1); else vec.push_back(vec[i-2]+vec[i-3]); } } void pell (int n) { vector& vec = _elems[_seq_idx]; int m = vec.size(); for (int i = m + 1; i <= n; i++) { if (i == 1) vec.push_back(1); else if (i == 2) vec.push_back(2); else vec.push_back(2*vec[i-2]+vec[i-3]); } } void lucas (int n) { vector& vec = _elems[_seq_idx]; int m = vec.size(); for (int i = m + 1; i <= n; i++) { if (i == 1) vec.push_back(1); else if (i == 2) vec.push_back(3); else vec.push_back(vec[i-2]+vec[i-3]); } } void triangular (int n) { vector& vec = _elems[_seq_idx]; int m = vec.size(); for (int i = m + 1; i <= n; i++) vec.push_back(i * (i + 1) / 2); } void square (int n) { vector& vec = _elems[_seq_idx]; int m = vec.size(); for (int i = m + 1; i <= n; i++) vec.push_back(i * i); } void pentagonal (int n) { vector& vec = _elems[_seq_idx]; int m = vec.size(); for (int i = m + 1; i <= n; i++) vec.push_back(i * (3*n-1) / 2); } int elem( int pos ) { if (pos > _elems[_seq_idx].size()) (this->*_func_pointer)(pos); return _elems[_seq_idx][pos-1]; } private: PtrType _func_pointer; int _seq_idx; static const int num_seq = 7; static PtrType _func_tables[num_seq]; static vector<vector > _elems; }; NumSequence::PtrType NumSequence::_func_tables[num_seq] = { NULL, NumSequence::fibonacci, NumSequence::pell, NumSequence::lucas, NumSequence::triangular, NumSequence::square, NumSequence::pentagonal}; vector<vector > NumSequence::_elems(num_seq); int main(void) { NumSequence ns; const int pos = 8; for (int i = 1; i < NumSequence::num_of_sequence(); i++) { ns.set_sequence( NumSequence::nstype(i) ); int elem_val = ns.elem( pos ); cout << elem_val << endl; } return 0; }

*5.4 定义一个抽象基类

• 抽象基类：

• 共有接口：定义抽象类的第一个步骤就是找出所有子类共通的操作行为。这些操作行为所代表的便是num_sequence这个基类的公有接口（public interface）。

  • int elem(int pos);
    • void gen_elems(int pos);
    • bool check_integrity(int pos);
    • static int max_elems();

  • 虚函数：设计抽象基类的下一步，便是设法找出哪些操作行为与类型相关（type-dependent）——也就是说，有哪些操作行为必须根据不同的派生类而有不同的实现方式。这些操作行为应该成为整个类继承体系中的虚函数（virtual function）。注意，static member function无法被声明为虚拟函数。

  • 每个数列类都必须提供它们自己的gen_elems（）实现

  • 访问层级：设计抽象基类的第三步，便是试着找出每个操作行为的访问层级（accesslevel）。

  • public：如果某个操作行为应该让一般程序皆能访问，我们应该将它声明为public，例如elem（）、max_elems（）、what_am_i（）。

    • virtual ~NumSequence() {};
      • virtual int elem(int pos) const = 0;
      • virtual int max_elems() { return _max_elems; }

    • private：但如果某个操作行为在基类之外不需要被用到，我们就将它声明为private。即使是该基类的派生类，亦无法访问基类中的private member。本例的所有操作行为都必须给派生类使用，所以我们不能把它们声明为private。

    • protected：第三种访问层级，是所谓的 protected。这种层级的操作行为可让派生类访问，却不允许一般程序使用。例如 check_integrity（）和 gen_elems（）都是派生类必须调用的，却不是一般程序会用到的。

    • virtual void gen_elems(int pos) const = 0;
      • bool check_integrity(int pos) const;
      • const static int _max_elems = 1024;

  • 纯虚函数：每个虚函数，要么得有其定义，要么可设为“纯”虚函数（pure virtual function）——如果对于该类而言，这个虚函数并无实质意义的话，例如gen_elems（）之于num_sequence class。将虚函数赋值为0，意思便是令它为一个纯虚函数。

  • virtual void gen_elems(int pos) const = 0;
    • 任何类如果声明有一个（或多个）纯虚函数，那么，由于其接口的不完整性（纯虚函数没有函数定义，是谓不完整），程序无法为它产生任何对象。这种类只能作为派生类的子对象（sub object）使用，而且前提是这些派生类必须为所有虚函数提供确切的定义。

  • 抽象基类只是为“数列继承体系”提供一个接口；其派生类必须自行设计自身的data member。

  • 由于此类并没有任何non-static datamember需要进行初始化操作，所以其construtor亦无存在价值。不过我会为它设计destructor。是的，根据一般规则，凡基类定义有一个（或多个）虚函数，应该要将其destructor声明为virtual。

  • ps是基类num_sequence的指针，但它实际上指向派生类Fibonacci的对象。当delete表达式被应用于该指针，destructor会先应用于指针所指的对象身上，于是将此对象占用的内存空间归还给程序的空闲空间（free store）。还记得吗，non-virtual函数在编译时便已完成解析（resolved），根据该对象被调用时的类型来判断。于是，通过 ps调用的 destructor一定是 Fibonacci的 destructor，不是num_sequence的destructor。正确的情况应该是“根据实际对象的类型选择调用哪一个destructor”，而此解析操作应该在运行时进行。为了促成正确行为的发生，我们必须将destructor声明为virtual。

    • NumSequence *ps = new Fibonacci(12);

    • 但是我并不建议在我们的这个基类中将其destructor声明为pure virtual（纯虚函数）——虽然它其实不具有任何实质意义的实现内容。对这类destructor而言，最好是提供空白定义。

    • inline NumSequence::~NumSequence() {}

• 抽象基类的整个定义并不完全，它仅仅是为其派生类提供一个接口罢了。每个派生类还必须提供适当的实现细节，以补足基类的不足。

*5.5 定义一个派生类

• 派生类：派生类由两部分组成：一是基类构成的子对象（subobject），由基类的non-static data member——如果有的话——组成，二是派生类的部分（由派生类的non-static data member组成）。

• 继承：派生类的名称之后紧跟着冒号、关键字public，以及基类的名称。唯一的规则是，类进行继承声明之前，其基类的定义必须已经存在（这也就是必须先行包含含有 基类定义头文件的原因）。

• class Fibonacci : public NumSequence

• Fibonacci class必须为从基类继承而来的每个纯虚函数提供对应的实现。除此之外，它还必须声明Fibonacci class专属的member。

• Fibonacci(int len = 1, int beg_pos =1)
  • virtual int elem(int pos) const;
  • int length() const { return _length; }
  • int beg_pos() const { return _beg_pos; }
  • protected:
  • virtual void gen_elems(int pos) const;
  • int _length;
  • int _beg_pos;
  • static vector _elems;

• 每个派生类都有长度和起始位置这两项 data member。length（）和 beg_pos（）这两个函数被声明为 non-virtual，因为它们并无基类所提供的实体可供覆盖。但也因为它们并非基类提供的接口的一员，所以当我们通过基类的pointer或reference进行操作时，无法访问它们。

• ps->length(); // 错误，length并非基类接口
  • 如果“通过基类的接口无法访问length（）和beg_pos（）”会对我们造成困扰，那么我们应该回过头去修改基类的接口。重新设计的方式之一便是在基类num_sequence内加上两个纯虚函数length（）和beg_pos（）。这样一来便会“自动”造成派生类的beg_pos（）和length（）都成为虚拟函数——它们不需要再指定关键字 virtual。如果必须加上关键字 virtual，那么修改基类的虚拟函数（例如beg_pos（））就得大费周章：每个派生类都必须对它重新声明。
  • 另一种重新设计的方式是，将储存长度和起始位置的空间，由派生类抽离出来，移至基类。于是length（）和beg_pos（）都成了继承而来的inline non virtual function。5.6节会讨论这种设计方式的一个变形。

• 当我们面临“萃取基类和派生类之间的性质，以决定哪些东西（包括接口和实际成员）属于谁”时，面向对象设计所面对的挑战，将不只是编程层面而已。一般而言，这是一个不断迭代的过程，过程之中借着程序员的经验和用户的反馈，不断演进。

• 派生类的虚函数必须精确吻合基类中的函数原型。在类之外对虚函数进行定义时，不必指明关键字virtual。

• 请注意，elem（）调用继承来的check_integrity（），其形式仿佛后者为其自身成员一般。一般来说，继承而来的public成员和protected成员，不论在继承体系中的深度如何，都可被视为派生类自身拥有的成员。

  • int elem(int pos) const { if(pos > _elems.size()) Fibonacci::gen_elems(pos); return _elems[pos-1]; }

  • 基类的public member在派生类中同样也是public，同样开放给派生类的用户使用。基类的protected member在派生类中同样也是protected，同样只能给后续的派生类使用，无法给目前这个派生类的用户使用。

  • 至于基类的private member，则完全无法让派生类使用（遑论派生类的用户）。（以上讨论仅限于public inheritance（公有继承）的情况。如果是protected inheritance或privateinheritance，情况就不一样了。

  • elem（）会调用 gen_elems（），计算必要的元素并填入_elems。这个操作必须写成 Fibonacci：：gen_elems（pos），不能只是简单地写gen_elems（pos）。在elem（）内，我们清楚地知道我们想调用的究竟是哪一个gen_elems（）。不必等到运行时才进行gen_elems（）的解析操作。事实上，我们希望跳过虚函数机制，使该函数在编译时就完成解析，不必等到运行时才解析。这就是我们指明调用对象的原因。通过class scope运算符，我们可以明确告诉编译器，我们想调用哪一份函数实例。于是，运行时发生的虚拟机制便被遮掩了。

• 每当派生类有某个member与其基类的member同名，便会遮掩住基类的那份member。也就是说，派生类内对该名称的任何使用，都会被解析为该派生类自身的那份member，而非继承来的那份member。这种情况下，如果要在派生类内使用继承来的那份member，必须利用class scope运算符加以限定。

• elem（）和 print（）都会检查_elems 存有的元素是否足够，并且在元素个数不足时调用gen_elems（）加以补足。我们该如何修改check_integrity（）以使这个检验操作的确能检验出pos的有效性呢？

  • 这种解决方法带来的问题是，在基类中check_integrity（）并未被视为虚函数。于是，每次通过基类的pointer或reference来调用check_integrity（），解析出来的都是num_sequence的那一份，未考虑到pointer或reference实际指向的究竟是什么对象。

  • inline bool Fibonacci::check_integrity(int pos) const { if(! NumSeq::check_integrity(pos)) return false; }

  • 基于这个原因，一般而言，在基类和派生类中提供同名的non-virtual函数，并不是好的解决办法。基于此点而归纳出来的结论或许是：基类中的所有函数都应该被声明为 virtual。我不认为这是个正确的结论，但它的确可以马上解决我们所面临的两难困境。

  • 造成这种两难困境的深层原因是，当派生类欲检查其自身状态的完整性时，已实现完成的基类缺乏足够的知识。而我们知道，根据不完整信息所完成的实现，可能也是不完整的。这和“宣称实现与类型相关，因而必须将它声明为virtual”的情形并不相同。

  • 我再重复一次，我认为，所谓设计，必须来来回回地借着程序员的经验和用户的反馈演进。本例中，较好的解决方案是重新定义check_integrity（），令它拥有两个参数。

  • bool NumSeq::check_integrity(int pos, int size) { if (pos > size) gen_elems(pos); }

  • 在这个check_integrity（）版本中，gen_elems（）通过虚拟机制被调用。如果check_integrity（）是由Fibonacci对象调用，那么后续就会调用Fibonacci的gen_elems（）。

  • int Fibonacci::elem( int pos ) { if (!check_integrity(pos, _elems.size()); return 0; }

• 逐步测试自己的实现代码，比整个程序都完成后才测试好多了。这不仅可以让我们更稳健地检查我们所完成的内容，更可以提供一整套回归测试的基准，使我们得以继续演进并改进原本的设计。

• 示例：

• 5.5：实现一个NumSequence数列基类和Fibonacci数列派生类。

/* Eg.5.5 Implement a NumSeq base class and Fibonacci derived class. */ # include # include # include using namespace std; class NumSeq { public: virtual ~NumSeq() {}; int length() { return _length; } int beg_pos() { return _beg_pos; } virtual int elem(int pos) = 0; protected: int _length; int _beg_pos; virtual void gen_elems(int pos) = 0; }; class Fibonacci : public NumSeq { public: Fibonacci(int len = 1, int beg_pos = 1) { _length = len; _beg_pos = beg_pos; } virtual ~Fibonacci() {} virtual int elem(int pos) { if (pos > _elems.size()) gen_elems(pos); return _elems[pos-1]; } protected: static vector _elems; virtual void gen_elems(int pos) { int m = _elems.size(), i; for (i = m + 1; i <= pos; i++) { if (i == 1) _elems.push_back(1); else if (i == 2) _elems.push_back(1); else _elems.push_back(_elems[i-2] + _elems[i-3]); } } }; vector Fibonacci::_elems; class Triangular : public NumSeq { public: Triangular(int len = 1, int beg_pos = 1) { _length = len; _beg_pos = beg_pos; } virtual ~Triangular() {} virtual int elem(int pos) { if (pos > _elems.size()) gen_elems(pos); return _elems[pos-1]; } protected: static vector _elems; virtual void gen_elems(int pos) { int m = _elems.size(), i; for (i = m + 1; i <= pos; i++) _elems.push_back(i * (i + 1) / 2); } }; vector Triangular::_elems; ostream& operator<<(ostream& os, NumSeq &ns) { int i = 0; int m = ns.beg_pos(), n = ns.length(); for (i = m; i < m + n; i++) os << ns.elem(i) << ' '; return os; } int main(void) { Fibonacci fib(16); cout << fib << endl; Fibonacci fib2(8, 12); cout << fib2 << endl; Triangular tri(12); cout << tri << endl; return 0; }

5.6 运用继承体系

• 继承体系：假定我们已经顺利地以定义Fibonacci class的方式定义出其他五种数列类（Pell，Lucas，Square，Triangular和Pentagonal）。现在，我们有了一个两层的继承体系，其中包括抽象基类num_sequence，以及六个派生类。

• 在display（）函数中，我调用了两个虚拟函数：what_am_i（）和elem（）。ns并非指向实际的num_sequence对象，而是指向num_sequence的某个派生类的对象。对上述两个虚函数的调用操作，会在运行时依据ns所指对象的真实类型进行解析。

  • inline void display(NumSeq &ns, int pos) { cout « ns.elem(pos) « endl; }

  • 我为每个派生类各自定义了一个对象，传给了display（）。这个程序的输出结果和稍早4.11节的程序输出结果相同。但是此刻num_sequence的设计却已改头换面。先前设计中的许多用来设定、记录、重新设定数列类型的机制，如今都已移除；程序语言通过继承和虚函数等机制，默默为我们提供了这些功能。面向对象设计大大简化了修改和扩展的负担。和先前的设计比起来，现在要加入一个新的数列类，或是移除一个既有的数列类，再也不需要大费周章。

  • 我们的基类num_sequence，曾经对output运算符做了重载操作。由于print（）是个虚函数，所以output运算符能够针对每个派生类工作无误。我为每个数列类各自定义了一个对象，并一一交给output运算符。

  • ostream& operator«(ostream &os, NumSeq &ns) { return ns.print(os); }

    • Fibonacci fib(8); cout « fib « endl;

5.7 基类应该多么抽象

• 基类的抽象：

• 抽象基类提供的是接口，并未提供任何实现。每个派生类不仅必须提供本身专属的元素产生算法，还必须支持特定元素的搜索、元素的打印、数列长度和起始位置的维护等任务。如果抽象基类的设计者，同时提供了一些派生类，而且他预期不会常有其他派生类需要加入此继承体系内，那么这样的设计可以顺畅工作。但是如果时常需要加入新的数列类，而且这类工作还外包给数学能力甚于编程能力的程序员，那么这样的设计反而会使派生类的加入工作变得更为复杂。

  • 另一个设计方式，将所有派生类共有的实现内容剥离出来，移至基类内。接口依旧没有变动，这样的设计简化了我们为提供派生类而必须付出的努力。

  • 重新改版后的num_sequence定义。两个data member_length和_beg_pos现在都提升至 num_sequence的层次了。我将它们声明为protected，让派生类可以直接访问它们。它们的访问函数——length（）和beg_pos（）——现在也都提升到了num_sequence的层次。我将它们声明为public，以便一般程序都能够读取上述两个值。

  • int length() const { return _length; }
    • int _length;

  • 有一个新的data member被加入num_sequence类内：_relems是个reference toint vector，用来指向派生类中的某个static vector。如我在2.3节所说，reference永远无法代表空对象（null object），pointer却有可能是null。让它成为reference，我们就再也不必检查它是否为null了。

  • vector &_relems;

  • Data member如果是个reference，必须在constructor的member initialization list中加以初始化。一旦初始化，就再也无法指向另一个对象。如果 data member 是个pointer，就无此限制：我们可以在constructor 内加以初始化，也可以先将它初始化为 null，稍后再令它指向某个有效的内存地址。程序设计过程中我们便是根据这些不同的性质来决定要使用reference或pointer。

  • NumSeq(int len, int bp, vector &re): _length(len), _beg_pos(bp), _relems(re) {}

  • 基类现在具备了所有必要信息，可在数列中进行元素的搜索和显示。这使我们得以重新定义elem（）和print（），使它们成为num_sequence的public member。虽然num_sequence依然是个抽象基类，但现在它提供了一些实现内容，可供各派生类继承。

  • int elem(int pos) const;

• 派生类：现在，每个派生数列类只需编写自身独特的部分即可，其中包括：数列元素产生器gen_elems（）、识别数列类型的what_am_i（）、储存数列元素的static vector，以及constructor。派生的数列类继承了元素搜索函数、元素打印函数、长度和起始位置的维护函数。

• 示例：

• 5.7：对基类NumSeq进行进一步抽象，使其支持length()和elem()成员函数。

/* Eg.5.5 Implement a NumSeq base class and Fibonacci derived class. */ # include # include # include using namespace std; class NumSeq { public: virtual ~NumSeq() {}; int length() { return _length; } int beg_pos() { return _beg_pos; } int elem(int pos) { if (pos > _relems.size()) gen_elems(pos); return _relems[pos-1]; } protected: NumSeq(int len, int bp, vector &re): _length(len), _beg_pos(bp), _relems(re) {} int _length; int _beg_pos; virtual void gen_elems(int pos) = 0; vector &_relems; }; class Fibonacci : public NumSeq { public: Fibonacci(int len = 1, int beg_pos = 1): NumSeq(len, beg_pos, _elems) {} virtual ~Fibonacci() {} protected: static vector _elems; virtual void gen_elems(int pos) { int m = _elems.size(), i; for (i = m + 1; i <= pos; i++) { if (i == 1) _elems.push_back(1); else if (i == 2) _elems.push_back(1); else _elems.push_back(_elems[i-2] + _elems[i-3]); } } }; vector Fibonacci::_elems; ostream& operator<<(ostream& os, NumSeq &ns) { int i = 0; int m = ns.beg_pos(), n = ns.length(); for (i = m; i < m + n; i++) os << ns.elem(i) << ' '; return os; } int main(void) { Fibonacci fib(16); cout << fib << endl; Fibonacci fib2(8, 12); cout << fib2 << endl; return 0; }

*5.8 初始化、析构、复制

• 初始化：

• 基类初始化：如今的num_sequence具有实际的data member，我必须为它们提供初始化行为。我可以将初始化操作留给每个派生类，但这么做会有潜在的危机。较好的设计方式是，为基类提供 constructor，并利用这个constructor处理基类所声明的所有data member的初始化操作。

  • num_sequence乃是一个抽象基类，我们无法为它定义任何对象。num_sequence扮演的角色是每个派生类对象的子对象（sub object）。基于这个原因，我将基类的constructor声明为protected而非public。

  • 派生类初始化：派生类对象的初始化行为，包含调用其基类的constructor，然后再调用派生类自己的constructor。派生类对象之中其实含有多个子对象：由基类constructor初始化的“基类子对象”，以及由派生类 constructor 所初始化的“派生类子对象”。5.1 节的三层类体系中的AudioBook，其对象便包含三个子对象，分别由对应的constructor加以初始化。

  • 派生类的构造函数：派生类的constructor，不仅必须为派生类的data member进行初始化操作，还需要为其基类的data member提供适当的值。本例中，基类num_sequence需要三个值，都需要通过member initialization list传入。

  • Fibonacci(int len, int beg_pos): NumSeq(len, beg_pos, _elems) {}
    • 如果我们忽略了上述对num_sequence constructor的调用操作，这一份Fibonacciconstructor定义就会被编译器视为错误。因为基类num_sequence要求我们明确指定调用哪一个constructor （本例为具有三个参数者）。

  • 基类的默认构造函数：另一个做法是，为num_sequence提供default constructor。不过，我们必须将_relems改为指针，并且在每次访问vector内容前，都检验这个指针是否不为null。现在，如果派生类的constructor未能明确指出调用基类的哪一个constructor，编译器便会自动调用基类的default constructor。

  • NumSeq(int len=1, int bp=1, vector *pe=0): _length(len), _beg_pos(bp), _pelems(pe) {}

  • 复制构造函数：当我们以某个Fibonacci对象作为另一个Fibonacci对象的初值时，如果我们为Fibonacci定义了一个copy constructor，以上便会调用该copy constructor。

  • Fibonacci(const Fibonacci &rhs): NumSeq(rhs) {}
    • 其中rhs代表等号右边的派生类对象，它在member initialization list中被传给基类的copy constructor。如果基类未自行定义 copy constructor，那又会发生什么事呢？不会太糟，因为 default memberwise initialization程序会起来执行。而如果我们为基类定义了copy constructor，它便会被调用。
    • 本例并不需要另行定义 Fibonacci 的 copy constructor，因为默认行为便能够达到同等效果：首先，基类子对象会被逐一初始化，然后派生类的member亦会被逐一初始化。

• 复制赋值运算符：Copy assignment operator的情形也一样。如果我们将某个Fibonacci对象赋值（assign）给另一个Fibonacci对象，而且Fibonacci class拥有明确定义的copy assignment operator，它便会在赋值操作发生时被调用。

• 同样地，本例其实不必为Fibonacci另行定义copy assignment operator，因为其默认行为已能达到同样效果。请回头看看 4.2 节和 4.8 节的讨论，便可了解何时才是提供 copy constructor 和 copy assignment operator的必要时机。

  • Fibonacci& operator=(const Fibonacci &rhs) { NumSeq::operator=(rhs); return *this; }

• 析构函数：基类的destructor会在派生类的destructor结束之后被自动调用。我们无须在派生类中对它做明确的调用操作。

*5.9 在派生类中定义一个虚函数

• 虚函数：

• 当我们定义派生类时，我们必须决定，究竟要将基类中的虚函数覆盖掉，还是原封不动地加以继承。如果我们继承了纯虚函数（pure virtual function），那么这个派生类也会被视为抽象类，也就无法为它定义任何对象。

  • 虚函数原型：如果我们决定覆盖基类所提供的虚函数，那么派生类提供的新定义，其函数原型必须完全符合基类所声明的函数原型，包括：参数列表、返回类型、常量性（const-ness）。

  • virtual const char* what_am_i() const { return “Fibonacci”; }

  • 先前的警告信息便是告诉我们，派生类所提供的函数，并未被用来覆盖基类所提供的同名函数，原因是两个函数并非完全吻合。这是初学者常犯的一种错误，而且很难察觉。这也就是我要花这么多时间加以解释的原因。虽然修正方法很简单；但是理解它则需费一番工夫。

  • “返回类型必须完全吻合”这一规则有个例外——当基类的虚函数返回某个基类形式（通常是pointer或reference）时。派生类中的同名函数便可以返回该基类所派生出来的类型。

  • virtual NumSeq *clone() = 0;
    • Fibonacci clone() { return new Fibonacci(this); }
  • 当我们在派生类中，为了覆盖基类的某个虚函数，而进行声明操作时，不一定得加上关键字virtual。编译器会依据两个函数的原型声明，决定某个函数是否会覆盖其基类中的同名函数。

• 虚函数的静态解析（Static Resolution）：

• 有两种情况，虚函数机制不会出现预期行为：

  • （1） 基类的constructor和destructor内
    • （2） 当我们使用的是基类的对象，而非基类对象的pointer或reference时。

  • 构造/析构函数内：当我们构造派生类对象时，基类的constructor会先被调用。如果在基类的construtor中调用某个虚函数，问题出在此刻派生类中的 data member 尚未初始化。如果此时调用派生类的那一份虚函数，它便有可能访问未经初始化的data member，这可不是一件好事。基于这个原因，在基类的 constructor中，派生类的虚函数绝对不会被调用。

  • 例如num_sequence constructor 内如果调用 what_am_i（），无论如何一定会被解析为num_sequence 自身的那一份what_am_i（）。
    • 如果在基类的destructor中调用虚函数，此规则同样成立。

  • 使用基类对象而非引用：为了能够“在单一对象中展现多种类型”，多态（polymorphism）需要一层间接性。在C++中，唯有用基类的pointer和reference才能够支持面向对象编程概念。

  • 当我们为基类声明一个实际对象（例如print（）的第一参数），同时也就分配出了足以容纳该实际对象的内存空间。如果稍后传入的却是个派生类对象，那就没有足够的内存放置派生类中的各个 data member。

    • void print(LibMat obj, const LibMat &ref) { obj.print(); } // 静态解析

    • 只有iWish内的“基类子对象（也就是属于LibMat的成分）”被复制到“为参数object而保留的内存”中。其他的子对象（Book成分和AudioBook成分）则被切掉（sliced off）了。至于另两个参数，pointer 和 reference，则被初始化为 iWish 对象所在的内存地址。这就是它们能够指向完整的AudioBook对象的原因。

    • AudioBook ab(“Snow White”); print(ab, ab);

5.10 运行时的类型鉴定机制

• 每个类都拥有一份what_am_i（）函数，都返回一个足以代表该类的字符串。另一种设计手法，便是只提供唯一的一份what_am_i（），令各派生类通过继承机制加以复用。这种设计手法可使各派生类不必再提供各自的what_am_i（）。

• 这种设计的一种可能做法，就是为num_sequence增加一个string member，并令每一个派生类的constructor都将自己的类名作为参数，传给num_sequence的constructor。

  • Fibonacci(int len, int beg_pos): NumSeq(len, beg_pos, _elems, “Fibonacci”) {}

  • 运行时类型鉴定机制：另一种实现便是利用所谓的 typeid 运算符，这是所谓运行时类型鉴定机制（Run-Time Type Identification，RTTI）的一部分，由程序语言支持。它让我们得以查询多态化的 class pointer 或 class reference，获得其所指对象的实际类型。

  • #include

    • const char* what_am_i() const { return typeid(*this).name(); }

• typeid：使用 typeid运算符之前，必须先包含头文件 typeinfo。typeid运算符会返回一个type_info对象，其中储存着与类型相关的种种信息。每一个多态类（polymorphic class），如Fibonacci、Pell，等等，都对应一个type_info对象，该对象的name（）函数会返回一个const char＊，用以表示类名。

• type_info对象，关联至“who_am_i（）函数之中由this指针所指对象”的实际类型。

  • type_info class也支持相等和不等两个比较操作。

  • NumSeq *ps = &fib;

    • if ( typeid(*ps) == typeid(Fibonacci) )

• static_cast运算符：ps并不“知道”它所指向的对象实际上是什么类型——纵使我们知道，typeid及虚函数机制也知道。为了调用 Fibonacci 所定义的 gen_elems（），我们必须指示编译器，将 ps 的类型转换为Fibonacci指针。static_cast运算符可以担起这项任务，进行无条件类型转换。

• static_cast其实有潜在危险，因为编译器无法确认我们所进行的转换操作是否完全正确。这也就是我要把它安排在“typeid运算符的运算结果为真”的条件下的原因。

  • if ( typeid(*ps) == typeid(Fibonacci) ) Fibonacci *pf = static_cast(ps);

• dynamic_cast运算符：dynamic_cast运算符就不同，它提供有条件的转换。dynamic_cast 也是一个 RTTI 运算符，它会进行运行时检验操作，检验 ps 所指对象是否属于Fibonacci类。如果是，转换操作便会发生，于是pf便指向该Fibonacci对象。如果不是，dynamic_cast运算符返回0。

• 一旦 if语句中的条件不成立，那么对Fibonacci的 gen_elems（）所进行的静态调用操作也不会发生。

  • if ( Fibonacci *pf = dynamic_cast(ps) ) pf->gen_elems(64);

• 拓展：

• 如果你想对C++的运行时类型鉴定机制（RTTI）有更多了解，请参阅[LIPPMAN98]的19.1节。
  • 基类可以public、protected或private三种方式继承而来。本书仅讨论public继承方式，如果想对其他两种继承方式有更多了解，请参阅[LIPPMAN98]的18.3节。
  • 甚至还有多重继承和虚继承。这些都是比较复杂而高级的主题，本书并不涵盖。[LIPPMAN98]第18章对它们有完整的讨论。

• 练习：

• 5.2：实现一个基类Stack，和两个派生类LifoStack和PeekbackStack。

/* 5.2 Implement a stack hierarchy with base class Stack and derived classes LifoStack and PeekbackStack. */ # include # include # include using namespace std; typedef string T; class Stack { public: virtual ~Stack() {} void pop() { if (!empty()) _stack.pop_back(); } bool empty() { return _stack.empty(); } void push(T &x) { if (!full()) _stack.push_back(x); } bool full() { return _stack.size() >= _stack.max_size(); } int size() { return _stack.size(); } virtual T peek() { return "null"; } virtual T peek(int idx) { return "null"; } void print(ostream &os = cout) { for (int i = 0; i < _stack.size(); i++) os << _stack[i] << ' '; } protected: vector _stack; }; class LifoStack : public Stack { public: virtual ~LifoStack() {} virtual T peek() { if (empty()) return "null"; return _stack[size()-1]; } }; class PeekbackStack : public Stack { public: virtual ~PeekbackStack() {} virtual T peek(int idx) { if (idx < 0 || idx >= size()) return "null"; return _stack[idx]; } }; ostream& operator<<(ostream& os, Stack &st) { st.print(os); return os; } int main(void) { string arr[4] = {"once", "upon", "a", "time"}; LifoStack st; string str; for (int i = 0; i < 4; i++) st.push(arr[i]); cout << st << endl; PeekbackStack pst; while (!st.empty()) { str = st.peek(); cout << str << ' '; st.pop(); pst.push(str); } cout << endl; cout << pst << endl; return 0; }

6 以template进行编程

• 参数化的类型：Bjarne Stroustrup（C++创造者）拟好C++语言中关于template的原始设计后，将template称为被参数化的类型（parameterized type）：称其参数化是因为，类型相关信息可自template定义中剥离，称其类型则是因为，每一个class template或function template基本上都随着它所作用或它所内含的类型而有性质上的变化（因此这些class template或function template本身就像是某种类型）。template所接受（或说作用于其上）的类型，系由template用户于使用时指定。

• 模板：其后不久，Stroustrup将名称改为比较通俗顺口的template（模板）。Template定义扮演的乃是“处方”角色，能根据用户指定的特定值或特定类型，自动产生一个函数或类。

• 二叉树类模板：

• 本章的任务之一，带你一览二叉树（binary tree）class template的所有实现过程。

  • 二叉树：所谓树（tree）乃是由节点（node，或谓 vertice）以及连接不同节点的链接（link）组成。所谓二叉树，维护着每个节点与下层另两个节点间的两条链接，一般将此下层二节点称为左子节点（left child）和右子节点（right child）。最上层第一个节点称为根节点（root）。无论是左子节点或右子节点，都可能扮演另一棵“子树（subtree）”的根节点。一个节点如果不再有任何子节点，便称为叶节点（leaf）。
  • 我们的二叉树包含两个 class：一个是 BinaryTree，用以储存一个指针，指向根节点，另一个是BTnode，用来储存节点实值，以及连接至左、右两个子节点的链接。此处，“节点实值的类型（value type）”正是我们希望加以参数化的部分。
  • BinaryTree类该提供的操作行为呢：用户必须能够将元素插入（insert）到BinaryTree，必须能够从BinaryTree移除（remove）特定元素，也必须能够在树中搜寻（find）某个元素、清除（clear）所有元素、以特定的遍历方式打印（print）整棵树。我们必须支持三种遍历方式：中序（inorder）、前序（preorder）、后序（postorder）。
  • 插入：第一个插入空树（empty tree）的值，会成为此树的根节点。接下来的每个节点都必须以特定规则插入：如果小于根节点，就被置于左子树，如果大于根节点，就被置于右子树。任何一个值只能在树中出现一次，但是此树有能力记录同一值的插入次数。
  • 任何遍历算法（traversal algorithm）皆由根节点出发。所谓前序（preorder）遍历，是指被遍历的节点本身先被打印；然后才打印左子树内容，再往后才轮到右子树内容。所谓中序（inorder）遍历，是先打印出左子树，然后是节点本身，最后才轮到右子树。所谓后序（postorder）遍历，则是先打印左子树，再打印右子树，最后才是节点本身。

*6.1 被参数化的类型

• 模板机制：由于缺乏template机制，为了储存不同类型的数值，我必须为它们实现各种不同的BTnode类，并且取不同的名称。template机制帮助我们将类定义中“与类型相关（type-dependent）”和“独立于类型之外”的两部分分离开来。

• 定义类模板：

• 遍历二叉树、插入/移除节点、维护重复次数等行为，并不会随着处理的类型不同而有所不同，因此这些程序代码可以在“通过class template产生出来的所有class”中使用。

  • class template所产生出来的各个class，其实值类型都有可能不同：可能是string，也可能是int或double等。在一个class template中，与类型相关的部分会被抽取出来，成为一个或多个参数。以BTnode class为例，data member_val的类型便可被参数化。

  • template class TreeNode {
    • public: friend class BinaryTree;
    • private: T _val; int _cnt; TreeNode *_left; TreeNode *_right;

  • 在此class template定义中，valType被拿来当作一个占位符。其名称可以任意设定。在用户为它指定某个特定类型之前，它被视为一个可取代为任意类型的东西。是的，类型参数（type parameter）可以被拿来用在实际类型（诸如int、string）的使用场合。在BTnode class中，我们拿它来声明_val所属类型。

  • 在我的实现中，BTnode class template必须和BinaryTree class template配合使用。BTnode储存了节点实值、节点实值的重复次数、左右子节点的指针。针对每一种 BTnode实际类型，我们希望对应的BinaryTree实例能够成为其 friend。

  • BinaryTree class仅声明一笔数据：一个BTnode指针，指向二叉树根节点。什么情形下需要以template parameter list进一步限定class template呢？一般规则是，在class template及其member的定义中，不必如此。除此之外的其他场合就需要以parameter list加以限定。

  • template class BinaryTree {
    • private: TreeNode *_root; // BTnode必须以template parameter list加以限定

• 使用类模板：

• 为了通过class template实例化类，我们必须在class template名称之后，紧接一个尖括号，其内放置一个实际类型（准备用来取代valType）。

  • TreeNode node;

  • 当我们指定某个实际类型作为BinaryTree的参数，指针_root便指向一个“节点值类型为string”的BTnode。

  • BinaryTree tree;

6.2 Class Template的定义

• 定义类模板：

• 为class template定义一个inline函数，其做法就像为non-template class定义一个inline函数一样。但是，在类体外，class template member function的定义语法却大相径庭。

  • BinaryTree& operator=( const BinaryTree& rhs);
    • template inline BinaryTree::BinaryTree(): _root(0) {}

  • 这个member function的定义始于关键字template和一个参数列表，然后便是函数定义本身，并带有关键字inline及class scope运算符。inline一词必须紧接在关键字template和参数列表之后。在 class scope运算符出现之后，其后所有东西都被视为位于class定义范围内。第二次出现的 BinaryTree便被视为class定义范围内，所以不需要再加以限定。

  • template inline BinaryTree::BinaryTree( const BinaryTree &rhs ) { copy(_root, rhs._root); }
    • template inline BinaryTree::~BinaryTree() { clear(); }
    • template inline BinaryTree& BinaryTree::operator=( const BinaryTree &rhs ) { if (this != &rhs) { clear(); copy(_root, rhs._root); } return *this; }

6.3 Template类型参数的处理

• 模板类型参数：处理一个“template类型参数”比处理一个“明确的类型参数”复杂一些。

• 明确的类型参数：函数类型参数以传值（by value）方式进行参数的传递。如果声明Matrix class为函数的参数，我们可能会改以传址（by reference）方式传递，这可避免因Matrix对象的复制而造成的不必要开销。

  • bool find( Matrix &mat );

  • 模板类型参数：当我们处理template类型参数时，我们无法得知用户实际要用的类型是否为语言内置类型。实际运用中，不论内置类型或class类型，都可能被指定为class template的实际类型。我建议，将所有的template类型参数视为“class类型”来处理。这意味着我们会把它声明为一个const reference，而非以by value方式传递。

  • 但如果它是一个class类型，就应该以by reference方式来编写find（）的参数列表。

  • 在constructor定义中，我选择在member initialization list内为每个类型参数进行初始化操作。而不选择在constructor函数体内进行，因为它可能是class类型。这么一来，当用户为valType指定一个class类型时，可以保证效率最佳。

  • template inline TreeNode::TreeNode( const T &val ): _val(val) { _cnt=1; _left=_right=0; }
    • TreeNode node(mat);

  • constructor函数体内对_val的赋值操作可分解为两个步骤：（1） 函数体执行前，Matrix 的 default constructor 会先作用于_val 身上；（2） 函数体内会以 copy assignment opreator将 val复制给_val。但如果我们采用上述第一种方法，在 constructor的 member initialization list中将_val初始化，那么只需一个步骤就能完成工作：以copy constructor将val复制给_val。

  • 不论我们是以传值方式来传递valType，或是在constructor函数体内为类型为valType的data member设置值，都没有错。但是这会花费较多的时间，而且可能使你背负“不谙C++编程技巧”的污名。如果你才刚开始学习C++，其实无须过度关心效率方面的议题。然而指出这两种情形的差异，却是十分有用。

*6.4 实现一个 Class Template

• 插入insert：每当我们插入某个新值，都必须建立BTnode对象、加以初始化、将它链接至二叉树的某处。我们必须自行以new表达式和delete表达式来管理每个节点的内存分配和释放。

• BinaryTree::insert：以insert（）为例，如果根节点之值尚未设定，它会由程序的空闲空间（freestore）分配一块新的BTnode需要的内存空间。否则就调用BTnode的insert_value（），将新值插入二叉树中。

  • void insert(const T &elem) { if (!_root) _root = new BTnode(elem); else _root->insert_value(elem); }

  • new表达式：new表达式可分解为两个操作：（1） 向程序的空闲空间（free store）请求内存。如果分配到足够的空间，就返回一个指针，指向新对象。（如果空间不足，会抛出bad_alloc异常。第7章会讨论C++的异常处理机制。）（2） 如果第一步成功，并且外界指定了一个初值，这个新对象便会以最适当的方式被初始化。对class类型来说：elem会被传入BTnode constructor。如果分配失败，初始化操作就不会发生。

  • TreeNode::insert_value：当根节点存在时，insert_value（）才会被调用。小于根节点的所有数值都放在根节点的左子树，大于根节点的所有数值都放在根节点的右子树。insert_value（）会通过左右子节点递归（recursively）调用自己，直到以下任何一种情形发生才停止：（1） 合乎资格的子树并不存在，（2） 欲插入的数值已在树中。由于每个数值只能在树中出现一次，所以我以BTnode的data member_cnt来记录这个节点的插入次数。

  • void insert_value(const T &val)

• 删除remove：移除某值的操作更为复杂，因为我们必须保持二叉树的次序不变。一般的算法是，以节点的右子节点取代节点本身，然后搬移左子节点，使它成为右子节点的左子树的叶节点。如果此刻并无右子节点，那么就以左子节点取代节点本身。

• BinaryTree::remove：无论 remove_root（）或 remove_value（），都会搬移左子节点，使它成为右子节点的左子树的叶节点。我将这一操作剥离至lchild_leaf（），那是BTnode的static member function。

  • void remove(const T &elem) { if (_root) if (_root->val == elem) remove_root(); else _root->remove_value(elem, _root); }
    • void lchild_leaf(TreeNode *leaf, TreeNode *sub) { while (sub->_left) sub=sub->_left; sub->_left = leaf; }

  • TreeNode::remove_root：根节点的移除。如果根节点拥有任何子节点，remove_root（）就会重设根节点。如果右子节点存在，就以右子节点取而代之；如果左子节点存在，就直接搬移，或通过lchild_leaf（）完成。如果右子节点为null，_root便以左子节点取代。

  • void remove_root()

  • TreeNode::remove_value：remove_value（）拥有两个参数：将被删除的值（如果存在的话）以及一个指针，指向目前关注的节点的父节点。

  • void remove_value(const T &val, TreeNode* &prev)
    • remove_value（）的参数列表告诉我们，两个参数皆以传址（by reference）方式传递，这是为了避免“当valType被指定为class类型时，因传值（by value）而产生的昂贵复制开销”。由于我们并不会改变val的值，所以将它限定为const。
    • 第二个参数就不那么直观了。为什么我们将prev以一个reference to pointer来传递呢？难道用单纯的pointer传递还不够吗？是的，不够！以pointer来传递，我们能够更改的是该pointer所指之物，而不是pointer本身。为了改变pointer本身，我们必须再加一层间接性。如果将prev声明为reference to pointer，我们不但可以改变pointer本身，也可以改变由此pointer指向的对象。

• 清除clear：我们还需要另一个函数来移除整棵二叉树。我把这个名为clear（）的函数分为两份：一个是inline public函数，另一个是前者的重载版本，用以执行实际工作，并放在private部分。

• void clear() { if (_root) { clear(_root); _root=0; } }
  • void clear(TreeNode *node) { if(node) {clear(node->_left); clear(node->_right); delete node;} }

• 遍历：不论哪一种遍历算法（traversal algorithm）——preorder（）或inorder（）或postorder（），都会作用于当前节点上（在我们的例子中就是_val），并递归作用于左子节点和右子节点。三个算法的差别仅在于三个操作的执行顺序。

• 先序遍历：TreeNode::preorder

  • void preorder(TreeNode *node, ostream &os) const

• 示例：

• 6.4：实现一个二叉树类模板，支持插入insert、移除remove、清除clear、遍历traverse等操作。

/* Eg.6.4 Implement a binary tree class template with insert, remove, clear and traverse operation. */ # include # include # include using namespace std; template class BinaryTree; template class TreeNode { public: friend class BinaryTree; TreeNode(T &val): _val(val), _cnt(0), _left(NULL), _right(NULL) {} private: T _val; int _cnt; TreeNode *_left; TreeNode *_right; }; template class BinaryTree { public: BinaryTree(): _root(NULL) {} ~BinaryTree() { clear(); } void insert(T &elem) { insert(_root, elem); } void preorder(ostream &os = cout) { preorder(_root, os); } void clear() { clear(_root); } void remove(T &elem) { remove(_root, elem); } private: TreeNode *_root; void preorder(TreeNode *node, ostream &os) { if (node == NULL) return; cout << node->_val << ' '; preorder(node->_left, os); preorder(node->_right, os); } void insert(TreeNode* &node, T &elem) { if (node == NULL) { node = new TreeNode(elem); return; } if (elem == node->_val) (node->_cnt)++; else if (elem < node->_val) insert(node->_left, elem); else insert(node->_right, elem); } void clear(TreeNode* &node) { if (node == NULL) return; clear(node->_left); clear(node->_right); delete node; } void remove(TreeNode* &node, T &elem) { if (node == NULL) return; if (node->_val == elem) { TreeNode *tmp = node; node = lchild_leaf(node->_left, node->_right); delete tmp; } else if (elem < node->_val) remove(node->_left, elem); else remove(node->_right, elem); } TreeNode* lchild_leaf(TreeNode* leaf, TreeNode* sub) { if (sub == NULL) return leaf; if (leaf == NULL) return sub; TreeNode *p = sub; while (p->_left != NULL) p = p->_left; p->_left = leaf; return sub; } }; int main(void) { string arr[7] = {"Piglet", "Eeyore", "Roo", "Tigger", "Chris", "Pooh", "Kanga"}; BinaryTree tree; for (int i = 0; i < 7; i++) tree.insert(arr[i]); tree.preorder(); cout << endl; tree.remove(arr[0]); tree.preorder(); cout << endl; tree.remove(arr[1]); tree.preorder(); cout << endl; return 0; }

6.5 一个以Function Template完成的Output运算符

• 输出运算符：为我们的BinaryTree class template提供一个output运算符。

• 比较好的解法是，将output运算符定义为一个function template：

  • template ostream& operator«(ostream &os, const BinaryTree &tree)
    • tree.print(os); return os;

  • print（）乃是BinaryTree class template的一个private member function（其定义请参阅网站所提供的程序代码）。为了让上述的output运算符得以顺利调用print（），output运算符必须成为BinaryTree的一个friend。

  • template class BinaryTree {
    • friend ostream& operator«(ostream &os, const BinaryTree &tree);

*6.6 常量表达式与默认参数值

• 非类型参数：本节有一半主题在于“以表达式（expression）作为template参数”。这种template参数在C++Prim一书（作者亦为Lippman）中称为“非类型参数（non-type parameter）”。

• 常量表达式：Template参数并不是非得某种类型（type）不可。我们也可以用常量表达式（constant expression）作为template参数。

• 先前的数列类继承体系可以重新以class template设计，将“对象所含的元素个数”参数化。对象皆属于Fibonacci，而其基类num_sequence会因为参数len而导致元素个数为16。

  • template class NumSeq
    • NumSeq(int beg_pos = 1);
    • template class Fibonacci : public NumSeq
    • Fibonacci(int beg_pos = 1): NumSeq(beg_pos) {}
    • Fibonacci<16> fib2(17);

  • 同样道理，我们也可以将长度和起始位置一并参数化。由于大部分数列对象的起始位置为1，如果我们能为起始位置提供默认值，就更理想了。这里的参数默认值和一般函数的默认参数值一样，由左至右进行解析。

  • template class Fibonacci : public NumSeq
    • Fibonacci<32,1> fib;

  • 全局作用域（global scope）内的函数及对象，其地址也是一种常量表达式，因此也可以被拿来表达这一形式的参数。

  • 例如，以下是一个接受函数指针作为参数的数列类。本例中的pf是一个指向“依据特定数列类型，产生pos个元素，放到vector seq内”的函数，
    • template &seq)> class NumSeq
    • NumSeq(int len, int beg_pos=1) { pf(beg_pos+len-1, _elems); }
    • void fibonacci(int pos, vector &seq);
    • NumSeq fib(12);

• 示例：

• 6.6：以表达式template参数重新定义第5章的num_sequence基类及Fibonacci派生类。

/* Eg.6.6 Implement a NumSeq basde class and Fibonacci derived class with template expression parameter. */ # include # include # include using namespace std; template <int len, int beg_pos> class NumSeq { public: virtual ~NumSeq() {}; int get_length() { return len; } int get_beg_pos() { return beg_pos; } int elem(int pos) { if (pos > _relems.size()) gen_elems(pos); return _relems[pos-1]; } protected: NumSeq(vector &re): _relems(re) {} // int _length; // int _beg_pos; virtual void gen_elems(int pos) = 0; vector &_relems; }; template <int len, int beg_pos=1> class Fibonacci : public NumSeq<len, beg_pos> { public: Fibonacci(): NumSeq<len, beg_pos>(_elems) {} virtual ~Fibonacci() {} protected: static vector _elems; virtual void gen_elems(int pos) { int m = _elems.size(), i; for (i = m + 1; i <= pos; i++) { if (i == 1) _elems.push_back(1); else if (i == 2) _elems.push_back(1); else _elems.push_back(_elems[i-2] + _elems[i-3]); } } }; template <int len, int beg_pos> vector Fibonacci<len, beg_pos>::_elems; template <int len, int beg_pos> ostream& operator<<(ostream& os, NumSeq<len, beg_pos> &ns) { int i = 0; int m = ns.get_beg_pos(), n = ns.get_length(); for (i = m; i < m + n; i++) os << ns.elem(i) << ' '; return os; } int main(void) { Fibonacci<8> fib; cout << fib << endl; Fibonacci<12,8> fib2; cout << fib2 << endl; return 0; }

6.7 以 Template参数作为一种设计策略

• 带模板的函数对象：

• 现在，4.9节的LessThan function object可以水到渠成地转为class template。是上述这种做法有一个潜在问题：一旦用户所提供的类型并未定义less-than运算符，上述做法便告失败。

  • template class LessThan
    • bool operator()(const T &a, const T &b) const { return a < b; }
    • LessThan lt;

  • 另一种可行策略便是提供第二个class template，将comparison运算符从类定义中剥离。但虽然这第二个类提供的是和 LessThan相同的语义，我们却得为它另外取个名称，因为 class template无法基于参数列表的不同而重载。就让我把它命名为LessThanPred吧——因为less-than运算符被我指定为默认参数值。

  • template > class LessThanPred
    • bool operator()(const T &a, const T &b) { return Comp(a, b); }
    • class StringLenComp
    • bool operator()(const string &s1, const string &s2) { return s1.size() < s2.size(); }
    • LessThanPred lt;

  • 我们可能会以另一个更通用的名称来命名 function object，表示它足以支持任何类型的比较操作。那么，本例就不需要再提供默认的function object了。Compare可将任何一种“BinaryComp操作”应用于两个同为elemType类型的对象身上。

  • template class Compare;

• 类作为模板参数：

• 我曾在第5章设计了一个面向对象的数列类体系。请思考以下另一种设计。在其中，我将数列类定义为class template，而将实际的数列类剥离成为参数。通过函数的命名规范，调用未知数列类中的同名函数。

  • template class NumericSeq
    • NumericSeq(int len=1, int bp=1): _ns(len, bp) {}
    • void calc_elems(int sz) const { _ns.calc_elems(sz); }
    • private: Seq _ns;
  • 以上 template 设计，将某种特定的命名规范强加于被当作参数的类身上：每个类都必须提供NumericSequence class template中调用到的函数，如calc_elems（）、is_elem（），等等。这种独特设计虽然比较高级，但我认为值得提这么一下，以免你可能认为class template的类型参数仅能用以传递元素类型——像二叉树或标准库的vector、list等容器那样。

*6.8 Member Template Function

• 成员模板函数：我们也可以将member function定义成template形式。

• 非模板类：PrintIt是一个non-template class，其初值为一个output stream（输出数据流）。它提供了一个名为print（）的member template function，后者能将任意类型的对象写至指定的output stream。只要像上面那样，令print（）成为PrintIt的membertemplate function，我们便可以在“只写一份函数定义”的情形下，支持任何类型——前提是该类型可应用output运算符。如果不将“要输出的元素”的类型剥离为参数，我们势必得为不同的类型各自建立一份class。采用member template，就只需要一份PrintIt类。

  • class PrintIt
    • PrintIt(ostream &os): _os(os) {}
    • template void print( const T &elem, char delimiter=’\n’) { _os « elem « delimiter; }
    • PrintIt to_stdout(cout);
    • to_stdout.print(“hello”);

  • 模板类：Class template内也可以定义member template function。例如，我们可能会将PrintIt原本指定的output stream再予以参数化，使其成为可指定的ostream类型，并仍然令print（）为一个member template function。

  • template class PrintIt
    • PrintIt(OutStream &os): _os(os) {}
    • template void print( const T &elem, char delimiter=’\n’) { _os « elem « delimiter; }
    • private: ostream &_os;
    • PrintIt to_stdout(cout);
    • to_stdout.print(1024);

• 除了本章所谈到的，template还有许多议题。如果你需要C++template机制的更多资料，请参阅[LIPPMAN98]的第10章（Function Templates）和第16章（Class Templates），以及[STROUSTRUP97]第13章。

• 练习：

• 6.2：以template形式实现练习4.3的Matrix class，使其能够通过堆内存heap memory支持任意行列的大小。分配/释放内存的操作在构造/析构函数中进行。

/* 6.2 Matrix class template with variable rows and columns. */ #include #include using namespace std; template class Matrix { public: Matrix (int row, int col, T *arr = NULL): _row(row), _col(col) { int size = row * col; _pmat = new T[row * col]; for (int i = 0; i < size; i++) _pmat[i] = arr ? arr[i] : T(); } Matrix ( const Matrix &rhs ) { cout << "copy constructor" << endl; _row = rhs._row; _col = rhs._col; _pmat = new T[_row * _col]; for (int i = 0; i < _row * _col; i++) _pmat[i] = rhs._pmat[i]; } ~Matrix() { delete [] _pmat; } int rows() { return _row; } int cols() { return _col; } Matrix& operator=( const Matrix &rhs ) { cout << "copy assignment" << endl; if (this == &rhs) return *this; _row = rhs._row; _col = rhs._col; delete [] _pmat; _pmat = new T[_row * _col]; for (int i = 0; i < _row * _col; i++) _pmat[i] = rhs._pmat[i]; return *this; } Matrix operator+( Matrix &rhs ) { Matrix m(rows(), cols()); for (int i = 0; i < rows(); i++) for (int j = 0; j < cols(); j++) m(i, j) = (*this)(i, j) + rhs(i, j); return m; } Matrix operator*( Matrix &rhs ) { Matrix m(rows(), rhs.cols()); for (int i = 0; i < rows(); i++) for (int j = 0; j < cols(); j++) { m(i, j) = 0; for (int k = 0; k < cols(); k++) m(i, j) += (*this)(i, k) * rhs(k, j); } return m; } void print(ostream &os) { for (int i = 0; i < rows(); i++) { for (int j = 0; j < cols(); j++) os << (*this)(i, j) << ' '; os << endl; } } void operator+=( Matrix &rhs ) { for (int i = 0; i < rows(); i++) for (int j = 0; j < cols(); j++) (*this)(i, j) += rhs(i, j); } T operator()( int row, int col ) const { return _pmat[row * cols() + col]; } T& operator()( int row, int col ) { return _pmat[row * cols() + col]; } private: int _row; int _col; T *_pmat; }; template ostream& operator<<( ostream &os, Matrix &rhs ) { rhs.print(os); return os; } int main(void) { double ar[16] = { 1., 0., 0., 0., 0., 1., 0., 0., 0., 0., 1., 0., 0., 0., 0., 1. }; double ar2[16] = { 1.3, 0.4, 2.6, 8.2, 6.2, 1.7, 1.3, 8.3, 4.2, 7.4, 2.7, 1.9, 6.3, 8.1, 5.6, 6.6 }; Matrix m1(4, 4, ar); cout << m1 << endl; Matrix m2(4, 4, ar2); cout << m2 << endl; Matrix m3(m1); m3 = m1 + m2; m3 += m1; cout << m3 << endl; Matrix m4(m2); m4 = m1 * m2; cout << m4 << endl; return 0; }

7 异常处理

• 异常处理：身为这个iterator class的设计者，我们却有能力辨识这一问题：iterator不再处于有效状态，再也不能被程序继续使用下去了。但是我们不知道这个问题对于整个程序的危害程度究竟如何——唯有iterator的用户才知道问题的严重性。因此我们的职责便是通知用户，告诉他发生了什么事。我们以C++的异常处理机制（exceptionhandling facility）来完成通知任务。

7.1 抛出异常

• 异常处理机制有两个主要成分：异常的鉴定与发出，以及异常的处理方式。

• 通常，不论是member function或non-member function，都有可能产生异常以及处理异常。异常出现之后，正常程序的执行便被暂停（suspended）。
  • 与此同时，异常处理机制开始搜索程序中有能力处理这一异常的地点。异常被处理完毕之后，程序的执行便会继续（resume），从异常处理点接着执行下去。

• 抛出异常：C++通过throw表达式产生异常

• throw表达式：throw 表达式看起来有点像函数调用。

  • if (_index >= _max_elems)
    • throw iterator_overflow(_index, _max_elems);

• 异常：何谓抛出（thrown）一个异常？所谓异常（exception）是某种对象。最简单的异常对象可以设计为整数或字符串。

• 异常类：大部分时候，被抛出的异常都属于特定的异常类（也许形成一个继承体系）。

  • class iterator_overflow
    • iterator_overflow(int index, int max): _index(index), _max(max) { }
    • void what_happened(ostream &os = cerr) { os « “Error”; }

  • 我们只是令异常类得以储存某些必要数据，用以表示异常的性质，以便我们得以在不同程序的不同调用点上相互传递这些性质。

  • 异常对象：前例的throw表达式，会直接调用拥有两个参数的constructor。我们可以换一种方式，明确指出被抛出的对象名称。

  • iterator_overflow ex(_index, _max_elems);
    • throw ex;

7.2 捕获异常

• 捕获异常：

• catch语句：我们可以利用单条或一连串的catch子句来捕获（catch）被抛出的异常对象。catch子句由三部分组成：关键字catch、小括号内的一个类型或对象、大括号内的一组语句（用以处理异常）。

  • catch (int errno) {

    • log_message(err_messages[errno]);
      • status = false; }

    • catch (iterator_overflow &iof) {

    • iof.what_happened(log_file);
      • status = false; }

  • 上述catch子句会处理前一节所抛出的异常对象

  • throw 42;

    • throw iterator_overflow(_index, _max_elems);

• 执行catch语句：异常对象的类型会被拿来逐一地和每个catch子句比对。如果类型符合，那么该catch子句的内容便会被执行。

• 当我们抛出iterator_overflow对象时，三个catch子句会被依次检验。其中第三个子句所声明的异常类型与被抛出的异常对象相符，于是其后的语句内容便被执行。
  • 我们通过iof这个异常对象，调用异常类（exceptionclass）中的member function what_happened（）。
  • 以上呈现了完整的异常处理过程。在通过所有 catch 子句之后，由正常程序重新接手。

• 重新抛出：有时候我们可能无法完成异常的完整处理。在记录信息之外，我们或许需要重新抛出（rethrow）异常，以寻求其他catch子句的协助，做进一步的处理。

• catch-all：想要捕获任何类型的异常，可以使用一网打尽（catch-all）的方式。只需在异常声明部分指定省略号（…）即可。

• • catch ( … ) { log_message(“exception of unknown type”); }

7.3 提炼异常

• try-catch：catch子句应该和 try块相应而生。try块是以关键字 try作为开始，然后是大括号内的一连串程序语句。catch子句放在try块的末尾，这表示如果try块内有任何异常发生，便由接下来的catch子句加以处理。

• • 程序代码放在try块内，并在接下来的catch子句中指定要捕获iterator_overflow异常：

  • • try { // 程序代码 }
    • catch { iterator_overflow &iof } { log_message( iof.what_happened() ); }

• 异常处理机制：抛出异常后，异常处理机制开始查看，异常由何处抛出，并判断是否位于try块内？如果是，就检验相应的catch子句，看它是否具备处理此异常的能力。如果有，这个异常便被处理，而程序也就继续正常执行下去。

• • throw 表达式并非位于 try 块内，因此异常处理机制不去处理它，剩余内容不会被执行。异常处理机制会继续上溯调用端搜寻类型吻合的catch子句，于是相应的catch子句被拿出来查看，类型吻合者会被执行。如此便完成了异常处理。正常的程序执行则于“被执行的catch子句”的下方第一行语句继续。
  • 如果“函数调用链”不断地被解开，一直回到了main（）还是找不到合适的catch子句，会发生什么事？C++规定，每个异常都应该被处理，因此，如果在main（）内还是找不到合适的处理程序，便调用标准库提供的terminate（）——其默认行为是中断整个程序的执行。

• 在try块内该放置哪些语句，在try块外该放置哪些语句，这些都是程序员的职责。如果某一语句有可能引发异常，而它不位于try块内，那么该异常保证不会在此函数内被捕获处理。这也许会有问题，也许不会有问题——并非每个函数都必须处理每一个可能发生的异常。

• • 如何知道某个函数是否能够安全地忽略可能发生的异常：我们可以保证，只有在无任何异常被抛出的情况下，dereference 运算符才会执行 return语句。只要发生任何异常，函数便会在“return语句被执行前”中断。
  • 当函数的try块发生某个异常，但并没有相应的catch子句将它捕获，此函数便会被中断，由异常处理机制接管，沿着“函数调用链”一路回溯，搜寻符合条件的 catch子句。
• 初学者常犯的错误是，将C++异常和segmentation fault或是bus error这类硬件异常混淆在一起。面对任何一个被抛出的 C++异常，你都可以在程序某处找到一个相应的 throw 表达式。（有些深藏在标准库中。）

7.4 局部资源管理

• 资源释放问题：

• • 函数在开始要求分配相关资源，然后进行某些处理操作。函数结束之前，这些资源会被释放。问题出在我们无法保证，函数执行之初所分配的资源最终一定会被释放掉。如果调用的函数抛出异常，那么process（）调用操作之后的两条用以释放资源的语句便不会被执行。在异常处理机制之下，这并不是一份好的实现。

  • • extern Mutex m;
    • int *p = new int; m.acquire(); // 请求资源
    • process(p);
    • m.release(); delete p; // 释放资源

  • 解决之道是导入一个 try块，以及相应的 catch子句。这样便可捕获所有异常、释放所有资源、再将异常重新抛出。这样虽然可以解决我们的问题，但仍然不是个令人完全满意的解答，因为用以释放资源的程序代码得出现两次。而且，捕获异常、释放资源、重新抛出异常，这些操作会使异常处理程序（exception handler）的搜寻时间进一步延长。此外，程序代码本身也更复杂了。我们希望写出更具防护性、更自动化的处理方式。在C++中这通常意味着定义一个专属的class。

  • • try { // 请求资源 // 处理 // 释放资源 }
    • catch( … ) { m.release(); delete p; throw; }

• 资源管理：C++的发明者Bjarne Stroustrup引入了所谓资源管理（resource management）的手法，他自己则称之为resource acquisition is initialization（在初始化阶段即进行资源请求）。对对象而言，初始化操作发生于constructor内，资源的请求亦应在constructor内完成。资源的释放则应该在destructor内完成。这样虽然无法将资源管理自动化，却可简化我们的程序。

• • p和 ml都是局部（local）对象。如果 process（）执行无误，那么相应的 destructor便会在函数结束前自动作用于p和ml身上。在异常处理机制终结某个函数之前，C++保证，函数中的所有局部对象的 destructor都会被调用。本例中，不论是否有任何异常被抛出，p和ml的destructor保证被调用。

  • • # include
    • auto_ptr p(new int);
    • MutexLock ml(m);
    • process(p);

  • MutexLock class可以实现成下面的样子：

  • • MutexLock(Mutex m): _lock(m) { _lock.acquire(); }
    • ~MutexLock(Mutex m): _lock(m) { _lock.release(); }
    • private: Mutex & _lock;

  • auto_ptr是标准库提供的class template，它会自动删除通过new表达式分配的对象，例如先前例子中的p。使用它之前，必须包含相应的memory头文件。auto_ptr将dereference运算符和arrow运算符予以重载，这使我们得以像使用一般指针一样地使用auto_ptr对象。

  • 关于 resource acquisition is initialization （在初始化阶段即进行资源的请求），详细讨论参见[STROUSTRUP97]的14.4节。如果想获得auto_ptr的更多知识，请参阅[LIPPMAN98]的8.4.2节。

7.5 标准异常

• bad_alloc异常：如果new表达式无法从程序的空闲空间（free store）分配到足够的内存，它会抛出bad_alloc异常对象。

• • 如果没有足够的内存足以表现一个 vector＜string＞对象，default constructor 就不会被调用，ptext也不会被设置值，因为这时候bad_alloc异常对象会被抛出，程序流程会跳到try块之后的catch子句。

  • • try { ptext = new vector }
    • catch ( bad_alloc ) { cerr « “heap memory exhausted\n”; }
  • catch子句并未声明出任何对象，因为我们只对捕获到的异常的类型感兴趣，并没有打算在catch子句中实际操作该对象。

• 标准异常：标准库定义了一套异常类体系（exception class hierarchy），其根部是名为exception的抽象基类。exception声明有一个what（）虚函数，会返回一个const char ＊，用以表示被抛出异常的文字描述。

• • bad_alloc派生自exception基类，它有自己的what（）。Visual C++所提供的bad_alloc，其what（）函数会产生“bad allocation”这样的信息。

  • 我们也可以将自己编写的 iterator_overflow继承于 exception基类之下。首先必须包含标准头文件exception，而且必须提供自己的what（）。

  • • #include
    • class iterator_overflow : public exception
    • public: const char* what() const;

  • 将 iterator_overflow 融入标准的 exception 类体系的好处是，它可以被任何“打算捕获抽象基类exception”的程序代码所捕获，这意味着我们不必修改原有的程序代码，就可以让那些程序代码认识这个class。我们也不必再用一网打尽（catch-all）的方式来捕获所有异常了。下面这个catch子句：会捕捉 excepion 的所有派生类。当 bad_alloc 异常被抛出，它会打印出“bad allocation”信息。

  • • catch (const exception &ex) { cerr « ex.what() « endl; }

  • 以下便是iterator_overflow的what（）的某种实现方式，其中运用ostringstream对象对输出信息进行了格式化：ostringstream class提供“内存内的输出操作”，输出到一个string对象上。当我们需要将多笔不同类型的数据格式化为字符串时，它尤其有用。它能自动将_index、max这类数值对象转换为相应的字符串，我们不必考虑储存空间、转换算法等问题。ostringstream所提供的一个member function str（），会将“与ostringstream对象相呼应”的那个string对象返回。标准库让what（）返回一个const char＊，将string对象转成C-style字符串，string class的转换函数c_str（）会返回我们所要的const char＊。使用ostringstream class之前，必须先包含标准头文件sstream。

  • • include
    • ostringstream ex_msg;
    • static string msg;
    • ex_msg « “Internal error”;
    • msg = ex_msg.str();
    • reuturn msg.c_str();

  • iostream库也对应提供了istringstream class。如果我们需要将非字符串数据（例如，整数值或内存地址）的字符串表示转换为其实际类型，istringstream可派上用场。请参阅[LIPPMAN98]的20.8节，其中有关于string stream class的丰富讨论。

  • 如果想要获得C++异常处理机制的更广泛讨论，请参见[LIPPMAN98]的第11章和19.2节，以及[STROUSTRUP97]第14章。[SUTTER99]对于exception-safe（异常发生时依旧安全）的设计，以及异常处理机制下class的各种设计考虑，有相当不错的见解。

• 练习：

• • 7.2：下列函数被上题的alloc_and_init（）调用，执行失败时会发出异常：请安置一个或多个try块，以及相应的catch子句，以便能适当地处理这些异常。相应的catch子句中只需将错误打印出来即可。

try { // 程序代码 } catch (const noMem &memFail) { cerr « memFail.waht() « endl; } catch (int &sortFail) { cerr « sortFail « endl; } catch (string ®isterFail) { cerr « registerFail « endl; }

• • 7.3：为练习5.2的Stack类体系加入两个异常类型，处理“想从空stack中取出元素”和“想为满stack添加元素”两种错误。请显示修改后的pop（）和push（）。

  • • 我定义PopOnEmpty和PushOnFull两个异常类，分别供pop（）和push（）抛出。为了让这两个Stack异常可以被完全不知情的其他组件捕获，它们应该融入StackException继承体系中，后者又应该派生自标准库所提供的logic_error class。logic_error派生自exception。exception是标准库的所有异常类别继承体系的最根本抽象基类。这个继承体系有一个名为what（）的虚函数，会返回const char＊，用以表示被捕获的异常究竟为何。

class StackException : public logic_error { public: StackException(const char *what): _what(what) {} const char *what() const { return _what.c_str(); } protected: string _what; }; class PopOnEmpty: public StackException { public: PopOnEmpty(): StackException(“Pop on Empty Stack”) {} } class PushOnFull: public StackException { public: PushOnFull(): StackException(“Push on Full Stack”) {} } void pop (elemType &elem) { if (empty()) throw PopOnEmpty(); // 程序代码 } void push(const elemType &elem) { if (full()) throw PushOnFull(); // 程序代码 }

附录B 泛型算法参考手册

参考文献

• Lippman, 侯捷 译. Essential C++. 1999.
• Lippman, Lajoie. C++ Primer. 1998.
• Lippman. Inside the C++ Object Model. 1996.
• Stroustrup. The C++ Programming Language. 1997.
• Sutter. Exceptional C++. 1999.
• Meyers. More Effective C++. 2011.
• C++官网API文档：http://www.cplusplus.com/reference/