侯捷STL课程及源码剖析学习2: allocator

　　以STL 的运用角度而言，空间配置器是最不需要介绍的东西，它总是隐藏在一切组件（更具体地说是指容器，container）的背后，默默工作默默付出。

一、分配器测试

测试代码

  1 #include <list>
  2 #include <stdexcept>
  3 #include <string>
  4 #include <cstdlib>         //abort()
  5 #include <cstdio>          //snprintf()
  6 #include <algorithm>     //find()
  7 #include <iostream>
  8 #include <ctime> 
  9 
 10 #include <cstddef>
 11 #include <memory>    //内含 std::allocator  
 12 //欲使用 std::allocator 以外的 allocator, 得自行 #include <ext...> 
 13 #ifdef __GNUC__        
 14 #include <extarray_allocator.h>
 15 #include <extmt_allocator.h>
 16 #include <extdebug_allocator.h>
 17 #include <extpool_allocator.h>
 18 #include <extitmap_allocator.h>
 19 #include <extmalloc_allocator.h>
 20 #include <ext
ew_allocator.h>  
 21 #endif
 22 
 23 namespace jj20
 24 {
 25     //pass A object to function template impl()，
 26     //而 A 本身是个 class template, 带有 type parameter T,  
 27     //那么有无可能在 impl() 中抓出 T, 创建一个 list<T, A<T>> object? 
 28     //以下先暂时回避上述疑问.
 29 
 30     void test_list_with_special_allocator()
 31     {
 32 #ifdef __GNUC__    
 33         cout << "
test_list_with_special_allocator().......... 
";
 34 
 35         //不能在 switch case 中宣告，只好下面这样.                 //1000000次 
 36         list<string, allocator<string>> c1;                        //3140
 37         list<string, __gnu_cxx::malloc_allocator<string>> c2;      //3110
 38         list<string, __gnu_cxx::new_allocator<string>> c3;         //3156
 39         list<string, __gnu_cxx::__pool_alloc<string>> c4;          //4922
 40         list<string, __gnu_cxx::__mt_alloc<string>> c5;         //3297
 41         list<string, __gnu_cxx::bitmap_allocator<string>> c6;      //4781                                                         
 42 
 43         int choice;
 44         long value;
 45 
 46         cout << "select: "
 47             << " (1) std::allocator "
 48             << " (2) malloc_allocator "
 49             << " (3) new_allocator "
 50             << " (4) __pool_alloc "
 51             << " (5) __mt_alloc "
 52             << " (6) bitmap_allocator ";
 53 
 54         cin >> choice;
 55         if (choice != 0) {
 56             cout << "how many elements: ";
 57             cin >> value;
 58         }
 59 
 60         char buf[10];
 61         clock_t timeStart = clock();
 62         for (long i = 0; i< value; ++i)
 63         {
 64             try {
 65                 snprintf(buf, 10, "%d", i);
 66                 switch (choice)
 67                 {
 68                 case 1:     c1.push_back(string(buf));
 69                     break;
 70                 case 2:     c2.push_back(string(buf));
 71                     break;
 72                 case 3:     c3.push_back(string(buf));
 73                     break;
 74                 case 4:     c4.push_back(string(buf));
 75                     break;
 76                 case 5:     c5.push_back(string(buf));
 77                     break;
 78                 case 6:     c6.push_back(string(buf));
 79                     break;
 80                 default:
 81                     break;
 82                 }
 83             }
 84             catch (exception& p) {
 85                 cout << "i=" << i << " " << p.what() << endl;
 86                 abort();
 87             }
 88         }
 89         cout << "a lot of push_back(), milli-seconds : " << (clock() - timeStart) << endl;
 90 
 91 
 92         //test all allocators' allocate() & deallocate();
 93         int* p;
 94         allocator<int> alloc1;
 95         p = alloc1.allocate(1);
 96         alloc1.deallocate(p, 1);
 97 
 98         __gnu_cxx::malloc_allocator<int> alloc2;
 99         p = alloc2.allocate(1);
100         alloc2.deallocate(p, 1);
101 
102         __gnu_cxx::new_allocator<int> alloc3;
103         p = alloc3.allocate(1);
104         alloc3.deallocate(p, 1);
105 
106         __gnu_cxx::__pool_alloc<int> alloc4;
107         p = alloc4.allocate(2);
108         alloc4.deallocate(p, 2);     //我刻意令参数为 2, 但这有何意义!! 一次要 2 个 ints? 
109 
110         __gnu_cxx::__mt_alloc<int> alloc5;
111         p = alloc5.allocate(1);
112         alloc5.deallocate(p, 1);
113 
114         __gnu_cxx::bitmap_allocator<int> alloc6;
115         p = alloc6.allocate(3);
116         alloc6.deallocate(p, 3);      //我刻意令参数为 3, 但这有何意义!! 一次要 3 个 ints? 
117 #endif             
118     }
119 }

View Code

注：直接使用分配器allocate时，释放时须指明释放内存大小。

二、简单的内存分配器

一般而言，c++的内存分配和释放是这样操作的

class Foo{ //...};
Foo* pf = new Foo;//配置内存，然后建构对象
delete pf; //将对象解构，然后释放内存

　　其中的 new操作内含两阶段动作：(1)调用::operator new配置内存，(2) 调用Foo::Foo()建构对象内容。delete操作也内含两阶段动作： (1)调用Foo::~Foo()将对象解构，(2)调用::operator delete释放内存。

　　为了精密分工，STL allocator决定将这两阶段区分开来。内存配置由alloc:allocate()负责，内存释放由alloc::deallocate()负责；对象建构由::construct()负责，对象析构由::destroy()负责。

简单内存分配器代码

  1 #ifndef SIMPLE_JJALLOC_H  
  2 #define SIMPLE_JJALLOC_H  
  3 #include<new>         //for placement new   
  4 #include<cstddef> //for ptrdiff_t,size_t  
  5 #include<cstdlib> //for exit()  
  6 #include<climits> //for UINT_MAX十进制的最大值   
  7 #include<iostream>    //for cerr  
  8   
  9 namespace JJ  
 10 {  
 11     /*****************ptrdiff_t与size_t类型*****size_type与difference_type类型********************  
 12     ****ptrdiff_t:signed类型，通常用于两指针减法操作的结果，它可以是负数。（因为指针相减有正有负）  
 13     ****size_t:unsigned类型，用于指明数组长度，它是非负整数。 
 14     ****size_type:unsigned类型，容器中元素长度或下表，vector<int>::size_type i=0; 
 15     ****difference_type:signed类型，表示迭代器差距，vector<int>::difference_type=iter1-iter2 
 16     ****前两者位于标准类库std内，后两者为stl对象所有  
 17     *********************************************************************************************/  
 18     template<class T>  
 19     inline T* _allocate(ptrdiff_t size, T*)  
 20     {     
 21         std::cout<<"I'm _allocate in simple_jjalloc!"<<std::endl;  
 22         /**************************new_handler与set_new_handler***********************************  
 23         ****new_handler:内存分配失败后，调用的处理函数。 
 24         ****set_new_handler:参数是被指定的new_handler函数指针，返回参数也是new_handler是被替换掉的new_handler  
 25         *****************************************************************************************/    
 26         std::set_new_handler(0);  
 27         /****************::*********************************************************************** 
 28         ****"::":全局作用。比如::luo这就是个全局变量，而luo这是个局部变量  
 29         ****"::":类作用。比如Node::function() 
 30         ****"::":名字空间。比如std::size_t  
 31         *****************************************************************************************/    
 32         T *tmp=(T*)(::operator new((size_t)(size*sizeof(T))));  
 33         if(tmp == 0)//没有前面的std::set_new_handler(0);把内存分配失败后的异常调用函数给替换掉，就执行不到这儿   
 34         {  
 35             std::cout<<"failed!"<<std::endl;  
 36             std::cerr<<"out of memory"<<std::endl;  
 37             exit(1);  
 38         }  
 39         return tmp;   
 40     }  
 41       
 42     template<class T>  
 43     inline void _deallocate(T* buffer)  
 44     {  
 45         ::operator delete(buffer);  
 46     }  
 47     /************************************new的三种形态******************************************* 
 48     ****new operator:就是平常用的new，通常做三件事，1.用operator new分配内存给对象，2.调用构造函数初始化那块内存，3.将地址转给对象指针  
 49                      如果仅仅是在堆上建立对象，那么应该使用new operator，它会提供周全的服务   
 50     ****operator new:在默认情况下首先会调用分配内存的代码，尝试从堆上得到一段空间，成功就返回，失败就调用new_hander，重复前面过程，直到抛出异常  
 51                      如果仅仅是分配内存，那么应该调用operator new，但初始化不在它的职责之内。若对默认的内存分配过程不满意，那就重载它  
 52     ****placement new:用来实现定位构造，可以通过它来选择合适的构造函数。  
 53                      如果想在一块已获得的内存里建立一个对象，那就改用placement new  
 54     ********************************************************************************************/  
 55     template<class T1,class T2>  
 56     inline void _construct(T1* p,const T2& val)  
 57     {  
 58         new(p) T1(val);//p为那块内存地址，T1()为指定构造函数；此句为p->T1::T1(val);   
 59         std::cout<<"I'm _construct!"<<std::endl;  
 60     }  
 61       
 62     template<class T>  
 63     inline void _destroy(T* ptr)  
 64     {  
 65         std::cout<<"I'm _destroy!"<<std::endl;  
 66         ptr->~T();  
 67     }  
 68       
 69     template<class T>  
 70     class mallocator  
 71     {  
 72         public:  
 73             typedef T value_type;//为什么要重新定义，原因在章三  
 74             typedef T* pointer;  
 75             typedef const T* const_pointer;  
 76             typedef T& reference;  
 77             typedef const T& const_reference;  
 78             typedef size_t size_type;  
 79             typedef ptrdiff_t difference_type;  
 80           
 81           
 82             template<class U>  
 83             struct rebind//干吗用？见下   
 84             {  
 85                 typedef mallocator<U> mother;  
 86             };   
 87               
 88             pointer allocate(size_type n,const void* hint=0)  
 89             {  
 90                 return _allocate((difference_type)n,(pointer)0);  
 91             }  
 92               
 93             void deallocate(pointer p,size_type n)  
 94             {  
 95                 _deallocate(p);  
 96             }  
 97               
 98             void construct(pointer p,const_reference val)  
 99             {  
100                 _construct(p,val);  
101             }  
102               
103             void destroy(pointer p)  
104             {  
105                 _destroy(p);  
106             }  
107               
108             pointer address(reference x)  
109             {  
110                 return (pointer)&x;  
111             }  
112               
113             const pointer const_address(const_reference x)  
114             {  
115                 return (const pointer)&x;  
116             }  
117               
118             size_type max_size()const  
119             {  
120                 return size_type(UINT_MAX/sizeof(value_type));  
121             }  
122     };  
123 }  
124 #endif

View Code

内存分配测试代码：

int ia[5] = {1,2,3,4,5};

vector<int,JJ::mallocator<int>> iv(ia,ia+3);

for (auto i : iv)
cout<<i<<" ";
cout<<endl;

测试结果

I'm _allocate in simple_jjalloc!
I'm _construct!
I'm _construct!
I'm _construct!
1 2 3
I'm _destroy!
I'm _destroy!
I'm _destroy!

直接使用allocate, 不用new. 代码环境GNU 2.9 ，高版本头文件找不到。

 1 #include<iostream>
 2 #include<defalloc.h>
 3 #include<stl_alloc.h>
 4 using namespace std;
 5 void main()
 6 {
 7     void* p = allocator<int>().allocate(512);
 8     allocator<int>().deallocate((int*)p);
 9     cout << "allocator<int>().allocate(512);"<<endl;
10 
11     void* p2 = alloc::allocate(512);
12     alloc::deallocate(p2, 512);
13 
14     cout << "allocate(512, 0);" << endl;
15 }

View Code

二、 OOP(Object-Oriented Programming) vs GP(Generic Programming)

　　OOP是将数据和方法封装在一起，多采用继承和多态。

　　GP却是将datas 和 methods 分开来。如STL中，Container 和 Algorithms 可以各自独立进行开发，两者使用迭代器进行关联。Algorithms通过iterators 确定操作范围，并获取容器元素。

深入理解留待后续。。。

内容参考：

侯捷STL课程, 《STL源码剖析》