[C++知识库]STL源码剖析 随心笔记01

参考资料：

• 《STL源码剖析》
• herongwei——图解源码

STL六大组件

• 设计配置器（包括内存池，构造 析构函数等）

  包括 allocator 和 constructor，分别定义在 allocator.h 和 construct.h 中。

  allocator 负责空间的配置与回收，定义了一个类mystl::alloc 用于管理内存，定义在 alloc.h 。

  constructor 负责对象的构造与析构，对应两个全局函数： construct 和destroy。

• 设计迭代器的五种类型

  iterator，连接着容器与算法，是一种泛型指针，定义在 iterator.h 中。每个容器都附带专属的迭代器，是一种重载了 operator*，operator->，operator++，operator-- 等操作的模板类。

• 设计容器

  如 vector，list，map

• 设计常用算法

  包括 基本算法，数值算法，set算法，heap算法，其他算法

• 设计仿函数

  即函数对象 ，定义在functional.h中。

  另外还有hash_functional ， mystl::hash 函数对象用于计算元素的哈希值(在哈希表中的位置)，对一些内置型别和容器做了特化处理。

• 设计配接器（适配器）

  container adapters ：如stack, queue, priority_queue

  iterator adapters：如reverse_iterator，是一种反向迭代器，重载了operator*，operator->，operator++，operator--，operator+，operator-，operator+=，operatpr-=，operator[] 等操作，变前进为后退，后退为前进。

六大组件介绍：https://blog.csdn.net/qq_45893475/article/details/120749735

上面图片地址：https://github.com/Alinshans/MyTinySTL/wiki

一、空间配置器

功能分析：C/C++需要手动的管理内存，而STL首先需要实现一个能自己申请空间并且释放空间不再需要我们管理的功能，即 空间配置器

解释：空间配置器一般隐藏在各个板块的组件中，实际操作中我们根本注意不到他的存在，但它又是实现STL非常重要的一部分。就像在 类 中我们实现的构造、析构函数，定义对象的时候会自动调用。

1、SGI STL

SGI的空间配置器与众不同，且与STL标准规范不同。名为alloc，而非allocator

虽然SGI也配置了allocator，但是不建议使用（效率~只在基层进行配置/释放空间，且不接受任何参数）

1.1 new 和 delete

在调用new 和 delete 进行对象的创建和销毁的同时，也会有内存配置操作和释放操作：

• new：编译器先调用::operator new 分配内存，然后调用 Obj::Obj() 构造对象内容
• delete：编译器先调用Obj::obj() 析构对象，然后调用::operator delete 释放内存

为了精密分工，STL allocator将这两个阶段操作区分开来：

• 对象构造由::construct()负责，对象释放由::destroy()负责
• 内存配置由alloc::allocate()负责，内存释放由alloc::deallocate() 负责

看一幅图：

下面分别来看：

1.2 构造 和 析构

在<stl_construct.h>中

construct()函数：

• 接受一个指针P 和一个初始值 value，该函数的用途就是将初值设定到指针所指的空间。

destroy()函数有两个版本：

• 第一个版本接受一个指针，准备将该指针所指之物 析构掉。
• 第二个版本接受 first 和 last 两个迭代器，将 [first, last) 范围内的所有对象 析构掉。

#include <new.h>    // 欲使用placement new

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

// destroy() 第一版本
template <class T>
inline void destroy(T* pointer) {
    pointer->~T();
}

// destroy() 第二版本，接受两个迭代器。此函数设法找出元素的数值类型
template <class ForwardIterator>
inline void destroy(ForwardIterator first, ForwardIterator last) {
    __destroy(first, last, value_type(first));
}

后面还有 判断元素的数值类型（value type）是否有 trivial destructor等…见P51

1.3 内存的配置与释放

在<stl_alloc.h>中，SGI对此设计原理：

• 向 system heap要求空间
• 考虑多线程(multi-threads)状态
• 考虑内存不足时的应变措施
• 考虑过多“小型区块” 可能造成的内存碎片(fragment) 问题

考虑到 “小型区块” 可能造成的内存碎片问题，SGI设计了双层级配置器：

• 当配置区块超过 128字节 时，视为足够大，使用第一级配置器——直接使用 malloc() 和 free()
• 当配置区块小于 128bytes 时，为了降低额外负担，直接使用第二级配置器——采用复杂的 memory pool 处理方式

无论第一级还是第二级配置器， alloc 都为其包装了接口，使其能够符合 STL标准。

#ifdef _USE_MALLOC
...
typedef __malloc_alloc_template<0> malloc_alloc;
typedef malloc_alloc alloc;     // 令 alloc 为第一级配置器
#else
...
typedef __default_alloc_template<__NODE_ALLOCATOR_THREADS, 0> alloc; // 令 alloc 为第二级配置器
#endif /* !__USE_MALLOC */

template <class T, class Alloc>
class simple_alloc {
public: 
    static T* allocate(size_t n) {
        return 0 == n ? 0 : (T*)Alloc::allocate(n * sizeof(T));
    }
    static T* allocate(void) {
        return (T*)Alloc::allocate(sizeof(T));
    }
    static void deallocate(T* p, size_t n) {
        if (0 != n) Alloc::deallocate(p, n * sizeof(T));
    }
    static void deallocate(T* p) {
        Alloc::deallocate(p, sizeof(T));
    }
};

一、二级配置器的关系：

一、二级配置器的包装接口和运用方式（SGI STL讲配置器多了一层包装使得Alloc具备标准接口）：

1.4 alloc 一级配置器源码阅读

注意：

1. 第一级配置器以 malloc(), free(), realloc() 等C函数执行实际的内存配置、释放和重配置操作，并实现类似的 C++ new-handler 的机制
2. SGI 第一级配置器的 allocate() 和 reallocate() 都是在调用 malloc() 和 realloc() 不成功后，该调用 oom_malloc() 和 oom_realloc()
3. oom_malloc() 和 oom_realloc() 都有内循环，不断调用 “内存不足处理例程”，期望某次调用后，获得足够的内存而圆满完成，哪怕有一丝希望也要全力以赴
   如果用户没有指定 “内存不足处理例程”，这时便无力回天，STL会抛出异常，或调用exit(1) 终止程序

template <int inst>
class __malloc_alloc_template {
private:
    // 以下函数用来处理内存不足
    // oom::out of memory
    static void* oom_malloc(size_t);
    static void* oom_realloc(void*, size_t);
    static void (*__malloc_alloc_oom_handler)();

public:
    static void* allocate(size_t n) {
        void* result = malloc(n);   // 第一级配置器直接使用malloc()
        // 以下无法满足需求时，改用oom_malloc
        if (0 == result) {
            result = oom_malloc(n);
        }
        return result;
    }

    static void* reallocate(void* p, size_t /*old_sz*/, size_t new_sz) {
        void* result = realloc(p, new_sz);  // 第一级配置器直接使用realloc()
        // 以下无法满足需求时，改用oom_realloc()
        if (0 == result) {
            result = oom_realloc(p, new_sz);
        }
        return result;
    }

    // 以下仿真C++的set_new_handler(),换句话说，你可以通过它指定你自己的out-of-memory handler
    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，有待客端设定
template <int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = 0;

template <int inst>
void* __malloc_alloc_template<inst>::oom_malloc(size_t n) {
    void (*my_malloc_handler)();
    void* result;

    for (;;) { // 不断尝试释放、配置、再释放、再配置
        my_alloc_handler = __malloc_alloc_oom_handler;
        if (0 == my_alloc_handler) {
            __THROW_BAD_ALLOC;
        }
        (*my_alloc_handler)();  // 调用处理例程，企图释放内存
        result = malloc(n);     // 再次尝试配置内存
        if (result) {
            return (result);
        }
    }
}

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_hanler)();     // 调用处理例程，企图释放内存
        result = realloc(p, n);     // 再次尝试配置内存
        if (result) {
            return (result);
        }
    }
}

// 注意，以下直接将参数inst指定为0
type __malloc_alloc_template<0> malloc_alloc;

1.5 alloc二级配置器源码阅读

第二级配置器多了一些机制，专门针对内存碎片。内存碎片化带来的不仅仅时回收时的困难，配置也是一个负担。

毕竟系统要划出这么多资源来管理另外的资源，额外负担永远都是无法避免的，但是区块越小，额外负担率就越高。

前面也说了，当区块大小小于 128bytes 时采用 内存池memory pool的策略：

上面提到了 自由链表，自由链表自由在哪？又如何维护？

一方面，自由链表中有些区块已经分配给了客端使用，所以 free-list 不需要再指向它们；另一方面，为了维护free-list，每个结点还需要额外的指针指向下一个结点。

现在考虑一下，如果每个结点都有两个指针，这样不就造成了额外负担吗？

解决办法，使用 union（联合体/共同体），几个变量共用一个内存位置，在不同的时间保存不同的数据类型和不同长度的变量。（一个union 只配置一个足够大的空间以容纳最大长度的数据成员）

因此，借助 union 的帮助，实现 free-list 节点的结构

union obj {
    union obj* free_list_link;
    char client_data[1];	// the client sees this
};

在 union obj 中，定义了两个字段：

• 第一个字段，obj可以看做一个指针，指向链表中的下一个节点
• 第二个字段，obj也可以看做一个指针，不过此时指向实际的内存区

一物二用的好处就是不会为了维护链表所必须的指针而造成内存的另一种浪费。

第二级配置器部分实现

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

// 以下是第二级配置器
// 注意，无 "template类型参数"，且第二参数完全没排上用场
// 第一参数用于多线程环境下。这里不讨论多线程环境
template <bool threads, int inst>
class __default_alloc_template {

private:
    // ROUND_UP()将bytes上调至8的倍数
    static size_t ROUND_UP(size_t bytes) {
        return (((bytes) + __ALIGN - 1) & ~(__ALIGN - 1));
    }
private:
    union obj {
        union obj* free_list_link;
        char client_data[1];
    };
private:
    // 16个 free-lists
    static obj* volatile free_list[__NFREELISTS];
    // 以下函数根据区块大小，决定使用第n号 free-list，n从0起算
    static size_t FREELIST_INDEX(size_t bytes) {
        return (((bytes) + __ALIGN - 1)/__ALIGN - 1);
    }

    // 返回一个大小为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);
};

// 以下是static data member的定义与初始值设定
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;

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, }

1.6 空间配置器函数 allocate源码阅读

第二级配置器拥有配置器的标准接口函数 allocate()。此函数首先判断区块的大小，如果大于128bytes ——>调用第一级配置器；小于128bytes——>检查对应的 free-list(如果没有可用区块，就将区块上调至8倍数的边界，然后调用refill()，为free-list重新填充空间)。

空间申请

调用标准接口函数 allocate()：

// n must be > 0
static void* allocate(size_t n) {
    obj* volatile* my_free_list;
    obj* result;
    // 大于128就嗲用第一级配置器
    if (n > (size_t)__MAX_BYTES) {
        return (malloc_alloc::allocate(n));
    }
    // 寻找16个free-lists 中适当的一个
    my_free_list = free_list + FREELIST_INDEX(n);
    result = *my_free_list;
    if (result == 0 ) {
        // 没有找到可用的free list，准备重新填充free list
        void* r = refill(ROUND_UP(n));  // 下节详述
        return r;
    }
    // 调整free list
    *my_free_list = result->free_list_link;
    return (result);
};

NOTE：每次都是从对应的 free-list 的头部取出可用的内存块。然后对 free_list 进行调整，使上一步调出的内存的下一节点变成头结点。

空间释放

NOTE：通过调整 free-list 链表将区块放入free_list 的头部

重新填充 free_lists

1. 当发现 free_list 中没有可用区块时，就会调用 refill() 为 free_list 重新填充空间
2. 新的空间将取自内存池（经由 chunk_alloc()完成）
3. 缺省取得20个新节点（区块），但万一内存池空间不足，获得的节点数可能小于20

// 返回一个大小为n的对象，并且有时候会为适当的free list增加节点
// 假设n已经适当上调至8的倍数
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n) {
    int nobjs = 20;
    // 调用 chunk_alloc()，尝试取得nobjs个区块作为free list的新节点
    // 注意参数nobjs是pass by reference
    char* chunk = chunk_alloc(n, nobjs);    // 稍后详述
    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的各节点串接起来
    for (i = 1; ; i++) {    // 从1开始，因为第0个将返回给客端
        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

我们知道从内存池中取空间给 free-list使用 是 chunk_alloc() 在工作，如何工作？

chunk_alloc() 函数以 end_free-start_free 来判断内存池的 “水量”。

如果第一级配置器的 malloc() 也失败了，就发出 bad_alloc 异常。

来看源码：

// 假设size已经适当上调至8的倍数
// 注意参数nobjs是 pass by reference
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;
        total_bytes = size * nobjs;
        result = start_free;
        start_free += total_bytes;
        return (result);
    }
    else {
        // 内存池剩余空间连一个区块大小都无法提供
        size_t bytes_to_get = 2 * total_bytes + ROUND_UP(heap_size >> 4);
        // 以下试着让内存池中的残余零头还有利用价值
        if (bytes_left > 0) {
            // 内存池还有一些零头，先配给适当的free list
            // 首先寻找适当的free list
            obj* volatile *my_free_list = free_list + FREELIST_INDEX(bytes_left);
            // 调整free list，将内存池中的残余空间编入
            ((obj*)start_free)->free_list_link = *my_free_list;
            *my_free_list = (obj*)start_free;
        }

        // 配置heap空间，用来补充内存池
        start_free = (char*)malloc(bytes_to_get);
        if (0 == start_free) {
            // heap空间不足，malloc()失败
            int i;
            obj* volatile *my_free_list, *p;
            // 试着检视我们手上拥有的东西。这不会造成伤害，我们不打算尝试配置
            // 较小的区块，因为那再多进程机器上容易导致灾难
            // 以下搜寻适当的 free list
            // 所谓适当是指 “尚有未用区块，且区块够大” 的 free list
            for (i = size; i <= __MAX_BYTES; i += __ALIGN) {
                my_free_list = free_list + FREELIST_INDEX(i);
                p = *my_free_list;
                if (0 != p) {   // free list内尚有为未用区块
                    // 调整free list以释出未用区块
                    *my_free_list= p->free_list_link;
                    start_free = (char*)p;
                    end_free = start_free + i;
                    // 递归调用自己，为了修改nobjs
                    return (chunk_alloc(size, nobjs));
                    // 注意，任何残余零头终将被编入释放的free list中备用
                }
            }
            end_free = 0;   // 如果出现意外（山穷水尽，到处没内存可用）
            // 调用第一级配置器，看看out-of-memory机制能够尽点力
            start_free = (char*)malloc_alloc::allocate(bytes_to_get);
            // 这会导致抛出异常，或内存不足的情况获得改善
        }
        heap_size += butes_to_get;
        end_free = start_free + bytes_to_get;
        // 递归调用自己，为了修正nobjs
        return (chunk_alloc(size, nobjs));
    }
}