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
////////////////////////////////////////////////////////////////////////////////////
#if 1
#include
#include
#include
using namespace std;
//#define __THROW_BAD_ALLOC throw bad_alloc
#define __THROW_BAD_ALLOC cerr<<"Throw bad alloc, Out Of Memory."<
#define __THROW_BAD_ALLOC cerr<<"out of memory"<
class __malloc_alloc_template{
private:
static void* oom_malloc(size_t);
static void* oom_realloc(void *, size_t);
static void(* __malloc_alloc_oom_handler)();
public:
static void* allocate(size_t n){
void *result = malloc(n);
if(0 == result){
result = oom_malloc(n);
}
return result;
}
static void deallocate(void *p, size_t){
free(p);
}
static void* reallocate(void *p, size_t, size_t new_sz){
void *result = realloc(p, new_sz);
if(0 == result){
oom_realloc(p,new_sz);
}
return result;
}
public:
//set_new_handler(Out_Of_Memory);
static void(*set_malloc_handler(void(*f)()))(){
void(*old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = f;
return old;
}
};
template
void (*__malloc_alloc_template::__malloc_alloc_oom_handler)() = 0;
template
void* __malloc_alloc_template::oom_malloc(size_t n){
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){
return result;
}
}
}
template
void* __malloc_alloc_template::oom_realloc(void *p, size_t n){
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){
return result;
}
}
}
typedef __malloc_alloc_template<0> malloc_alloc;
/////////////////////////////////////////////////////////////////////////////////////
enum {__ALIGN = 8};
enum {__MAX_BYTES = 128};
enum {__NFREELISTS = __MAX_BYTES / __ALIGN};
template
class __default_alloc_template{
public:
static void* allocate(size_t n);
static void deallocate(void *p, size_t n);
static void* reallocate(void *p, size_t, size_t new_sz);
private:
static size_t ROUND_UP(size_t bytes){
return (((bytes) + __ALIGN-1) & ~(__ALIGN-1));
}
private:
union obj{
union obj * free_list_link;
char client_data[1];
};
private:
static obj* volatile free_list[__NFREELISTS];
static size_t FREELIST_INDEX(size_t bytes){
return ((bytes)+__ALIGN-1) / __ALIGN-1;
}
private:
static char *start_free;
static char *end_free;
static size_t heap_size;
static void *refill(size_t n);
static char* chunk_alloc(size_t size, int &nobjs);
};
template
char* __default_alloc_template::start_free = 0;
template
char* __default_alloc_template::end_free = 0;
template
size_t __default_alloc_template::heap_size = 0;
template
typename __default_alloc_template::obj* volatile
__default_alloc_template::free_list[__NFREELISTS] =
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
template
void* __default_alloc_template::allocate(size_t n){
obj * volatile *my_free_list;
obj *result;
if(n > __MAX_BYTES){
return malloc_alloc::allocate(n);
}
my_free_list = free_list + FREELIST_INDEX(n);
result = *my_free_list;
if(result == 0){
void *r = refill(ROUND_UP(n));
return r;
}
*my_free_list = result->free_list_link;
return result;
}
template
void* __default_alloc_template::refill(size_t n){
int nobjs = 20;
char *chunk = chunk_alloc(n, nobjs);
obj * volatile *my_free_list;
obj *result;
obj *current_obj, *next_obj;
int i;
if(1 == nobjs){
return chunk;
}
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;
}
}
return result;
}
template
char* __default_alloc_template::chunk_alloc(size_t size, int &nobjs){
char *result;
size_t total_bytes = size * nobjs;
size_t bytes_left = end_free - start_free;
if(bytes_left >= total_bytes){
result = start_free;
start_free += total_bytes;
return result;
}
else if(bytes_left >= size){
nobjs = bytes_left / size;
total_bytes = size * nobjs;
result = start_free;
start_free += total_bytes;
return result;
}else{
size_t bytes_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){
int i;
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;
return chunk_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;
return chunk_alloc(size, nobjs);
}
}
/////////////////////////////////////////////////////////////////////////////////
#ifdef __USE_MALLOC
typedef malloc_alloc alloc;
#else
typedef __default_alloc_template<0,0> alloc;
#endif
template
class simple_alloc{
public:
static T* allocate(size_t n){
return 0==n ? 0 : (T*)Alloc::allocate(n * sizeof(T));
}
static T* allocate(void){
return (T*)Alloc::allocate(sizeof(T));
}
static void deallocate(T *p, size_t n){
if(0!=n) Alloc::deallocate(p, n*sizeof(T));
}
static void deallocate(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_H
template
void construct(T1* p, const T2& value){
new (p) T1(value);
}
#endif
////////////////////////////////////////////////////////////////////////////////////////
#ifndef __STL_ITERATOR_H
#define __STL_ITERATOR_H
template
T* value_type(const T*){
return (T*)(0);
}
#endif
////////////////////////////////////////////////////////////////////////////////////////
#ifndef __STL_UNINITIALIZED_H
#define __STL_UNINITIALIZED_H
template
ForwardIterator _uninitialized_fill_n_aux(ForwardIterator first, Size n,
const T &x, _true_type){
cout<<"yyyyyyyyyyy"<
ForwardIterator _uninitialized_fill_n_aux(ForwardIterator first, Size n,
const T &x, _false_type){
ForwardIterator cur = first;
for(; n>0; --n, ++cur){
cout<<"xxxxxxxxxxxx"<
ForwardIterator _uninitialized_fill_n(ForwardIterator first, Size n, const T &x, T1*){
//typedef _false_type is_POD;
typedef typename _type_traits::is_POD_type is_POD;
//return _uninitialized_fill_n(first, n, x, _false_type());
return _uninitialized_fill_n_aux(first, n, x, is_POD());
}
template
ForwardIterator uninitialized_fill_n(ForwardIterator first, Size n, const T &x){
return _uninitialized_fill_n(first, n, x, value_type(first));
}
#endif
////////////////////////////////////////////////////////////////////////////////////////
#ifndef __STL_VECTOR_H
#define __STL_VECTOR_H
template
class vector{
public:
typedef T value_type;
typedef value_type* pointer;
typedef value_type* iterator;
typedef value_type& reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
public:
vector() : start(0), finish(0), end_of_storage(0){}
vector(size_type n){
fill_initialize(n, T());
}
protected:
void fill_initialize(size_type n, const T &value){
start = allocate_and_fill(n, value);
finish = start + n;
end_of_storage = finish;
}
iterator allocate_and_fill(size_type n, const T &x){
iterator result = data_allocator::allocate(n);
uninitialized_fill_n(result, n, x);
return result;
}
protected:
typedef simple_alloc data_allocator;
iterator start;
iterator finish;
iterator end_of_storage;
};
#endif
////////////////////////////////////////////////////////////////////////////////////////
#ifndef __TYPE_TRAITS_H
#define __TYPE_TRAITS_H
//
struct _true_type {};
struct _false_type{};
template
struct _type_traits {
typedef _true_type this_dummy_member_must_be_first;
typedef _false_type has_trivial_default_constructor;
typedef _false_type has_trivial_copy_constructor;
typedef _false_type has_trivial_assignment_operator;
typedef _false_type has_trivial_destructor;
typedef _false_type is_POD_type;
};
template<>
struct _type_traits {
typedef _true_type has_trivial_default_constructor;
typedef _true_type has_trivial_copy_constructor;
typedef _true_type has_trivial_assignment_operator;
typedef _true_type has_trivial_destructor;
typedef _true_type is_POD_type;
};
#endif
///////////////////////////////////////////////////////////////////////////////////////
#ifndef _VECTOR_H_
#define _VECTOR_H_
#include"memory.h"
#include"stl_vector.h"
#endif
///////////////////////////////////////////////////////////////////////////////////////
测试代码
#include
#include
#include"vector.h"
using namespace std;
class Test{};
int main(){
vector v(10); //开辟了10个元素的空间;
return 0;
测试结果
4、分析
(1)、vector的空间灵活性更高;
(2)、POD：也就是标量型别，也就是传统的型别，采取最保险安全的做法,调用构造函数；否则的话，就是调用系统的，基本类型就是true;
(3)、空构造了2个类型，针对不同萃取得到其_false_type或_true_type ; 就可以调用不同的函数，进行空间的分配，存在效率上的差异!!!
_true_type：将调用系统的填充函数，效率比较高.
(4)、容器、算法单独好实现，关键是通用性，模板是一种很好的解决方案，真正关键之处还在 : 迭代器的实现;
(5)、空间配置器负责分配、回收空间，只有一个；迭代器针对不同的容器有不同的实现方法!!!
另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
本文题目：STL的框架实现-创新互联
新闻来源：
http://jkwzsj.com/article/dpoopi.html
