什麼是數據抽象
數據抽象(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++ 工程實踐(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++ 的。
兩個程序使用了相同的算法。
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;
}
圖形學中的三維齊次坐標 Vector4 和對應的 4x4 變換矩陣 Matrix4
金融領域中經常成對出現的“買入價/賣出價”，可以封裝為 BidOffer struct，這個 struct 的成員可以有 mid() “中間價”，spread() “買賣差價”，加減操作符，等等。
小結
數據抽象是C++的重要抽象手段，適合封裝“數據”，它的語義簡單，容易使用。數據抽象能簡化代碼書寫，減少偶然錯誤。
