STL——allocator

目录

1 JJ::allocator——STL源码解析

2 配置器std::alloc

2.1 二级配置器——__default_alloc_template

2.1.1 区块大小和空闲链块总数

2.1.2 union obj和free_list

2.1.3 从内存池获取区块放置free_list中

2.1.4 refill和chunk_alloc

2.1.5 allocate，deallocate，reallocate

3 全局函数construct，deconstruct

3.1 ：stl_alloc.h，stl_construct.h

3.1.1 stl_alloc.h——配置器

3.1.2 stl_construct.h——construct()和destroy()

3.2 construct和destroy

3.2.1 construct

3.2.2 destroy

4  全局函数uninitialized_copy，uninitialized_fill，uninitialized_fill_n

4.1 uninitialized_fill_n

4.2 uninitialized_fill

4.3 uninitialized_copy

allocator的必要接口

allocator	value_type
pointer
const_pointer
reference
const_reference
size_type
difference_type
rebind

allocator为什么需要这些成员函数，可以试着从new和delete的角度来分析

（1）new分配堆空间，需要size，type两个参数，即分配size大小的内存，类型为type。

（2）new分配完内存后，返回指向分配空间的首地址

（3）delete回收new分配的空间

为什么要实现这些必要的接口，除了从功能的角度，还可以从复用的角度来看。

标准就是为了复用，allocator是为上层容器提供服务的，所以它要稳定，一旦它不稳定，对于上层结构的冲击是巨大的——就像网络协议栈

稳定即意味着提供稳定不变的接口——不管内部实现是什么，要接口符合标准就行

空间配置器——只做空间分配和释放工作，不做初始化对象工作。（单一职责）

1 JJ::allocator——STL源码解析

#include <new>  //for placement new
/*
1、ptrdiff_t，与机器相关的数据类型，通常用来保存两个指针减法操作的结果，可正可负，是long int类型 
2、siz_t，用于指明数组长度，是unsigned乐星 
*/
#include <cstddef>  //for ptrdiff_t, size_t

#include <cstdlib>  //for exit()
#include <climits>  //for UINT_MAX
#include <iostream> //for cerr

using namespace std;

namespace JJ
{
template <typename T>
inline T* _allocate(ptrdiff_t size, T*){
    set_new_handler(0);  //当new分配空间失败时，不做任何处理 
    T* tmp = (T*)(::operator new((size_t)(size * sizeof(T))));  //封装了全局new操作符，而且使用operator() 
    if (tmp == 0){
        cerr << "out of memory" << endl;
        exit(1);
    }
    return tmp;
}

template <typename T>
inline void _deallocate(T* buffer){
    ::operator delete(buffer);  //使用operator()释放空间 
}

template <class T1, class T2>
inline void _construct(T1* p, const T2& value){
/*
定位new运算符——在为对象分配内存时，可以指定内存的位置，括号中放置指定位置的指针 
*/
    new(p) T1(value);  //placement new. invoke ctor of T1——在p指向的内存空间，调用T1的构造函数，并使用T2类型参数作为构造参数 
}

template <class T>
inline void _destroy(T* ptr){
    ptr->~T();
}

template <class T>
class allocator{
public:

    /*
        这种定义方式似乎使得程序的可读性变高了
		但是我在项目中曾经遇到一个BUG——比如，随着版本的迭代，value_type的本质变了，不再是T
		所以有的时候使用T本身可以带来不必要的麻烦 
    */
    typedef T value_type;
    typedef T* pointer;
    typedef const T* const_pointer;
    typedef T& reference;
    typedef const T& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    
    template <class U>
    struct rebind{
        typedef allocator<U> other;
    };
    
    pointer allocate(size_type n, const void* hint = 0){
        return _allocate((difference_type)n, (pointer)0);
    }
    
    void deallocate(pointer p, size_type n){
        _deallocate(p);
    }
    
    void construct(pointer p, const T& value){
        _construct(p, value);
    }
    
    void destroy(pointer p){
        _destroy(p);
    }
    
    pointer address(reference x){
	    return (pointer)&x;
	}
	
	const_pointer const_address(const_reference x){
	    return (const_pointer)&x;
	}
	
	size_type max_size() const{
	    return size_type(UINT_MAX/sizeof(T));
	} 
};

} 

#include <vector>
#include <algorithm>
using std::vector;
using namespace JJ;

int main(int argc, char** argv) {
    
    int array[5] = {1, 2, 3, 4, 5};
	unsigned int i;
	
	vector<int, JJ::allocator<int> > v(array, array + 5);
	for_each(v.begin(), v.end(), [](int i){ cout << i << endl;});
	return 0;
}
           

2 配置器std::alloc

双层级配置器std::alloc，128bytes是阈值

1、typedef __malloc_alloc_template<0> malloc_alloc; typdef malloc_alloc alloc;——第一级配置器

当要求的内存大于128bytes时，使用该配置器。

成员函数allocate调用malloc分配内存，返回一个void *指针

成员函数deallocate调用free释放内存，返回void

2、typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;——第二级配置器

使用内存池，由free_lists管理16个节点，每个节点管理的区块大小分别为——8，16，24，32，40，48，56，64，72，80，88，96，104，112，120，128bytes

每个节点管理着该节点对应的区块大小的链表，如果需要分配的节点在128bytes范围内，则找到最匹配节点（不满8的倍数，按照8的倍数分配），分配给客户端。

SGI为alloc包装了一个接口，使得其符合STL规范

template <class T, class Alloc>
class simple_alloc{
public:
    static T *allocate(size_t);
    static T *allocate(void);
    static void deallocate(T*, size_t);
    static void deallocate(T*);
};


//这种定义方式多用在容器中
typedef simple_alloc<T, alloc> data_allocator;
           

2.1 二级配置器——__default_alloc_template

源码——128bytes为一个门限，大于128bytes就调用第一级配置器

#include <iostream>
#include <new.h>
using namespace std;

enum { __ALIGN = 8 };  //小型区块的上调边界 
enum { __MAX_BYTES = 128 };  //小型区块上限 
enum { __NFREELISTS = __MAX_BYTES / __ALIGN };  //free-lists 个数 

template <bool threads, int inst>
class default_alloc_template{
private:
	static size_t ROUND_UP(size_t bytes){
		//~(__ALIGN - 1）= 11111000
		//与的过程中，把0~7的值全部消除，只留下了8的倍数
		//而且 + (__ALIGN - 1)保证了返回值必然 >= bytes 
		return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));   
	}
private:
	union obj{
		union obj * free_list_link;  //在64位Windows系统gcc编译器上，指针的大小为8字节 
		char client_data[1];  //这里的值是地址低字节的值 
	};
private:
    //16个free-lists：8, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96, 104, 112, 120, 128。
	//这个有点类似hash-table的buckets-nodes结构 
	//每个数组节点管理一个链表，同一链表上的节点区块大小相等 
	//volatile告诉编译器这是个“易变化”的变量，随时可能改变。
	//这样编译器就不会对它进行某些优化——比如不会从寄存器读取数据，而是从变量地址读取；
	//                                    比如不会调整指令顺序以优化CPU指令流水线 
	static obj * volatile free_list[__NFREELISTS];  //一个数组，效率高 
	
	static size_t FREELIST_INDEX(size_t bytes){
		return ((bytes) + __ALIGN - 1) / __ALIGN - 1;  //返回数组的索引——索引与请求的区块的小是一一对象的 
	}
		
	
private: 
	//返回一个大小为 n 的对象，并可能加入大小为 n 的其它区块到 free-list 
	static void *refill(size_t n);
	//配置一大块空间，可容纳 nobjs 个大小为 "size" 的区块
	//如果配置 nobjs 个区块有所不便，nobjs 可能会降低
	static char *chunk_alloc(size_t size, int &nobjs);
	
	//Chunk allocation state
	static char *start_free;  //内存池起始位置。只在chunk_alloc()中变化 
	static char *end_free;  //内存池结束为止。只在chunk_alloc()中变化 
	static size_t heap_size; 
	
public:
	static void * allocate(size_t n);
	static void deallocate(void *p, size_t n);
	static void * reallocate(void *p, size_t old_sz, size_t new_sz);
}; 

//staitc data memeber的定义与初值设定
template <bool threads, int inst>
char *default_alloc_template<threads, inst>::start_free = 0; 

template <bool threads, int inst>
char *default_alloc_template<threads, inst>::end_free = 0;

template <bool threads, int inst>
size_t default_alloc_template<threads, inst>::heap_size = 0;  //初值为0 

template <bool threads, int inst>
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
};


// allocate的算法
//（1）首先判断区块大小，大于128bytes就调用第一级配置器，小于128bytes就检查对应free-lists
//（2）小于128bytes——在free_list上寻找适当的区块，返回当前索引 
template <bool threads, int inst>
void * default_alloc_template<threads, inst>::allocate(size_t n)
{
    if (n > (size_t) __MAX_BYTES)
	{
		return malloc(n); //第一级配置器的allocate()内部直接使用malloc()分配 
	}	
	
	obj * volatile * my_free_list;
	obj * result;
	//寻找free_list中适当的区块
	my_free_list = free_list + FREELIST_INDEX(n); //my_free_list为数据节点的地址 
	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 <bool threads, int inst>
void default_alloc_template<threads, inst>::deallocate(void * p, size_t n)
{
	//大于128就调用第一级配置器
	if (n > (size_t) __MAX_BYTES){
		free(p);
		return;
	} 
	
	obj * q = (obj *)p;
	obj * volatile * my_free_list;
	//寻找对应的free list 
	my_free_list = free_list + FREELIST_INDEX(n);
	//调整free list，回收区块
	q->free_list_link = *my_free_list;  //把待回收的区块插入到当前空闲区块的前面 
	*my_free_list = q;   //使得索引对应的值为首部指针 
}


//如果free_list没有可用区块，调用refill()，准备为free_list重新填充空间
//新的空间将取自内存池（经由chunk_alloc()）完成
//缺省取得20个新节点（新区块），但万一内存池空间不足，获得的节点数（区块数）可能小于20
 
template <bool threads, int inst>
void * default_alloc_template<threads, inst>::refill(size_t n)  //假设 n 已经调节为 8 的倍数 
{
    int nobjs = 20;
    //调用chunk_alloc()，尝试取得nobjs个区块作为free_list的新节点
	//注意参数nobjs是pass by reference
	char * chunk = chunk_alloc(n, nobjs);  //chunk_alloc分配了一个块。这个块共有20个节点，每个节点大小为 n。
	
	obj * volatile * my_free_list;
	obj * result;
	obj * current_obj, *next_obj;
	int i;
	
	//如果只获得一个区块，这个区块就分配给调用者用，free_list无新节点
	if (1 == nobjs)
	    return (chunk);
	//否则准备调整free_list，纳入新节点
	my_free_list = free_list + FREELIST_INDEX(n);
	
	//以下在 chunk 空间内建立 free_list
	result = (obj*)chunk;  //把块的第一个节点返回给客户端，剩下的链接到free_list 
	//导引free_list指向新配置的空间（取自内存池）
	*my_free_list = next_obj = (obj *)(chunk + n);  //这里它把请求的内存块解释为 union obj
	                                                //即该内存块的前8个字节存放的是union obj 
	                                                //这样也就满足了前面一个union既可以指向下一个union obj，又可以指向内存块
													//因为通过数组下标，即可访问obj后续的空闲内存块。 
	//将free_list的各节点串接起来
	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);
}

//内存池——memory pool
//chunk_alloc操作的对象时内存池，从内存池中取得所需内存
//如果内存池空间不足，则重新malloc内存
//如果malloc不到，则从free_list寻找空闲的区块，赋给内存池，再对内存池chunk_alloc 
template <bool threads, int inst>
char * default_alloc_template<threads, inst>::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;  //剩余空间共有 nobjs 个区块
		total_bytes = size * nobjs;
		result = start_free;
		start_free += total_bytes;  //把剩余空间都分配到free_list上 
		return (result); 
	}else{
		//内存池剩余空间连一个区块的大小都无法提供，则扩充内存池，重新调用chunk_alloc 
		//分配所需空间的两倍 
		size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);  //为什么要向右移动4位或者说为什么要除以8 
		//让内存池的残余零头插入到free_list对应位置上 
		if (bytes_left > 0)
		{
			obj * volatile * my_free_list = free_list + FREELIST_INDEX(bytes_left);  //这里索引用的是bytes_left，而不是size 
			((obj *)start->free)->free_list_link = *my_free_list;  //使得新节点为索引所指链表的头结点 
			*my_free_list = (obj *)start_free;  //指向插入新节点后的链表的头结点 
		 } 
		 
		 //链表节点管理的链表为空才会调用refill，refill调用chunk_alloc分配大块内存
		 //如果内存池中空间满足需求，则分配出去，否则，把剩余空间分配出去；
		 //如果内存池空间不足一个size，则重新malloc两倍空间 
		 //配置heap空间，用来补充内存池
	    start_free = (char *)malloc(bytes_to_get);  //分配所需空间的两倍 
	    if (0 == start_free){
	    	//malloc()失败
			int i;
			obj * volatile * my_free_list, *p;
			//malloc()失败，则从free_list上寻找可用空间（从大于size的区块的索引开始寻找） 
			for (i = size; i <= __MAX_BYTES; i += __ALIGN){
				my_free_list = free_list + FREELIST_INDEX(i);  //遍历free_list，寻找比size更大的区块 
				p = *my_free_list;
				if (0 != p)
				{
				   *my_free_list = p->free_list_link;
				   start_free = (char *)p;    //把链表中大于size且空闲的空间赋给内存池 
				   end_free = start_free + i;
				   return (chunk_alloc(size, nobjs));  //递归调用自己，修正nobjs 
				}
			} 
            //如果free_list上也没有满足需求的空闲区块 
			end_free = 0;
			start_free = (char *)malloc(bytes_to_get);  //调用第一级配置器，借用out-of-memory机制 
		}
	
	heap_size += bytes_to_get;
	end_free = start_free + bytes_to_get;
	return (chunk_alloc(size, nobjs)); 
	} 
} 



int main(int argc, char** argv){
   
	
	return 0;
}
           

2.1.1 区块大小和空闲链块总数

enum { __ALIGN = 8 };  //小型区块的上调边界 
enum { __MAX_BYTES = 128 };  //小型区块上限 
enum { __NFREELISTS = __MAX_BYTES / __ALIGN };  //free-lists 个数
           

为什么是8？

从union obj的内部结构来看，在32位下，sizeof(obj) = 4；在64位下，sizeof(obj) = 8；所以，最小的区块大小为8，且其他均为8的倍数。（个人认为是这样的原因，毕竟底层实现中，数据结构和算法还是耦合在一起的）

2.1.2 union obj和free_list

union obj{
 		union obj * free_list_link;  //在64位Windows系统gcc编译器上，指针的大小为8字节 
		char client_data[1];  //这里的值是地址低字节的值 
	};

	static obj * volatile free_list[__NFREELISTS];  //一个数组，效率高 
	
	static size_t FREELIST_INDEX(size_t bytes){
		return ((bytes) + __ALIGN - 1) / __ALIGN - 1;  //返回数组的索引——索引与请求的区块的小是一一对象的 
	}
           

书中说：union obj，从第一字段来看，obj可被视为一个指针，指向相同形式的另一个obj；从第二个字段来看，obj可被视为一个指针，指向实际区块。一物二用。（这样可以避免为了维护链表所必须的指针而造成内存的一种浪费）

union obj，从定义来看，char[0-3/7]和obj *公用同一段存储空间，char[0-3/7]所指空间已经被obj *的值所填充了，其本身并不能存储数据，所以，只看定义无法很快理解它的效果。需要结合实际应用。

char * chunk = chunk_alloc(n, nobjs);  //chunk_alloc分配了一个块。这个块共有20个节点，每个节点大小为 n。
	
	obj * volatile * my_free_list;
	obj * result;
	obj * current_obj, *next_obj;
	int i;
	
	//如果只获得一个区块，这个区块就分配给调用者用，free_list无新节点
	if (1 == nobjs)
	    return (chunk);
	//否则准备调整free_list，纳入新节点
	my_free_list = free_list + FREELIST_INDEX(n);
	
	//以下在 chunk 空间内建立 free_list
	result = (obj*)chunk;  //把块的第一个节点返回给客户端，剩下的链接到free_list 
	//导引free_list指向新配置的空间（取自内存池）
	*my_free_list = next_obj = (obj *)(chunk + n);
           

在refill中用到了union obj *，这里就可以了解一物二用的原理了——当把一个大块内存空间解释为union obj时，只有内存空间的前几个字节被占用，后面的内存仍然是空闲的。这也正对应书中所画的图——union obj在大块内存的前面一小部分。

这样就可以使用union obj中指针指向另一个区块，而使用client_data来访问空闲区块

2.1.3 从内存池获取区块放置free_list中

//返回一个大小为 n 的对象，并可能加入大小为 n 的其它区块到 free-list 
	static void *refill(size_t n);
	//配置一大块空间，可容纳 nobjs 个大小为 "size" 的区块
	//如果配置 nobjs 个区块有所不便，nobjs 可能会降低
	static char *chunk_alloc(size_t size, int &nobjs);
	
	//Chunk allocation state
	static char *start_free;  //内存池起始位置。只在chunk_alloc()中变化 
	static char *end_free;  //内存池结束为止。只在chunk_alloc()中变化 
	static size_t heap_size; 
           

static char *start_free;  static char *end_free; 分别指向分配的内存块的首部和尾部

refill调用chunk_alloc分配多个大块内存，分出一个给客户端，其他的放入free_list中

chunk_alloc从内存池中获取一整块内存，如果内存池没有，则重新malloc到内存池——>如果malloc失败则从free_list上请求大于size的空闲区块——>如果free_list也没有，则使用第一级配置器来分配内存（其有out-of-memory机制可以跑出异常或释放出一些内存）。

2.1.4 refill和chunk_alloc

1、refill的算法

（1）调用chunk_alloc获取大块内存

（2）把第一块内存返回给客户端

（3）剩下的内存插入到free_list成链

2、chunk_alloc算法

（1）chunk_alloc操作的对象时内存池，从内存池中取得所需内存

（2）如果内存池空间不足，则重新malloc内存

（3）如果malloc不到，则从free_list寻找空闲的区块，赋给内存池，再对内存池chunk_alloc 

（4）都不行，则调用第一级配置器的allocate分配内存，利用其out-of-memory机制解围 

2.1.5 allocate，deallocate，reallocate

当free_list中需求的区块空间不足时，调用allocate，reallocate中会调用refill来获取空间

1、allocate的算法

（1）首先判断区块大小，大于128bytes就调用第一级配置器，小于128bytes就检查对应free-lists

（2）小于128bytes——在free_list上寻找适当的区块，返回当前索引 

2、deallocate的算法

（1）大于128bytes则调用第一级配置器

（2）寻找当前回收的区块大小对应的索引，把该区块插入该索引管理的链表首部

3 全局函数construct，deconstruct

类有构造函数，有析构函数

当声明了一个类对象，空间配置器为它分配空间，并调用类的构造函数把内存空间初始化

即内存空间的配置与释放和对象内容的构造与析构是分开的。

3.1 <memory>：stl_alloc.h，stl_construct.h

配置器的std::alloc定义于<memory>中，内含两个文件

#include <stl_alloc.h>  //负责内存空间的配置和释放

#include <stl_constuct.h>  //负责对象内容的构造与析构

3.1.1 stl_alloc.h——配置器

负责内存空间的配置与释放

3.1.2 stl_construct.h——construct()和destroy()

construct()负责对象的构造

destroy()负责对象的析构

3.2 construct和destroy

3.2.1 construct

construct全局函数通过在分配了内存空间的p指针上，调用构造函数来构造对象。——使用placement new：new(p) T(value)

template <class T1, class T2>
inline void construct(T1* p, const T2& value){
    new (p) T2(value);
}
           

3.2.2 destroy

有两种

1、通过指针调用析构函数

template <class T>
inline void destroy(T* pointer){
    pointer->~T();
}
           

2、判断元素的数值型别是否有trivial destructor

（1）有，则destroy不做任何事

（2）无，则通过指针调用析构函数

template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last, T*)
{
    __destroy(first, last, value_type(first));
}

template <class ForwardIterator, class T>
inline void __destroy(ForwardIterator first, ForwardIterator last, T*)
{
    typedef typename _type_traits<T>::has_trival_destructor trivial_destructor;
    __destroy_aux(first, last, trivial_destructor());
}


template <class ForwardIterator>
inline void __destroy_aux(ForwardIterator first, ForwardIterator last, T*)
{
    for (; first < last; ++first)
        destroy(&*first);
}
           

4  全局函数uninitialized_copy，uninitialized_fill，uninitialized_fill_n

三个函数都具有“ commit or rollback ”语意——要么构造出所有必要元素，要么（当有任何一个copy constructor失败时）不构造任何东西。

uninitialized_copy()

uninitialized_fill()

uninitialized_fill_n()

PS：

虽然这些函数不属于配置器的范畴，但与对象初值设置有关。

对于容器的大规模元素初值设置很有帮助。对于效率的考虑也面面俱到——最差情况下调用construct()，最佳情况使用C标准memmove()直接进行内存数据移动。

4.1 uninitialized_fill_n

从first开始，使用x，初始化往后n个对象

template <class ForwardIterator, class Size, class T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first, 
                                            Size n, const T& x){
    return __uninitialized_fill_n(first, n, x, value_type(first));
}

template <class ForwardIterator, class Size, class T, class T1>
inline ForwardIterator __uninitialized_fill_n(ForwardIterator first, Size n,
                                              const T& x, T1*)
{
    typedef typename __type_trait<T1>::is_POD_type is_POD;
    return __uninitialized_fill_n_aux(first, n, x, is_POD());
}


//POD型别
//调用高阶函数fill_n实现——可能直接memcopy了
template <class ForwardIterator, class Size, class T>
inline ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, 
                                            Size n, const T& x, __true_type){
    return fill_n(first, n, x);
}

//非POD型别
//采用安全的方法——调用构造函数
template <class ForwardIterator, class Size, class T>
inline ForwardIterator __uninitialized_fill_n_aux(ForwardIterator first, 
                                            Size n, const T& x, __false_type){
    ForwardIterator cur = first;
    for (; n > 0; --n, ++cur)
        construct(&*cur, x);  //传入指针，通过指针调用构造函数
    return cur;
}
           

1、首先萃取出迭代器first的value_type，然后判断型别是否为POD型别

POD意指Plain Old Data，即标量型别或传统的C struct。

POD型别必然拥有trivial ctor/dtor/copy/assignment函数，因此可以对POD型别采用最高效的初值填写手法。

4.2 uninitialized_fill

用x，初始化从first到last的所有对象

形式与uninitialized_fill_n差不多

4.3 uninitialized_copy

把first到last的对象复制到result开始的容器中

template <class InputIterator, class ForwardIterator>
inline ForwardIterator uninitialized_copy(InputIterator first, InputIterator last,
                                          ForwardIterator result){
    return __uninitialized_fill_n(first, n, x, value_type(first));
}

template <class InputIterator, class ForwardIterator, class T>
inline ForwardIterator __uninitialized_copy(InputIterator first, InputIterator last,
                                            ForwardIterator reslut, T*){
    typedef typename __type_trait<T1>::is_POD_type is_POD;
    return __uninitialized_copy_aux(first, last, result, is_POD());
}

//POD型别
//调用高阶函数fill_n实现——可能直接memcopy了
template <class InputIterator, class ForwardIterator>
inline ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
                                            ForwardIterator reslut, __true_type){
    return copy(first, last, result);
}

//非POD型别
//采用安全的方法——调用构造函数
template <class InputIterator, class ForwardIterator>
inline ForwardIterator __uninitialized_copy_aux(InputIterator first, InputIterator last,
                                            ForwardIterator reslut, __false_type){
    ForwardIterator cur = result;
    for (; n > 0; --n, ++cur)
        construct(&*cur, *first);  //传入指针，通过指针调用构造函数
    return cur;
}
           

对于char*和wchar_t*两种型别，可以采用最具效率的做法memmove（直接移动内存内容）来执行复制行为

inline char* uninitialized_copy(const char* first, const char* last, char* result)
{
    memmove(result, first, last - first);
    return result + (last - first);  //返回最后位置？？
}

inline wchar_t* uninitialized_copy(const wchar_t* first, const wchar_t* last, 
                                   wchar_t* result)
{
    memmove(result, first, sizeof(wchar_t) * (last - first));
    return result + (last - first);
}