C++工程实践(9):数据抽象
什么是数据抽象
数据抽象(data abstraction)是与面向对象(object-oriented)并列的一种编程范式(programming paradigm)。说“数据抽象”或许显得陌生,它的另外一个名字“抽象数据类型/abstract data type/ADT”想必如雷贯耳。
“支持数据抽象”一直是C++语言的设计目标,Bjarne Stroustrup 在他的《The C++ Programming Language》第二版(1991年出版)中写道[2nd]:
The C++ programming language is designed to
be a better C
support data abstraction
support object-oriented programming
这本书第三版(1997年出版)[3rd] 增加了一条:
C++ is a general-purpose programming language with a bias towards systems programming that
is a better C,
supports data abstraction,
supports object-oriented programming, and
supports generic programming.
有一篇 Bjarne Stroustrup 在 1984 年写的 《Data Abstraction in C++》 http://www.softwarepreservation.org/projects/c_plus_plus/cfront/release_e/doc/DataAbstraction.pdf 。在这个页面还能找到 Bjarne 写的关于 C++ 操作符重载和复数运算的文章,作为数据抽象的详解与范例。可见 C++ 早期是以数据抽象为卖点的,支持数据抽象是C++相对于C的一大优势。
作为语言的设计者,Bjarne 把数据抽象作为C++的四个子语言之一。这个观点不是普遍接受的,比如作为语言的使用者,Scott Meyers 在《Effective C++ 第三版》中把 C++ 分为四个子语言:C、Object-Oriented C++、Template C++、STL。在 Scott Meyers 的分类法中,就没有出现数据抽象,而是归入了 object-oriented C++。
那么到底什么是数据抽象?
简单的说,数据抽象是用来描述数据结构的。数据抽象就是 ADT。一个 ADT 主要表现为它支持的一些操作,比方说 stack.push、stack.pop,这些操作应该具有明确的时间和空间复杂度。另外,一个 ADT 可以隐藏其实现细节,比方说 stack 既可以用动态数组实现,又可以用链表实现。
按照这个定义,数据抽象和基于对象(object-based)很像,那么它们的区别在哪里?语义不同。ADT 通常是值语义,而 object-based 是对象语言。(这两种语义的定义见前文《C++ 工程实践(8):值语义》)。ADT class 是可以拷贝的,拷贝之后的 instance 与原 instance 脱离关系。
比方说 stack a; a.push(10); stack b = a; b.pop(); 这时候 a 里仍然有元素 10。
C++ 标准库中的数据抽象
C++ 标准库里 complex<> 、pair<>、vector<>、list<>、map<>、set<>、string、stack、queue 都是数据抽象的例子。vector 是动态数组,它的主要操作有 push_back()、size()、begin()、end() 等等,这些操作不仅含义清晰,而且计算复杂度都是常数。类似的,list 是链表,map 是有序关联数组,set 是有序集合、stack 是 FILO 栈、queue是 FIFO 队列。“动态数组”、“链表”、“有序集合”、“关联数组”、“栈”、“队列”都是定义明确(操作、复杂度)的抽象数据类型。
数据抽象与面向对象的区别
本文把 data abstraction、object-based、object-oriented 视为三个编程范式。这种细致的分类或许有助于理解区分它们之间的差别。
庸俗地讲,面向对象(object-oriented)有三大特征:封装、继承、多态。而基于对象(object-based)则只有封装,没有继承和多态,即只有具体类,没有抽象接口。它们两个都是对象语义。
面向对象真正核心的思想是消息传递(messaging),“封装继承多态”只是表象。
数据抽象与它们两个的界限在于“语义”,数据抽象不是对象语义,而是值语义。比方说 muduo 里的 TcpConnection 和 Buffer 都是具体类,但前者是基于对象的(object-based),而后者是数据抽象。
类似的,muduo::Date、muduo::Timestamp 都是数据抽象。尽管这两个 classes 简单到只有一个 int/long 数据成员,但是它们各自定义了一套操作(operation),并隐藏了内部数据,从而让它从 data aggregation 变成了 data abstraction。
数据抽象是针对“数据”的,这意味着 ADT class 应该可以拷贝,只要把数据复制一份就行了。如果一个 class 代表了其他资源(文件、员工、打印机、账号),那么它就是 object-based 或 object-oriented,而不是数据抽象。
ADT class 可以作为 Object-based/object-oriented class 的成员,但反过来不成立,因为这样一来 ADS class 的拷贝就失去意义了。
数据抽象所需的语言设施
不是每个语言都支持数据抽象,下面简要列出“数据抽象”所需的语言设施。
支持数据聚合
数据聚合 data aggregation,或者 value aggregates。即定义 C-style struct,把有关数据放到同一个 struct 里。FORTRAN77没有这个能力,FORTRAN77 无法实现 ADT。这种数据聚合 struct 是 ADT 的基础,struct List、struct HashTable 等能把链表和哈希表结构的数据放到一起,而不是用几个零散的变量来表示它。
全局函数与重载
例如我定义了 complex,那么我可以同时定义 complex sin(const complex& x); 和 complex exp(const complex& x); 等等全局函数来实现复数的三角函数和指数运算。sin 和 exp 不是 complex 的成员,而是全局函数 double sin(double) 和 double exp(double) 的重载。这样能让 double a = sin(b); 和 complex a = sin(b); 具有相同的代码形式,而不必写成 complex a = b.sin();。
C 语言可以定义全局函数,但是不能与已有的函数重名,也就没有重载。Java 没有全局函数,而且 Math class 是封闭的,并不能往其中添加 sin(Complex)。
成员函数与 private 数据
数据也可以声明为 private,防止外界意外修改。不是每个 ADT 都适合把数据声明为 private,例如 complex、point、pair<> 这样的 ADT 使用 public data 更加合理。
要能够在 struct 里定义操作,而不是只能用全局函数来操作 struct。比方说 vector 有 push_back() 操作,push_back 是 vector 的一部分,它必须直接修改 vector 的 private data members,因此无法定义为全局函数。
这两点其实就是定义 class,现在的语言都能直接支持,C 语言除外。
拷贝控制(copy control)
copy control 是拷贝 stack a; stack b = a; 和赋值 stack b; b = a; 的合称。
当拷贝一个 ADT 时会发生什么?比方说拷贝一个 stack,是不是应该把它的每个元素按值拷贝到新 stack?
如果语言支持显示控制对象的生命期(比方说C++的确定性析构),而 ADT 用到了动态分配的内存,那么 copy control 更为重要,不然如何防止访问已经失效的对象?
由于 C++ class 是值语义,copy control 是实现深拷贝的必要手段。而且 ADT 用到的资源只涉及动态分配的内存,所以深拷贝是可行的。相反,object-based 编程风格中的 class 往往代表某样真实的事物(Employee、Account、File 等等),深拷贝无意义。
C 语言没有 copy control,也没有办法防止拷贝,一切要靠程序员自己小心在意。FILE* 可以随意拷贝,但是只要关闭其中一个 copy,其他 copies 也都失效了,跟空悬指针一般。整个 C 语言对待资源(malloc 得到的内存,open() 打开的文件,socket() 打开的连接)都是这样,用整数或指针来代表(即“句柄”)。而整数和指针类型的“句柄”是可以随意拷贝的,很容易就造成重复释放、遗漏释放、使用已经释放的资源等等常见错误。这方面 C++ 是一个显著的进步,boost::noncopyable 是 boost 里最值得推广的库。
操作符重载
如果要写动态数组,我们希望能像使用内置数组一样使用它,比如支持下标操作。C++可以重载 operator[] 来做到这一点。
如果要写复数,我们系统能像使用内置的 double 一样使用它,比如支持加减乘除。C++ 可以重载 operator+ 等操作符来做到这一点。
如果要写日期时间,我们希望它能直接用大于小于号来比较先后,用 == 来判断是否相等。C++ 可以重载 operator< 等操作符来做到这一点。
这要求语言能重载成员与全局操作符。操作符重载是 C++ 与生俱来的特性,1984 年的 CFront E 就支持操作符重载,并且提供了一个 complex class,这个 class 与目前标准库的 complex<> 在使用上无区别。
如果没有操作符重载,那么用户定义的ADT与内置类型用起来就不一样(想想有的语言要区分 == 和 equals,代码写起来实在很累赘)。Java 里有 BigInteger,但是 BigInteger 用起来和普通 int/long 大不相同:
public static BigInteger mean(BigInteger x, BigInteger y) {
BigInteger two = BigInteger.valueOf(2);
return x.add(y).divide(two);
}
public static long mean(long x, long y) {
return (x + y) / 2;
}
当然,操作符重载容易被滥用,因为这样显得很酷。我认为只在 ADT 表示一个“数值”的时候才适合重载加减乘除,其他情况下用具名函数为好,因此 muduo::Timestamp 只重载了关系操作符,没有重载
补充:软件开发 , C++ ,