分配器

分配器最早由亞歷山大·斯特潘諾夫作為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::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（析構函數）以對對象進行構造與析構，且兩者應等價於如下函數：

以上代碼中使用了placementnew語法，且直接調用了析構函數。

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