空间配置器 (Allocator 的标准接口)
template<class _Tp>
class allocator {
typedef alloc _Alloc; // The underlying allocator.
public:
// type 的设计
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef _Tp *pointer;
typedef const _Tp *const_pointer;
typedef _Tp &reference;
typedef const _Tp &const_reference;
typedef _Tp value_type;
// rebind 可以允许 allocator<T> 转化成另一种类型的对象
// 例如从 allocator<int> 转化到 allocator<double>
template<class _Tp1>
struct rebind {
typedef allocator<_Tp1> other;
};
// 默认构造
allocator() __STL_NOTHROW {}
// 拷贝构造
allocator(const allocator &) __STL_NOTHROW {}
// 泛化拷贝构造
template<class _Tp1>
allocator(const allocator<_Tp1>&) __STL_NOTHROW {}
// 析构
~allocator() __STL_NOTHROW {}
pointer address(reference __x) const { return &__x; }
const_pointer address(const_reference __x) const { return &__x; }
// __n is permitted to be 0. The C++ standard says nothing about what
// the return value is when __n == 0.
_Tp *allocate(size_type __n, const void* = 0) {
return __n != 0 ? static_cast<_Tp *>(_Alloc::allocate(__n * sizeof(_Tp))) : 0;
}
// __p is not permitted to be a null pointer.
void deallocate(pointer __p, size_type __n) {
_Alloc::deallocate(__p, __n * sizeof(_Tp));
}
size_type max_size() const __STL_NOTHROW {
return size_t(-1) / sizeof(_Tp);
}
// 这里比较耐人寻味，此处的 new 是 placement new，与我们常规使用的 new 不同的是
// 常规 new 的时候会执行两步操作：
// 1: 调用 ::operator new 申请一块原始内存
// 2: 执行对象的构造函数 -> new(T::T())
// 这里的第一个参数是一个指向开辟好原始内存空间的指针，第二个参数才是对象要构造的值
void construct(pointer __p, const _Tp &__val) {
// 这行代码并不会再开辟新的内存空间，而是将通过_Tp() 构造的对象放入__p 所指向的空间
new(__p) _Tp(__val);
}
// 这里析构对象也是同理，我们常用的 delete 实际上也是两步操作
// 1: 执行~T() 对象的析构函数
// 2: 调用 ::operator delete 释放空间
void destroy(pointer __p) {
__p->~_Tp();
}
};
上述是 C++ 标准设计的 Allocator 源代码，通过阅读我们获得一些启发：空间配置器不是单纯的使用 new 和 delete 来分配空间。
空间的分配分为两步：
- 先通过
::operator new来申请原始内存空间，在这一步的时候就类似于 malloc 并不会构造对象。 - 再通过
placement new->new(__p) T(value)来构造对象并将对象放入__p指向的空间中。
空间的回收在注释中有写则不再重复。如此做的好处是，方便控制 STL 构造和析构对象的时机。
但是，SGI STL 并没有采用这种空间配置的方式，主要原因是在频繁分配小对象的时候效率不佳，且整个类只是对 ::operator new 和 ::operator delete 做了简单的封装。
SGI STL 则使用了一种与众不同的配置器 (alloc)，它具有次配置力 (sub-allocation)，且它不接受任何参数，它对配置器做了分级结构，分为一级配置器和二级配置器，尤其在分配小空间的时候效率极佳。
SGI 的特殊空间配置器 std::alloc
为了精密分工，在上面提到了，STL allocator 将 内存空间的配置/释放 和 对象内容的构造/析构 拆解开来，空间配置器写在 <memory> 中。
SGI 的 <memory> 则包含了这三个文件 (节选了与空间配置器有关的)：
// #include <stl_algobase.h>
#include <stl_alloc.h> // 负责空间配置和释放
#include <stl_construct.h> // 负责对象构造和析构
// #include <stl_tempbuf.h>
#include <stl_uninitialized.h> // 用来填充或复制大块内存数据，与对象的初值设置有关
// #include <stl_raw_storage_iter.h>
构造和析构的基本工具 construct() 和 destroy()
为了更好的理解构造和析构过程，节选一段 stl_construct.h 的源代码，观察对象构造和析构的过程。
#include <new.h>
// 想使用 ::operator new 必须要包含这个头文件
// 这个构造为带参构造 (拷贝构造)
// 本质就是在已有的空间上构造对象
template<class _T1, class _T2>
inline void _Construct(_T1 *__p, const _T2 &__value) {
new ((void*)__p) _T1(__value);
}
// 默认构造 - 常使用在构建多个容器对象
// vector<int> (10);
// 内部就会循环调用
// _Construct(p);
// _Construct(p + 1);
// ...
template<class _T1>
inline void _Construct(_T1 *__p) {
new ((void*)__p) _T1();
}
// 这个是 destroy 的第一个版本，接收一个指针，析构一个对象
template<class _Tp>
inline void _Destroy(_Tp *__pointer) {
__pointer->~_Tp();
}
// 这是 destroy 的第二个版本，接收两个迭代器，此函数会先找出元素的数值型别
// 进而利用 __type_traits<> 求取最合适的措施
template<class _ForwardIterator>
inline void _Destroy(_ForwardIterator __first, _ForwardIterator __last) {
__destroy(__first, __last, __VALUE_TYPE(__first));
}
// 判断这个元素数值类别有没有 (trivial destructor) 即编译器默认生成的析构函数
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());
}
// 元素有 trivial destructor
template<class _ForwardIterator>
inline void __destroy_aux(_ForwardIterator, _ForwardIterator, __true_type) {}
// 元素有 non-trivial destructor(即程序员手写的析构函数)
template<class _ForwardIterator>
void __destroy_aux(_ForwardIterator __first, _ForwardIterator __last, __false_type) {
for (; __first != __last; ++__first) destroy(&*__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*) {}
从上述源码中可以观察到，stl 提供了一种通过迭代器大范围销毁对象的方式，但是我们也不知道这个范围有多大。如果这个范围很大 (上百万个对象)，如果不分青红皂白一律调用 ~T() 就会大大损失性能，所以这里根据元素类型做了一些判断。
当使用传入两个迭代器析构对象时，函数会先判断元素数值类型，紧接着再去观察这种类型有没有 trivial destructor (编译器生成的析构)。如果有则不执行任何操作，如果是 non-trivial destructor 则按顺序依次执行析构函数。
下面举个例子来观察优化前后的区别：
vector<int> v(1000000);
当上面这个 vector 销毁时，如果不进行类型判断，就会默认调用 100 万次析构 (然而这个析构并无任何作用)。但是当进行优化后，整个过程不需要调用一次析构。
空间的配置和释放 std::alloc
C++ 内存的基本配置操作为 ::operator new，内存释放的基本操作为 ::operator delete 这俩全局函数，就相当于 C 的 malloc() 和 free()，而 SGI 正是通过 malloc() 和 free() 完成的内存配置和释放。
考虑到标准 allocator 无法解决小型区块导致内存破碎的问题，所以 SGI 配置了双层级配置器。一级配置器直接使用 malloc(), free()，而第二级配置器则根据不同情况来选择不同策略。
- 当配置区块大于 128byte 的时候，会被视为'足够大'，会调用第一级配置器。
- 当配置区块小于 128byte 的时候，被视为'过小'，则会使用复杂的 memory pool 方式来管理内存。
而是只使用第一级配置器还是同时开放第二级配置器则通过是否 define __USE_MALLOC 来决定 (但是不管无论如何，都要使用 malloc)。
#ifdef __USE_MALLOC
typedef __malloc_alloc_template<0> malloc_alloc; // 令 alloc 为第一级配置器
typedef malloc_alloc alloc;
#else
// ...
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc; // 令 alloc 为第二级配置器
typedef __default_alloc_template<false, 0> single_client_alloc;
#endif
其中 __malloc_alloc_template 就是第一级配置器，__default_alloc_template 为第二级配置器。但是不管 alloc 被定义为第一或者第二级配置器，SGI 都会给它再包一层接口，使整个配置器能够符合 STL 的规格。
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));
}
};
上述四个内部成员都是简单的转调用，调用传递给配置器 (可以是第一级也可以是第二级)，配置单位则从 byte 转化到一个元素的大小。SGI 的所有 STL 容器都使用这个 simple_alloc 接口。
第一级配置器 __malloc_alloc_template 剖析
这里贴出第一级配置器源码，剖析则放在注释中。
template<int __inst>
class __malloc_alloc_template {
private:
// 处理 oom(out of memory) 内存不足的情况
static void *_S_oom_malloc(size_t);
static void *_S_oom_realloc(void*, size_t);
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
static void (*__malloc_alloc_oom_handler)();
#endif
public:
static void *allocate(size_t __n) {
// 第一级配置器，直接使用 malloc
void *__result = malloc(__n);
if (0 == __result) // 内存不足调用 oom 函数，这里在下文会细说
__result = _S_oom_malloc(__n);
return __result;
}
static void deallocate(void *__p, size_t /* __n */) {
// 直接调用 free
free(__p);
}
static void *reallocate(void *__p, size_t /* old_sz */, size_t __new_sz) {
// 直接调用 realloc
void *__result = realloc(__p, __new_sz);
if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
return __result;
}
// __set_malloc_handler 相当于仿真 C++ 中的 set_new_handler，换句话说，你可以通过它来指定自己的 oom 后的处理策略
static void (*__set_malloc_handler(void(*__f)()))() {
void (*__old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = __f;
return (__old);
}
};
// malloc_alloc out-of-memory handling
// 处理内存不足，无法配置的情况，需要等待用户自己设置，否则默认为 0
#ifndef __STL_STATIC_TEMPLATE_MEMBER_BUG
template<int __inst>
void (*__malloc_alloc_template<__inst>::__malloc_alloc_oom_handler)() = 0;
#endif
// 处理 oom 函数
template<int __inst>
void *__malloc_alloc_template<__inst>::_S_oom_malloc(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 = 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;
for (;;) {
__my_malloc_handler = __malloc_alloc_oom_handler;
if (0 == __my_malloc_handler) {
__THROW_BAD_ALLOC;
}
(*__my_malloc_handler)(); // 与 oom_malloc 的处理方式相同
__result = realloc(__p, __n);
if (__result) return (__result);
}
}
第一级配置器使用 malloc, realloc, free 等 C 语言函数来配置空间，同时还实现了类似 C++ new-handle 的机制。它无法直接使用 new-handle 机制，因为它没有使用 ::operator new，而是使用了 malloc。
new-handle 机制：当系统无法满足用户的内存配置要求时，调用一个用户所指定的函数，即在调用 ::operator new 时内存空间不足，在抛出 bad_alloc() 之前，会先调用用户传入的处理例程。
第一级配置器在调用 allocate 和 reallocate 失败后就会执行 _S_oom_malloc 和 _S_oom_realloc，希望可以通过用户传入的方法来找到一些空内存，但是当用户没有传入方法的时候，则会直接抛出 bad_alloc 异常。
第二级配置器 __default_alloc_template
第二级配置器多了一些机制，避免太多小额区块造成的内存的碎片 (主要解决的是内碎片问题)。第二层配置器会将大于 128byte 的内存配置交给第一层配置器，而小于 128byte 的则使用 memory pool 来管理。
- 每次将会配置一大块内存，并维护 free-list。
- 如果下次有相同的内存配置请求则直接去查找对应的 free-list，从 free-list 中取出一个空间的内存块。
- 当内存被归还时，也会查找对应大小的 free-list 并挂到上面。
- 为了方便管理，会将内存申请自动对齐 (RoundUp) 到 8 的倍数，free-list 的个数 = 128 / 8 = 16 个。
下面是第二级内存配置器实现部分源码。
// Important implementation properties:
// 1. If the client request an object of size > _MAX_BYTES, the resulting
// object will be obtained directly from malloc.
// 2. In all other cases, we allocate an object of size exactly
// _S_round_up(requested_size). Thus the client has enough size
// information that we can return the object to the proper free list
// without permanently losing part of the object.
enum { _ALIGN = 8 }; // 对齐方式
enum { _MAX_BYTES = 128 }; // 向第二级配置器申请的最大内存
enum { _NFREELISTS = 16 }; // _MAX_BYTES/_ALIGN
template<bool threads, int inst>
class __default_alloc_template {
private:
// 将内存对齐到 8 的倍数
static size_t _S_round_up(size_t __bytes) {
return (((__bytes) + (size_t)_ALIGN - 1) & ~((size_t)_ALIGN - 1));
}
// 定义自由链表的节点
// 这里使用 Union(共用体) 是为了一物两用:
// 1. 可以被视为一个指针，指向下一个 obj 对象
// 2. 视为一个指针，指向实际区块
// 不会因为为了维护链表采用指针而造成的内存浪费
// 这里说一下我的理解:
// union 计算大小的时候是按照占空间最大的成员来计算的，当多个成员使用 union 的时候
// 只有一个成员会生效
// 例如 union A 中有两个成员，这个 union 既可以当 int 用也可以当 char[4] 用
// union A {
// int a;
// char b[4];
// };
// 如果用 struct 存 obj 节点的话，所消耗的内存就是 8b(指针) + 16b(用户数据) /* struct node{ node* next; // 假设 8byte(64 位) char data[16]; } */
// 但是如果用 union 存就是 16b(最大成员大小)，节省了指针消耗的内存
// 即用户内存 = 链表节点
/* 内存被当作指针时 block1 +---------+ | next | -----> block2 +---------+ 此时 _Obj->_M_free_list_link */
/* 内存被当作用户空间 block1 +----------------+ | user data | +----------------+ 此时 _Obj->_M_client_data */
// char _M_client_data[1]; 也不是只给一个字节的大小存数据
// 而是一种占位方式，标记用户数据从 _M_client_data[1] 开始
// &obj->_M_client_data[0]
/* 实际内存空间 +----------------+ | union Obj | | client data | <-指向用户数据的起始位置 | ........... | +----------------+ */
// 至于为什么不从 0 开始而是 1，主要是因为老版本 C++ 不支持 [] 也不允许 [0]
// 申请一个 16B 的空间情况如图
/* +--------------------------+
// | union Obj |
// | data[0] |
// | data[1] |
// | data[2] |
// | data[3] |
// | data[4] |
// | data[5] |
// | data[6] |
// | data[7] |
// | data[8] |
// | data[9] |
// | data[10] |
// | data[11] |
// | data[12] |
// | data[13] |
// | data[14] |
// | data[15] |
// +--------------------------+ */
__PRIVATE:
union _Obj {
union _Obj *_M_free_list_link; // 指向下一个内存块
char _M_client_data[1]; /* The client sees this. */
};
private:
// 自由链表本体
static _Obj *__STL_VOLATILE _S_free_list[];
// 类外定义，提到这里方便观察
/* __default_alloc_template<__threads, __inst> ::_S_free_list[_NFREELISTS] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }; */
// 计算该区块应在哪个 free-list 中拿/还
static size_t _S_freelist_index(size_t __bytes) {
return (((__bytes) + (size_t)_ALIGN - 1) / (size_t)_ALIGN - 1);
}
// Returns an object of size __n, and optionally adds to size __n free list.
// 返回一个大小为 n 的对象，并且可能加入大小为 n 的其他区块到 free-list 中
// (说人话就是一次性可能多申请一些内存块，避免多次申请，如果内存池大小不够就最少先返回一个)
static void *_S_refill(size_t __n);
// Allocates a chunk for nobjs of size size. nobjs may be reduced
// if it is inconvenient to allocate the requested number.
// 向堆申请 njobs 个 size 大小的内存块，njobs 在内存不足的情况下可能会降低
static char *_S_chunk_alloc(size_t __size, int &__nobjs);
// Chunk allocation state.
// 标定内存池的起始位置，只会在_S_chunk_alloc 中改变
static char *_S_start_free;
static char *_S_end_free;
static size_t _S_heap_size;
// 初值设定 本来设定在类外，这里提上来方便观察
/* 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; */
public:
/* __n must be > 0 */
// 内存申请
static void *allocate(size_t __n) {
void *__ret = 0;
// 大于 128byte 直接去调用第一级配置器
if (__n > (size_t)_MAX_BYTES) {
__ret = malloc_alloc::allocate(__n);
} else {
// 计算 free-list 对应内存块的起始地址
_Obj *__STL_VOLATILE *__my_free_list = _S_free_list + _S_freelist_index(__n);
// 取出第一个内存块
_Obj *__RESTRICT __result = *__my_free_list;
if (__result == 0) // 如果一个内存块都没有，则直接去内存池中申请
__ret = _S_refill(_S_round_up(__n));
else {
// 将剩下的内存块连起来返回结果
*__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 {
// 查找 index
_Obj *__STL_VOLATILE *__my_free_list = _S_free_list + _S_freelist_index(__n);
_Obj *__q = (_Obj *)__p;
// 头插到自由链表
__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);
};
// ========================== 类外定义的函数 ==========================
/* Returns an object of size __n, and optionally adds to size __n free list.
/* We assume that __n is properly aligned.
/* We hold the allocation lock.
*/
// 在 free-list 上没有空余的小块内存时调用，调用后至少可以给 1 个内存对象 -> 与内存池打交道
template<bool __threads, int __inst>
void *__default_alloc_template<__threads, __inst>::_S_refill(size_t __n) {
// 默认一次取 20 个，但是如果内存空间不够的话可能会减少
int __nobjs = 20;
// 获取 njobs 个大小为 n 的对象
char *__chunk = _S_chunk_alloc(__n, __nobjs);
_Obj *__STL_VOLATILE *__my_free_list;
_Obj *__result;
_Obj *__current_obj;
_Obj *__next_obj;
int __i;
// 如果只申请到一个就直接返回
if (1 == __nobjs) return (__chunk);
// 申请到不止一个，则将第一个返回，其余的挂到对应位置的自由链表上
__my_free_list = _S_free_list + _S_freelist_index(__n);
/* Build free list in chunk */
__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>
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) {
_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;
}
// 从堆上申请空间
_S_start_free = (char*)malloc(__bytes_to_get);
// 堆空间不足，malloc 失败
if (0 == _S_start_free) {
size_t __i;
_Obj *__STL_VOLATILE *__my_free_list;
_Obj *__p;
// Try to make do with what we have. That can't
// hurt. We do not try smaller requests, since that tends
// to result in disaster on multi-process machines.
// 从一个对象大小开始遍历每个自由链表的槽位，看看有没有空闲的内存块能用得上
for (__i = __size; __i <= (size_t)_MAX_BYTES; __i += (size_t)_ALIGN) {
__my_free_list = _S_free_list + _S_freelist_index(__i);
__p = *__my_free_list;
if (0 != __p) {
// 如果找到空闲的内存块则更新
*__my_free_list = __p->_M_free_list_link;
_S_start_free = (char*)__p;
_S_end_free = _S_start_free + __i;
// 递归调用自己，修正 njobs
return (_S_chunk_alloc(__size, __nobjs));
// Any leftover piece will eventually make it to the
// right free list.
}
}
// 实在是啥都没有了，再尝试调用第一级配置器，如果用户配置了 oom-handle，看看能不能发力
// 否则直接抛出 bad_alloc 了
_S_end_free = 0; // In case of exception.
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
// This should either throw an
// exception or remedy the situation. Thus we assume it
// succeeded.
}
// 申请到内存->更新内存池的大小
_S_heap_size += __bytes_to_get;
_S_end_free = _S_start_free + __bytes_to_get;
// 递归调用自己
return (_S_chunk_alloc(__size, __nobjs));
}
}
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);
}
以上便是第二级配置器的完整实现。
uninitialized_xx
STL 定义五个全局函数，作用于未初始化的空间上，前两个函数是 construct() 和 destroy()，剩下的三个就是 uninitialized_xx 类型函数，具体分为：uninitialized_copy(), uninitialized_fill(), uninitialized_fill_n()。
uninitialized_copy()
该函数接收三个参数，迭代器 first, last, result。first 和 last 指向输出的起始和结尾，result 指向输出端。
// 属于 POD 类型
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 *) {
// 在<type_traits>中有实现，与 iterator_traits<T, Alloc> 类似
typedef typename __type_traits<_Tp>::is_POD_type _Is_POD;
return __uninitialized_copy_aux(__first, __last, __result, _Is_POD());
}
template<class _InputIter, class _ForwardIter>
inline _ForwardIter uninitialized_copy(_InputIter __first, _InputIter __last, _ForwardIter __result) {
// 使用 traits 来获取迭代器类型，如果是 POD(Plain Old Data)，即原生类型就直接调用高阶函数批量处理
// 否则只能使用循环 + constructr() 的方式循环构造
return __uninitialized_copy(__first, __last, __result, __VALUE_TYPE(__result));
}
// 对 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);
}
uninitialized_fill()
template<class _ForwardIter, class _Tp>
inline void __uninitialized_fill_aux(_ForwardIter __first, _ForwardIter __last, const _Tp &__x, __true_type) {
fill(__first, __last, __x);
}
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());
}
template<class _ForwardIter, class _Tp>
inline void uninitialized_fill(_ForwardIter __first, _ForwardIter __last, const _Tp &__x) {
__uninitialized_fill(__first, __last, __x, __VALUE_TYPE(__first));
}
uninitialized_fill_n()
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);
}
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());
}
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));
}
综上所述，uninitialized_*() 类别的函数执行流程如下：
- 在
uninitialized_*()中执行__uninitialized_*()。 - 在
__uninitialized_*()中判断传入迭代器类型进行判断。 - 如果是 POD 则使用高阶函数 (特化
char*,wchar*，使用memmove()直接进行内存移动)。 - 如果非 POD 则使用循环 + constructor() 构造对象。
