1、模板的特化

泛化模板 : 对各种不同版本的特殊化处理---->特化;

2、萃取

拿相同的代码提取不同的类型;

3、整个搭建框架如下：

在这里已经不关心空间配置器是如何实现的;

其框架代码如下：

#ifndef_MEMORY_H_#define_MEMORY_H_#include"stl_alloc.h"#include"stl_iterator.h"#include"type_traits.h"#include"stl_construct.h"#include"stl_uninitialized.h"#endif////////////////////////////////////////////////////////////////////////////////////#if1#include<iostream>#include<new>#include<malloc.h>usingnamespacestd;//#define__THROW_BAD_ALLOCthrowbad_alloc#define__THROW_BAD_ALLOCcerr<<"Throwbadalloc,OutOfMemory."<<endl;exit(1)#elif!defined(__THROW_BAD_ALLOC)#include<iostream.h>#define__THROW_BAD_ALLOCcerr<<"outofmemory"<<endl;exit(1);#endiftemplate<intinst>class__malloc_alloc_template{private:staticvoid*oom_malloc(size_t);staticvoid*oom_realloc(void*,size_t);staticvoid(*__malloc_alloc_oom_handler)();public:staticvoid*allocate(size_tn){void*result=malloc(n);if(0==result){result=oom_malloc(n);}returnresult;}staticvoiddeallocate(void*p,size_t){free(p);}staticvoid*reallocate(void*p,size_t,size_tnew_sz){void*result=realloc(p,new_sz);if(0==result){oom_realloc(p,new_sz);}returnresult;}public://set_new_handler(Out_Of_Memory);staticvoid(*set_malloc_handler(void(*f)()))(){void(*old)()=__malloc_alloc_oom_handler;__malloc_alloc_oom_handler=f;returnold;}};template<intinst>void(*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)()=0;template<intinst>void*__malloc_alloc_template<inst>::oom_malloc(size_tn){void*result;void(*my_malloc_handler)();for(;;){my_malloc_handler=__malloc_alloc_oom_handler;if(0==my_malloc_handler){__THROW_BAD_ALLOC;}(*my_malloc_handler)();result=malloc(n);if(result){returnresult;}}}template<intinst>void*__malloc_alloc_template<inst>::oom_realloc(void*p,size_tn){void(*my_malloc_handler)();void*result;for(;;){my_malloc_handler=__malloc_alloc_oom_handler;if(0==my_malloc_handler){__THROW_BAD_ALLOC;}(*my_malloc_handler)();result=realloc(p,n);if(result){returnresult;}}}typedef__malloc_alloc_template<0>malloc_alloc;/////////////////////////////////////////////////////////////////////////////////////enum{__ALIGN=8};enum{__MAX_BYTES=128};enum{__NFREELISTS=__MAX_BYTES/__ALIGN};template<boolthreads,intinst>class__default_alloc_template{public:staticvoid*allocate(size_tn);staticvoiddeallocate(void*p,size_tn);staticvoid*reallocate(void*p,size_t,size_tnew_sz);private:staticsize_tROUND_UP(size_tbytes){return(((bytes)+__ALIGN-1)&~(__ALIGN-1));}private:unionobj{unionobj*free_list_link;charclient_data[1];};private:staticobj*volatilefree_list[__NFREELISTS];staticsize_tFREELIST_INDEX(size_tbytes){return((bytes)+__ALIGN-1)/__ALIGN-1;}private:staticchar*start_free;staticchar*end_free;staticsize_theap_size;staticvoid*refill(size_tn);staticchar*chunk_alloc(size_tsize,int&nobjs);};template<boolthreads,intinst>char*__default_alloc_template<threads,inst>::start_free=0;template<boolthreads,intinst>char*__default_alloc_template<threads,inst>::end_free=0;template<boolthreads,intinst>size_t__default_alloc_template<threads,inst>::heap_size=0;template<boolthreads,intinst>typename__default_alloc_template<threads,inst>::obj*volatile__default_alloc_template<threads,inst>::free_list[__NFREELISTS]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};template<boolthreads,intinst>void*__default_alloc_template<threads,inst>::allocate(size_tn){obj*volatile*my_free_list;obj*result;if(n>__MAX_BYTES){returnmalloc_alloc::allocate(n);}my_free_list=free_list+FREELIST_INDEX(n);result=*my_free_list;if(result==0){void*r=refill(ROUND_UP(n));returnr;}*my_free_list=result->free_list_link;returnresult;}template<boolthreads,intinst>void*__default_alloc_template<threads,inst>::refill(size_tn){intnobjs=20;char*chunk=chunk_alloc(n,nobjs);obj*volatile*my_free_list;obj*result;obj*current_obj,*next_obj;inti;if(1==nobjs){returnchunk;}my_free_list=free_list+FREELIST_INDEX(n);result=(obj*)chunk;*my_free_list=next_obj=(obj*)(chunk+n);for(i=1;;++i){current_obj=next_obj;next_obj=(obj*)((char*)next_obj+n);if(nobjs-1==i){current_obj->free_list_link=0;break;}else{current_obj->free_list_link=next_obj;}}returnresult;}template<boolthreads,intinst>char*__default_alloc_template<threads,inst>::chunk_alloc(size_tsize,int&nobjs){char*result;size_ttotal_bytes=size*nobjs;size_tbytes_left=end_free-start_free;if(bytes_left>=total_bytes){result=start_free;start_free+=total_bytes;returnresult;}elseif(bytes_left>=size){nobjs=bytes_left/size;total_bytes=size*nobjs;result=start_free;start_free+=total_bytes;returnresult;}else{size_tbytes_to_get=2*total_bytes+ROUND_UP(heap_size>>4);if(bytes_left>0){obj*volatile*my_free_list=free_list+FREELIST_INDEX(bytes_left);((obj*)start_free)->free_list_link=*my_free_list;*my_free_list=(obj*)start_free;}start_free=(char*)malloc(bytes_to_get);if(0==start_free){inti;obj*volatile*my_free_list,*p;for(i=size;i<=__MAX_BYTES;i+=__ALIGN){my_free_list=free_list+FREELIST_INDEX(i);p=*my_free_list;if(0!=p){*my_free_list=p->free_list_link;start_free=(char*)p;end_free=start_free+i;returnchunk_alloc(size,nobjs);}}end_free=0;start_free=(char*)malloc_alloc::allocate(bytes_to_get);}heap_size+=bytes_to_get;end_free=start_free+bytes_to_get;returnchunk_alloc(size,nobjs);}}/////////////////////////////////////////////////////////////////////////////////#ifdef__USE_MALLOCtypedefmalloc_allocalloc;#elsetypedef__default_alloc_template<0,0>alloc;#endiftemplate<classT,classAlloc>classsimple_alloc{public:staticT*allocate(size_tn){return0==n?0:(T*)Alloc::allocate(n*sizeof(T));}staticT*allocate(void){return(T*)Alloc::allocate(sizeof(T));}staticvoiddeallocate(T*p,size_tn){if(0!=n)Alloc::deallocate(p,n*sizeof(T));}staticvoiddeallocate(T*p){Alloc::deallocate(p,sizeof(T));}};//////////////////////////////////////////////////////////////////////////////////////////#ifndef__STL_CONFIG_H#define__STL_CONFIG_H//#define__USE_MALLOC#endif//////////////////////////////////////////////////////////////////////////////////////////#ifndef__STL_CONSTRUCT_H#define__STL_CONSTRUCT_Htemplate<classT1,classT2>voidconstruct(T1*p,constT2&value){new(p)T1(value);}#endif////////////////////////////////////////////////////////////////////////////////////////#ifndef__STL_ITERATOR_H#define__STL_ITERATOR_Htemplate<classT>T*value_type(constT*){return(T*)(0);}#endif////////////////////////////////////////////////////////////////////////////////////////#ifndef__STL_UNINITIALIZED_H#define__STL_UNINITIALIZED_Htemplate<classForwardIterator,classSize,classT>ForwardIterator_uninitialized_fill_n_aux(ForwardIteratorfirst,Sizen,constT&x,_true_type){cout<<"yyyyyyyyyyy"<<endl;returnfill_n(first,n,x);}template<classForwardIterator,classSize,classT>ForwardIterator_uninitialized_fill_n_aux(ForwardIteratorfirst,Sizen,constT&x,_false_type){ForwardIteratorcur=first;for(;n>0;--n,++cur){cout<<"xxxxxxxxxxxx"<<endl;construct(&*cur,x);//construct(cur,x);}returncur;}template<classForwardIterator,classSize,classT,classT1>ForwardIterator_uninitialized_fill_n(ForwardIteratorfirst,Sizen,constT&x,T1*){//typedef_false_typeis_POD;typedeftypename_type_traits<T1>::is_POD_typeis_POD;//return_uninitialized_fill_n(first,n,x,_false_type());return_uninitialized_fill_n_aux(first,n,x,is_POD());}template<classForwardIterator,classSize,classT>ForwardIteratoruninitialized_fill_n(ForwardIteratorfirst,Sizen,constT&x){return_uninitialized_fill_n(first,n,x,value_type(first));}#endif////////////////////////////////////////////////////////////////////////////////////////#ifndef__STL_VECTOR_H#define__STL_VECTOR_Htemplate<classT,classAlloc=alloc>classvector{public:typedefTvalue_type;typedefvalue_type*pointer;typedefvalue_type*iterator;typedefvalue_type&reference;typedefsize_tsize_type;typedefptrdiff_tdifference_type;public:vector():start(0),finish(0),end_of_storage(0){}vector(size_typen){fill_initialize(n,T());}protected:voidfill_initialize(size_typen,constT&value){start=allocate_and_fill(n,value);finish=start+n;end_of_storage=finish;}iteratorallocate_and_fill(size_typen,constT&x){iteratorresult=data_allocator::allocate(n);uninitialized_fill_n(result,n,x);returnresult;}protected:typedefsimple_alloc<value_type,Alloc>data_allocator;iteratorstart;iteratorfinish;iteratorend_of_storage;};#endif////////////////////////////////////////////////////////////////////////////////////////#ifndef__TYPE_TRAITS_H#define__TYPE_TRAITS_H//struct_true_type{};struct_false_type{};template<classtype>struct_type_traits{typedef_true_typethis_dummy_member_must_be_first;typedef_false_typehas_trivial_default_constructor;typedef_false_typehas_trivial_copy_constructor;typedef_false_typehas_trivial_assignment_operator;typedef_false_typehas_trivial_destructor;typedef_false_typeis_POD_type;};template<>struct_type_traits<int>{typedef_true_typehas_trivial_default_constructor;typedef_true_typehas_trivial_copy_constructor;typedef_true_typehas_trivial_assignment_operator;typedef_true_typehas_trivial_destructor;typedef_true_typeis_POD_type;};#endif///////////////////////////////////////////////////////////////////////////////////////#ifndef_VECTOR_H_#define_VECTOR_H_#include"memory.h"#include"stl_vector.h"#endif///////////////////////////////////////////////////////////////////////////////////////

测试代码

#include<iostream>#include<stdlib.h>#include"vector.h"usingnamespacestd;classTest{};intmain(){vector<Test>v(10);//开辟了10个元素的空间;return0;

测试结果

4、分析

(1)、vector的空间灵活性更高;

(2)、POD：也就是标量型别，也就是传统的型别，采取最保险安全的做法,调用构造函数；否则的话，就是调用系统的，基本类型就是true;

(3)、空构造了2个类型，针对不同萃取得到其_false_type或_true_type ; 就可以调用不同的函数，进行空间的分配，存在效率上的差异!!!

_true_type：将调用系统的填充函数，效率比较高.

(4)、容器、算法单独好实现，关键是通用性，模板是一种很好的解决方案，真正关键之处还在 : 迭代器的实现;

(5)、空间配置器负责分配、回收空间，只有一个；迭代器针对不同的容器有不同的实现方法!!!