陳碩 (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)。
文章結構：
- 什么是數據抽象？它與面向對象有何區別？
- 數據抽象所需的語言設施
- 數據抽象的例子
什么是數據抽象
數據抽象(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 數組也是連續的。
C++ 盡管定義了了 Vector3 這個抽象，它的內存布局并沒有改變，Planet 的布局和 C planet 一模一樣，Planet[] 的布局也和 C 數組一樣。
另一方面，C++ 的 inline 函數在這里也起了巨大作用，我們可以放心地調用 Vector3::operator+=() 等操作符，編譯器會生成和 C 一樣高效的代碼。
不是每個編程語言都能做到在提升抽象的時候不影響性能，來看看 Java 的內存布局。
如果我們用 class Vector3、class Planet、Planet[] 的方式寫一個 Java 版的 N-body 程序，內存布局將會是：
這樣大大降低了 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
小結
數據抽象是C++的重要抽象手段，適合封裝“數據”，它的語義簡單，容易使用。數據抽象能簡化代碼書寫，減少偶然錯誤。