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

2014-11-24 12:50:46 · 作者: · 浏览: 1
tor 有 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、vector、vector、vector 等等具体类型。

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

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

数据抽象的例子
下面我们看看数值模拟 N-body 问题的两个程序,前一个用 C 语言,后一个是 C++ 的。

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

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 是 obje