分配器

在 C++ 編程中，**分配器**（英語：allocator）是 C++ 標準庫的重要組成部分。C++ 的庫中定義了多種被統稱為「容器」的資料結構（如連結串列、集合等），這些容器的共同特徵之一，就是其大小可以在程式的執行時改變；為了實現這一點，進行動態記憶體分配就顯得尤為必要，在此分配器就用於處理容器對記憶體的分配與釋放請求。換句話說，分配器用於封裝標準模板庫（STL）容器在記憶體管理上的低層細節。預設情況下，C++ 標準庫使用其內建的通用分配器，但根據具體需要，程式設計師也可自行客製化分配器以替代之。

分配器最早由亞歷山大・斯特潘諾夫作為 C++ 標準模板庫（Standard Template Library，簡稱 STL）的一部分發明，其初衷是創造一種能「使庫更加靈活，並能獨立於底層資料模型的方法」，並允許程式設計師在庫中利用自訂的指標和參照類型；但在將標準模板庫納入 C++ 標準時，C++ 標準委員會意識到對資料模型的完全抽象化處理會帶來不可接受的效能損耗，為作折中，標準中對分配器的限制變得更加嚴格，而有鑑於此，與斯特潘諾夫原先的設想相比，現有標準所描述的分配器可客製化程度已大大受限。

雖然分配器的客製化有所限制，但在許多情況下，仍需要用到自訂的分配器，而這一般是為封裝對不同類型記憶體空間（如共享記憶體與已回收記憶體）的存取方式，或在使用記憶體池進行記憶體分配時提高效能而為。除此以外，從記憶體占用和執行時間的角度看，在頻繁進行少量記憶體分配的程式中，若引入為之專門客製化的分配器，也會獲益良多。

## 背景

亞歷山大・斯特潘諾夫與李夢（Meng Lee）在 1994 年將標準模板庫草案提交給 C++ 標準委員會。提交伊始，草案就得到了委員會的初步支援，但委員會成員也對此提出了一些意見，尤其是要求斯特潘諾夫客製化庫內的容器，使之與底層儲存模型相獨立。作為對要求的回應，斯特潘諾夫發明了分配器，而正因此，標準模板庫的所有容器介面也被迫重寫，以與分配器相容。在修改標準模板庫以將之引入 C++ 標準庫的過程中，許多標準委員會成員（如安德魯・克尼格與比雅尼・史特勞斯特魯普）也與斯特潘諾夫協同工作。他們亦發現自訂分配器甚至有應用於長生命周期（持續儲存）的標準模板庫容器的潛力，斯特潘諾夫對此的評論則是「重要而有趣的見解」。

在原有的提案里的分配器設定中，斯特潘諾夫雜糅了一些語言特性（如可將模板參數也定義為模板），但由於當時的編譯器皆無法處理之，所以最終並未被標準委員會所接納，斯特潘諾夫則如此描述當時的情形：「比雅尼・史特勞斯特魯普與安迪・克尼格需要花大量時間來檢查我們是否正確使用了這些未實現的特性。」在分配器應用後，之前庫中直接使用的指標與參照類型也可以分配器所定義的類型替代，斯特潘諾夫亦曾如此描述分配器：「標準模板庫有個不錯的特性便是：唯一要提及機器相關類型的地方（……）（只需）被封裝成（僅）約 16 行內的代碼。」除此以外，斯特潘諾夫原本還打算在分配器中完全封裝儲存模型，但標準委員會意識到這一做法會造成無法接受的效能損失，因而為補償之，分配器的使用需求也做了一定擴充。

分配器的應用中比較特別的一點是，容器的實現過程中可能會假定分配器對指標與相關整型的類型定義與預設分配器所提供的等價，因而給定分配器類型的所有實例在比較時常會得出「相等」的結果，而這一效果實際上恰與設計分配器的初衷背道而馳，並使帶狀態分配器的可用性大大受限，斯特潘諾夫後來對此評論道：「（分配器）理論上說是不差的主意（……）但不幸的是在實踐中無法發揮其功效。「他洞察到若要令分配器更加實用，就有必要針對核心語言的參照部分進行修改。

## 使用需求

任意滿足分配器使用需求的 C++ 類別都可作分配器使用。具體來說，當一個類別（在此設為類別 A）有為一個特定類型（在此設為類型 T）的物件分配記憶體的能力時，該類別就必須提供以下類型的定義：

* A::pointer 指標
* A::const\_pointer 常數指標
* A::reference 參照
* A::const\_reference 常數參照
* A::value\_type 值類型
* A::size\_type 所用記憶體大小的類型，表示類別 A 所定義的分配模型中的單個物件最大尺寸的無符號整型
* A::difference\_type 指標差值的類型，為帶符號整型，用於表示分配模型內的兩個指標的差異值。

如此才能以通用的方式聲明物件與對該類物件的參照 T。allocator 提供這些指標或參照的類型定義的初衷，是隱蔽指標或參照的物理實現細節；因為在 16 位元編程時代，_遠指標_（far pointer）是與普通指標非常不同的，allocator 可以定義一些結構來表示這些指標或參照，而容器類使用者不需要了解其是如何實現的。

雖然按照標準，在庫的實現過程中允許假定分配器（類別）A 的 A::pointer（指標）與 A::const\_pointer（常數指標）即是對 T\* 與 T const\* 的簡單的類型定義，但一般更鼓勵支援通用分配器。

另外，設有對於為某一物件類型 T 所設定的分配器 A，則 A 必須包含四項成員函式，分別為分配函式、解除分配函式、最大個數函式和位址函式：

* A::pointer A::allocate(size\_type n, A<void>::const\_pointer hint = 0)。分配函式用以進行記憶體分配。其中呼叫參數 n 即為需要分配的物件個數，另一呼叫參數 hint（須為指向已為 A 所分配的某一物件的指標）則為可選參數，可用於在分配過程中指定新陣列所在的記憶體位址，以提高參照局部性，但在實際的分配過程中程式也可以根據情況自動忽略掉該參數。該函式呼叫時會返回指向分配所得的新陣列的第一個元素的指標，而這一陣列的大小足以容納 n 個 T 類別元素。在此需要注意的是，呼叫時只為此陣列分配了記憶體，而並未實際構造物件。
* void A::deallocate(A::pointer p, A::size\_type n)。解除分配函式。其中 p 為需要解除分配的物件指標（以 A::allocate 函式所返回的指標做參數），n 為物件個數，而呼叫該函式時即是將以 p 起始的 n 個元素解除分配，但同時並不會解構之。C++ 標準明確要求在呼叫 deallocate 之前，該位址空間上的物件已經被解構。
* A::max\_size()，最大個數函式。返回 A::allocate 一次呼叫所能成功分配的元素的最大個數，其返回值等價於 A::size\_type(-1) / sizeof(T) 的結果 。
* A::pointer A::address ( reference x )，位址函式。呼叫時返回一個指向 x 的指標。

除此以外，由於物件的構造 / 解構過程與分配 / 解除分配過程分別進行 ，因而分配器還需要成員函式 A::construct（建構函式）與 A::destroy（解構函式）以對物件進行構造與解構，且兩者應等價於如下函式：

以上代碼中使用了 placement new 語法，且直接呼叫了解構函式。

分配器應是可複製構造的，任舉一例，為 T 類別物件而設的分配器可由另一為 U 類別所設的分配器構造。若某分配器分配了一段儲存空間，則這段儲存空間只能由與該分配器等價的分配器解除分配。分配器還需要提供一個模板類別成員類 template <typename U> struct A::rebind { typedef A<U> other; };，以模板 (C++) 參數化的方式，借之來針對不同的資料類型取得不同的分配器。例如，若給定某一為整型（int）而設的分配器 IntAllocator，則可執行 IntAllocator::rebind<long>::other 以取得對應長整型（long）的相關分配器。實際上，stl::list<int> 實際要分配的是包含了雙向連結串列指標的 node<int>，而不是實際分配 int 類型，這是引入了 rebind 的初衷。

與分配器相關聯的 operator ==，僅當一個 allocator 分配的記憶體可以被另一個 allocator 釋放時，上述相等比較算符返回真。operator != 的返回結果與之相反。

## 自訂分配器

定義自訂分配器的主要原因之一是提升效能。利用專用的自訂分配器可以提高程式的效能，又或提高記憶體使用效率，亦或兩者兼而有之。預設分配器使用 new 運算子分配儲存空間，而這常利用 C 語言堆分配函式（malloc ()）實現。由於堆分配函式常針對偶發的記憶體大量分配作最佳化，因此在為需要一次分配大量記憶體的容器（如向量、雙端佇列）分配記憶體時，預設分配器一般效率良好。但是，對於關聯容器與雙向連結串列這類別需要頻繁分配少量記憶體的容器來說，若採用預設分配器分配記憶體，則通常效率很低。除此之外，基於 malloc () 的預設分配器還存在許多問題，諸如較差的參照局部性，以及可能造成記憶體碎片化。

有鑑於此，在這一情況下，人們常使用基於記憶體池的分配器來解決頻繁少量分配問題。與預設的「按需分配」方式不同，在使用基於記憶體池的分配器時，程式會預先為之分配大塊記憶體（即「記憶體池」），而後在需要分配記憶體時，自訂分配器只需向請求方返回一個指向池內記憶體的指標即可；而在物件解構時，並不需實際解除分配記憶體，而是延遲到記憶體池的生命周期完結時才真正解除分配。

在「自訂分配器」這一話題上，已有諸多 C++ 專家與相關作者參與探討，例如斯科特・梅耶斯的作品《Effective STL》與安德烈・亞歷山德雷斯庫的《Modern C++ Design》都有提及。梅耶斯洞察到，若要求針對某一類型 T 的分配器的所有實例都相等，則可移植的分配器的實例必須不包含狀態。雖然 C++ 標準鼓勵庫的實現者支援帶狀態的分配器，但梅耶斯稱，相關段落是「（看似）美妙的觀點」，但也幾乎是空話，並稱分配器的限制「過於嚴苛」。例如，STL 的 list 允許 splice 方法，即一個 list 物件 A 的節點可以被直接移入另一個 list 物件 B 中，這就要求 A 的分配器申請到的記憶體，可被 B 的分配器釋放掉，從而推導出 A 與 B 的分配器實例必須相等。梅耶斯的結論是，分配器最好定義為使用靜態方法的類型。例如，根據 C++ 標準，分配器必須提供一個實現了 rebind 方法的 other 類別模板。

另外，在《C++ 程式設計語言》中，比雅尼・史特勞斯特魯普則認為「『嚴格限制分配器，以免各物件資訊不同』，這點顯然問題不大」（大意），並指出大部分分配器並不需要狀態，甚至沒有狀態情形下效能反倒更佳。他提出了三個自訂分配器的用例：記憶體池型的分配器、共享記憶體型分配器與垃圾回收型分配器，並展示了一個分配器的實現，此間利用了一個內部記憶體池，以快速分配 / 解除分配少量記憶體。但他也提到，如此最佳化可能已經在他所提供的樣例分配器中實現。

自訂分配器的另一用途是除錯記憶體相關錯誤。若要做到這一點，可以編寫一個分配器，令之在分配時分配額外的記憶體，並藉此存放除錯資訊。這類分配器不僅可以保證記憶體由同類別分配器分配 / 解除分配記憶體，還可在一定程度上保護程式免受緩衝區溢位之害。

### 使用方法

當初始化標準容器時，若需使用自訂分配器，則可將其寫入模板參數，以代替預設的 std::allocator<T>，如下所示：

正如其他所有 C++ 類別模板般，在初始化同一標準庫容器時，若使用了不同的分配器，則所生成容器的類型亦不同。譬如，若函式需一整型向量陣列 std::vector<int>作為參數，則其只能接受由預設分配器生成的整型向量陣列。

### C++11

通過加入「作用域」分配器，C++11 標準進一步強化了分配器介面，從而保證帶有巢狀式記憶體分配特點的容器（如字串向量陣列等）所分配到的記憶體皆來自容器自身的分配器。

另外，C++11 標準刪除了「給定類型的分配器在比較時總是相等」的模稜兩可的要求，使帶狀態分配器不僅實用性得到提升，而且可管理行程外的共享記憶體。現今分配器的作用多為讓程式設計師可以控制容器的記憶體分配，而非適應基底硬體的位址模型。事實上，C++11 標準刪去了分配器「自適應位址模型」的功能，結果抹消了其設計初衷。

## 注釋

## 參考資料

### 標準文件

* ISO/IEC 14882:2003(E): Programming Languages - C++. ISO/IEC. 2003.

## 外部連結

* 分配器（STL） （頁面存檔備份，存於網際網路檔案館）, CodeGuru
* C++ 標準分配器：介紹與實現 （頁面存檔備份，存於網際網路檔案館）, CodeProject
* 基於 malloc () 的分配器實現樣例 （頁面存檔備份，存於網際網路檔案館）, Dr. Dobb's Journal