值语义和数据抽象（二）

发表于 | 更新于 | 分类于 | 阅读次数：

什么是数据抽象

数据抽象(data abstraction)是与面向对象(object-oriented)并列的一种编程范式(programming paradigm)。说“数据抽象”或许显得陌生，它的另外一个名字“抽象数据类型/abstract data type/ADT”想必如雷贯耳。

“支持数据抽象”一直是C++语言的设计目标，Bjarne Stroustrup 在他的《The C++ Programming Language》中写道：

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.

数据抽象是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 是对象语言。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 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 大不相同：

1
2
3
4
5
6
7
8
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、vector、vector、vector 等等具体类型。

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

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

数据抽象的例子

下面我们看看数值模拟 N-body 问题的两个程序，前一个用 C 语言，后一个是 C++ 的。两个程序使用了相同的算法。

C语言版

planet 保存与行星位置、速度、质量，位置和速度各有三个分量，程序模拟几大行星在三维空间中受引力支配的运动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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++ 数据抽象版

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 写错位了，这种错误较难发现。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 数组也是连续的。

object-ram-distribution

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

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

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

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

object-ram-distribution-in-java

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

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

小结

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