SGI STL 标准库 空间配置器 1

STL 空间配置器

github源码分析仓库

STL实现了两个空间配置器,std::allocatorstd::allocstd::allocator是STL标准的空间配置器,是对C++的::operator new::operator delete的简单封装。std::alloc是SGI自定义的特殊的空间配置器。std::alloc是SGI STL各个容器的缺省空间配置器。

C++ new和delete 在alloc中的分解

C++内存配置操作和释放操作new和delte,分别包含两阶段操作:
对new

  1. 调用::operator new分配空间
  2. 调用对象的构造函数

对delete

  1. 调用对象的析构函数
  2. 调用::operator delete释放空间

STL alloc将new与delete的两个阶段区分开来,内存配置操作alloc::allocate(),内存释放操作alloc::deallocate(),对象构造::construct(),对象析构::destroy()

构造和析构工具 construct()和destroy()

源代码<stl_construct.h>的部分内容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <new.h>
template <class _T1, class _T2>
inline void _Construct(_T1* __p, const _T2& __value) {
new ((void*) __p) _T1(__value); //调用 T1::T1(value) 在__p所指的内存空间上构造T1
}

template <class _T1>
inline void _Construct(_T1* __p) {
new ((void*) __p) _T1(); //调用 T1::T1() 在__p所指的内存空间上构造T1
}

template <class _Tp>
inline void _Destroy(_Tp* __pointer) {
__pointer->~_Tp(); //调用析构函数
}

//需要调用析构函数 有non-trivial destrucotr
template <class _ForwardIterator>
void
__destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type)
{
for ( ; __first != __last; ++__first)
destroy(&*__first);
}

//不需要调用析构函数 有trivial destrucotr
template <class _ForwardIterator>
inline void __destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {}

//判断元素的数值型别(value type)调用具体的函数
template <class _ForwardIterator, class _Tp>
inline void
__destroy(_ForwardIterator __first, _ForwardIterator __last, _Tp*)
{
typedef typename __type_traits<_Tp>::has_trivial_destructor
_Trivial_destructor;
__destroy_aux(__first, __last, _Trivial_destructor());
}

//接受两个迭代器,找出元素的数值型别,根据__type_traits<>调用最合适的函数
template <class _ForwardIterator>
inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
__destroy(__first, __last, __VALUE_TYPE(__first));
}

//对内置类型的特化版本
inline void _Destroy(char*, char*) {}
inline void _Destroy(int*, int*) {}
inline void _Destroy(long*, long*) {}
inline void _Destroy(float*, float*) {}
inline void _Destroy(double*, double*) {}
inline void _Destroy(wchar_t*, wchar_t*) {}

template <class _T1, class _T2>
inline void construct(_T1* __p, const _T2& __value) {
_Construct(__p, __value);
}

template <class _T1>
inline void construct(_T1* __p) {
_Construct(__p);
}

template <class _Tp>
inline void destroy(_Tp* __pointer) {
_Destroy(__pointer);
}

template <class _ForwardIterator>
inline void destroy(_ForwardIterator __first, _ForwardIterator __last) {
_Destroy(__first, __last);
}

destroy(_Tp *)直接调用_Destroy(_Tp *)执行析构函数。
destroy(_ForwardIterator, _ForwardIterator)有特化版本则直接调用,否则调用_Destroy(_ForwardIterator, _ForwardIterator),通过__VALUE_TYPE()得到要析构对象的值类型,调用__destroy(_ForwardIterator __first,_ForwardIterator __last, _Tp ),使用类型萃取,通过_Trivial_destructor()区分调用__destroy_aux(_ForwardIterator, _ForwardIterator, __true_type)或者调用__destroy_aux(_ForwardIterator, _ForwardIterator, __false_type)

construct(_T1*, const _T2&)调用_Construct(_T1* __p, const _T2& __value),执行new ((void*) __p) _T1(__value),构造一个对象。
construct(_T1*)调用_Construct(_T1* __p),执行new ((void*) __p) _T1(),构造一个对象。

空间的配置和释放

对象构造前的空间配置和对象析构后的空间释放,由<stl_alloc.h>负责。C++的内存配置基本操作是::operator new()、内存释放操作是::operator delete(),相当于C的malloc()free()函数,SGI用malloc()free()完成内存的配置和释放。
SGI设计双层空间配置器,解决小块内存可能造成的内存碎片问题,第一级配置器直接使用malloc()free(),第二级配置器根据不同情况采用不同策略,当要配置的内存块大于128b,调用第一次配置器,当配置的内存块小于128b,则采用memory pool整理方式。__USE_MALLOC用来控制配置器的使用,如果定义了__USE_MALLOC则只开放第一级空间配置器。
为了使配置器的接口符合STL规格,SGI为alloc包装了接口:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
typedef __malloc_alloc_template<0> malloc_alloc;

# ifdef __USE_MALLOC
// 定义__USE_MALLOC则将__malloc_alloc_template定义为alloc
typedef malloc_alloc alloc;
# else
// 否则将__default_alloc_template定义为alloc
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
# endif

template<class _Tp, class _Alloc>
class simple_alloc {

public:
static _Tp* allocate(size_t __n)
{ return 0 == __n ? 0 : (_Tp*) _Alloc::allocate(__n * sizeof (_Tp)); }
static _Tp* allocate(void)
{ return (_Tp*) _Alloc::allocate(sizeof (_Tp)); }
static void deallocate(_Tp* __p, size_t __n)
{ if (0 != __n) _Alloc::deallocate(__p, __n * sizeof (_Tp)); }
static void deallocate(_Tp* __p)
{ _Alloc::deallocate(__p, sizeof (_Tp)); }
};

simplealloc的四个成员函数都是单纯的转调用,调用传递给配置器。同时将要配置元素的个数__n转化为要配置的空间大小``(__n*sizeof(_Tp))。实际使用时都调用simple_alloc``。

一级空间配置器 __malloc_alloc_template

  1. allocate()直接使用malloc()deallocate()直接使用free()
  2. 模拟C++的set_new_handler()处理内存不足的情况

二级空间配置器 __default_alloc_template

  1. 维护16个自由链表,负责16种小块内存的配置,内存池用malloc配置,如果内存不足,调用一级空间配置器
  2. 如果需要配置的内存块大于128b,直接调用一级空间配置器

一级空间配置器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//没有template型别参数 非型别参数__inst未使用
template <int __inst>
class __malloc_alloc_template {

private:

//函数指针 所代表的函数用来处理内存不足的情况
static void* _S_oom_malloc(size_t);
static void* _S_oom_realloc(void*, size_t);
static void (* __malloc_alloc_oom_handler)();
public:

static void* allocate(size_t __n)
{
void* __result = malloc(__n); //一级配置器直接使用malloc()
if (0 == __result) __result = _S_oom_malloc(__n); //内存不足,调用_S_oom_malloc
return __result;
}

static void deallocate(void* __p, size_t /* __n */)
{
free(__p); //一级配置器直接使用free()释放空间
}

static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
{
void* __result = realloc(__p, __new_sz); //一级配置器直接使用realloc()
if (0 == __result) __result = _S_oom_realloc(__p, __new_sz); //空间不足,调用_S_oom_realloc()
return __result;
}

//设置out-of-memory handler 仿真C++ set_new_handler()
static void (* __set_malloc_handler(void (*__f)()))()
{
void (* __old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = __f;
return(__old);
}

};

//初始值设为0
template <int __inst>
void (* __malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;

template <int __inst>
void*
__malloc_alloc_template<__inst>::_S_oom_malloc(size_t __n)
{
void (* __my_malloc_handler)();
void* __result;
//如果存在__malloc_alloc_oom_handler则不断调用,尝试释放、配置、再释放、再配置,
//直到分配成功。 否则 抛出异常 或者 执行exit(1)退出程序。
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 <int __inst>
void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
{
void (* __my_malloc_handler)();
void* __result;

//如果存在__malloc_alloc_oom_handler则不断调用,尝试释放、配置、再释放、再配置,
//直到分配成功。 否则 抛出异常 或者 执行exit(1)退出程序。
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);
}
}

// 直接将参数inst指定为0
typedef __malloc_alloc_template<0> malloc_alloc;

第一级空间配置器以malloc()、free()、realloc()等C函数执行实际的内存配置、释放、重配置操作,并实现类似C++ new-handler的机制。因为它未使用::operator new配置内存,所以不能直接运用C++ new-handler。C++ new-handler机制,要求系统在内存配置需求无法被满足时,调用一个指定的函数。

第二级空间配置器

第二级空间配置器避免太多小内存块造成内存碎片。
SGI第二级配置器,如果配置内存块大于128B时,调用第一级配置器处理,当配置内存块小于128B时,用内存池管理,即每次配置一大块内存,并维护对应的自由链表(free-list),下次再分配相同大小的内存快时,从free-list拨出,释放小块内存则加入到free-list中。为了方便管理,SGI二级配置器,将任何小块内存调整为8的倍数,并维护16个free-list,各自管理大小分别为8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128B的小块内存。
free-list节点结构:

1
2
3
4
union _Obj {
union _Obj* _M_free_list_link;
char _M_client_data[1]; /* The client sees this. */
};

使用union,从第一个字段看,_Obj可看做一个指针,指向相同形式的另一个_Obj,从第二个字段看,指向实际内存。不会为了维护联播所必须的指针造成内存的另一种浪费。
空间配置函数allocate()首先判断申请内存块的大小,大于128B,调用第一级空间配置器,小于128B检查对应的free-list,如果free-list有可用内存块,直接拿来用,如果没有,将区块大小上调至8的倍数,调用_S_refill()重新为free-list重新填充空间。
空间释放函数deallocate()首先判断内存块大小,大于128B调用第一级配置器,小于128B找到对应free-list将区块回收。
填充操作和内存池的实现看下面代码(附注释)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
//threads用于多线程环境
template <bool threads, int inst>
class __default_alloc_template {
private:
enum {_ALIGN = 8};
enum {_MAX_BYTES = 128};
enum {_NFREELISTS = 16}; // _MAX_BYTES/_ALIGN
//将__bytes上调至8的倍数
static size_t
_S_round_up(size_t __bytes)
{ return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1)); }

//free-lists的节点
union _Obj {
union _Obj* _M_free_list_link; //指向下一个可用的相同大小的内存块
char _M_client_data[1]; /* The client sees this. */
};
private:
// 16个free_lists
static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];
//根据要分配的内存块大小__bytes决定使用第n号free_lists。n从1起算。
static size_t _S_freelist_index(size_t __bytes) {
return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
}
// 返回一个大小为n的对象,并可能加入大小为__n的其它内存块到free_lists
static void* _S_refill(size_t __n);
// 配置一大块,可容纳__nobjs个大小为"__size"的内存块
// 如果配置__nobjs个内存块不足,可以减少数量
static char* _S_chunk_alloc(size_t __size, int& __nobjs);
static char* _S_start_free; //内存池起始位置,只在_S_chunk_alloc()中改变
static char* _S_end_free; //内存池结束位置,只在_S_chunk_alloc()中改变
static size_t _S_heap_size;

public:

/* __n must be > 0 空间分配函数*/
static void* allocate(size_t __n)
{
void* __ret = 0;
// 大于128直接调用第一级空间配置器
if (__n > (size_t) _MAX_BYTES) {
__ret = malloc_alloc::allocate(__n);
}
else {
//寻找16个free_lists中适当的一个
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
//获取free_lists
_Obj* __RESTRICT __result = *__my_free_list;
if (__result == 0)
//没有可用的free_lists,准备重新填充free_lists
__ret = _S_refill(_S_round_up(__n));
else {
//有可用的,free_lists调整下
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
};

/* __p may not be 0 空间释放函数*/
static void deallocate(void* __p, size_t __n)
{
// 大于128直接调用艺集空间配置器
if (__n > (size_t) _MAX_BYTES)
malloc_alloc::deallocate(__p, __n);
else {
//寻找对应的free_lists
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n);
_Obj* __q = (_Obj*)__p;
// 调整free_lists,回收内存块
__q -> _M_free_list_link = *__my_free_list;
*__my_free_list = __q;
}
}

static void* reallocate(void* __p, size_t __old_sz, size_t __new_sz);

} ;

typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc;
typedef __default_alloc_template<false, 0> single_client_alloc;

template <bool __threads, int __inst>
inline bool operator==(const __default_alloc_template<__threads, __inst>&,
const __default_alloc_template<__threads, __inst>&)
{
return true;
}

// 假设__size已经上调至8的倍数
// __nobjs是期望获得的内存块个数,传引用,用来返回实际分配的内存块个数
template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size,
int& __nobjs)
{
char* __result;
size_t __total_bytes = __size * __nobjs; //总共需要的内存块大小
size_t __bytes_left = _S_end_free - _S_start_free; //内存池剩余空间

if (__bytes_left >= __total_bytes) { //内存池剩余空间足够
__result = _S_start_free;
_S_start_free += __total_bytes; //调整内存池起始位置
return(__result);
} else if (__bytes_left >= __size) {
//内存池剩余空间不能完全满足需求量,但足够分配一个及以上的内存块
__nobjs = (int)(__bytes_left/__size); //计算可分配的内存块的个数
__total_bytes = __size * __nobjs; //重新计算分配出去的内存块大小
__result = _S_start_free;
_S_start_free += __total_bytes; //调整内存池起始位置
return(__result);
} else {
//内存池剩余空间不足分配一个内存块
//计算重新申请内存池的大小
size_t __bytes_to_get =
2 * __total_bytes + _S_round_up(_S_heap_size >> 4);
// Try to make use of the left-over piece.
if (__bytes_left > 0) {
//内存池还有部分空间,尝试利用它们 将其加入free_lists
_Obj* __STL_VOLATILE* __my_free_list =
_S_free_list + _S_freelist_index(__bytes_left);

((_Obj*)_S_start_free) -> _M_free_list_link = *__my_free_list;
*__my_free_list = (_Obj*)_S_start_free;
}
//直接调用malloc()申请内存空间
_S_start_free = (char*)malloc(__bytes_to_get);
if (0 == _S_start_free) {
//malloc()分配失败
size_t __i;
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __p;
// 尝试从“尚未使用的内存块,且足够大”的free_lists中找一个内存块
// 作为新的内存池
for (__i = __size;
__i <= (size_t) _MAX_BYTES;
__i += (size_t) _ALIGN) {
//得到free_lists
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;
if (0 != __p) {
//free_lists有未使用的内存块 调整free_lists去除未使用的内存块
*__my_free_list = __p -> _M_free_list_link;
//将取出的内存块作为内存池 设置内存池的起始位置和结束位置
_S_start_free = (char*)__p;
_S_end_free = _S_start_free + __i;
//递归调用下,返回申请的空间
return(_S_chunk_alloc(__size, __nobjs));
}
}
//找不到合适的内存块
_S_end_free = 0; // In case of exception.
//调用一级配置器,尝试out-of-memory
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
// 调用一级配置器,可以得到内存或者抛出异常(或直接结束程序)
}
//分配到新的内存池,调整下大小,设置内存池结束为止
_S_heap_size += __bytes_to_get;
_S_end_free = _S_start_free + __bytes_to_get;
//递归调用下,返回申请的空间,修正__nobjs
return(_S_chunk_alloc(__size, __nobjs));
}
}


// 返回一个大小为_n的对象,并且适当的为free_lists增加节点 要求__n已适当上调为8的倍数
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n)
{
int __nobjs = 20;
//调用_S_chunk_alloc,尝试取得nobjs个内存块作为free_lists的新节点
//__nobjs传引用,返回获得节点的个数
char* __chunk = _S_chunk_alloc(__n, __nobjs);
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;

//如果只获取到一个内存块,返回给调用者使用,free_lists未新加节点
if (1 == __nobjs) return(__chunk);
//调整free_lists新加节点
__my_free_list = _S_free_list + _S_freelist_index(__n);

//在__chunk空间建立free_lists
__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 -> _M_free_list_link = 0;
break;
} else {
__current_obj -> _M_free_list_link = __next_obj;
}
}
return(__result);
}

template <bool threads, int inst>
void*
__default_alloc_template<threads, inst>::reallocate(void* __p,
size_t __old_sz,
size_t __new_sz)
{
void* __result;
size_t __copy_sz;

if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) {
return(realloc(__p, __new_sz));
}
if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
__result = allocate(__new_sz);
__copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
memcpy(__result, __p, __copy_sz);
deallocate(__p, __old_sz);
return(__result);
}

//__default_alloc_template中static成员定于与初始值设定
template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;

template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;

template <bool __threads, int __inst>
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;

template <bool __threads, int __inst>
typename __default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE
__default_alloc_template<__threads, __inst> ::_S_free_list[
__default_alloc_template<__threads, __inst>::_NFREELISTS
] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };

内存基本处理工具

STL定义五个全局函数,construct()、destroy()、uninitialized_copy()、uninitialized_fill()、uninitialized_fill_n(),作用于内存空间。
construct()用于构造,destroy()用于析构。
uninitialized_copy()uninitialized_fill()uninitialized_fill_n()分别对应高层次函数copy()fill()fill_n()
uninitialized_copy()uninitialized_fill()uninitialized_fill_n()都具有要么产生所有必要元素,否则就不产生任何元素的机制。如果任何一个拷贝构造抛出异常,必须析构已产生的所有元素。
POD(Plain Old Data)即标量类型或传统C struct类型。POD类型必然有无价值的(trivial) ctor/dtor/copy/assignment函数,因此对于POD类型采用最有效率的操作,对非POD类型调用其ctor/dtor/copy/assignment函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
// POD类型,调用memcpy()
template <class _InputIter, class _ForwardIter>
inline _ForwardIter
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
_ForwardIter __result,
__true_type)
{
return copy(__first, __last, __result);
}

// 非POD类型,逐个调用拷贝构造函数 如果构造过程中出错抛出异常,析构已构造的对象
template <class _InputIter, class _ForwardIter>
_ForwardIter
__uninitialized_copy_aux(_InputIter __first, _InputIter __last,
_ForwardIter __result,
__false_type)
{
_ForwardIter __cur = __result;
__STL_TRY {
for ( ; __first != __last; ++__first, ++__cur)
_Construct(&*__cur, *__first);
return __cur;
}
__STL_UNWIND(_Destroy(__result, __cur));
}


template <class _InputIter, class _ForwardIter, class _Tp>
inline _ForwardIter
__uninitialized_copy(_InputIter __first, _InputIter __last,
_ForwardIter __result, _Tp*)
{
//使用类型萃取,对POD类型使用memcpy(),非OPD类型逐个调用构造函数
typedef typename __type_traits<_Tp>::is_POD_type _Is_POD;
return __uninitialized_copy_aux(__first, __last, __result, _Is_POD());
}

//将[__first, __last)复制一份到[__result, __result+__last-__first)
template <class _InputIter, class _ForwardIter>
inline _ForwardIter
uninitialized_copy(_InputIter __first, _InputIter __last,
_ForwardIter __result)
{
return __uninitialized_copy(__first, __last, __result,
__VALUE_TYPE(__result));
}

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);
}

// uninitialized_copy_n (not part of the C++ standard)

template <class _InputIter, class _Size, class _ForwardIter>
pair<_InputIter, _ForwardIter>
__uninitialized_copy_n(_InputIter __first, _Size __count,
_ForwardIter __result,
input_iterator_tag)
{
_ForwardIter __cur = __result;
__STL_TRY {
for ( ; __count > 0 ; --__count, ++__first, ++__cur)
_Construct(&*__cur, *__first);
return pair<_InputIter, _ForwardIter>(__first, __cur);
}
__STL_UNWIND(_Destroy(__result, __cur));
}

template <class _RandomAccessIter, class _Size, class _ForwardIter>
inline pair<_RandomAccessIter, _ForwardIter>
__uninitialized_copy_n(_RandomAccessIter __first, _Size __count,
_ForwardIter __result,
random_access_iterator_tag) {
_RandomAccessIter __last = __first + __count;
return pair<_RandomAccessIter, _ForwardIter>(
__last,
uninitialized_copy(__first, __last, __result));
}

template <class _InputIter, class _Size, class _ForwardIter>
inline pair<_InputIter, _ForwardIter>
__uninitialized_copy_n(_InputIter __first, _Size __count,
_ForwardIter __result) {
return __uninitialized_copy_n(__first, __count, __result,
__ITERATOR_CATEGORY(__first));
}

template <class _InputIter, class _Size, class _ForwardIter>
inline pair<_InputIter, _ForwardIter>
uninitialized_copy_n(_InputIter __first, _Size __count,
_ForwardIter __result) {
return __uninitialized_copy_n(__first, __count, __result,
__ITERATOR_CATEGORY(__first));
}

// Valid if copy construction is equivalent to assignment, and if the
// destructor is trivial.
//对于POD类型调用memset
template <class _ForwardIter, class _Tp>
inline void
__uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last,
const _Tp& __x, __true_type)
{
fill(__first, __last, __x);
}

//对于非POD类型逐个调用构造函数 如果中途抛出异常,析构已经构造的对象
template <class _ForwardIter, class _Tp>
void
__uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last,
const _Tp& __x, __false_type)
{
_ForwardIter __cur = __first;
__STL_TRY {
for ( ; __cur != __last; ++__cur)
_Construct(&*__cur, __x);
}
__STL_UNWIND(_Destroy(__first, __cur));
}

template <class _ForwardIter, class _Tp, class _Tp1>
inline void __uninitialized_fill(_ForwardIter __first,
_ForwardIter __last, const _Tp& __x, _Tp1*)
{
typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
__uninitialized_fill_aux(__first, __last, __x, _Is_POD());

}

//对[__first, __last)中迭代器所指向的内存,已__x为参数调用_Tp的拷贝构造函数
template <class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first,
_ForwardIter __last,
const _Tp& __x)
{
__uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first));
}

//对于POD类型逐个执行赋值操作
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n,
const _Tp& __x, __true_type)
{
return fill_n(__first, __n, __x);
}

//对于非POD类型逐个调用构造函数 如果中途抛出异常,析构已经构造的对象
template <class _ForwardIter, class _Size, class _Tp>
_ForwardIter
__uninitialized_fill_n_aux(_ForwardIter __first, _Size __n,
const _Tp& __x, __false_type)
{
_ForwardIter __cur = __first;
__STL_TRY {
for ( ; __n > 0; --__n, ++__cur)
_Construct(&*__cur, __x);
return __cur;
}
__STL_UNWIND(_Destroy(__first, __cur));
}

template <class _ForwardIter, class _Size, class _Tp, class _Tp1>
inline _ForwardIter
__uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x, _Tp1*)
{
typedef typename __type_traits<_Tp1>::is_POD_type _Is_POD;
return __uninitialized_fill_n_aux(__first, __n, __x, _Is_POD());
}

//从__first开始构造__n个_Tp对象,已__x为模版
template <class _ForwardIter, class _Size, class _Tp>
inline _ForwardIter
uninitialized_fill_n(_ForwardIter __first, _Size __n, const _Tp& __x)
{
return __uninitialized_fill_n(__first, __n, __x, __VALUE_TYPE(__first));
}

template <class _InputIter1, class _InputIter2, class _ForwardIter>
inline _ForwardIter
__uninitialized_copy_copy(_InputIter1 __first1, _InputIter1 __last1,
_InputIter2 __first2, _InputIter2 __last2,
_ForwardIter __result)
{
_ForwardIter __mid = uninitialized_copy(__first1, __last1, __result);
__STL_TRY {
return uninitialized_copy(__first2, __last2, __mid);
}
__STL_UNWIND(_Destroy(__result, __mid));
}

template <class _ForwardIter, class _Tp, class _InputIter>
inline _ForwardIter
__uninitialized_fill_copy(_ForwardIter __result, _ForwardIter __mid,
const _Tp& __x,
_InputIter __first, _InputIter __last)
{
uninitialized_fill(__result, __mid, __x);
__STL_TRY {
return uninitialized_copy(__first, __last, __mid);
}
__STL_UNWIND(_Destroy(__result, __mid));
}

template <class _InputIter, class _ForwardIter, class _Tp>
inline void
__uninitialized_copy_fill(_InputIter __first1, _InputIter __last1,
_ForwardIter __first2, _ForwardIter __last2,
const _Tp& __x)
{
_ForwardIter __mid2 = uninitialized_copy(__first1, __last1, __first2);
__STL_TRY {
uninitialized_fill(__mid2, __last2, __x);
}
__STL_UNWIND(_Destroy(__first2, __mid2));
}