C++ 工程实践(9):数据抽象

简介:

陈硕 (giantchen_AT_gmail)
http://blog.csdn.net/Solstice  http://weibo.com/giantchen
陈硕关于 C++ 工程实践的系列文章: http://blog.csdn.net/Solstice/category/802325.aspx
排版正常的版本: http://www.cnblogs.com/Solstice/category/287661.html
陈硕博客文章合集下载: http://blog.csdn.net/Solstice/archive/2011/02/24/6206154.aspx
本作品采用“Creative Commons 署名-非商业性使用-禁止演绎 3.0 Unported 许可协议(cc by-nc-nd)”进行许可。http://creativecommons.org/licenses/by-nc-nd/3.0/

前一篇文章谈了值语义,这篇文章谈一谈与之密切相关的数据抽象(data abstraction)。

文章结构:

  1. 什么是数据抽象?它与面向对象有何区别?
  2. 数据抽象所需的语言设施
  3. 数据抽象的例子

什么是数据抽象

数据抽象(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.

在 http://www.softwarepreservation.org/projects/c_plus_plus/index.html#cfront 可以找到 C++ 的早期文献,其中有一篇 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),“封装继承多态”只是表象。这一点孟岩 http://blog.csdn.net/myan/article/details/5928531 和王益 http://cxwangyi.wordpress.com/2011/06/19/%E6%9D%82%E8%B0%88%E7%8E%B0%E4%BB%A3%E9%AB%98%E7%BA%A7%E7%BC%96%E7%A8%8B%E8%AF%AD%E8%A8%80/ 都有精彩的论述,陈硕不再赘言。

数据抽象与它们两个的界限在于“语义”,数据抽象不是对象语义,而是值语义。比方说 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++ 工程实践(3):采用有利于版本管理的代码格式》。

效率无损

“抽象”不代表低效。在 C++ 中,提高抽象的层次并不会降低效率。不然的话,人们宁可在低层次上编程,而不愿使用更便利的抽象,数据抽象也就失去了市场。后面我们将看到一个具体的例子。

模板与泛型

如果我写了一个 int vector,那么我不想为 doule 和 string 再实现一遍同样的代码。我应该把 vector 写成 template,然后用不同的类型来具现化它,从而得到 vector<int>、vector<double>、vector<complex>、vector<string> 等等具体类型。

不是每个 ADT 都需要这种泛型能力,一个 Date class 就没必要让用户指定该用哪种类型的整数,int32_t 足够了。

 

根据上面的要求,不是每个面向对象语言都能原生支持数据抽象,也说明数据抽象不是面向对象的子集。

数据抽象的例子

下面我们看看数值模拟 N-body 问题的两个程序,前一个用 C 语言,后一个是 C++ 的。这个例子来自编程语言的性能对比网站 http://shootout.alioth.debian.org/gp4/benchmark.php?test=nbody&lang=all

两个程序使用了相同的算法。

C 语言版,完整代码见 https://gist.github.com/1158889#file_nbody.c,下面是代码骨干。planet 保存与行星位置、速度、质量,位置和速度各有三个分量,程序模拟几大行星在三维空间中受引力支配的运动。

struct planet
{
  double x, y, z;
  double vx, vy, vz;
  double mass;
};

void advance(int nbodies, struct planet *bodies, double dt)
{
  for (int i = 0; i < nbodies; i++)
  {
    struct planet *p1 = &(bodies[i]);
    for (int j = i + 1; j < nbodies; j++)
    {
      struct planet *p2 = &(bodies[j]);
      double dx = p1->x - p2->x;
      double dy = p1->y - p2->y;
      double dz = p1->z - p2->z;
      double distance_squared = dx * dx + dy * dy + dz * dz;
      double distance = sqrt(distance_squared);
      double mag = dt / (distance * distance_squared);
      p1->vx -= dx * p2->mass * mag;
      p1->vy -= dy * p2->mass * mag;
      p1->vz -= dz * p2->mass * mag;
      p2->vx += dx * p1->mass * mag;
      p2->vy += dy * p1->mass * mag;
      p2->vz += dz * p1->mass * mag;
    }
  }
  for (int i = 0; i < nbodies; i++)
  {
    struct planet * p = &(bodies[i]);
    p->x += dt * p->vx;
    p->y += dt * p->vy;
    p->z += dt * p->vz;
  }
}

其中最核心的算法是 advance() 函数实现的数值积分,它根据各个星球之间的距离和引力,算出加速度,再修正速度,然后更新星球的位置。这个 naive 算法的复杂度是 O(N^2)。

C++ 数据抽象版,完整代码见 https://gist.github.com/1158889#file_nbody.cc,下面是代码骨架。

首先定义 Vector3 这个抽象,代表三维向量,它既可以是位置,有可以是速度。本处略去了 Vector3 的操作符重载,Vector3 支持常见的向量加减乘除运算。

然后定义 Planet 这个抽象,代表一个行星,它有两个 Vector3 成员:位置和速度。

需要说明的是,按照语义,Vector3 是数据抽象,而 Planet 是 object-based.

struct Vector3
{
  Vector3(double x, double y, double z)
    : x(x), y(y), z(z)
  {
  }

  double x;
  double y;
  double z;
};

struct Planet
{
  Planet(const Vector3& position, const Vector3& velocity, double mass)
    : position(position), velocity(velocity), mass(mass)
  {
  }

  Vector3 position;
  Vector3 velocity;
  const double mass;
};

相同功能的 advance() 代码简短得多,而且更容易验证其正确性。(想想如果把 C 语言版的 advance() 中的 vx、vy、vz、dx、dy、dz 写错位了,这种错误较难发现。)

void advance(int nbodies, Planet* bodies, double delta_time)
{
  for (Planet* p1 = bodies; p1 != bodies + nbodies; ++p1)
  {
    for (Planet* p2 = p1 + 1; p2 != bodies + nbodies; ++p2)
    {
      Vector3 difference = p1->position - p2->position;
      double distance_squared = magnitude_squared(difference);
      double distance = std::sqrt(distance_squared);
      double magnitude = delta_time / (distance * distance_squared);
      p1->velocity -= difference * p2->mass * magnitude;
      p2->velocity += difference * p1->mass * magnitude;
    }
  }
  for (Planet* p = bodies; p != bodies + nbodies; ++p)
  {
    p->position += delta_time * p->velocity;
  }
}

性能上,尽管 C++ 使用了更高层的抽象 Vector3,但它的性能和 C 语言一样快。看看 memory layout 就会明白:

C struct 的成员是连续存储的,struct 数组也是连续的。

value3

C++ 尽管定义了了 Vector3 这个抽象,它的内存布局并没有改变,Planet 的布局和 C planet 一模一样,Planet[] 的布局也和 C 数组一样。

另一方面,C++ 的 inline 函数在这里也起了巨大作用,我们可以放心地调用 Vector3::operator+=() 等操作符,编译器会生成和 C 一样高效的代码。

不是每个编程语言都能做到在提升抽象的时候不影响性能,来看看 Java 的内存布局。

如果我们用 class Vector3、class Planet、Planet[] 的方式写一个 Java 版的 N-body 程序,内存布局将会是:

value4

这样大大降低了 memory locality,有兴趣的读者可以对比 Java 和 C++ 的实现效率。

注:这里的 N-body 算法只为比较语言之间的性能与编程的便利性,真正科研中用到的 N-body 算法会使用更高级和底层的优化,复杂度是O(N log N),在大规模模拟时其运行速度也比本 naive 算法快得多。

更多的例子

  • Date 与 Timestamp,这两个 class 的“数据”都是整数,各定义了一套操作,用于表达日期与时间这两个概念。
  • BigInteger,它本身就是一个“数”。如果用 C++ 实现 BigInteger,那么阶乘函数写出来十分自然,下面第二个函数是 Java 语言的版本。
BigInteger factorial(int n)
{
    BigInteger result(1);
    for (int i = 1; i <= n; ++i) {
        result *= i;
    }
    return result;
}

public static BigInteger factorial(int n) {
    BigInteger result = BigInteger.ONE;
    for (int i = 1; i <= n; ++i) {
        result = result.multiply(BigInteger.valueOf(i));
    }
    return result;
}

高精度运算库 gmp 有一套高质量的 C++ 封装 http://gmplib.org/manual/C_002b_002b-Interface-General.html#C_002b_002b-Interface-General

  • 图形学中的三维齐次坐标 Vector4 和对应的 4x4 变换矩阵 Matrix4,例如 http://www.ogre3d.org/docs/api/html/classOgre_1_1Matrix4.html
  • 金融领域中经常成对出现的“买入价/卖出价”,可以封装为 BidOffer struct,这个 struct 的成员可以有 mid() “中间价”,spread() “买卖差价”,加减操作符,等等。

小结

数据抽象是C++的重要抽象手段,适合封装“数据”,它的语义简单,容易使用。数据抽象能简化代码书写,减少偶然错误。


    本文转自 陈硕  博客园博客,原文链接:http://www.cnblogs.com/Solstice/archive/2011/08/22/2148786.html,如需转载请自行联系原作者





相关文章
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
139 77
|
1月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
58 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
42 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
67 19
|
1月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
46 13
|
1月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
46 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
42 10
|
1月前
|
算法 C++
【C++数据结构——图】最小生成树(头歌实践教学平台习题) 【合集】
【数据结构——图】最小生成树(头歌实践教学平台习题)目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:【合集】任务描述 本关任务:编写一个程序求图的最小生成树。相关知识 为了完成本关任务,你需要掌握:1.建立邻接矩阵,2.Prim算法。建立邻接矩阵 上述带权无向图对应的二维数组,根据它建立邻接矩阵,如图1建立下列邻接矩阵。注意:INF表示无穷大,表示整数:32767 intA[MAXV][MAXV];Prim算法 普里姆(Prim)算法是一种构造性算法,从候选边中挑
42 10
|
1月前
|
存储 算法 C++
【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】
本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。
46 10
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
36 7