规范库规定，分配器最顶层在 《...\memory》 头文件下
new_allocator
new_allocator 的 allocate 间接调用的 ::operator new ，deallocate 间接调用 ::operator delete
malloc_allocator
malloc_allocator 的 allocate 间接调用的 malloc，deallocate 间接调用 free。
array_allocator
tr1 (Technical Report 1) 不是正式的库只是一个草案，作为C++ 2003规范的附加库被大多数编译器厂商所反对，它是个过渡性质的库，其实现将会作为C++11规范的一部分。到 C++2011 时，其局部内容被正式蕴含到规范库，在应用形式上依然保留 std::tr1，例如 std::tr1::array 可用 std::array 代替。在构造函数中须要传入一个指针，这个指针能够指向动态调配的数组，也能够指向动态分配的数组，所以说内存调配不是在array_allocator中进行的，array_allocator 只是对调配好的内存进行治理（因而 deallocate 什么都没做）。
array_allocator 并不会"回收"(指从新被array_allocator治理)已给出的内存空间，因而很少被应用
动态内存调配的形式应用
动态内存调配的形式应用
debug_allocator
包裹另一个分配器，应用至多一个元素大小的空间，用于记录整个区块大小（子元素数量）（是不是相等于另一种 cookie? 但 allocator 的主要用途是缩小 cookie，因而很少被应用）pool_allocator
G2.9 容器应用的分配器不是 std::allocator 而是 std::alloc (毛病，只申请不偿还)
G4.9 中的进化
G4.9 规范库中有许多 extented allocators， 其中 __pool_alloc 就是 G2.9 的化身
#include <iostream>#include <cstddef>#include <memory> //內含 std::allocator#include <ext\pool_allocator.h> //欲应用 std::allocator 以外的 allocator, 就得自行 #include <ext/...>#include <ext\array_allocator.h>#include <ext\mt_allocator.h>#include <ext\debug_allocator.h>#include <ext\bitmap_allocator.h>#include <ext\malloc_allocator.h>#include <ext\throw_allocator.h>#include <ext\new_allocator.h> //這其實已被 <memory> included, 它就是 std:allocator 的 base class#include <iostream>#include <list>#include <deque>#include <vector>using namespace std;template<typename Alloc>void cookie_test(Alloc alloc, size_t n){ typename Alloc::value_type *p1, *p2, *p3; //需有 typename p1 = alloc.allocate(n); //allocate() and deallocate() 是 non-static, 需以 object 呼叫之. p2 = alloc.allocate(n); p3 = alloc.allocate(n); cout << "p1= " << p1 << '\t' << "p2= " << p2 << '\t' << "p3= " << p3 << '\n'; alloc.deallocate(p1,sizeof(typename Alloc::value_type)); //需有 typename alloc.deallocate(p2,sizeof(typename Alloc::value_type)); //有些 allocator 對於 2nd argument 的值無所謂 alloc.deallocate(p3,sizeof(typename Alloc::value_type));}int main(){ //從語法上試用各式各樣的 allocators cout << sizeof(std::allocator<int>) << endl; //1 cout << sizeof(__gnu_cxx::new_allocator<int>) << endl; //1. //觀察 STL source 可知: new_allocator 是 std::allocator 的 base //我們無法改變 std::allocator 的 base class, 那該如何应用其余的 GNU allocators ? //是否要寫個 custom_allocator (像下面) 並為它加上我想要的 base (例如 __pool_alloc) ? //不，不用，就间接应用, 但需自行 #include <ext/...> cout << sizeof(__gnu_cxx::malloc_allocator<int>) << endl; //1. 大小 1者其實為 0, fields 都是 static. cout << sizeof(__gnu_cxx::__pool_alloc<int>) << endl; //1 cout << sizeof(__gnu_cxx::__mt_alloc<int>) << endl; //1 cout << sizeof(__gnu_cxx::bitmap_allocator<int>) << endl; //1 cout << sizeof(__gnu_cxx::array_allocator<int>) << endl; //8 ==> 因為它有一個 ptr 指向 array 和一個 size_t 示意耗费到 array 哪兒 cout << sizeof(__gnu_cxx::debug_allocator<std::allocator<double>>) << endl; //8 //! cout << sizeof(__gnu_cxx::throw_allocator<int>) << endl; //只有 throw_allocator_base, throw_allocator_random, throw_allocator_limit, 沒有 throw_allocator !! cout << endl; //搭配容器 list <int, __gnu_cxx::malloc_allocator<int>> list_malloc; deque <int, __gnu_cxx::debug_allocator<std::allocator<int>>> deque_debug; vector<int, __gnu_cxx::__pool_alloc<int>> vector_pool; //! vector<int, __pool_alloc<int>> vector_pool; //如果沒加上 namespace : [Error] '__pool_alloc' was not declared in this scope cookie_test(std::allocator<int>(), 1); //相距 10h (示意帶 cookie) cookie_test(__gnu_cxx::malloc_allocator<int>(), 1); //相距 10h (示意帶 cookie) cookie_test(__gnu_cxx::__pool_alloc<int>(), 1); //相距 08h (示意不帶 cookie) //以下將 int 改為 double 結果不變，象征上述 ints 間隔 8 (而非 4) 乃是因為 alignment. cookie_test(std::allocator<double>(), 1); //相距 10h (示意帶 cookie) cookie_test(__gnu_cxx::malloc_allocator<double>(), 1); //相距 10h (示意帶 cookie) cookie_test(__gnu_cxx::__pool_alloc<double>(), 1); //相距 08h (示意不帶 cookie) cout << endl; try { //示範应用 array_allocator: 須先 new an array, 將其 ptr 設給 array_allocator, 最後還要 delete array std::tr1::array<double,100>* arrayTR1 = new std::tr1::array<double,100>; //应用 tr1::array cookie_test(__gnu_cxx::array_allocator<double, std::tr1::array<double,100>>(arrayTR1), 1); //相距 08h (示意不帶 cookie) delete arrayTR1; array<double,100>* arraySTD = new array<double,100>; //应用 std::array cookie_test(__gnu_cxx::array_allocator<double, array<double,100>>(arraySTD), 1); //相距 08h (示意不帶 cookie) delete arraySTD; std::tr1::array<double,1>* p = new std::tr1::array<double,1>; //為搭配下一行 "default 2nd argument 是 std::tr1::array<T,1>" (見 source), 我們须要做一個來. cookie_test(__gnu_cxx::array_allocator<double>(p), 1); //未指明 2nd argument, 所以应用 default, 即 std::tr1::array<T,1> //bad allocation! 因為 cookie_test() 需 3 doubles 而 // 本處所用之 array_allocator 卻只能提供 1 double。 delete p; } catch(...) { cout << "bad allocation! \n"; } return 0;}输入：
11111188p1= 0xe91630 p2= 0xe98328 p3= 0xe98338p1= 0xe91630 p2= 0xe98328 p3= 0xe98338p1= 0xe98368 p2= 0xe98370 p3= 0xe98378p1= 0xe91630 p2= 0xe984b0 p3= 0xe984c0p1= 0xe91630 p2= 0xe984b0 p3= 0xe984c0p1= 0xe98380 p2= 0xe98388 p3= 0xe98390p1= 0xe984b0 p2= 0xe984b8 p3= 0xe984c0p1= 0xe984b0 p2= 0xe984b8 p3= 0xe984c0bad allocation! bitmap_allocator
<.../ext/bitmap_allocator.h> 文件中template<typename _Tp>class bitmap_allocator : private free_list { // 此处学习可不思考 free_list ......public: pointer allocate(size_type __n) { if (__n > this->max_size()) std::__throw_bad_alloc(); if (__builtin_expect(__b == 1, true)) return this->_M_allocate_single_object(); // 一次仅供给一个给客户！（因为次要被容器所应用，而容器一次申请只一个对象） else { // 当间接应用 bitmap_allocator 时可能会走向这里 const size_type __b = __n * sizeof(value_type); return reinterpret_cast<pointer>(::operator new(__b)); } } void deallocate(pointer __p, size_type __n) throw() { if (__builtin_expect(__p != 0, true)) { if (__builtin_expect(__n == 1, true)) this->_M_deallocate_single_object(__p); else ::operator delete(__p); } }};对于 blocks，super-blocks, bitmap, mini-vector
- block, 客户申请的一个节点，最小 8 字节，大小 8 的倍数增长（8, 16, 32 ...）
- super-blocks, 由 use-count + bitmap + blocks 组成[一次申请一大块，缩小 cookie 应用，每次 2 倍增长]
- use-count, 已调配出的 blocks 数量
- bitmap, unsigned int 为单位（32bit）, 反方向标记对应 blocks 是否闲暇 （1 闲暇， 0 已调配进来）
- __mini_vector, 一个小的 vector 实现, 治理应用中的 super-blocks （每次 2 倍增长）
第 1 次内存调配
1. use-count + 1 = 0 + 1 = 12. bitmap 批改为 0xFFFFFFFF FFFFFFFE第 2 次内存调配
1. use-count + 1 = 1 + 1 = 22. bitmap 批改为 0xFFFFFFFF FFFFFFFC第 63 次内存调配
1. use-count + 1 = 62 + 1 = 632. bitmap 批改为 0x10000000 00000000第 1 次内存偿还
1. use-count - 1 = 63 - 1 = 622. bitmap 批改为 0x10100000 000000001st super-block 用完，启动 2nd super-block
2nd super-block 用完，启动 3nd super-block
1st super-block 全回收
问题1：
如果 1st super-block 回收 2 blocks, 而尚未全回收，接下来调配 2 blocks, bitmap_allocator 会从 #0 super-block 取出亦或从 #2 super-block 取出?（假如 #0， #1， #2 block-size 一样大）
答：后者（其实都能够）
问题2：
如果接下来把 #2 super-block 用光，而后调配 2 blocks, bitmap_allocator 会从 #0 super-block 取出亦或新建一个 #3 super-block 并从中取出（假如 #0， #1， #2 block-size 一样大）？
答：前者
2nd super-block 全回收
3rd super-block 全回收
问题：接下来调配 1 block， 如何解决？
此时 _S_mem_blocks 为空而 _S_free_list 有三个 super-blicks, 于是取一个放进 _S_mem_blocks， 而后遵循先前法令实现调配
#include <iostream>#include <ext\bitmap_allocator.h> //欲应用 std::allocator 以外的 allocator, 就得自行 #include <ext/...>using namespace std;int main(){ cout << "\ntest_bitmap_allocators().......\n"; __gnu_cxx::bitmap_allocator<double> alloc; //造成一個 static __mini_vector<pair>, size=0 __gnu_cxx::bitmap_allocator<double>::value_type* p[1000]; // __gnu_cxx::bitmap_allocator<double>::value_type* ptr; for (int i=0; i<448; ++i) { p[i] = alloc.allocate(1); cout << "p[" << i << "]" << p[i] << endl; }}G4.9 分配器的应用
pool_allocator 和 bitmap_allocator 是最精美的分配器，不仅缩小了 cookies 的应用，同时更有速度劣势(bitmap_allocator 还可归还os内存)
#include <list>#include <stdexcept>#include <string>#include <cstdlib> // abort#include <cstdio> // snprintf()#include <algorithm> // find#include <iostream>#include <ctime>#include <cstddef>#include <memory> // 内含 std::allocator// 欲应用 std::allocator 以外的 allocator, 得自行 #include <ext\...>#include <ext\array_allocator.h>#include <ext\mt_allocator.h>#include <ext\debug_allocator.h>#include <ext\pool_allocator.h>#include <ext\bitmap_allocator.h>#include <ext\malloc_allocator.h>#include <ext\new_allocator.h>using namespace std;void test_list_with_special_allocator(int choice, long value){ cout << "test_list_with_special_allocator() ......" << endl; cout << "choice: " << choice << " value: " << value << endl; list<string, allocator<string>> c1; list<string, __gnu_cxx::malloc_allocator<string>> c2; list<string, __gnu_cxx::new_allocator<string>> c3; list<string, __gnu_cxx::__pool_alloc<string>> c4; list<string, __gnu_cxx::__mt_alloc<string>> c5; list<string, __gnu_cxx::bitmap_allocator<string>> c6; char buf[10]; clock_t timeStart = clock(); for (int i=0; i<value; ++i) { try { snprintf(buf, 10, "%d", i); switch (choice) { case 1: c1.push_back(string(buf)); break; case 2: c2.push_back(string(buf)); break; case 3: c3.push_back(string(buf)); break; case 4: c4.push_back(string(buf)); break; case 5: c5.push_back(string(buf)); break; case 6: c6.push_back(string(buf)); break; default: break; } } catch (exception &p) { cout << "i= " << i << " " << p.what() << endl; abort(); } } cout << "a lot of push_back(), milli-seconds : " << (clock() - timeStart) << endl;}void test_all_allocator(){ int *p; allocator<int> alloc1; p = alloc1.allocate(1); alloc1.deallocate(p, 1); __gnu_cxx::malloc_allocator<int> alloc2; p = alloc2.allocate(1); alloc2.deallocate(p, 1); __gnu_cxx::new_allocator<int> alloc3; p = alloc3.allocate(1); alloc3.deallocate(p, 1); __gnu_cxx::__pool_alloc<int> alloc4; p = alloc4.allocate(2); alloc4.deallocate(p, 2); __gnu_cxx::__mt_alloc<int> alloc5; p = alloc5.allocate(1); alloc5.deallocate(p, 1); __gnu_cxx::bitmap_allocator<int> alloc6; p = alloc6.allocate(3); alloc6.deallocate(p, 3);}int main(){ test_list_with_special_allocator(1, 600000); test_list_with_special_allocator(2, 600000); test_list_with_special_allocator(3, 600000); test_list_with_special_allocator(4, 600000); test_list_with_special_allocator(5, 600000); test_list_with_special_allocator(6, 600000); return 0;}输入：
test_list_with_special_allocator() ......choice: 1 value: 600000a lot of push_back(), milli-seconds : 105test_list_with_special_allocator() ......choice: 2 value: 600000a lot of push_back(), milli-seconds : 101test_list_with_special_allocator() ......choice: 3 value: 600000a lot of push_back(), milli-seconds : 107test_list_with_special_allocator() ......choice: 4 value: 600000a lot of push_back(), milli-seconds : 80test_list_with_special_allocator() ......choice: 5 value: 600000a lot of push_back(), milli-seconds : 85test_list_with_special_allocator() ......choice: 6 value: 600000a lot of push_back(), milli-seconds : 76