分配器 (C++)

這是一篇優良條目，請按此取得更多資訊。
本頁使用了標題或全文手工轉換
維基百科，自由的百科全書
分配器的發明者亞歷山大·斯特潘諾夫

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

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

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

背景

參見：標準模板庫

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

從移植性的角度說，所有因在地址、指針等概念上有所限定而只兼容特定機器的組件都應該封裝進一個輕量且易於理解的工具之中。但分配器並非標準模板庫的本質所在，且也非分解基本數據結構與算法的關鍵。（節錄）[2]
——標準模板庫的設計者亞歷山大·斯特潘諾夫

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

分配器的應用中比較特別的一點是，容器的實現過程中可能會假定分配器對指針與相關整型的類型定義與默認分配器所提供的等價，因而給定分配器類型的所有實例在比較時常會得出「相等」的結果[文 1][文 2]，而這一效果實際上恰與設計分配器的初衷背道而馳，並使帶狀態分配器的可用性大大受限[4]，斯特潘諾夫後來對此評論道：「（分配器）理論上說是不差的主意（……）但不幸的是在實踐中無法發揮其功效。「他洞察到若要令分配器更加實用，就有必要針對核心語言的引用（英語：Reference (C++)）部分進行修改[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]。但是，對於關聯容器（英語：Associative containers (C++)）與雙向鍊表這類別需要頻繁分配少量內存的容器來說，若採用默認分配器分配內存，則通常效率很低[4][9]。除此之外，基於malloc()的默認分配器還存在許多問題，諸如較差的引用局部性[4]，以及可能造成內存碎片化（英語：fragmentation (computer)）[4][9]。

簡言之，此段（……）（如同）是這一標準針對分配器的一場《我有一個夢想》的演講。在夢想成真之前，關心可移植性的程序員將把自己局限於（使用）無狀態的自定義分配器上。
——斯科特 梅耶斯，《Effective STL》

有鑑於此，在這一情況下，人們常使用基於內存池的分配器來解決頻繁少量分配問題[8]。與默認的「按需分配」方式不同，在使用基於內存池的分配器時，程序會預先為之分配大塊內存（即「內存池」），而後在需要分配內存時，自定義分配器只需向請求方返回一個指向池內內存的指針即可；而在對象析構時，並不需實際解除分配內存，而是延遲到內存池的生命周期完結時才真正解除分配[註 1][8]。

在「自定義分配器」這一話題上，已有諸多C++專家與相關作者參與探討，例如斯科特·梅耶斯的作品《Effective STL》與安德烈·亞歷山德雷斯庫的《Modern C++ Design（英語：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]。

注釋

  1. ^ Boost C++ Libraries內便有包含基於內存池的分配器的樣例。

參考資料

  1. ^ 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. ^ 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. ^ 3.0 3.1 Stroustrup, Bjarne. The C++ Programming Language, 3rd edition. Addison-Wesley. 1997. 
  4. ^ 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. 
  5. ^ Lo Russo, Graziano. An Interview with A. Stepanov. www.stlport.org. 1997 [2009-05-13]. （原始內容存檔於2009-03-04）. 
  6. ^ Langer, Angelika; Klaus Kreft. Allocator Types. C++ Report. 1998 [2009-05-13]. （原始內容存檔於2008-05-17）. 
  7. ^ 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. ^ 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. ^ 9.0 9.1 9.2 Alexandrescu, Andrei. Modern C++ Design. Addison-Wesley. 2001: 352. ISBN 0-201-70431-5. 
  10. ^ Vlasceanu, Christian. Debugging Memory Errors with Custom Allocators. Dr. Dobb's Journal. 2001-04-01 [2009-05-14]. （原始內容存檔於2012-06-09）. 
  11. ^ Austern, Matthew. The Standard Librarian: A Debugging Allocator. Dr. Dobb's Journal. 2001-12-01 [2009-05-14]. （原始內容存檔於2012-06-09）. 
  12. ^ Halpern, Pablo. The Scoped Allocator Model (Rev 2) (PDF). ISO. 2008-02-29 [2012-08-21]. （原始內容存檔 (PDF)於2012-06-07）. 
  13. ^ Halpern, Pablo. Allocator-specific Swap and Move Behavior (PDF). ISO. 2008-02-04 [2012-08-21]. （原始內容存檔 (PDF)於2012-06-07）. 
  14. ^ Halpern, Pablo. Allocators post Removal of C++ Concepts (Rev 1) (PDF). ISO. 2009-10-22 [2012-08-21]. （原始內容存檔 (PDF)於2012-06-17）. 
  15. ^ Becker, Pete. LWG Issue 1318: N2982 removes previous allocator capabilities (closed in March, 2011). ISO. [2012-08-21]. （原始內容存檔於2012-08-16）. 

標準文檔

  1. ^ C++03 ，§20.1.5 Allocator requirements [lib.allocator.requirements], 第4段
  2. ^ C++03 ，§20.4.1 The default allocator [lib.default.allocator]
  3. ^ 3.0 3.1 3.2 C++03 ，§20.1.5 Allocator requirements [lib.allocator.requirements], 第2段
  4. ^ 4.0 4.1 C++03 ，§20.1.5 Allocator requirements [lib.allocator.requirements], 第5段
  5. ^ C++03 ，§20.4.1.1 allocator members [lib.allocator.members], 第3段
  6. ^ C++03 ，§23.2 Sequences [lib.sequences], 第1段

外部連結

取自「https://zh.wikipedia.org/w/index.php?title=分配器_(C%2B%2B)&oldid=80414565」