前言 本书是为计算机科学或计算机工程课程编写的一本教材，可满足不同层次读者的需求。首先，本书可作为学习使用C++编程语言实现面向对象设计(OOD)的参考书。在第1、2章中，讲述了它的三个主要概念：封装、继承和多态性，并使用简单易懂的基本数学概念对它们进行了定义和举例说明。其次，本书介绍了标准模板库(Standard Template Library，STL)中的主要组件。第3、4两章先介绍了一些传统的概念，如：搜索、排序和散列。这两章为随后的几章奠定了基础，在后几章中介绍了包括标准模板库组件的预定义容器类和泛型算法。 本书前4章可作为数据结构和算法传统课程的基础内容，常被计算机协会(Association for Computing Machinery，ACM)作为CS7课程的内容。本书也可满足以下需求： 重点讲述标准库组件及其功能的计算机科学和计算机工程的高年级本科生和低年级研究生课程。 使用标准库(Standard Library)进行面向对象设计的计算机科学和计算机工程的高级本科生和低年级研究生课程。 本书不是为数据结构初级课程编写的(即ACM课程中的CS2课程)，因为已经有许多书籍可以满足这一课程的需求。本书主要介绍了使用标准库进行面向对象设计，并用大量的例子解释了数据结构课程中首先介绍的内容，如：链表、栈、队列和优先队列。然而，在CS2课程中，C++中这些数据结构的实现通常没有用到标准库。此外，本书中没有涉及CS2课程中讲述的树这一专题，因为STL的设计没有把树包含在容器类模板中。事实上，STL中用到树的地方可由使用红-黑树的排序关联容器类的实现来代替。 STL的主要观点是：它的使用不鼓励或强调面向对象设计的主要思想，特别是涉及到继承和多态性时。在9.6节和附录中，这些概念以及虚函数和类层次的概念与不同STL类模板中定义的组件的使用结合在一起。而这些类模板来自于两个独立的应用程序域。它的一个实现是图抽象数据类型，另一个实现是局域网的面向对象设计。 在用C++作为实现语言的数据结构和算法(ACM的CS7)课程的讲授中，一些新方法的关键就是使用标准库。这是由于标准模板库组件应用了商用软件设计中的另一个重要的目的，即强调了软件问题的正确性、效率、复用性和移植性。这些是软件工程课程中必讲的重要概念。本书中的程序代码设计也应用了这些概念。 目前，没有哪一本书给出了本书中的全部专题，这就是本书的特别之处。虽然有些书也介绍了本书中的某些内容，但是除了本书之外，没有哪本书包含了本书提到的全部内容。在许多书中，在介绍这些主要概念前并不提及预定义的标准模板库组件。然后在讲述标准模板库时又再次讲述这个专题，以保证正确性、效率和可移植性。与STL建立了某些关联后就达到了以下目的： 程序员不再需要考虑自己设计代码的正确性和效率，因为被访问的STL组件保证了正确性和效率。 因为STL的设计与任意特定的硬件配置无关，所以其代码可用于所有平台。 使用C++作为实现语言，并以软件开发专业人员为职业的学生获得了两个重要的里程碑。第一个是逐渐熟悉基本数据结构的理论描述；第二个是结构的实现细节(使用标 准库)。 本书中，每一章的开始都列出了通过学习本章里讲述的概念来达到的目的。此外，每章的最后一节总结了该章讲授的最重要问题，以便于学生在忘记重要的概念时能找到相应的章节。每章最后的练习试图使学生使用该章描述的一些概念给出每个习题的解答，证明自己解决问题的能力，从过去的旁观者转变为实际的参与者。最后，每章的结束给出了至少一个程序设计项目，其难度超过了解决练习题所需的解题能力的一般水平。这些项目是学生感兴趣的一般理论的扩展，或是该章所描述的实现方法的另一种形式。每章中的习题和项目都经过了测试，大部分标准答案都可在附带的光盘中找到。 本书假定学生已经熟悉了数据结构的初级课程，因而书中所讲述的方法更为高级。对某些数据结构属性的描述只在需要加强本文可读性时才会提及。 本书是一本有用的参考书，它强调了面向对象程序设计方法的概念以及如何使用标准模板库组件来实现这些概念。书中介绍的概念大部分来自于软件设计中经常遇到的问题。以程序的形式给出它们的解答，其中有很多用到了标准模板库中的组件。每章中的练习都包括对该章所述概念的变化和概括。这些练习的范围包括从最基本的概念到对这些概念的挑战性的扩展。实际上，最具挑战性的练习是在独立的程序设计项目部分中。如前所述，设计这些练习的目的是使学生实际参与到面向对象设计的环境中，而不是只作为临时的看客。 以下列出了每一章所讲述的主题： 第1章：类。本章重述了在类的定义、设计和编码中出现的概念。讲述了构造函数、析构函数、数据成员和成员函数的概念，并用大量的例子说明了这些概念。强调了设计类的注意事项：被构造的对象的哪个属性应指定为私有(private)，哪个属性应指定为公有(public)。强调了数据抽象的概念和抽象数据类型(如C++的类)的实现。本章还讨论了函数和类模板的概念、友元函数的使用、void*指针、异常和异常处理以及类的静态成员。通过大量的例子，使学生复习以前的课程中学习过的部分熟悉的概念。 第2章：继承和多态性。本章介绍并举例说明了某些概念的重要性，这些概念包括：类的层次关系、基类、派生类、抽象类、虚函数、类的保护成员以及静态和动态多态性。明确地强调了类的层次关系和多态性的价值及其在现代商用软件设计中的作用。 第3章：搜索和排序。本章首次用到了算法的概念，并给出了在排序和搜索中常用的算法。描述了这些算法的实现，而没有使用标准模板库中提供的程序，因为本章内容只是作为在第8章中提到的概念的预览。特别地，用Big-O分析方法定义了效率的概念及其量化；用有限归纳法定义了数学证明的概念。给出了递归编程方法和分而治之原则的思想。举例说明了在排序方法的传统问题中用到的概念。这些排序方法包括线性和二叉搜索、选择排序、插入排序、快速排序、合并排序以及其他排序方法。 第4章：散列：标准模板库的序幕。本章讨论了有关数据存储和在某种深度上进行检索的介绍性的专题。这些概念包括散列、散列函数、散列表、公开寻址、使用各种形式的探查方法解决散列冲突以及链表等内容。此外，本章末尾讨论了命名空间，它提供了一种普遍的进入标准模板库环境的方法。 第5章：STL中的组件概述。本章意欲在前4章中讲述的面向对象设计的传统特点和此后第6到第9章中讲述的使用STL组件的特点之间架起一座桥梁。概述了容器、泛型算法、迭代器、适配器和分配器的概念。从第6章开始将详述并举例说明这些概念。 第6章：队列容器。本章讲述了向量、双端队列和列表队列容器类模板的基础知识，详细介绍了这些概念在商用面向对象设计中的价值，特别强调了它们的使用效率。给出了使用这些形式的容器类模板的大量示例，并重点强调了如何选择合适的容器形式来有效地解决问题。 第7章：容器适配器。在第6章中介绍了基本队列容器后，本章介绍了容器适配器：栈、队列和优先队列，并把计算机科学中遇到过的问题作为例子来说明各个概念。这些例子主要来自于编译系统和操作系统的设计。内容包括检查圆括号、方括号和大括号是否成对出现，把算术表达式的前缀形式转变为等价的后缀形式，后缀算术表达式的赋值以及模拟多道程序时间共享操作系统中进程的就绪队列。 第8章：泛型算法。本章介绍了STL <algorithm>，强调了库中大量函数的重要性。这些函数包括lower_bound、binary_search、find、sort等。本章并没有透彻全面地对这些内容进行解释，而是强调了在数据处理(例如复制、搜索和排序)中常使用的函数的效率。这些概念的大多数在第3章中已介绍过，本章将用<algorithm>中提供的强大而有效的函数来再次讲述这些概念。 第9章：排序关联容器。本章重点介绍了集、多集、映射和多重映射类模板，如何区分这些模板，并说明了它们在大量重要应用程序域中的应用。这些应用程序域包括排序、搜索和各种形式的图数据类型的定义和实现。在本章中，也将介绍关联数组这一重要概念以及如何在数据检索和散列中使用它。 附录：局域网模拟器。这里把STL中的概念的应用延伸到了一个重要的应用程序域：模拟局域令牌环网络的行为。 本书使用的全部代码已经在不同平台上进行了测试，包括Visual C++ 6.0版本和Borland C++ 5.02版本的编译器以及大量基于UNIX的平台。