SGI STL 内存池源码剖析

大纲

• Nginx 内存池源码剖析
• SGI STL 内存池源码剖析

前言

本文将剖析 SGI STL 二级空间配置器中的内存池源码，并介绍内存池的底层设计和工作原理，最后移植 SGI STL 内存池的核心源码。

C++ 常见的池

在 C++ 中有五大池，包括内存池、连接池、协程池、线程池、进程池。

源码下载

• SGI STL 源码下载

书籍推荐

• 《STL 源码剖析》 第二章 - 空间配置器（Allocator）

STL

概念介绍

C++ 中的 STL（Standard Template Library）是标准模板库，提供了一组通用的数据结构和算法，如向量（vector）、链表（list）、集合（set）、映射（map）、排序、查找等；基于模板实现，支持泛型编程，代码复用性高、效率也好。

多种实现

除了 C++ 自身提供的 STL 之外，常见的第三方 STL（标准模板库）实现有以下几种：

• RW STL（Rogue Wave STL）

  • 开发者：
    • Rogue Wave Software 公司（后被 Perforce 收购）
  • 性质：
    • 商业版本的 C++ 标准模板库实现
  • 代表产品：
    • 作为 SourcePro C++ 产品的一部分提供（包含 STL、线程库、网络库、数据库访问库等）
  • 产品特点：
    • 遵循 ISO C++ 标准
    • 跨平台，适配多种操作系统和编译器
    • 提供高级调试、异常安全、多线程支持
    • 可配置性强，适用于嵌入式和大型系统
  • 应用场景：
    • 金融系统、通信系统、嵌入式开发、航空航天、政府项目等对可靠性要求高的场景

• PJ STL（Dinkumware STL）

  • 开发者：
    • P. J. Plauger（C++ 标准委员会成员），其自己公司 Dinkumware 提供支持
  • 性质：
    • 商业版本的 C++ 标准模板库实现
  • 代表使用者：
    • Microsoft Visual C++（尤其是 VC++ 6 及后续版本）默认使用 PJ STL
  • 特点：
    • 遵循 ISO C++ 标准
    • 接口稳定、实现清晰，强调工程实用性
    • 提供 STL、C 标准库（如 <cmath>，<cstdlib>）、TR1 和部分 C++ 11 / 14 特性
  • 优势：
    • 商业支持
    • 与微软编译器深度集成
    • 重视可移植性和性能
  • 局限：
    • 并非开源，文档和源代码可见性有限

• HP STL（Hewlett-Packard STL）

  • 开发者：
    • Hewlett-Packard 公司（惠普实验室），由 Alexander Stepanov 及其团队在 HP（惠普）初步实现
  • 性质：
    • STL 的原始实现，是 SGI STL 的前身
  • 历史意义：
    • 1994 年 Stepanov 在 HP Labs（惠普实验室）首次实现 STL，随后向 C++ 标准委员会提交
    • 后由 SGI 改进并推广形成 SGI STL，逐渐成为业界学习模板编程的典范
  • 特点：
    • 结构清晰，贴近标准草案
    • 强调通用算法和迭代器的分离设计
    • 奠定了 STL 的基础架构，如容器、迭代器、算法的三大支柱
  • 应用与影响：
    • 虽然未被广泛部署于实际商业编译器中，但在学术界和标准委员会中具有开创性意义
    • 是理解 STL 起源与设计哲学的关键资料
  • 现状：
    • 已不再维护，但源码与设计理念在 SGI STL 中得以继承和发扬

• SGI STL（Silicon Graphics STL）

  • 开发者：
    • Alexander Stepanov（STL 之父）、Meng Lee 等人在 SGI（Silicon Graphics Inc.）公司开发
  • 性质：
    • 最早公开发布的 STL 实现之一，并作为学习范例广泛传播
  • 特点：
    • 完全开源，源码可读性和学习性极强
    • 强调泛型编程、模板技巧和性能优化
    • 提供了 allocator、traits、function object、iterator 等先进设计
  • 贡献：
    • 为后来的标准库实现（如 GCC 的 libstdc++）提供了基础
    • 推动了 STL 的工业化、模块化和标准化
  • 现状：
    • 虽然已经不再更新，但作为教学和研究材料仍具重要历史价值

第三方 STL 实现的总结对比表

名称	开发者	是否开源	典型应用	特点描述
RW STL	Rogue Wave Software	❌ 商业版	金融、嵌入式、政府、工业系统	工程化程度高，稳定性强，附带调试与多线程支持，属于 SourcePro C++ 一部分
PJ STL	P. J. Plauger / Dinkumware	❌ 商业版	Visual C++、商业工具链	工程稳健，兼容性好，被微软 Visual Studio 多版本采用
HP STL	Alexander Stepanov / HP	✅ 开源	教育、历史研究、标准演化	STL 的最早实现版本，设计哲学完整，影响了 SGI STL 和后续标准化进程
SGI STL	Alexander Stepanov / SGI	✅ 开源	教育、研究、GCC libstdc++ 原型	泛型编程示范，模板设计前沿，影响广泛

SGI STL

概念介绍

SGI STL 是什么

SGI STL 是由 Alexander Stepanov 和 Meng Lee 等人在 SGI（Silicon Graphics Inc.）公司开发的 C++ 标准模板库实现，最早出现在 1990 年代。这个库实现了 STL 的核心思想：泛型编程与容器 - 算法 - 迭代器模型。SGI STL 包含了一级空间配置器和二级空间配置器，其中一级空间配置器 allocator 采用 malloc() 和 free() 来管理内存，和 C++ 标准模板库（STL）中提供的 allocator 是一样的，但其二级空间配置器 allocator 采用了基于自由链表（Free List）原理的内存池机制来实现内存管理。具体来说，当申请的内存块超过 128 字节时，视之为 “足够大”，会调用一级空间配置器；当申请的内存块小于 128 字节时，视之为 “过小”，会调用二级空间配置器，采用复杂的内存池管理方式，这样可以避免小内存频繁申请和释放导致的内存碎片问题，同时提高效率。

STL 空间配置器的作用

• 在 C++ STL 中，空间配置器（allocator）的作用主要有两种：
• (1) 分离了对象的内存开辟（allocate()）和对象的构造（construct()）。
• (2) 分离了对象的析构（destroy()）和对象的内存释放（deallocate()）。

SGI STL 的主要特性

• 提供了 STL 的主要组件：vector、list、map、set、algorithm、iterator 等。
• 包含一些非标准扩展，例如：
  • slist（单向链表）
  • hash_map / hash_set（后来的 unordered_map / unordered_set 的前身）
• 代码高度模板化、效率高、注释详尽。
• 源码开放，很多 C++ 开发者都用它来学习 STL 的底层实现。

SGI STL 的历史作用

SGI STL 是 现代 C++ STL 的原型，其思想和实现对 C++ 98 标准 STL 的设计有极大影响。许多早期编译器，如 GCC、MSVC、Intel C++，都在某个时期采用过 SGI STL 或其变种（比如 STLport）。

今天还需要使用 SGI STL 吗

• 通常不需要使用 SGI STL，因为现代 C++ 编译器都自带符合标准的 STL 实现，比如 GCC：libstdc++、Clang：libc++、MSVC：Dinkumware。
• 如果是为了学习 STL 的内部实现机制（底层原理），SGI STL 是一个非常好的教学资源；但在生产环境中，应该使用现代 C++ STL（标准模板库）。

SGI STL 与 C++ STL 的区别

项目	SGI STL	C++ STL（标准模板库）
作者 / 出处	SGI 公司（如 STLport）	C++ 标准委员会
标准性	非正式实现，非标准的一些扩展	从 C++ 98 开始，成为标准 C++ 的一部分
扩展内容	hash_map、slist、rope 等非标准组件	标准化容器如 vector、deque、map、set 等
可移植性	与平台、编译器耦合程度较高	作为标准模板库，各主流编译器都支持
现代兼容性	不支持 C++ 11 及以后的特性	现代 STL 持续演进（如 move semantics, unordered_map, ranges 等）
教育价值	非常适合学习 STL 实现机制	通常以黑箱方式使用

自由链表

这里将介绍 SGI STL 二级空间配置器中自由链表的底层实现。

自由链表是什么

自由链表是一种用于管理空闲内存块的链表结构。每个链表节点指向一个未被使用的内存块，便于快速分配和回收。在 SGI STL 的二级空间配置器中，自由链表有以下特点：

• 每种固定大小的内存块（如 8 字节、16 字节、24 字节 …）都有一个对应的自由链表。
• 小对象内存块的复用：当用户释放内存时，并不会直接 free()，而是将内存放回对应的自由链表中，供后续复用。
• 分配内存时，优先从自由链表中取；只有自由链表为空时，才会从系统堆（Heap）分配一大块内存进行切分。

特性	描述
数量	16 个自由链表（按 8 ~ 128 字节分为 16 类）
数据结构	union obj 实现链表节点
分配策略	优先从自由链表取，否则从堆中批量 refill()
回收策略	小块内存回收到对应的自由链表，大块内存直接释放
性能优势	避免频繁 malloc / free，显著减少内存碎片和内存开辟 / 释放的开销

自由链表的结构

内存块粒度与分类

• 内存块的粒度信息

#if defined (__SUNPRO_CC) || defined (__GNUC__)
  enum {_ALIGN = 8};            // 小块内存的对齐粒度（每次分配 8 字节的倍数）
  enum {_MAX_BYTES = 128};      // 二级空间配置器最大管理范围（128 字节）
  enum {_NFREELISTS = 16};      // 自由链表的数量，计算方式：_MAX_BYTES / _ALIGN
#endif

• 一共维护 16 个自由链表，每个自由链表负责管理一种字节大小的内存块：

自由链表的下标	内存块的大小
0	8 字节
1	16 字节
2	24 字节
…	…
15	128 字节

自由链表节点结构

• 每个空闲内存块都可以看作是一个 _Obj，其中 _M_free_list_link 用来链接空闲内存块（最终形成自由链表）

union _Obj {
    union _Obj* _M_free_list_link;    // 下一个内存 chunk 块的地址
    char _M_client_data [1];          // 实际分配给用户的内存起始位置
};

自由链表的存储结构

• 这个数组保存了每种块大小的链表头指针

static _Obj* __STL_VOLATILE _S_free_list [_NFREELISTS];  // 16 个自由链表

内存分配策略

• 当调用 allocate(n)：
  • 如果 n > 128，则交由一级空间配置器处理（直接调用 malloc() 分配内存）。
  • 否则：
    • (1) 将 n 向上对齐到 8 的倍数（实现内存对齐）。
    • (2) 找到对应的自由链表索引。
    • (3) 如果该链表非空，从中取一个满足大小的空闲内存块返回。
    • (4) 如果链表为空，调用 refill() 从堆上批量分配一大块内存（默认分配 2 x 20 个块），挂到自由链表上。

内存回收策略

• 当调用 deallocate(p, n)：
  • 如果 n > 128，则交由一级空间配置器处理（直接调用 free() 释放内存）。
  • 否则：
    • (1) 将 n 向上对齐到 8 的倍数（实现内存对齐）。
    • (2) 找到对应的自由链表索引。
    • (3) 把块头强制转换为 obj*，插入到自由链表的头部（头插法）。

源码剖析

在剖析 SGI STL 的内存池源码时，建议以 vector 容器的源码作为切入点，然后一步步分析一级和二级空间配置器的底层实现，如下图所示：

空间配置器的相关定义

• vector 容器的定义

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR (_Tp) >
class vector : protected _Vector_base<_Tp, _Alloc> { }

• vector 容器的默认空间配置器是 __STL_DEFAULT_ALLOCATOR ( _Tp)，它是一个宏定义，如下：

# ifndef __STL_DEFAULT_ALLOCATOR
#   ifdef __STL_USE_STD_ALLOCATORS
#     define __STL_DEFAULT_ALLOCATOR (T) allocator< T >   // 使用标准 STL allocator（一级空间配置器）
#   else
#     define __STL_DEFAULT_ALLOCATOR (T) alloc            // 使用 SGI alloc（二级空间配置器）
#   endif
# endif

• 从上面可以看到 __STL_DEFAULT_ALLOCATOR 通过宏控制有两种空间配置器实现，一种是 allocator<T>，另一种是 alloc，这两种分别就是 SGI STL 的一级空间配置器和二级空间配置器的实现

template <int __inst>
class __malloc_alloc_template           // 一级空间配置器内存管理类（底层通过 malloc 和 free 管理内存）

template <bool threads, int inst> 
class __default_alloc_template { }      // 二级空间配置器内存管理类（底层通过自定义内存池实现内存管理）

• SGI STL 的一级和二级空间配置器对比

类型	实现类	内存管理机制	用途	源码位置
一级空间配置器	__malloc_alloc_template	malloc() / free()	分配大块内存	定义在 stl_alloc.h 头文件，如图所示
二级空间配置器	__default_alloc_template	内存池机制	分配小块内存，其核心机制就是使用一组自由链表（Free List）来管理内存块，提高小对象（小于等于 128 字节）的内存分配效率，底层也是使用 malloc() / free() 分配和释放内存	定义在 stl_alloc.h 头文件，如图所示

SGI STL 默认的空间配置器

从上面的 vector 容器源码可以发现，SGI STL 的每一个容器都已经指定其缺省的空间配置器为 alloc，即默认使用的是二级空间配置器 __default_alloc_template。

重要类型和变量的定义

在 SGI STL 的二级空间配置器（__default_alloc_template）中，有以下重要类型和变量定义，其底层的自由链表节点结构如下图所示：

• 内存池的粒度信息

#if defined (__SUNPRO_CC) || defined (__GNUC__)
  enum {_ALIGN = 8};            // 小块内存的对齐粒度（每次分配 8 字节的倍数）
  enum {_MAX_BYTES = 128};      // 小块内存的最大字节数（128 字节）
  enum {_NFREELISTS = 16};      // 自由链表的数量，计算方式：_MAX_BYTES / _ALIGN
#endif

• 每一个内存 chunk 块的头信息

union _Obj {
    union _Obj* _M_free_list_link;     // 下一个内存 chunk 块的地址
    char _M_client_data [1];           // 实际分配给用户的内存起始位置
};

• 组织所有自由链表的数组，数组的每一个元素的类型都是 _Obj*，全部初始化为 0

static _Obj* __STL_VOLATILE _S_free_list [_NFREELISTS]; 

• 记录内存 chunk 块的分配情况

// Chunk allocation state.
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;

重要的辅助接口函数

• 将 __bytes 上调至最邻近的 8 的倍数（实现内存对齐）

static size_t _S_round_up (size_t __bytes) {
    return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1));
}

• 返回 __bytes 大小的 chunk 块位于自由链表数组中的索引

static  size_t _S_freelist_index (size_t __bytes) {
    return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
}

内存池管理核心函数

// 分配内存的入口函数
static void* allocate (size_t __n);

// 分配新的 chunk 块，并将分配好的 chunk 块进行连接，添加到自由链表当中
static void* _S_refill (size_t __n);

// 分配相应内存字节大小的 chunk 块
static char* _S_chunk_alloc (size_t __size, int& __nobjs);

// 把 chunk 块归还到内存池
static void deallocate (void* __p, size_t __n);

// 内存池扩容/缩容函数
static void* reallocate (void* __p, size_t __old_sz, size_t __new_sz);

内存池管理总结说明

SGI STL 对内存分配和内存释放的设计哲学

• 向 System Heap 要内存空间。
• 考虑多线程（Multi Threads）状态
• 考虑内存不足时的应变措施
• 考虑过多 “小型区块内存” 可能造成的内存碎片（Fragment）问题

SGI STL 二级空间配置器中内存池的优点

• 内存分配具有预留机制

  • 对于每种特定字节大小的 chunk（内存块）分配，内存池并不会仅分配刚好所需的内存，而是会一次性申请较大一块内存，并将其划分为多个 chunk（比如 40 个）。其中一部分（20 个 chunk）立即用于分配，另一部分（20 个 chunk）作为备用，供后续相同字节大小的分配请求使用。更重要的是，如果其他字节大小的 chunk 分配失败，这部分备用内存也有可能被重新划分后用于其他字节大小的 chunk 分配请求，从而提升内存使用的灵活性与效率。

• 最大化利用碎片内存

  • 在将一大块备用内存划分为若干 chunk 后，可能会剩下一小部分无法完整划分的内存碎片。SGI STL 会在后续分配中尽可能再次利用这些内存碎片，避免资源浪费，确保备用内存池被 “用得干干净净”。

• 具有健壮的回退机制

  • 当某一特定字节大小的内存块分配失败时，二级空间配置器会遍历所有字节大小的自由链表，查找是否有可用的空闲 chunk 块可暂时 “借用”。如果发现其他链表中有满足需求的空闲 chunk 块，就会将其临时分配出去，以缓解当前内存分配压力。如果其他链表中没有满足需求的空闲 chunk 块可以借用，就会直接调用 malloc() 继续分配内存空间。

• 支持 OOM 回调机制

  • 如果其他自由链表中没有空闲的 chunk 块可以借用，且调用 malloc() 分配内存失败，那么二级空间配置器将尝试调用用户预设的 oom_handler 回调函数（可以用于释放用户自定义的内存资源），以应对 malloc() 执行失败的情况（在死循环中处理）。若用户未设置 oom_handler 回调函数，则直接抛出 OOM（Out Of Memory）异常，提示内存分配失败，确保程序行为的可控性和安全性。

SGI STL 一级和二级空间配置器的关系

SGI STL 内存池的的核心源码文件

源码移植

这里将移植 SGI STL 二级空间配置器中的内存池代码，即单独抽出内存池的代码以复用，其中移植的代码主要位于 SGI STL 的 stl_alloc.h 头文件中。

核心源码

• allocator.h 头文件

#pragma once

#include<mutex>
#include<stdexcept>

// 一级空间配置器，按字节分配大块内存
// 封装 malloc() 和 free() 来实现内存管理，可以设置发生 OOM 时释放内存的回调函数
template<int inst>
class __malloc_alloc_template {

public:

    // 开辟内存空间
    static void *allocate(size_t __n) {
        void *__result = malloc(__n);
        if (nullptr == __result) {
            // 调用OOM处理流程
            __result = _S_oom_malloc(__n);
        }
        return __result;
    }

    // 释放内存空间
    static void deallocate(void *__p, size_t /* __n */) {
        free(__p);
    }

    // 内存空间重分配
    static void *reallocate(void *__p, size_t /* old_sz */, size_t __new_sz) {
        void *__result = realloc(__p, __new_sz);
        if (nullptr == __result) {
            // 调用OOM处理流程
            __result = _S_oom_realloc(__p, __new_sz);
        }
        return __result;
    }

    // 设置新的OOM处理函数，返回旧的处理函数
    static void (*__set_malloc_handler(void (*__f)()))() {
        void (*__old)() = __malloc_alloc_oom_handler;
        __malloc_alloc_oom_handler = __f;
        return (__old);
    }

private:

    // 内存空间开辟时的OOM处理流程
    static void *_S_oom_malloc(size_t);

    // 内存空间重分配时的OOM处理流程
    static void *_S_oom_realloc(void *, size_t);

    // OOM回调函数
    static void (*__malloc_alloc_oom_handler)();

};

// 初始化类静态成员变量
template<int inst>
void (*__malloc_alloc_template<inst>::__malloc_alloc_oom_handler)() = nullptr;

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 (nullptr == __my_malloc_handler) { throw std::bad_alloc(); }
        // 调用OOM回调函数
        (*__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 (nullptr == __my_malloc_handler) { throw std::bad_alloc(); }
        // 调用OOM回调函数
        (*__my_malloc_handler)();
        // 再次尝试内存重分配
        __result = realloc(__p, __n);
        if (__result) return (__result);
    }
}

// 重定义类型
using malloc_alloc = __malloc_alloc_template<0>;


//////////////////////////////////////////////////////////////////////////////////////////////////////////////


// 二级空间配置器，按字节分配小块内存
// 基于自由链表原理的内存池机制来实现内存管理
template<int inst>
class __default_alloc_template {

public:

    // 开辟内存空间
    static void *allocate(size_t __n) {
        void *__ret = nullptr;

        // 分配大块内存（当字节数大于 128）
        if (__n > (size_t) _MAX_BYTES) {
            // 调用一级空间配置器分配大内存
            __ret = malloc_alloc::allocate(__n);
        }
        // 分配小块内存
        else {
            // 获取对应大小的自由链表
            _Obj *volatile *__my_free_list = _S_free_list + _S_freelist_index(__n);

            // 获取对应大小的自由链表的互斥锁
            std::lock_guard<std::mutex> __lock_instance(_S_free_list_mtx[_S_freelist_index(__n)]);

            // 获取自由链表的头节点
            _Obj *__result = *__my_free_list;

            // 如果头节点为空（即没有空闲的内存 chunk 块），则分配新的内存 chunk 块
            if (__result == nullptr) {
                __ret = _S_refill(_S_round_up(__n));
            }
            // 如果有空闲的内存 chunk 块，则将其取出来，并维护自由链表的结构
            else {
                // 将自由链表的头节点指向下一个内存 chunk 块
                *__my_free_list = __result->_M_free_list_link;
                __ret = __result;
            }
        }

        return __ret;
    }

    // 释放内存空间
    static void deallocate(void *__p, size_t __n) {
        // 大块内存（当字节数大于 128）直接交由一级空间配置器释放掉
        if (__n > (size_t) _MAX_BYTES) {
            malloc_alloc::deallocate(__p, __n);
        }
        // 小块内存回收到自由链表
        else {
            // 获取对应大小的自由链表
            _Obj *volatile *__my_free_list = _S_free_list + _S_freelist_index(__n);

            _Obj *__q = (_Obj *) __p;

            // 获取对应大小的自由链表的互斥锁
            std::lock_guard<std::mutex> __lock_instance(_S_free_list_mtx[_S_freelist_index(__n)]);

            // 回收内存，将释放的小块内存插入到自由链表的头部（头插法）
            __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) {
        void *__result;
        size_t __copy_sz;

        // 第一种情况：当新旧大小均超过最大内存池处理阈值是，直接调用系统的 realloc()
        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);
    }

private:

    enum { _ALIGN = 8 };            // 小块内存的对齐粒度（每次分配 8 字节的倍数）
    enum { _MAX_BYTES = 128 };      // 小块内存的最大字节数（128 字节）
    enum { _NFREELISTS = 16 };      // 自由链表的数量，计算方式：_MAX_BYTES / _ALIGN

    // 每一个内存 chunk 块的头信息
    union _Obj {
        union _Obj *_M_free_list_link;        // 下一个内存 chunk 块的地址
        char _M_client_data[1];                // 实际分配给用户的内存起始位置
    };

    // 记录内存 chunk 块的分配情况
    static char *_S_start_free;     // 整个内存池的起始位置，只在 _S_chunk_alloc() 中发生变化
    static char *_S_end_free;       // 整个内存池的结束位置，只在 _S_chunk_alloc() 中发生变化
    static size_t _S_heap_size;

    // 组织所有自由链表的数组，数组的每一个元素的类型都是 _Obj*
    static _Obj *volatile _S_free_list[_NFREELISTS];

    // 所有自由链表的互斥锁的数组（内存池基于自由链表实现，需要考虑线程安全问题，为每个自由链表添加一个互斥锁，降低锁的粒度）
    static std::mutex _S_free_list_mtx[_NFREELISTS];

    // 将 __bytes 上调至最邻近的 8 的倍数（实现内存对齐）
    static size_t _S_round_up(size_t __bytes) {
        return (((__bytes) + (size_t) _ALIGN - 1) & ~((size_t) _ALIGN - 1));
    }

    // 返回 __bytes 大小的 chunk 块位于自由链表数组中的索引
    static size_t _S_freelist_index(size_t __bytes) {
        return (((__bytes) + (size_t) _ALIGN - 1) / (size_t) _ALIGN - 1);
    }

    // 分配新的内存 chunk 块，并将分配好的 chunk 块进行连接，添加到自由链表当中
    static void *_S_refill(size_t __n);

    // 分配相应字节大小的内存 chunk 块
    static char *_S_chunk_alloc(size_t __size, int &__nobjs);

};

// 初始化类静态成员变量
template<int inst>
char *__default_alloc_template<inst>::_S_start_free = nullptr;

template<int inst>
char *__default_alloc_template<inst>::_S_end_free = nullptr;

template<int inst>
size_t __default_alloc_template<inst>::_S_heap_size = 0;

template<int inst>
std::mutex __default_alloc_template<inst>::_S_free_list_mtx[_NFREELISTS];

template<int inst>
typename __default_alloc_template<inst>::_Obj *volatile __default_alloc_template<inst>::_S_free_list[_NFREELISTS] = {nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr,
                                                                                                                     nullptr, nullptr, nullptr};

template<int inst>
void *__default_alloc_template<inst>::_S_refill(size_t __n) {
    // 一次性分配 20 个内存 chunk 块，但万一内存空间不足，获得的块数可能小于 20
    int __nobjs = 20;

    // 分配多个指定大小的内存 chunk 块，参数 __nobjs 使用引用传递
    char *__chunk = _S_chunk_alloc(__n, __nobjs);

    _Obj *volatile *__my_free_list;
    _Obj *__result;
    _Obj *__current_obj;
    _Obj *__next_obj;
    int __i;

    // 如果只获得一个内存 chunk 块，就直接分配给调用者使用，自由链表不会添加新节点
    if (1 == __nobjs) {
        return (__chunk);
    }

    // 获取对应大小的自由链表
    __my_free_list = _S_free_list + _S_freelist_index(__n);

    // 将分配到的多个内存 chunk 块添加到对应的自由链表中（即将各个 chunk 块串联起来）
    __result = (_Obj *) __chunk;    // 这个内存 chunk 返回给调用者
    *__my_free_list = __next_obj = (_Obj *) (__chunk + __n);
    for (__i = 1;; __i++) {     // 从 1 开始，因为第 0 个返回给调用者
        __current_obj = __next_obj;
        __next_obj = (_Obj *) ((char *) __next_obj + __n);
        if (__nobjs - 1 == __i) {
            __current_obj->_M_free_list_link = nullptr;
            break;
        } else {
            __current_obj->_M_free_list_link = __next_obj;
        }
    }
    return (__result);
}

template<int inst>
char *__default_alloc_template<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);
    }
    // 第二种情况：整个内存池的剩余空间不能满足全部需求，但至少能分配一个以上的内存 chunk 块
    else if (__bytes_left >= __size) {
        // 更改为实际能够供应的内存 chunk 数
        __nobjs = (int) (__bytes_left / __size);
        __total_bytes = __size * __nobjs;
        __result = _S_start_free;
        _S_start_free += __total_bytes;
        return (__result);
    }
    // 第三种情况：整个内存池的剩余空间不足一个内存 chunk 块大小
    else {
        // 计算需要申请的内存总量：2倍需求 + 附加量（堆大小的1/16并向上对齐）
        size_t __bytes_to_get = 2 * __total_bytes + _S_round_up(_S_heap_size >> 4);

        // 尝试回收利用内存池的剩余碎片
        if (__bytes_left > 0) {
            // 获取对应大小的自由链表
            _Obj *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);

        //  新的内存块申请失败处理
        if (nullptr == _S_start_free) {
            size_t __i;
            _Obj *volatile *__my_free_list;
            _Obj *__p;

            // 尝试从其他字节数更大的自由链表中查找可用内存块
            // 注意：不尝试从字节数更小的自由链表中查找，因为在多处理器环境中容易出现问题
            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 (nullptr != __p) {
                    // 调整自由链表以获取未使用的内存块
                    *__my_free_list = __p->_M_free_list_link;
                    _S_start_free = (char *) __p;
                    _S_end_free = _S_start_free + __i;
                    // 递归调用自身，为了修正 __nobjs
                    return (_S_chunk_alloc(__size, __nobjs));
                    // 注意：任何剩余碎片最终都会被加入到合适的自由链表中备用
                }
            }

            // 所有自由链表都无可用内存时的最后处理手段
            _S_end_free = nullptr;    // 异常安全处理
            _S_start_free = (char *) malloc_alloc::allocate(__bytes_to_get);    // 调用一级空间配置器分配内存（可能会抛出OOM异常）
            // 此处假设分配操作总会成功（要么抛出异常，要么解决问题）
        }

        // 更新内存池管理参数
        _S_heap_size += __bytes_to_get;    // 累计分配的内存总量
        _S_end_free = _S_start_free + __bytes_to_get;    // 设置新的内存池结束位置

        // 递归调用自身，为了修正 __nobjs（此时内存池已有新申请的内存块）
        return (_S_chunk_alloc(__size, __nobjs));
    }
}

// 重定义类型
using default_alloc = __default_alloc_template<0>;


//////////////////////////////////////////////////////////////////////////////////////////////////////////////


// 空间配置器的接口，符合 STL 规范，按元素的大小分配内存
template<typename T, typename Alloc>
class simple_alloc {

public:

    // 重定义类型
    using value_type = T;

    // 构造函数
    constexpr simple_alloc() noexcept {}

    // 拷贝构造函数
    constexpr simple_alloc(const simple_alloc &) noexcept = default;

    // 模板构造函数
    template<typename _U, class _Other>
    constexpr simple_alloc(const simple_alloc<_U, _Other> &) noexcept {}

    // 开辟内存空间
    static T *allocate(size_t n) {
        return n == 0 ? nullptr : (T *) Alloc::allocate(n * sizeof(T));
    }

    // 开辟内存空间
    static T *allocate() {
        return (T *) Alloc::allocate(sizeof(T));
    }

    // 释放内存空间
    static void deallocate(T *p, size_t n) {
        if (n != 0) {
            Alloc::deallocate(p, n * sizeof(T));
        }
    }

    // 释放内存空间
    static void deallocate(T *p) {
        Alloc::deallocate(p, sizeof(T));
    }

    // 对象构造（利用可变参数模板 + 引用折叠 + 完美转发）
    template<typename... Args>
    void construct(T *__p, Args &&... args) {
        // 在指定的内存构造对象（定位 new）
        new(__p) T(std::forward<Args>(args)...);
    }

    // 对象析构
    void destroy(T *__p) {
        // 在指定的内存析构对象
        __p->~T();
    }

};

测试代码

• main.cpp 源文件

#include<iostream>
#include<vector>
#include<cstring>
#include "allocator.h"

using namespace std;

// 自定义数据类型
class Person {

private:
    char *name;
    int age;

    // 深拷贝字符串
    void deepCopy(const char *source) {
        if (source) {
            name = new char[strlen(source) + 1];
            strcpy(name, source);
        } else {
            name = nullptr;
        }
    }

public:
    // 构造函数
    Person(const char *name, int age) : age(age) {
        cout << "Person(name, age)" << endl;
        deepCopy(name);
    }

    // 拷贝构造函数
    Person(const Person &other) : age(other.age) {
        cout << "Person(const Person&)" << endl;
        deepCopy(other.name);
    }

    // 赋值运算符
    Person &operator=(const Person &other) {
        cout << "Person& operator=(const Person&)" << endl;
        // 防止自赋值
        if (this != &other) {
            // 先释放原有内存
            delete[] name;

            // 拷贝新数据
            age = other.age;
            deepCopy(other.name);
        }
        return *this;
    }

    // 析构函数
    ~Person() {
        cout << "~Person()" << endl;
        delete[] name;
    }

    const char *getName() const {
        return name;
    }

    int getAge() const {
        return age;
    }

    void display() const {
        cout << "Name: " << (name ? name : "[Unnamed]") << ", Age: " << age << endl;
    }

};

// 测试基础类型的内存分配
void test01() {
    // 设置随机种子
    srand(time(nullptr));

    // 使用 SGI STL 二级空间配置器
    vector<int, simple_alloc<int, default_alloc>> vec1;

    for (int i = 0; i < 10; ++i) {
        vec1.push_back(rand() % 10 + 1);
    }

    for (const int &item : vec1) {
        cout << item << " ";
    }

    cout << endl;
}

// 测试自定义类型的内存分配
void test02() {
    // 使用 SGI STL 二级空间配置器
    vector<Person, simple_alloc<Person, default_alloc>> vec2;

    // 如果不想频繁触发容器扩容，可以强制指定容器的预留容量
    // vec2.reserve(5);

    vec2.push_back(Person("Jim", 18));
    vec2.push_back(Person("Peter", 23));

    for (auto it = vec2.begin(); it != vec2.end(); ++it) {
        it->display();
    }
}

int main() {
    test01();
    test02();
    return 0;
}

• 测试代码运行的输出结果

3 4 1 8 8 5 10 1 8 8 
Person(name, age)           // 构造临时对象 Jim
Person(const Person&)       // push_back 时拷贝临时对象 Jim 进容器
~Person()                   // 析构临时对象 Jim
Person(name, age)           // 构造临时对象 Peter
Person(const Person&)       // push_back 时触发容器扩容后，拷贝容器已有元素 Jim 到新容器中
Person(const Person&)       // push_back 时触发容器扩容后，拷贝临时对象 Peter 到新容器中
~Person()                   // 析构旧容器中的对象 Jim
~Person()                   // 析构临时对象 Peter
Name: Jim, Age: 18
Name: Peter, Age: 23
~Person()                   // 析构新容器中的对象 Jim
~Person()                   // 析构新容器中的对象 Peter

参考资料

• 容器内存分析 STL 容器内存分配
• SGI STL 二级空间配置器内存池源码
• SGI STL 空间配置器 allocator /alloc
• SGI STL 空间配置器 - 第二级空间配置器
• 高效利用内存资源：掌握内存池设计与实现