# [36] 序列化與反序列化 ## FAQs in section [36]: * [36.1]“序列化”是什么東東？ * [36.2] 如何選擇最好的序列化技術？ * [36.3] 如何決定是要序列化為可讀的（“文本”）還是不可讀的（“二進制”）格式？ or non-human-readable ("binary") format?") * [36.4] 如何序列化/反序列化數字，字符，字符串等簡單類型？ * [36.5] 如何讀/寫簡單類型為可讀的（“文本”）格式？ format?") * [36.6] 如何讀/寫簡單類型為非可讀的（“二進制”）格式？ format?") * [36.7] 如何序列化沒有繼承層次結構的對象，并且該對象不包含指向其他對象的指針？ * [36.8] 如何序列化有繼承層次結構的對象 ， 并且該對象不包含指向其他對象的指針？ * [36.9] 我如何序列化包含指向其他對象指針的對象，但這些指針是沒有回路和鏈接的樹形結構？ * [36.10] 我如何序列化包含指向其他對象指針的對象，這些指針是沒有回路，但是有平凡鏈接的樹形結構？ * [36.11] 我如何序列化包含指向其他對象指針的對象，這些指針是可能含有回路或者非平凡鏈接的圖？ * [36.12] 序列化/ 反序列化對象的時候有什么注意事項？ * [36.13] 什么是圖，樹，節點，回路，鏈接，葉鏈接與內部節點鏈接？ ## 36.1 “序列化”是什么東東？ 它可以讓你把一個對象或組對象存儲在磁盤；或通過有線或無線傳輸到另一臺計算機，然后通過反向過程：喚醒原始的對象。基本機制是把對象扁平化(flatten)為一維的字節流，然后把字節流再變成原始的對象。 .如同星際迷航中的運輸機，把復雜的東西扁平化為1和0的序列，然后把1和0的序列（可能在另一個地方，另一個時間）重新構造為原有的復雜“東西”。 ## 36.2 如何選擇最好的序列化技術？ 有很多很多的條件限制，實際上，涉及到技術整體連貫性的多個方面。因為我時間有限（翻譯：我沒有報酬），我將之簡化為“使用人類可讀的（“文本”）或者非人類可讀的（“二進制“）格式”，由或多或少按照技術成熟度排序的5個小技巧組成。 當然，不局限于上述五技術。你可能會想最終混合的幾種技術。當然你也可以隨時使用比實際需求更復雜（編號更高）的技術。事實上，使用比實際需求更復雜的技術是明智的，如果你認為未來的式樣變更需要更大的復雜度。所以，這份名單僅僅是一個很好的起點。 最好準備！有許多東東在這里呢！ 1. 決定使用人類可讀的（“文本”）還是非可讀（“二進制”）格式 or non-human-readable ("binary") format?")。折中很困難。后面的FAQ會告訴 如何序列化簡單類型為文本格式 format?")和 如何編寫簡單類型的二進制格式 format?")。 2. 使用最簡單的解決方案，當序列化對象不是繼承層次結構的一部分（也就是說，當他們都派生自同一個類）和不包含指向其他對象指針的時候。 3. 使用較簡單的解決方案，當序列化對象是繼承層次結構的一部分，但是不包含指向其他對象的指針的時候。 4. 使用第三級復雜的解決方案 ，當序列化對象包含指向其他對象指針的對象，但這些指針是沒有回路和鏈接的樹形結構的時候。 5. 使用第四級復雜的解決方案， 當序列化對象包含指向其他對象指針的對象，但這些指針是沒有回路，只有葉子鏈接的圖的時候。 6. 使用最復雜的解決方案，當 序列化對象包含指向其他對象指針的對象，這些指針是可能含有回路或者鏈接的圖的時候。 下面是同樣的信息，但是使用算法格式： 1. 第一步是要決定使用文本還是二進制格式。 2. 如果對象不是繼承層次結構的一部分，不包含指針， 那么使用解決方案#1 。 3. 否則，如果對象不包含指向其他對象的指針， 那么使用解決方案#2 。 4. 否則，如果指針的圖不包含回路和鏈接，那么使用解決方案#3。 5. 否則，如果指針的圖不包含循序，并且鏈接是葉子鏈接，那么使用解決方案#4。 6. 否則，使用解決方案#5。 記住：可以隨意混合/增加上述列表，如果你能夠判斷使用更復雜的技術可以讓額外成本最小。 還有一件事：對象繼承和對象含有指針在邏輯上是不相關的，因此#2比#3-5簡單并沒有任何理論依據。然而在實踐中常常（并不總是）總是這樣。所以請不要認為這些分類是金科玉律—在某種程度上他們有些武斷，你可能需要混合的這些解決方案以滿足你的具體情況。序列化技術領域遠非幾個問題和解答能解決的。 ## 36.3 如何決定是要序列化為可讀的（“文本”）還是不可讀的（“二進制”）格式？ 要小心。 這個問題沒有“正確”回答，它取決于你的目標。下面是人類可讀（“文本”） 與非人類可讀的（“二進制”）格式的一些利弊： * **文本格式**是比較容易檢查。這意味著你將不必編寫額外的工具來調試輸入和輸出，你可以使用文本編輯器打開序列化輸出，來檢查輸出內容是否正確。 * **二進制格式**使用較少的CPU周期。但是，這種相關僅僅當你的應用程序是與CPU綁定，并且序列化和/或反序列化是在一個內部循環和bottleneck之中。記住：90％的CPU時間花費在10%的代碼中，這意味著這將不會有任何實際意義，除非你 “CPU”使用量總是100％，你的序列化和/或反序列化代碼僅僅花費100％的一小部分。 * **文本格式**不用擔心一些編程問題，例如sizeof、小印第安編碼與大印第安編碼。 * **二進制格式**不用擔心相鄰值的分隔符，因為許多值具有固定長度。 * **文本格式**可以生成更小的結果集，當大多數數值很小和你需要文本化二進制編碼的時候，例如uuencode的或Base64。 * **二進制格式**可以生成更小的結果集，當大多數數值很大或不需要文本化二進制編碼的時候。 你也許會有補充添加其他的優缺點…重要的是要知道一鞋難合眾人腳-請作出自己慎重決定。 還有：無論你如何選擇，你要在每個文件/流的開頭加上“magic”標簽和版本號。版本號將顯示格式規則。這樣，如果你決定對格式做重大改變的時候，將仍然可以讀取舊的軟件產生的輸出。 ## 36.4 如何序列化/反序列化數字，字符，字符串等簡單類型？ 答案取決于使用人類可讀（“文本”）還是非格式人類可讀（“二進制”）格式的決定： * 下面是如何讀/寫簡單類型為可讀的（“文本”）格式。 * 下面是如何讀/寫簡單類型為非可讀的（“二進制”）格式。 在本節幾乎所有的其他FAQ中都需要上述FAQ中的討論作為基礎。 ## 36.5 如何讀/寫簡單類型為可讀的（“文本”）格式？ 閱讀之前，請確保要評估人類可讀和非人類可讀的格式之間的平衡。這種均衡評估是非常重要的，所以不能因為上一個項目沒有這么做而下意識地抵制它—一鞋難合眾人腳。 如果你已明確決定使用人類可讀（“文本”）格式，你應該記住這些要點： * 你最好使用`iostream`的`>>`和`<<`，而不是它的`read()`和`write()`方法。`>>`和`<<`比較適合文本模式，而`read()`和`write()`則更適合二進制模式。 * 當儲存數值時，你需要添加分隔符，以防止數值連在一起。一個簡單的方法是在每個數字之前添加一個空格（` `），這一數字1和數字2不會連在一起看起來像數值12。由于前導空格自動會被`>>`操作符忽略，你不需要顯示的處理空格當讀入序列化的結果的時候。 * 字符串需要一些訣竅，因為你必須明確地知道什么時候該字符串結束。你不能明確地使用`'\n'`或`'”'`甚至`'\ 0'`來終止所有字符串，因為一些字符串可能包含這些字符。你要使用C++字符轉義序列，例如，當你看到一個新行時寫`'\ '`接著`'n'`等等。做了這個轉換之后，你可以輸出字符串一直到行尾（這意味著它們使用`'\n'`分割），也可以以`'”'`來分割字符串。 * 如果對于字符串你使用C++字符轉義序列，對于16進制數一定要始終`'\x'`和`'\u'`之后使用相同的位數。我通常分別使用2為和4位。原因：如果你寫入的十六進制數值較少，假如你只是使用`stream` `<<` `"\\x"` `<<` `hex` `<<` `unsigned(theChar)`，當字符串中的下一個字符碰巧是十六進制數位時就會得到錯誤的結果。例如，如果字符串包含`'\F'`之后是`’A’`，那么你應該寫入`“\x0FA”`而不是`“\xFA”`。 * 對于像`”\n”`的字符，如果你不使用字符序轉義序列，那么請確保操作系統不會攪亂你的字符串數據。特別是，如果你打開一個沒有`std::ios::binary`的`std::fstream`時候，有的操作系統將會企圖翻譯行結束字符。 * 處理字符串數據的另一個方法是在字符串前面添加長度前綴，例如，寫入“`now is the time`”為”`15:now is the time`” 。請注意，這可能使人很難讀/寫文件，因為長度值之后可能會有不可見的分隔字符。盡管這樣這種方法也很有用。 請記住，這些是在本節中的其他FAQ中需要的一些基礎知識。 ## 36.6 如何讀/寫簡單類型為非可讀的（“二進制”）格式？ 閱讀之前，請確保要評估人類可讀和非人類可讀的格式之間的平衡。這種均衡評估是非常重要的，所以不能因為上一個項目沒有這么做而下意識地抵制它—一鞋難合眾人腳。 如果你已明確決定使用非人類可讀（“文本”）格式，你應該記住這些要點： * 請確保打開輸入和輸出流時使用`std::ios::binary`。即使在Unix系統也需要這么做，因為它很容易做到并且它說明了你的意圖，它也更容易移植和修改。 * 你最好使用的`iostream`的`read()`和`write()`方法而不是它的`>>`和`<<`運算符。 `read()`和`write()`更適合二進制模式，`>>`和`<<`更適合文本模式。 * 如果二進制數據有可能被另外一臺電腦讀取，必須小心不同的計算機上的印第安編碼問題（小印第安編碼與大印第安編碼）和`sizeof`問題。最簡單的處理方法是，選定一種編碼作為正式的“網絡”格式，并創建一個包含依賴計算機實現的頭文件（我通常稱之為`machine.h`）。該頭文件應該定義諸如`readNetworkInt`這樣的內聯函數（`std::istream& istr`）來讀“網絡 `int`”類型。對于其他所有的基本類型，都要定義相應的函數。你可以以任何你想要的方式來定義這些類型的格式。例如，你可以定義一個“網絡 `int` ”類型為32位的小印第安編碼格式。在任何情況下，`machine.h`內的函數將做任何必要的印第安編碼轉換，`sizeof`轉換等等。你要么對每臺機器定義不同的`machine.h`，要么在`machine.h`格式中使用# `ifdef`宏。但無論如何，所有這些丑陋的編碼將被放置在一個頭文件，所有其余代碼將會變得很清晰。注：浮點數誤差的處理是最微妙最棘手的。可以做到，但你必須小心像`NaN`，緩沖區向上溢出和向下溢出，尾數的位數和指數等。 * 如果空間成本是個問題的話，例如你要儲存序列化數據到一個小存儲設備的或通過慢速鏈接發送序列化數據，你可以壓縮流和/或你可以使用一些小技巧。最簡單的是使用最少的字節存儲小的數值。例如，要在只有有8位字節的流中存儲無符號整數，你可以劫持每個字節的第8位，來判斷是否有另一個字節。.這意味著你可以存儲0 ... 127在1個字節，128 ... 16384在2個字節等等。如果平均值小于500，000，000左右，這比使用4字節存儲無符號數。對于這一問題有許多其他演變方式，例如，對于排序的數值數組可以存儲每個數值之差，存儲極小值為unary格式等等。 * 字符串數據是棘手的，因為你必須明確地知道什么時候該字符串的本身結束。你不能明確地使用`'\ 0'`來結束所有字符串，回想一下`std::string`可以存儲`'\0'`字符。最簡單的方法是在字符串之前寫入字符串長度。確保整形長度是“網絡格式”，這樣可以避免`sizeo`f和印第安編碼問題（參見前一帖的解決方案）。 請記住，這些是在本節中的其他FAQ中需要的一些基礎知識。 ## 36.7 如何序列化沒有繼承層次結構的對象，并且該對象不包含指向其他對象的指針？ 這是最簡單的問題，毫不奇怪它也最容易解決： * 每個類應處理好自己的序列化和反序列化。你通常會創建一個成員函數，把對象序列化到存儲體（如`std::ostream`），另一個成員函數來生成一個新的對象，或者修改現有對象，讀取數據源（如一個`std::IStream`）并設置對象的成員。 * 如果你的對象本身包含另一個對象，例如一個`Car`對象可能有一個類型為`Engine`的成員變量，外層對象的`serialize()`成員函數應該簡單地調用成員變量的相應函數來序列化。 * 使用前面描述的基本知識來以文本或者二進制格式來讀/寫簡單類型或二進制 格式。 * 如果一個類的數據結構將來可能發生變化，在對象的序列化輸出的開頭類應該輸出一個版本號。版本號僅僅代表序列化的格式 ，不應該遞增類的版本號如果只是類的行為發生了變化。 就是說，該版本數字并不需要太花哨-通常不需要主版本號和次版本號。 ## 36.8 如何序列化有繼承層次結構的對象 ， 并且該對象不包含指向其他對象的指針？ 假設你要序列化`shape`對象，其中shape是一個抽象類，它的派生類有`Rectangle`, `Ellipse`, `Line`, `Text`, etc等。在shape類中你將聲明一個純虛函數`serialize(std:: ostream&) const`，并確保每個重寫首先會輸出類的身份。例如，`Ellipse::serialize(std::ostream&) const`會輸出`Ellipse`的標識符（可能只是一個簡單的字符串，但也可以是下文討論的幾種方案）。 當反序列化對象時，事情有點棘手。通常首先從基類的靜態成員函數如`Shape::unserialize(std::istream& istr)開始`。這是聲明返回一個 `Shape *`或可能是像`shape::Ptr`的智能指針。它讀取類名標識符 ，然后使用某些創建模式來創建對象。例如，你可能有類名到對象的映射表，然后使用虛擬構造函數用法來創建對象。 這里有一個具體的例子：在基類`shape`內添加一個純虛函數`create(std::istream&) const`，并定義只有一行的重寫函數，來生成一個適當的派生類對象。例如，`Ellipse::create(std::istream& istr) const`將是`{ return new Ellipse(istr); }`。 添加一個`static` `std::map<std::string,Shape*>`對象，映射類名到一個對應類的代表（又名原型 ）對象，例如，`Ellipse`將映射到`new Ellipse()`。函數`Shape::unserialize(std::istream& istr)` 將讀取類名，然后查找關聯的`Shape*`并調用它的`create()`方法：`return theMap[className]->create(istr)，`如果類名不再映射表里則拋出一個異常(`if (theMap.count(className) == 0) throw ...something...`)。 映射表通常采用靜態初始化。例如，如果文件`Ellipse.cpp`包含了派生類`Ellipse`的代碼，它還將包含一個靜態的對象，其構造函數將類添加到映射表：`theMap["Ellipse"] = new Ellipse()`。 說明和注意事項： * 如果`Shape::unserialize()傳`遞類名到`create()`會增加一些彈性。特別是，這將讓派生類可以使用兩個或兩個以上的類名，每個都有自己的“網絡”格式。例如，派生類`Ellipse`可以被傳遞“`Ellipse`”和“`Circle`”，這有益于輸出時節省空間或者另有其他原因。 * 在序列化過程中通過拋出異常來處理錯誤通常是最容易的。如果你想你可以返回 `NULL`，但你需要把讀取輸入流的代碼從派生類的構造函數到相應的`create()`方法中，最終結果往往是你的代碼變得更復雜。 * 你必須小心`Shape::unserialize()`所使用的映射表，避免靜態初始化順序錯誤。這通常意味著對于映射表要使用初次使用時進行初始化的手法。 * 對于由`Shape::unserialize()`所使用的映射表，我個人更喜歡基于虛構造函數手法的命名構造函數手法-—它能簡化一些步驟。詳細信息：我通常會在`shape`內定`typedef`，例如`typedef Shape* (*Factory)(std::istream&)`。這意味著`Shape::Factory`是一個函數指針，它接受`std::istream&`為參數并返回一個`shape*`。然后，我定義映射表為`std::map<std::string,Factory>`。最后，我使用類似`theMap"Ellipse"] = Ellipse::create`代碼來生成映射表（其中`Ellipse::create(std::istream&`）是一個`Ellipse`類的靜態成員函數，即命名構造函數用法）。你可能需要把`Shape::unserialize(std::istream& istr)`函數的返回值從`theMap[className]->create(istr)`變為`theMap[className](istr)。` * 序列化一個 `NULL`指針通常很容易，因為你已經輸出了類標識符，你可以很容易地輸出一個偽類標識符，比如`NULL`。你可能在`Shape::unserialize()`中需要一個額外`if`語句 ，但是如果使用我上面的寫法的話，你可以消除這種特殊情況（通常可以保持代碼干凈整齊）通過定義一個靜態成員函數`Shape* Shape::nullFactory(istream&) { return NULL; }`。你也需要和其他的類一樣把`NULL`加入到映射表：`theMap["NULL"] = Shape::nullFactory;`。 * 如果標記類名的話，序列化形式可能會更小更快一些。例如，僅在第一次看到一個類名的時候寫一個類名，在以后使用時只使用相應的整數索引。如`std::map<std::string,unsigned> unique`將使之變得簡單：如果一個類名已經在映射表里，只用寫`unique[className]`；否則設置一個變量`unsigned n = unique.size()`,寫`n`，寫類名，并設置`unique[className] = n`。（注： 一定要復制到一個單獨的變量，不要使用`unique[className] = unique.size()`！別怪我沒警告你！）。當反序列化的時候， 使用`std::vector<std::string> unique`，讀出 `n`，如果 `n == unique.size()`，讀出類名并將其添加到`vector` 。無論哪種方式類名都是`unique[n]`。您還可以預先填充前 `N`個最常見的類名，這樣流就不需要包含任何字符串。 ## 36.9 我如何序列化包含指向其他對象指針的對象，但這些指針是沒有回路和鏈接的樹形結構？ 開始之前，你必須明白，“樹”并不意味著對象存儲在數據結構的樹中。它只是意味著你的對象互相指向對方。沒有回路是指，如果不斷地從一個對象指針跟隨到下一個對象，你永遠不會回到一個較早的對象。你的對象不是在樹的內部，它們是一棵“樹”。如果你不理解這些話，在繼續之前你應該閱讀行話FAQ。 第二，如果圖將來可能包含回路或者鏈接不要使用此技術。 既無回路也無鏈接的圖非常常見，即使像組合或者修飾樣的“遞歸組合”設計模式。例如，表示XML文檔或HTML文檔的對象可以表示為一個沒有回路和鏈接的圖。 序列化圖的關鍵是忽視節點的身份 ，但注重其內容 。算法（通常遞歸）遍歷樹并且不斷地輸出其內容。例如，如果當前節點恰好有一個整數a，指針B，浮點數c和另一個指針d，那么你先輸出整數 a， 然后遞歸遍歷b指向的子節點，然后輸出浮點數 c，最后遞歸遍歷d指向的子節點 。 （你不必以聲明順序來進行序列化/反序列化，唯一的規則是，序列化和反序列化的順序要一致。） 反序列化時你需要一個構造函數以std::istream＆為參數。上述對象的構造函數將讀入一個整數并存儲結果到a中，然后分配一個對象存儲在指針b中（需要傳遞std::istream到對象的構造函數中，然它也可以讀取流的內容）， 讀入一個浮點數到c，最后將分配一個對象存儲在指針d中 。一定要在對象中使用智能指針，否則，如果任何序列化拋出異常的話(除了第一個指針象之外)，將會出現內存泄露。 當創建對象的時候，使用命名構造函數慣用法很方便。這樣做的好處是可以強制使用的智能指針。要在類 Foo中實現這一點，需要添加一個如`FooPtr Foo::create(std::istream& istr) { return new Foo(istr); }` 的靜態方法。（其中`FooPtr`是一個指向`Foo`的只能指針 ）。警覺的讀者會注意到這與以前FAQ討論的技術很相像 -這兩種技術是完全兼容的。 如果一個對象包含可變數目的子對象，例如， 一個`std::vector`類型的指針，通常的做法是在遞歸之前輸出子對象的數目。當反序列化時，只需要讀入子對象的數目 , 然后就可以使用一個循環來創建適當數量的子對象。 如果一個子對象有可能是 `NULL`指針，一定要在序列化和反序列化時候做處理。這不應該是一個問題， 如果對象使用繼承 ；詳情見上面的解決方案。 否則，如果第一個序列化的成員有一個已知的范圍，使用范圍以外的東西來表示一個`NULL`指針。例如，如果一個序列化對象的第一個成員總是一個數字，那就使用比如`N`這樣的非數字來表示一個 `NULL`指針。反序列化是偶可以使用`std::istream::peek()`來檢查`'n`'標簽。如果第一個成員沒有范圍，那就強加一個范圍，例如，每個對象之前總是輸出`'×'`，然后使用`’y’`來表示`NULL`。 如果一個對象內部本身包含另一個對象，而不是包含指向其他對象的指針，這與上述做法沒有什么兩樣：你仍然需要遞歸子節點，就好像是通過指針一樣。 ## 36.10 我如何序列化包含指向其他對象指針的對象，這些指針是沒有回路，但是有平凡鏈接的樹形結構？ 和之前一樣，“樹”并不意味著對象存儲在數據結構的樹中。它只是意味著你的對象互相指向對方。沒有回路是指，如果不斷地從一個對象指針跟隨到下一個對象，你永遠不會回到一個較早的對象。你的對象不是在樹的內部，它們是一棵“樹”。如果你不理解這些話，在繼續之前你應該閱讀行話FAQ。 如果圖包含葉節點的鏈接，但這些鏈接可以很容易地通過一個簡單的查找表重建，那么使用此解決方案。舉例來說，像`(3*(a+b) - 1/a)`樣的算術表達式的解析樹可能會有鏈接，因為變量名稱（如`a`）出現不止一次。如果你想讓圖使用完全相同的節點對象來表示該變量的兩次出現，那么你可以可能需要這種解決方案。 雖然上述限制，不適合于那些沒有任何鏈接的解決方案。但是它是如此的接近，因此你可以想辦法套用那個解決方案。差異是： * 序列化時候，完全忽視鏈接。 * 反序列化時候，創建一個查找表， 比如`std::map<std::string,Node*>`，映射變量名稱到相關的節點。 警告：這里假設變量a的所有出現應該映射到同一個節點對象；如果情況比這復雜，即如果一部分a映射到一個對象，另一些部分映射到另一個對象，你可能需要使用一個更復雜的解決方案。 ## 36.11 我如何序列化包含指向其他對象指針的對象，這些指針是可能含有回路或者非平凡鏈接的圖？ 警告：術語“樹”并不意味著對象存儲在數據結構的樹中。它只是意味著你的對象互相指向對方。沒有回路是指，如果不斷地從一個對象指針跟隨到下一個對象，你永遠不會回到一個較早的對象。你的對象不是在樹的內部，它們是一棵“樹”。如果你不理解這些話，在繼續之前你應該閱讀行話FAQ。 如果圖包含回路，或者包含比平凡鏈接解決方案中更復雜的鏈接，那么使用此解決方案。該解決方案處理的兩個核心問題：它避免了無限循環，除了節點的內容之外還寫入/讀取每個節點的身份 。 一個節點的身份在不同的輸出流中通常不會一致。例如，如果某個文件使用數字3代表節點 `x`，一個不同的文件可以使用數字3代表一個不同的節點`y` 。 有一些巧妙的方法來序列化這種圖，但最容易描述的是兩階段(two-pass)算法，該算法使用一個對象的ID映射表 ，例如`std::map<Node*,unsigned> oidMap`。在第一階段設置`oidMap`，也就是說，它構建一個對象指針到對象整數ID的映射。 通過遞歸圖，在每個節點檢查該節點是否已經在`oidMap`，如果沒有在`oidMap`中，就添加節點和一個唯一的整數ID到oidMap，然后遞歸新的子節點。唯一的整數ID通常取`oidMap.size()`，如`unsigned n = oidMap.size(); oidMap[nodePtr] = n`。（是的，需要使用兩條語句。你也必須這樣做。 不要縮短為一條語句。莫怪我沒有警告你！） 第二階段遍歷`oidMap`的所有節點，并在在每個節點輸出入節點的身份（相關的整數ID）之后輸入節點內容。當輸出節點內容時候，如果包含指向其他節點的指針，不要遍歷這些子對象，只需要輸出子節點的身份（相關整數ID）。例如，當節點包含`Node* child`，只需輸出整數`oidMap[child]`。第二階段之后，該`oidMap`可以被丟棄。換句話說，節點`*`到無符號整數ID的映射通常不會活過任何給定圖的序列化結束。 也有一些巧妙的方法來反序列化這種圖，但在這里還是使用最容易描述的是兩階段(two-pass)算法。第一階段設置一個含有正確類型的`std::vector<Node*> v`對象，但所有這些對象的子指針都是`NULL`指針。這意味著`v[3]`將指向對象ID是3的對象，但該對象內部的任何子指針將都是 `NULL`指針。第二階段設置對象內部的的子指針，例如， 如果 `v [3]`有一個子指針叫`child`，應該指向對象ID是5的對象。在第二階段的將`v[3].child`從`NULL`修改為`v [5]`（顯然封裝可能禁止直接訪問`v[3].child`，但最終`v[3].child`需要被改為`v[5]`）。反序列化一個給定流之后， `vector v`通常被丟棄。換句話說，當序列化或反序列化不同的流時，對象ID（3，5等等）沒有任何意義-這些數字只在一個給定流內有意義。 注意：如果你的對象包含多態性指針（_polymorphic pointers_） ，也就是基類指針可能指向派生類對象，那么使用以前描述的技術。 你還需要閱讀的先前的關于處理`NULL`指針和版本號的一些技術。 注意：當遞歸遍歷圖的時候，你應該考慮訪問者模式。因為序列化可能只是需要做遞歸遍歷的原因之一，任何遞歸都需要避免無限循環。 ## 36.12 序列化/ 反序列化對象的時候有什么注意事項？ 除非在特殊情況下，不要在遍歷時候改變節點數據。例如，有些人覺得通過簡單地增加一個節點類的整型數據成員，他們就可以映射`Node*`到整數。有時也添加布爾型的`haveVisited`標志作為`Node`對象的另外一個數據成員。 _但是_ ，這將導致大量的多線程和/或性能問題。你的`serialize()`方法可能不能再為`const`，所以即使它在邏輯上只是讀取節點數據，盡管它在邏輯上可以有多個線程同時讀取節點，但是實際的算法卻寫入數據到節點。如果你理解線程和讀/寫沖突，你只能寄希望于你的代碼更復雜更慢（你必須阻止所有的讀取線程，只要任何線程對圖進行操作的話）。如果你(或者后繼的代碼維護者)不理解線程和讀/寫沖突，這可能引起非常嚴重和非常不容易覺察的錯誤。讀/寫和寫/寫沖突很不容易覺察，這些錯誤很難測試到。壞消息！相信我！如果你不相信我，找個你信任的人。但是切莫偷工減料！ 現在還有很多更多要說，例如一些特殊情況。但我已經花了太多時間。如果想了解更多信息，花一些錢吧。 ## 36.13 什么是圖，樹，節點，回路，鏈接，葉鏈接與內部節點鏈接？ 當你的對象包含指向其他對象的指針，你就有了一種計算機科學家稱之為_圖_的東東 。你的對象都存儲在一個像樹的數據結構里面；他們是一個像樹的數據結構。 圖的_節點_又名頂點相當于你的對象 ，圖的_邊_相當于你的對象里面的指針 。 該圖是一個樹的一個特例，稱為_帶根有向圖_。要序列化的根對象對應于圖的_根節點_ ，指針對應于_直接邊_。 如果對象 x有一個指向對象 Y的指針，我們說x是Y_雙親_ 或Y是X 的 _孩子_ 。 圖的_路徑_是指從一個對象開始，順著指針到另一個對象等等，可以是任意深度。如果存在一個從 x 到 z的路徑，我們說，x是z的祖先 和/或z是x 的 子孫。 圖的_鏈接_是指有兩個或兩個以上不同的路徑可以到達同一對象。例如， 如果 z是x和y的孩子，則圖有一個鏈接，z是一個_鏈接節點_ 。 圖的_回路__(__環__)_是指存在一個返回對象自己的路徑： 如果 x有一個指向自己的指針，或指向Y的指針，Y又指向x，或者為 Y，Y指向 z，Z又指向x等。圖是_有環的_如果有一個或多個回路，否則是_無環的_ 。 一個_內部節點_是有孩子的節點。_葉節點_是沒有孩子的節點。 正如本節中使用的那樣，_樹_是指一個_帶根的，有向的，無環圖_。請注意，樹的節點也是樹。