2.9 抽象数据类型
C++面向对象高效编程(第2版)
有时,人们谈论的是抽象数据类型(abstract data type),而不是数据抽象(data abstraction),这可能让学习OOP的人感到困惑。其实,它们的关系非常密切。
抽象数据类型是由程序员定义的新类型,附带一组操控新类型的操作。定义新抽象类型将直接应用数据抽象的概念。抽象数据类型也称为程序员定义类型(programmer defined type)。
任何语言基本上都支持内置数据类型(如整数、浮点数、字符等),而且通常会提供一组操控这些内置类型1的操作。当我们使用这些内置(或语言定义)类型时,并不知道也不关心(使用了数据抽象和封装)如何实现这些数据类型。但是,语言(更精确地说是语言编译器的实现者)非常了解实现,知道如何实现这些内置类型。进一步而言,语言定义类型的用户不能直接访问这些类型的内部表示,而且必须使用语言提供的操作来操控它们。
例如,我们在使用语言提供的浮点数时,并不知道浮点类型的内部表示2。但是,我们肯定知道类似+和-的操作可用于浮点数计算。当我们使用浮点类型时,便间接地使用了语言编译器的实现者所提供的内部表示,而且只能使用语言已定义的操作。这也让特定编译器和特定机器彼此独立,因此,我们可以在任何机器上运行任何语言编译器(即我们获得了实现独立)。
支持结构化编程的语言(Pascal、Algol和C等)也允许用户定义新类型,它们被称为用户定义类型(user defined type)或程序员定义类型(programmer defined type)。这些用户定义类型在它们的实现中使用语言定义类型。另外,支持结构化编程的语言也允许程序员为用户定义类型定义一组操作(不要与类似+和-这样的操作混淆)。但是,主要的问题是,用户定义类型的实现并未封装。要使用程序员定义类型必须完全了解该类型的实现,但是语言并不会保护新类型的实现者,也就是说,缺少数据封装(在C中使用static数据,可实现一些封装)。新类型通常定义为一个组合,由数据结构和一组用于操控该数据结构的
图2-4
函数组成,后者通过特定的方式访问数据结构。原则上,任何新类型的用户都必须使用这些函数来操作新类型,换言之,用户不应该直接访问或修改数据结构。但是,由于语言无法强制执行这条规则,因此无需了解数据结构如何使用,任何人都可以编写新函数操作数据结构。也就是说,这样做并未防止非法访问实现。在Pascal、Algol、C等语言中,只有在用户遵守隐性规则的前提下,才能确保数据完整,而语言不能强制执行这条规则。从本质上而言,新类型只不过是由一组函数(或操作)支持的数据结构。
举个简单的例子,带有Push()和Pop()这样操作的Stack(栈)类,其数据结构可以是一个数组或链表(栈通过数组或链表实现),在需要时通过Push()和Pop()操作修改数据结构。此外,我们还要考虑多个栈的创建和销毁。为简单起见,我们仅以整数栈为例,储存在栈中的元素类型相同。在后续的章节中,我们将介绍如何用模板类实现泛型栈(generic stack)。