SGI STL 源码阅读：空间配置器与对象生命周期
从 allocator 标准接口、construct/destroy 到 SGI 二级配置器，理解 STL 如何分离内存分配与对象构造。
阅读地图：先抓住这篇源码的主线
flowchart LR
A[容器需要空间] --> B{区块大小}
B -->|大于 128 bytes| C[一级配置器 malloc/free]
B -->|小于等于 128 bytes| D[二级配置器 free list]
D --> E[从内存池切分小块]
C --> F[返回原始内存]
E --> F
F --> G[construct: placement new 构造对象]
G --> H[destroy: 按 type_traits 判断是否析构]内存层allocate/deallocate 只处理原始空间，不负责对象语义。
对象层construct/destroy 负责构造和析构，时机由容器控制。
性能层二级配置器通过 free list 缓解小对象频繁分配。
空间配置器(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(1,000,000);
当上面这个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;
其中__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机制: 当系统无法满足用户的内存配置要求时，调用一个用户所指定的函数，即在调用::operatror new 时内存空间不足，在抛出bad_alloc()之前，会先调用用户传入的处理例程。
第一级配置器在调用allocate和reallocate失败后就会执行_S_oom_malloc和_S_oom_reallo，希望可以通过用户传入 的方法来找到一些空内存，但是当用户没有传入方法的时候，则会直接抛出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的时候
// 只有一个成员会生效
// 例如 unionA中有两个成员，这个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()构造对象