分配器 (C++)
在C++編程中，分配器（英語：allocator）是C++標準庫的重要組成部分。C++的庫中定義了多種被統稱為「容器」的資料結構（如鏈結串列、集合等），這些容器的共同特徵之一，就是其大小可以在程式的執行時改變；為了實現這一點，進行動態記憶體分配就顯得尤為必要，在此分配器就用於處理容器對記憶體的分配與釋放請求。換句話說，分配器用於封裝標準模板庫（STL）容器在記憶體管理上的低層細節。預設情況下，C++標準庫使用其內建的通用分配器，但根據具體需要，程式設計師也可自行客製化分配器以替代之。
分配器最早由亞歷山大·斯特潘諾夫作為C++標準模板庫（Standard Template Library，簡稱STL）的一部分發明，其初衷是創造一種能「使庫更加靈活，並能獨立於底層資料模型的方法」，並允許程式設計師在庫中利用自訂的指標和參照類型；但在將標準模板庫納入C++標準時，C++標準委員會意識到對資料模型的完全抽象化處理會帶來不可接受的效能損耗，為作折中，標準中對分配器的限制變得更加嚴格，而有鑑於此，與斯特潘諾夫原先的設想相比，現有標準所描述的分配器可客製化程度已大大受限。
雖然分配器的客製化有所限制，但在許多情況下，仍需要用到自訂的分配器，而這一般是為封裝對不同類型記憶體空間（如共享記憶體與已回收記憶體）的訪問方式，或在使用記憶體池進行記憶體分配時提高效能而為。除此以外，從記憶體占用和執行時間的角度看，在頻繁進行少量記憶體分配的程式中，若引入為之專門客製化的分配器，也會獲益良多。
背景
[編輯]亞歷山大·斯特潘諾夫與李夢（Meng Lee）在1994年將標準模板庫草案提交給C++標準委員會[1]。提交伊始，草案就得到了委員會的初步支援，但委員會成員也對此提出了一些意見，尤其是要求斯特潘諾夫客製化庫內的容器，使之與底層儲存模型相獨立[2]。作為對要求的回應，斯特潘諾夫發明了分配器，而正因此，標準模板庫的所有容器介面也被迫重寫，以與分配器相容。在修改標準模板庫以將之引入C++標準庫的過程中，許多標準委員會成員（如安德魯·克尼格與比雅尼·史特勞斯特魯普）也與斯特潘諾夫協同工作。他們亦發現自訂分配器甚至有應用於長生命周期（持續儲存）的標準模板庫容器的潛力，斯特潘諾夫對此的評論則是「重要而有趣的見解」[2]。
| 從移植性的角度說，所有因在位址、指標等概念上有所限定而只相容特定機器的組件都應該封裝進一個輕量且易於理解的工具之中。但分配器並非標準模板庫的本質所在，且也非分解基本資料結構與演算法的關鍵。（節錄）[2] |
| ——標準模板庫的設計者亞歷山大·斯特潘諾夫 |
在原有的提案里的分配器設定中，斯特潘諾夫雜糅了一些語言特性（如可將模板參數也定義為模板），但由於當時的編譯器皆無法處理之，所以最終並未被標準委員會所接納，斯特潘諾夫則如此描述當時的情形：「比雅尼·史特勞斯特魯普與安迪·克尼格需要花大量時間來檢查我們是否正確使用了這些未實現的特性[2]。」在分配器應用後，之前庫中直接使用的指標與參照類型也可以分配器所定義的類型替代，斯特潘諾夫亦曾如此描述分配器：「標準模板庫有個不錯的特性便是：唯一要提及機器相關類型的地方（……）（只需）被封裝成（僅）約16行內的代碼[2]。」除此以外，斯特潘諾夫原本還打算在分配器中完全封裝儲存模型，但標準委員會意識到這一做法會造成無法接受的效能損失[3][4]，因而為補償之，分配器的使用需求也做了一定擴充。
分配器的應用中比較特別的一點是，容器的實現過程中可能會假定分配器對指標與相關整型的類型定義與預設分配器所提供的等價，因而給定分配器類型的所有實例在比較時常會得出「相等」的結果[文 1][文 2]，而這一效果實際上恰與設計分配器的初衷背道而馳，並使帶狀態分配器的可用性大大受限[4]，斯特潘諾夫後來對此評論道：「（分配器）理論上說是不差的主意（……）但不幸的是在實踐中無法發揮其功效。「他洞察到若要令分配器更加實用，就有必要針對核心語言的參照部分進行修改[5]。
使用需求
[編輯]任意滿足分配器使用需求的C++類別都可作分配器使用。具體來說，當一個類別（在此設為類別A）有為一個特定類型（在此設為類型T）的對象分配記憶體的能力時，該類別就必須提供以下類型的定義：
- A::pointer 指標
- A::const_pointer 常數指標
- A::reference 參照
- A::const_reference 常數參照
- A::value_type 值類型
- A::size_type 所用記憶體大小的類型，表示類別A所定義的分配模型中的單個對象最大尺寸的無符號整型
- A::difference_type 指標差值的類型，為帶符號整型，用於表示分配模型內的兩個指標的差異值[文 3]。
如此才能以通用的方式聲明對象與對該類對象的參照T。allocator提供這些指標或參照的類型定義的初衷，是隱蔽指標或參照的物理實現細節；因為在16位元編程時代，遠指標（far pointer）是與普通指標非常不同的，allocator可以定義一些結構來表示這些指標或參照，而容器類使用者不需要了解其是如何實現的。
雖然按照標準，在庫的實現過程中允許假定分配器（類別）A的A::pointer（指標）與A::const_pointer（常數指標）即是對T*與T const*的簡單的類型定義，但一般更鼓勵支援通用分配器[文 4]。
另外，設有對於為某一對象類型T所設定的分配器A，則A必須包含四項成員函式，分別為分配函式、解除分配函式、最大個數函式和位址函式：
- A::pointer A::allocate(size_type n, A<void>::const_pointer hint = 0)。分配函式用以進行記憶體分配。其中呼叫參數n即為需要分配的對象個數，另一呼叫參數hint（須為指向已為A所分配的某一對象的指標）則為可選參數，可用於在分配過程中指定新陣列所在的記憶體位址，以提高參照局部性[6]，但在實際的分配過程中程式也可以根據情況自動忽略掉該參數。該函式呼叫時會返回指向分配所得的新陣列的第一個元素的指標，而這一陣列的大小足以容納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一次呼叫所能成功分配的元素的最大個數[7]，其返回值等價於A::size_type(-1) / sizeof(T)的結果[7] 。
- A::pointer A::address ( reference x )，位址函式。呼叫時返回一個指向x的指標。
除此以外，由於對象的構造/解構過程與分配/解除分配過程分別進行[7] ，因而分配器還需要成員函式A::construct（建構函式）與A::destroy（解構函式）以對對象進行構造與解構，且兩者應等價於如下函式[文 3]：
template <typename T>
void A::construct(A::pointer p, A::const_reference t) { new ((void*) p) T(t); }
template <typename T>
void A::destroy(A::pointer p){ ((T*)p)->~T(); }
以上代碼中使用了placement new語法，且直接呼叫了解構函式。
分配器應是可複製構造的，任舉一例，為T類別對象而設的分配器可由另一為U類別所設的分配器構造。若某分配器分配了一段儲存空間，則這段儲存空間只能由與該分配器等價的分配器解除分配[文 3]。分配器還需要提供一個模板類別成員類template <typename U> struct A::rebind { typedef A<U> other; };，以模板 (C++)參數化的方式，借之來針對不同的資料類型取得不同的分配器。例如，若給定某一為整型（int）而設的分配器IntAllocator，則可執行IntAllocator::rebind<long>::other以取得對應長整型（long）的相關分配器[7]。實際上，stl::list<int>實際要分配的是包含了雙向鏈結串列指標的node<int>，而不是實際分配int類型，這是引入了rebind的初衷。
與分配器相關聯的operator ==，僅當一個allocator分配的記憶體可以被另一個allocator釋放時，上述相等比較算符返回真。operator !=的返回結果與之相反。
自訂分配器
[編輯]定義自訂分配器的主要原因之一是提升效能。利用專用的自訂分配器可以提高程式的效能，又或提高記憶體使用效率，亦或兩者兼而有之[4][8]。預設分配器使用new運算子分配儲存空間[文 5]，而這常利用C語言堆分配函式（malloc()）實現[9]。由於堆分配函式常針對偶發的記憶體大量分配作最佳化，因此在為需要一次分配大量記憶體的容器（如向量、雙端佇列）分配記憶體時，預設分配器一般效率良好[8]。但是，對於關聯容器與雙向鏈結串列這類別需要頻繁分配少量記憶體的容器來說，若採用預設分配器分配記憶體，則通常效率很低[4][9]。除此之外，基於malloc()的預設分配器還存在許多問題，諸如較差的參照局部性[4]，以及可能造成記憶體碎片化[4][9]。
| 簡言之，此段（……）（如同）是這一標準針對分配器的一場《我有一個夢想》的演講。在夢想成真之前，關心可移植性的程式設計師將把自己局限於（使用）無狀態的自訂分配器上。 |
| ——斯科特 梅耶斯，《Effective STL》 |
有鑑於此，在這一情況下，人們常使用基於記憶體池的分配器來解決頻繁少量分配問題[8]。與預設的「按需分配」方式不同，在使用基於記憶體池的分配器時，程式會預先為之分配大塊記憶體（即「記憶體池」），而後在需要分配記憶體時，自訂分配器只需向請求方返回一個指向池內記憶體的指標即可；而在對象解構時，並不需實際解除分配記憶體，而是延遲到記憶體池的生命周期完結時才真正解除分配[註 1][8]。
在「自訂分配器」這一話題上，已有諸多C++專家與相關作者參與探討，例如斯科特·梅耶斯的作品《Effective STL》與安德烈·亞歷山德雷斯庫的《Modern C++ Design》都有提及。梅耶斯洞察到，若要求針對某一類型T的分配器的所有實例都相等，則可移植的分配器的實例必須不包含狀態。雖然C++標準鼓勵庫的實現者支援帶狀態的分配器[文 4]，但梅耶斯稱，相關段落是「（看似）美妙的觀點」，但也幾乎是空話，並稱分配器的限制「過於嚴苛」[4]。例如，STL的list允許splice方法，即一個list對象A的節點可以被直接移入另一個list對象B中，這就要求A的分配器申請到的記憶體，可被B的分配器釋放掉，從而推導出A與B的分配器實例必須相等。梅耶斯的結論是，分配器最好定義為使用靜態方法的類型。例如，根據C++標準，分配器必須提供一個實現了rebind方法的other類別模板。
另外，在《C++程式設計語言》中，比雅尼·史特勞斯特魯普則認為「『嚴格限制分配器，以免各對象資訊不同』，這點顯然問題不大」（大意），並指出大部分分配器並不需要狀態，甚至沒有狀態情形下效能反倒更佳。他提出了三個自訂分配器的用例：記憶體池型的分配器、共享記憶體型分配器與垃圾回收型分配器，並展示了一個分配器的實現，此間利用了一個內部記憶體池，以快速分配/解除分配少量記憶體。但他也提到，如此最佳化可能已經在他所提供的樣例分配器中實現[3]。
自訂分配器的另一用途是除錯記憶體相關錯誤[10]。若要做到這一點，可以編寫一個分配器，令之在分配時分配額外的記憶體，並藉此存放除錯資訊。這類分配器不僅可以保證記憶體由同類別分配器分配/解除分配記憶體，還可在一定程度上保護程式免受緩衝區溢位之害[11]。
使用方法
[編輯]當初始化標準容器時，若需使用自訂分配器，則可將其寫入模板參數，以代替預設的std::allocator<T>，如下所示[文 6]：
namespace std {
template <class T, class Allocator = allocator<T> > class vector;
// ...
正如其他所有C++類別模板般，在初始化同一標準庫容器時，若使用了不同的分配器，則所生成容器的類型亦不同。譬如，若函式需一整型向量陣列std::vector<int>作為參數，則其只能接受由預設分配器生成的整型向量陣列。
C++11
[編輯]通過加入「作用域」分配器，C++11標準進一步強化了分配器介面，從而保證帶有巢狀式記憶體分配特點的容器（如字串向量陣列等）所分配到的記憶體皆來自容器自身的分配器[12]。
另外，C++11標準刪除了「給定類型的分配器在比較時總是相等」的模稜兩可的要求，使帶狀態分配器不僅實用性得到提升，而且可管理行程外的共享記憶體[13][14]。現今分配器的作用多為讓程式設計師可以控制容器的記憶體分配，而非適應基底硬體的位址模型。事實上，C++11標準刪去了分配器「自適應位址模型」的功能，結果抹消了其設計初衷[15]。
注釋
[編輯]- ^ Boost C++ Libraries內便有包含基於記憶體池的分配器的樣例。
參考資料
[編輯]- ^ Stepanov, Alexander; Meng Lee. The Standard Template Library. Presentation to the C++ standards committee (PDF). Hewlett Packard Libraries. 1994-03-07 [2009-05-12]. （原始內容存檔 (PDF)於2010-03-26）.
- ^ 2.0 2.1 2.2 2.3 2.4 Stevens, Al. Al Stevens Interviews Alex Stepanov. Dr. Dobb's Journal. 1995 [2009-05-12]. （原始內容存檔於2009-05-01）.
- ^ 3.0 3.1 Stroustrup, Bjarne. The C++ Programming Language, 3rd edition. Addison-Wesley. 1997.
- ^ 4.0 4.1 4.2 4.3 4.4 4.5 4.6 Scott Meyers. Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library. Addison-Wesley. 2001.
- ^ Lo Russo, Graziano. An Interview with A. Stepanov. www.stlport.org. 1997 [2009-05-13]. （原始內容存檔於2009-03-04）.
- ^ Langer, Angelika; Klaus Kreft. Allocator Types. C++ Report. 1998 [2009-05-13]. （原始內容存檔於2008-05-17）.
- ^ 7.0 7.1 7.2 7.3 Austern, Matthew. The Standard Librarian: What Are Allocators Good For?. Dr. Dobb's Journal. 2000-12-01 [2009-05-12]. （原始內容存檔於2012-06-06）.
- ^ 8.0 8.1 8.2 8.3 Aue, Anthony. Improving Performance with Custom Pool Allocators for STL. Dr. Dobb's Journal. 2005-09-01 [2009-05-13]. （原始內容存檔於2010-04-10）.
- ^ 9.0 9.1 9.2 Alexandrescu, Andrei. Modern C++ Design. Addison-Wesley. 2001: 352. ISBN 0-201-70431-5.
- ^ Vlasceanu, Christian. Debugging Memory Errors with Custom Allocators. Dr. Dobb's Journal. 2001-04-01 [2009-05-14]. （原始內容存檔於2012-06-09）.
- ^ Austern, Matthew. The Standard Librarian: A Debugging Allocator. Dr. Dobb's Journal. 2001-12-01 [2009-05-14]. （原始內容存檔於2012-06-09）.
- ^ Halpern, Pablo. The Scoped Allocator Model (Rev 2) (PDF). ISO. 2008-02-29 [2012-08-21]. （原始內容存檔 (PDF)於2012-06-07）.
- ^ Halpern, Pablo. Allocator-specific Swap and Move Behavior (PDF). ISO. 2008-02-04 [2012-08-21]. （原始內容存檔 (PDF)於2012-06-07）.
- ^ Halpern, Pablo. Allocators post Removal of C++ Concepts (Rev 1) (PDF). ISO. 2009-10-22 [2012-08-21]. （原始內容存檔 (PDF)於2012-06-17）.
- ^ Becker, Pete. LWG Issue 1318: N2982 removes previous allocator capabilities (closed in March, 2011). ISO. [2012-08-21]. （原始內容存檔於2012-08-16）.
標準文件
[編輯]- ^ C++03 ，§20.1.5 Allocator requirements [lib.allocator.requirements], 第4段
- ^ C++03 ，§20.4.1 The default allocator [lib.default.allocator]
- ^ 3.0 3.1 3.2 C++03 ，§20.1.5 Allocator requirements [lib.allocator.requirements], 第2段
- ^ 4.0 4.1 C++03 ，§20.1.5 Allocator requirements [lib.allocator.requirements], 第5段
- ^ C++03 ，§20.4.1.1 allocator members [lib.allocator.members], 第3段
- ^ C++03 ，§23.2 Sequences [lib.sequences], 第1段
外部連結
[編輯]- 分配器（STL） （頁面存檔備份，存於網際網路檔案館）, CodeGuru
- C++標準分配器：介紹與實現 （頁面存檔備份，存於網際網路檔案館）, CodeProject
- 基於malloc()的分配器實現樣例 （頁面存檔備份，存於網際網路檔案館）, Dr. Dobb's Journal