STL 空间配置器
#STL 2024-11-17

一级空间配置器之__malloc_alloc_template

allocate

1
2
3
4
5
6
static void * allocate(size_t n)
{
    void *result = malloc(n);
    if (0 == result) result = oom_malloc(n);
    return result;
}

allocate 接口 本质就是调用 malloc 函数分配指定大小 n 的内存，如果分配内存失败，进入到 oom_malloc 接口。

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
#if 0
#   include <new>
#   define __THROW_BAD_ALLOC throw bad_alloc
#elif !defined(__THROW_BAD_ALLOC)
#   include <iostream.h>
#   define __THROW_BAD_ALLOC cerr << "out of memory" << endl; exit(1)
#endif

static void (* set_malloc_handler(void (*f)()))()
{
    void (* old)() = __malloc_alloc_oom_handler;
    __malloc_alloc_oom_handler = f;
    return(old);
}

template <int inst>
void * __malloc_alloc_template<inst>::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);
    }
}

oom_malloc 接口 本质就是循环执行两个关键点，空间分配异常的回调函数 和 malloc 函数分配内存。

  • 如果用户通过 set_malloc_handler 设置 __malloc_alloc_oom_handler 回调函数，那么即便分配空间失败（指 allocate 接口）也不会抛出异常，而是选择执行用户的回调函数。如果用户设置的回调函数不选择退出或抛出异常，那么下一步就是 继续尝试分配指定大小 n 内存。如此反复执行，直到 malloc 成功为止。
  • 如果用户没有设置 __malloc_alloc_oom_handler 回调函数，那么就会抛出异常，亦不会尝试分配指定大小 n 内存，提早退出循环。

下图是第一种情况，至于第二种情况是在 执行默认的回调函数之后就退出，也不会到 malloc 阶段。

oom_malloc.png

deallocate

1
2
3
4
static void deallocate(void *p, size_t /* n */)
{
    free(p);
}

reallocate

1
2
3
4
5
6
static void * reallocate(void *p, size_t /* old_sz */, size_t new_sz)
{
    void * result = realloc(p, new_sz);
    if (0 == result) result = oom_realloc(p, new_sz);
    return result;
}

reallocate 接口本质就是调用 realloc 重新分配指定大小空间。如果失败 进入 oom_realloc 接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <int inst>
void * __malloc_alloc_template<inst>::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);
    }
}

二级空间配置器之__default_alloc_template

allocate

说明

联合体（共用体）及其链表的应用

在 C 语言中，联合体（union）是一种数据结构，它允许在同一内存位置存储不同的数据类型。与结构体不同，联合体的所有成员共享同一块内存，因此联合体的大小是其最大成员的大小。

1
2
3
4
5
union union_name {
    数据类型 变量名;
    数据类型 变量名;
    ...
};

特点：

  1. 内存共享：所有成员共享同一内存区域，联合体的大小等于其最大成员的大小。
  2. 只能存储一个值：在任何时刻，联合体只能存储一个成员的值，修改一个成员的值会影响其他成员的值。
  3. 存储的最后一次存放的成员：共用体变量中起作用的成员是最后一次存放的成员，在存入一个新的成员后，原有的成员就失去作用了。

union.png

以上 3 个变量在内存中占的字节数不同，但都从同一地址开始存放，也就是几个变量相互覆盖。这种使几个不同的变量共占同一段内存的结构。

我们来看 STL 中利用 union 定义，你在理解层面想象成链表的节点即可。

1
2
3
4
union obj {
      union obj * free_list_link;
      char client_data[1];    /* The client sees this.        */
};

示意图：

联合体.png

将 bytes 调整为 _ALIGN 的最小整数倍

1
2
3
4
5
enum {__ALIGN = 8};  // 对齐的字节数

static size_t ROUND_UP(size_t bytes) {
        return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1));
  }

向上对齐为 __ALIGN 的倍数，如果你传递的 bytes 为 13，那么会向上取整为 16。

这个函数主要用于内存管理，确保分配的内存块按照特定的字节对齐。

返回 bytes 所在的下标

1
2
3
4
5
enum {__ALIGN = 8};  

static  size_t FREELIST_INDEX(size_t bytes) {
      return (((bytes) + __ALIGN-1)/__ALIGN - 1);
}

根据区块大小，决定使用第 n 号 free-list 。

free_list.png

FREELIST_INDEX 可以根据传入的字节大小，方便找到合适的下标。比方说 传入的 30 字节，那么应该是在 下标 3 处，因为 下标 2 处 一个块的大小为 24，明显不合适。

1
(((bytes) + __ALIGN-1)/__ALIGN - 1) = ((30) + 8 - 1) / 8 - 1 = 37 / 8 - 1 = 4 - 1 = 3

free_list 数组和枚举介绍

1
2
3
4
5
6
7
enum {__ALIGN = 8};
enum {__MAX_BYTES = 128};
enum {__NFREELISTS = __MAX_BYTES/__ALIGN};	

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

__NFREELISTS = __MAX_BYTES/__ALIGN ，即 __NFREELISTS = 128 / 8 = 16。free_list 是一个 索引 0 ~15的数组，里面记录的 obj* 对象。

free_list.png

因此，我们讲 free_list + FREELIST_INDEX(n) 就是定位到合适块的可用的内存的起始地址。

二级空间配置器从零开始推导

第一次申请32字节

申请字节 n > 128 调用一级空间配置器，否则调用二级空间配置器。

sum01.png

为了方便讨论，假定一切都是最初的状态，用户第一次申请的字节大小为 30 字节。通过 FREELIST_INDEX 方法找到合适的块的下标。我们必然只能多给，不能少给，所以选择 下标 3 处，代表每次申请一个块的大小为 24 字节。

sum02.png

当前肯定是没有分配任何空间的，free_list 数组中的对象没有任何一个指向有效的内存区域。因此，会调用 refill 接口。调用该接口的时候，会调用 ROUND_UP 的方法把用户申请的目标字节数向上取整为 8 的倍数，因此传递进去的参数不是 30，而是 32。

sum03.png

还没有往下分析多少，就看到 chunk_alloc 接口，这是实际分配空间的接口，但我们需要重点知道传递给 chunk_alloc 的两个参数。n 是用户申请的字节大小，已被向上取整为 8 的倍数，即32。nobjs（局部变量） 是最初为 20，但不代表永远都是，后续的其他地方可能会被改动，但这是后话。

1
chunk_alloc(n, nobjs);

在确定传递进来的参数情况之后，下面两个变量的含义和值情况就明晰了。total_bytes = 32 * 20 = 640，bytes_left = 0。最初肯定是没有可用空间的，再者我们申请的字节数变为 640 字节了，尽管这依旧不是 STL 最终会申请的大小。

1
2
size_t total_bytes = size * nobjs;	//申请的总字节数
size_t bytes_left = end_free - start_free;	// 可用空间

由于 bytes_left = 0，暗示没有任何可用空间，因此进入到 else 逻辑中，申请真正的堆内存。如下就是 STL 会真正需要去申请的空间大小，即申请 40 个块 + heap_size / 16 之后的空间大小，即 1280 字节。

1
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);

然后就回去申请堆内存，暂时不去考虑申请失败的情况。那么就会更新 heap_size的大小 和 end_free 的指向。然后继续递归调用 chunk_alloc。这时候就会执行到如下逻辑中：

1
2
3
4
5
6
7
8
9
char * result;	// 返回用户可用空间的起始地址
size_t total_bytes = size * nobjs;	// 目标总字节数，640
size_t bytes_left = end_free - start_free;	// 1280

if (bytes_left >= total_bytes) {	// 满足
    result = start_free;
    start_free += total_bytes;
    return (result);
}

当前示意图如下：

第一次申请.png

明明一个块就可以满足用户，但我们足足申请 40 个块。多申请就是为了避免反复申请，因为 malloc 是系统调用嘛。下面我们会看到 第一个块 会返回给用户，另外 19 个块会挂载到 free_list 数组下标 3 处，等到用户需要 32 字节点时候，直接来取。至于剩下的 20 块是为了后续给的时候也不必再去申请做准备了（不属于 free_list 数组下标 3 处，有可能会被挂载到其他下标处去，这个后面会有演示）。至此，我们可以看到 start_free 指向剩余空间的起始位置，end_free 指向剩余空间的末尾位置，end_free - start_free 就代表剩下的可分配空间（因为它现在是自由的，不属于任何一个 free_list 数组）。

这个时候，我们就返回到 refill 中，由于申请的得到的是 20 个块，因此不会直接返回，而是要去构建链表。先把第一个节点存储，这是后面要返回给用户的。剩下的 19 个块 会通过指针连起来，和链表一样。而且最后一个节点指向的空指针，源码可见 current_obj -> free_list_link = 0。

构建.png

对于剩下的 19 个块链接起来之后，会挂载到下标为 3 的 free_list 中，源码可见 *my_free_list = next_obj = (obj *)(chunk + n)。

剩下的19.png

然后就回到 allocate 中，由于已经申请到空间，直接就返回刚刚得到的第一个块，非常顺利。如果下次继续调用 allocate 申请 30 字节空间，它会跳过 refill 代码，因为目前有足够的堆空间，执行的是如下代码：

1
2
3
4
5
6
7
8
9
10
static void * allocate(size_t n)
{
  obj * __VOLATILE * my_free_list;
  obj * __RESTRICT result;

  my_free_list = free_list + FREELIST_INDEX(n);
  result = *my_free_list;
  *my_free_list = result -> free_list_link;
  return (result);
};

这个时候它是如何取处第二个块，并且返回给用户的呢？核心代码就是 result -> free_list_link。你可以理解这行代码就是链表中 node->next 的行为。

示意图如下：

allocate已有空间.png

为了方便后面讨论，我们做出如下规定。

sum06.png

前面演示从没有分配空间到构建出内存池的过程，期间我们忽略很多逻辑，下面我们需要把它补回来，但我们确实是走完 allocate 的流程了，剩下 refill 和 chunk_alloc 的还有些没有走。

下面这个路线，即从用户本欲申请 30 字节，到 STL 实际分配大小的情况：

大小变化流程.png

第二次申请64字节

这次我们申请 64 字节，发现 下标 7 处为空指针，因此调用 refill，然后就是调用 chunk_alloc。

1
2
size_t total_bytes = size * nobjs;	// 64 * 20 = 1280
size_t bytes_left = end_free - start_free; // 640

64 < bytes_left < total_bytes，进入的逻辑是：

1
2
3
4
5
nobjs = bytes_left / size;	// 640 / 64 = 10
total_bytes = size * nobjs;	// 64 * 10 = 640
result = start_free;
start_free += total_bytes;
return (result);

就是把之前多申请的 20 个块，用来弥补这里，示意图如下：

64.png

第三次申请96字节

之前申请的 20 个 32 字节的块都已分配完，start_free = end_free = 0，可用空间为 0 了。

这次计算 bytes_to_get 结果有所不同，因为 heap_size 是全局变量，会不止申请 20 个 96 字节块。计算 bytes_to_get = 2 * 96 * 20 + 80 = 3920。

1
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);

示意图如下：

96.png

最后申请72字节，认为内存池和堆空间都没有连续的72字节

这次我们申请 72 字节，发现 下标 8 处为空指针，因此调用 refill，然后就是调用 chunk_alloc。

1
2
size_t total_bytes = size * nobjs;	// 20 * 72 = 1440
size_t bytes_left = end_free - start_free;	// 不足以 72 字节

由于我们认为内存池和堆空间都没有连续的72字节，目的是为了把另外两份代码展示出来。

bytes_left 小于 72 字节且大于 0 的话，通过下面的方式 让 start_free 空指针，即 free_list[8]。

1
2
3
4
5
6
7
size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);	// 3205
if (bytes_left > 0) { 
    obj * __VOLATILE * my_free_list = free_list + FREELIST_INDEX(bytes_left);	// free_list[8]，空指针

    ((obj * ) start_free) - >free_list_link = *my_free_list; 
    * my_free_list = (obj * ) start_free;
}

如果分配成功，就又回到我们之前的逻辑了。可正是因为我们规定 malloc 分配失败，才得以进入下面的代码中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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) { // i = 72, i <= 128, i += 8
        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);
}

起始字节数是 72，因为这是我们的目标，我们会从下标 8 的 free_list 数组中开始往后寻找，由于小于72字节的空间可能不是连续的，所以需要向后面大于72字节的链表”借”。

如果 free_list 数组的下标处为 NULL，表明不可能有空间给我们。否则，我们认为必然可以满足 72 字节需求。

如果遍历 free_list 的结果是没有任何可用的内存池，那么我们 将 end_free 置为 0，而 start_free 当前已经是 0，最后我们调用一级空间配置器，如果这都失败，就会抛出异常，这个我们在之前已经讨论过了。

如果我们遍历 free_list 有结果，进入下面的逻辑中：

1
2
3
4
* my_free_list = p - >free_list_link;
start_free = (char * ) p;
end_free = start_free + i;
return (chunk_alloc(size, nobjs));

p 是 满足题意的下标的起始地址，也是获取可用空间的一个块，此时 start_free 和 end_free 情况如下：

失败.png

然后递归调用 chunk_alloc。下面是两个变量最新的值情况。

1
2
size_t total_bytes = size * nobjs;	// 20 * 72 = 1440
size_t bytes_left = end_free - start_free;	// 96

由于 bytes_left >= size，进入到下面的逻辑代码中。

1
2
3
4
5
nobjs = bytes_left / size;	// 1
total_bytes = size * nobjs;	// 72
result = start_free;	
start_free += total_bytes;	// 72
return (result);

效果就是把 96字节 切割出 72字节返回，剩下 24 字节。

切割.png

然后让 start_free 和 end_free 记录着剩下的 24 字节，留着后续使用。

终结.png

回到 refill 函数，就会执行如下代码，这个代码此前还没有演示过。

1
if (1 == nobjs) return(chunk);

至此，我们终于把 alloacte 的所有源代码拿下了。

deallocate

1
2
3
4
5
6
7
8
9
10
11
12
13
static void deallocate(void *p, size_t n)
{
  obj *q = (obj *)p;
  obj * __VOLATILE * my_free_list;

  if (n > (size_t) __MAX_BYTES) {
      malloc_alloc::deallocate(p, n);
      return;
  }
  my_free_list = free_list + FREELIST_INDEX(n);	
  q -> free_list_link = *my_free_list;
  *my_free_list = q;
}

如果 释放的字节数 大于 128，调用之前的讲的 deallocate。否则，就把要释放的空间重新归还到合适的 free_list 下标处，通过 free_list + FREELIST_INDEX(n) 计算。

申请空间：

d1.png

归还空间：

d2.png

reallocate

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 (ROUND_UP(old_sz) == 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);
}

如果新分配空间的长度和旧分配空间的长度都 大于 128，调用本小节讲的 realloc 接口。

如果新分配空间的长度和旧分配空间 向上取整为 8 的倍数，比较相等，那么直接返回指针 p 即可。

否则，就调用 allocate 分配 new_sz 长度的空间大小，确定要拷贝的长度 copy_sz ，调用 memcpy 即可。

对于不在使用的空间，记得归还，调用本小节讲的 deallocate 即可。

construct

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

参数 p 是一个 T1 类型的指针，也就是通过 allocate 分配的实际空间的起始地址。参数 value 就是要拷贝到该空间的数据，即作为要构造 T1 对象的初始值。

因此，该函数的功能就是在指定内存地址上构造对象。

destroy

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

就是调用对象的析构函数。

空间配置器的使用

四个重要函数

1
2
3
4
5
6
7
8
9
10
11
用于申请一块未初始化的内存。
T* allocate(std::size_t n)：申请一块大小为 n 个 T 类型的未初始化内存块，返回指向这块内存的指针。

用于释放先前分配的内存块。
void deallocate(T* p, std::size_t n)：释放指向 p 的内存，这块内存大小为 n 个 T 类型。

用于在分配的内存上构造对象。
void construct(pointer p, const_reference val)：在指针 p 所指向的内存位置上构造一个对象，其值为 val。

用于销毁对象。
void destroy(pointer p)：销毁指针 p 所指向的对象，但不释放内存。

容器源码内部在涉及内存和对象相关操作的时候，就是调用此四个接口。

为什么要将空间的申请和对象的构建分开

因为在 STL 中元素的个数往往都批量创建，这个时候如果创建一个对象申请一块空间，那么空间的申请就会非常频繁，效率自然低下。况且你还不能保证一个一个去申请，最后的内存是否连续的情况。

因此，一开始就创建指定大小的空间，再去构建对象能避免多次申请空间出现的内存碎片问题。

内存基本处理工具

uninitialized_fill_n

uninitialized_fill_n –> __uninitialized_fill_n –> __uninitialized_fill_n_aux

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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);
}

template <class ForwardIterator, class Size, class T>
ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
                           const T& x, __false_type) {
  ForwardIterator cur = first;
  __STL_TRY {
    for ( ; n > 0; --n, ++cur)
      construct(&*cur, x);
    return cur;
  }
  __STL_UNWIND(destroy(first, cur));
}

这里面有个参数值得去细究，即__false_type。下面看看它是如何一步一步传递过来的：

1
2
3
4
5
6
7
8
9
10
11
12
13
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_traits<T1>::is_POD_type is_POD;
  return __uninitialized_fill_n_aux(first, n, x, is_POD());
                                    
}

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

追溯：value_type(first)

作用是获取 first 所指向元素的类型。

1
2
template <class T>
inline T* value_type(const T*) { return (T*)(0); }

追溯：is_POD()

用来判断类型 T1 是否是一个 POD 类型。

1
2
3
4
5
6
7
8
__type_traits<T1>::is_POD_type
		↓
__false_type
		↓
struct __true_type {
};
struct __false_type {
};

如果是 POD 类型（如内置类型 int、double 等），则使用下面这个函数完成初始化，而无需调用构造函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
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);
}

template <class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T& value) {
  for ( ; n > 0; --n, ++first)
    *first = value; // 初始化数据
  return first;
}

否则，会通过调用 construct 函数手动构造对象。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class ForwardIterator, class Size, class T>
ForwardIterator
__uninitialized_fill_n_aux(ForwardIterator first, Size n,
                           const T& x, __false_type) {
  ForwardIterator cur = first;
  __STL_TRY {
    for ( ; n > 0; --n, ++cur)
      construct(&*cur, x);
    return cur;
  }
  __STL_UNWIND(destroy(first, cur));
}

template <class T1, class T2>
inline void construct(T1* p, const T2& value) {
  new (p) T1(value);	// 调用构造函数完成初始化
}

uninitialized_copy

uninitialized_copy –> __uninitialized_copy –> __uninitialized_copy_aux

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <class InputIterator, class ForwardIterator>
inline ForwardIterator 
__uninitialized_copy_aux(InputIterator first, InputIterator last,
                         ForwardIterator result,
                         __true_type) {
  return copy(first, last, result);
}

template <class InputIterator, class ForwardIterator>
ForwardIterator 
__uninitialized_copy_aux(InputIterator first, InputIterator last,
                         ForwardIterator result,
                         __false_type) {
  ForwardIterator cur = result;
  __STL_TRY {
    for ( ; first != last; ++first, ++cur)
      construct(&*cur, *first);
    return cur;
  }
  __STL_UNWIND(destroy(result, cur));
}

其余部分代码，已不在话下，重点追溯 copy(first, last, result)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class InputIterator, class OutputIterator>
inline OutputIterator copy(InputIterator first, InputIterator last,
                           OutputIterator result)
{
  return __copy_dispatch<InputIterator,OutputIterator>()(first, last, result);
}

inline char* copy(const char* first, const char* last, char* result) {
  memmove(result, first, last - first);
  return result + (last - first);
}

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

__copy_dispatch –> __copy

1
2
3
4
5
6
7
8
template <class InputIterator, class OutputIterator>
inline OutputIterator __copy(InputIterator first, InputIterator last,
                             OutputIterator result, input_iterator_tag)
{
  for ( ; first != last; ++result, ++first)	// 遍历
    *result = *first;	// 赋值
  return result;
}

还有另一个重载的函数，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class RandomAccessIterator, class OutputIterator>
inline OutputIterator 
__copy(RandomAccessIterator first, RandomAccessIterator last,
       OutputIterator result, random_access_iterator_tag)
{
  return __copy_d(first, last, result, distance_type(first));
}

template <class RandomAccessIterator, class OutputIterator, class Distance>
inline OutputIterator
__copy_d(RandomAccessIterator first, RandomAccessIterator last,
         OutputIterator result, Distance*)
{
  for (Distance n = last - first; n > 0; --n, ++result, ++first) // n 是 遍历的长度，且从 first d
    *result = *first;
  return result;
}

明显看出这个函数实现的功能是复制指定长度的数据，而前一个是拷贝所有的数据。

uninitialized_fill

uninitialized_fill –> __uninitialized_fill –> __uninitialized_fill_aux

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <class ForwardIterator, class T>
inline void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, 
                         const T& x, __true_type)
{
  fill(first, last, x);
}


template <class ForwardIterator, class T>
void
__uninitialized_fill_aux(ForwardIterator first, ForwardIterator last, 
                         const T& x, __false_type)
{
  ForwardIterator cur = first;
  __STL_TRY {
    for ( ; cur != last; ++cur)
      construct(&*cur, x);
  }
  __STL_UNWIND(destroy(first, cur));
}

有之前的基础，这份源码也不再话下，即便是 fill 函数也没什么可讲之处。

1
2
3
4
5
template <class ForwardIterator, class T>
void fill(ForwardIterator first, ForwardIterator last, const T& value) {
  for ( ; first != last; ++first)
    *first = value;
}