【STL源码剖析】【2、空间配置器——allocator】

1、什么是空间配置器？

空间配置器是STL（标准模板库）中的一个重要组件，它的主要作用是高效管理各个容器的空间，包括空间的申请与回收。在程序运行时，内存可能存在于栈上（由系统自动分配）或堆上（由用户自行申请）。如果用户频繁地申请和释放空间而不加以管理，可能会导致内存碎片，从而影响内存使用效率并降低程序效率。为了解决这些问题，STL库提供了空间配置器，其原理类似于利用内存池来提高效率。

1.1设计一个简单的空间配置器，JJ::allocator

jjalloc.h

#include "jjalloc.h"
#include <vector>
#include <iostream>
using namespace std;
int main(){int ia[5] = {0,1,2,3,4};unsigned int i;vector<int,JJ::allocator<int>> iv(ia,ia+5);for(i = 0;i < iv.size();i++){cout << iv[i] << " ";}cout <<endl;
}

jjalloc.cpp

#ifndef _JJALLOC_
#define _JJALLOC_#include <new>
#include <cstddef>
#include <cstdlib>
#include <iostream>
#include <climits>
using namespace std;namespace JJ {
//分配内存空间来存储指定类型的对象
template <class T>
inline T* _allocate(ptrdiff_t size,T*){//禁用新的处理器set_new_handler(0);  //调用全局的operator new来分配内存T* tmp = (T*)(::operator new ((size_t)(size * sizeof(T))));if(tmp == 0){std::cerr << "out of memory" << endl;exit(1);}return tmp;
}//处理动态分配的内存的释放
template <class T>
inline void _deallocate(T* buffer){::operator delete(buffer);
}//在已分配但尚未构造的内存中构造一个对象。
//它接受两个参数：
//一个指向 T1 类型对象的指针 p 
//一个 T2 类型的常量引用 value
template <class T1,class T2>
inline void _construct(T1*p ,const T2& value){new(p) T1(value);
}//显式调用对象的析构函数来销毁对象，但不释放内存。
//它接受一个指向 T 类型对象的指针 ptr，并调用该对象的析构函数。
template <class T>
inline void _destroy(T* ptr){ptr->~T();
}
//定义allocator的模板类
template <class T>
class allocator{
public://定义类型别名typedef T          value_type;typedef T*         pointer;typedef const T*   const_pointer;typedef T&         reference;typedef const T&   const_reference;typedef size_t     size_type;typedef ptrdiff_t  difference_type;//从一个类型的分配器“重新绑定”到另一个类型的分配器template<class U>struct rebind{typedef allocator<U> other;};// 用于分配内存来存储 n 个 value_type 类型的对象。// 它调用之前定义的 _allocate 函数来执行实际的内存分配，// 并将返回的内存地址转换为正确的指针类型。pointer allocate(size_type n,const void* hint = 0){return _allocate((difference_type)n,(pointer)0);}// 用于释放之前通过 allocate 函数分配的内存。//它调用 _deallocate 函数来执行实际的内存释放void deallocate(pointer p,size_type n){_deallocate(p);}//在已分配但尚未构造的内存中构造一个对象。//它调用 _construct 函数void construct(pointer p,const T& value){_construct(p,value);}//显式调用对象的析构函数以销毁对象，但不释放内存。//它调用 _destroy 函数来执行此操作void destroy(pointer p){_destroy(p);}//返回对象的地址pointer address(reference x){return (pointer) &x;}//返回常量对象的地址const_pointer const_address(const_reference x){return (const_pointer) &x;}//返回分配器可以分配的最大对象数size_type max_size() const{return size_type(UINT_MAX/sizeof(T));}
};// end of allocator   } //end of namespce JJ#endif //_JJALLOC_

2、具备次配置力( sub-allocation)的 SGI 空间配置器

2.1 什么是次配置力

“次配置力”（sub-allocator）这个概念不是C++标准中的术语，但在某些上下文中，特别是在讨论更复杂的内存管理策略时，可能会使用这个概念。次配置器通常指的是用于管理较小内存块或特定类型对象的配置器。在复杂的内存管理系统中，你可能会有一个主配置器（用于处理大块内存分配）和多个次配置器（用于处理不同类型的对象或更小的内存块）。
次配置器的使用可以提高内存管理的效率，因为它们可以针对特定类型的对象或特定大小的内存块进行优化。例如，一个次配置器可能使用内存池技术来快速分配和回收小块内存，而另一个次配置器可能使用特定的对齐策略来优化特定类型对象的存储。

2.2 SGI标准的空间配置器，std::allocator

虽然 SGI 也配置了 allocatalor，但是它自己并不使用，也不建议我们使用，原因是效率比较 感人，因为它只是在基层进行配置/释放空间而已，而且不接受任何参数。
看一下std::allocator的代码示例：

#ifndef DEFALLOC_H
#define DEFALLOC_H#include <new.h>
#include <stddef.h>
#include <stdlib.h>
#include <limits.h>
#include <iostream.h>
#include <algobase.h>
template <class T>
inline T* allocate(ptrdiff_t size,T*){set_new_handler(0);T* tmp = (T*)(::operator new((size_t)(size*(sizeof(T))));if(tmp == 0){cerr<<"out of memory"<<endl;exit(1);}return tmp;
}
template <class T>
inline void deallocate(T* buffer){::operator delete(buffer);
}
template <class T>
class allocator{
public:typedef T 			value_type;typedef T* 			pointer;typedef const T* 	const_pointer;typedef T& 			reference;typedef const T& 	const_reference;typedef size_t		size_type;typedef ptrdiff_t	difference_type;	pointer allocate(size_type n){return ::allocate((difference_type)n,(pointer)0);}void deallocate(pointer p){::deallocate(p);}pointer address(reference x){return (pointer)&x;}const_pointer const_address(const_refernce x){return (const_pointer)&x;}//确定一个“页面”或“块”的大小size_type int_page_size(){return max(size_type(1),size_type(4096/sizeof(T)));}size_type max_size() const{return max(size_type(1),size_type(UINT_MAX/sizeof(T)));}
};
class allocator<void>{
public:typedef void* pointer;
}
#endif //DEFALLOC_H

从源码可以看到allocator只是基层内存配置/释放行为的简单包装，在效率上没有任何的提升。

2.2 SGI特殊的空间配置器，std::alloc

一般而言，对C++内存配置操作和释放操作

class Foo{...};
Foo* pf = new Foo;   //配置内存，然后构造对象
delete pf;			 //将对象析构，然后释放内存

为了精密分工，STL allocator决定将这两阶段的操作区分开来，
内存配置操作由alloc:allocate()负责，内存释放操作由alloc:deallocate()负责；
对象构造操作由::construct()负责，对象析构操作由::destroy()负责。
SGI内含有以下两个文件：

#include<stl_alloc.h>           //负责内存空间的配置与释放
#include<stl_construct.h>       //负责对象内容的构造与析构

图1. STL配置器的框架

2.3 构造和析构的基本工具：construct()和destroy()

以下是<stl_construct.h>的部分内容：

#include<new.h> //欲使用placement new,需要包含次文件
template <class T1,class T2>{
inline void construct(T1* p,const T2& value){new(p) T1(value);  //placement new
}//destroy有2个版本
//版本1，接受一个指针；
template<class T1>
inline void destroy(T* pointer){pointer->~T();    
}
//版本2，接受2个迭代器，此函数设法找出元素的数值型别
template<class ForwardIterator>
inline void destroy(ForwardIterator first,ForwardIterator last){__destroy(first,last,value_type(first));
}//判断元素的数值类型，是否有trivial destructor
template<class ForwardIterator, class T>
inline void __destroy(ForwardIterator first,ForwardIterator last, T*){typedef typename __type_traits<T>::has_trivial_destructor trivial_destructor;__destroy_aux(first,last,trivial_destructor());
}
//如果元素的数值型别有 non-trivial destructor
template<class ForwardIterator>
inline void __destroy_aux(ForwardIterator first,ForwardIterator last, __false_type){for(;first<last;++first)destroy(& *first);
}
//如果元素的数值型别有 trivial destructor
template<class ForwardIterator>
inline void __destroy_aux(ForwardIterator first,ForwardIterator last, __true_type){}//destroy()第二版本对迭代器char* wchar_t*的特化版
inline void destroy(char*,char*){}
inline void destroy(wchar_t*,wchar_t*){}

construct()接受一个指针p和一个初值value，该函数的用途就是将初值设定到指针所指的空间上。
destruct()有2个版本。版本1接受一个指针，准备将该指针所指之物析构调，直接调用该对象的析构函数即可；版本2接受first，last两个迭代器，讲[first,last)范围内的对象都析构掉。做了一些处理，万一对象有(trivial destructor)，每一次调用他们，会极大的降低效率。所以做了一些处理来判断析构函数是否是trivial destruct，如果是的话，什么也不做就立马结束。如果不是的话，以循环方式巡访整个范围，在循环中每访问一个对象就调用第一个版本的destroy()。

图2. construct()和destroy()函数

补充：

2.3.1、什么是 trivial destruct:

“trivial destructor”指的是用户没有自定义析构函数，而是由系统生成的析构函数。这种析构函数在对象生命周期结束时
被调用，但由于用户没有定义任何特定的析构逻辑，它实际上并不执行任何特定的清理或资源释放操作。因此，它被称
为“trivial”，即无用的或无关紧要的析构函数。
相对而言，如果用户为某个类定义了特定的析构函数，那么这个析构函数就被称为“non-trivial destructor”。在这种情况
下，析构函数可能会执行一些必要的清理操作，如释放动态分配的内存、关闭文件句柄或断开网络连接等。需要注意的是，即
使析构函数是trivial的，它仍然会在对象生命周期结束时被自动调用。这是因为C++的析构机制确保了每个构造的对象最终都会
被正确地销毁。然而，对于trivial destructor来说，由于它不执行任何实质性的操作，频繁地调用它可能会对性能产生一定的
影响。因此，在一些高级编程场景中，可能会使用特定的技术或工具来优化或避免不必要的trivial destructor调用。

2.3.2、从__destroy_aux来看，他的销毁范围是[first,last),为什么没有销毁最后一个

在C++中，迭代器通常遵循“左闭右开”的原则，即迭代器first指向的范围是包括的，而迭代器last指向的位置是不包括的。这意味着 last迭代器实际上指向的是范围之外的第一个位置 ，而不是范围内的最后一个元素的下一个位置。因此，循环在first小于last时继续，这样last指向的元素就不会被包括在销毁的范围内。
这种设计有几个原因：
（1）一致性：C++标准库中的许多算法和容器都遵循这种 “左闭右开” 的范围定义方式，保持一致性使得代码更容易理解和使用。
（2）避免越界访问（安全性）：如果尝试访问或销毁last指向的元素，那么可能会越界访问内存，导致未定义行为。保持“左闭右开”的范围定义可以避免这种潜在的问题。
（3）效率：在某些情况下，last可能正好指向一个容器的末尾之后的位置，这个位置本身并不存储任何对象，因此没有销毁的必要。
（4）语义清晰：对于用户来说，知道last不指向要销毁的最后一个元素，可以更容易地理解函数的行为，特别是当使用自定义迭代器或特殊容器时。
综上所述，不将last销毁是出于一致性、安全性、效率和语义清晰性的考虑。在设计类似的算法或函数时，通常应该遵循这些原则来确保代码的正确性和可维护性。

2.4 空间的配置和释放，std::alloc

2.3讲的是对象构造行为与对象析构行为，现在来看一下内存的配置与释放。这一部分代码都在<stl_alloc.h>中。stl对此的设计哲学是：

• （1）向 system heap 要求空间
• （2）考虑多线程 (multi-threads) 状态
• （3）考虑内存不足时的应变措施
• （4）考虑过多“小型区块”可能造成的内存碎片 (fragment) 问题
  考虑到小型区块可能造成的内存破碎问题，SGI 为此设计了双层级配置器。当配置区块超过 128bytes 时，称为足够大，使用第一级配置器，直接使用 malloc() 和 free()。
  当配置区块不大于 128bytes 时，为了降低额外负担，直接使用第二级配置器，采用复杂的 memory pool 处理方式。

#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;
#endif /*  !__USE_MALLOC*/

其中， __malloc_alloc_template 就是第一级配置器; __default_alloc_template 就是第二级配置器。无论使用第一级配接器(malloc_alloc_template)或是第二级配接器 (default_alloc_template)，alloc 都为其包装了接口，使其能够符合 STL 标准。

template<class T,class Alloc>
class simple_alloc{
public:static T*allocate(size_t n){return 0==n?:(T*)Alloc::allocate(n*sizeof(T));}static T*allocate(void){return (T*) Alloc::allocate(sizeof(T));}static T*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));}
};

图3. 第一级配置器与第二级配置器

图4. 第一级配置器与第二级配置器包装接口和运用方式

2.5 第一级配置器 __malloc_alloc_template剖析

#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)
#endiftemplate <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)
{//第一级配置器直接使用malloc()void *result = malloc(n);if(0 == result) result = 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);//当以下无法满足要求时，改用oom_realloc()if(0 == result) result = oom_realloc(p,new_sz);return result;
}
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_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>::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);}
}
//以下直接将参数inst指定为0
typedef __malloc_alloc_template<0> malloc_alloc;

(1)第一级配置器以 malloc(), free(), realloc() 等 C 函数执行实际的内存配置、释放和重配置 操作，并实现类似 C++ new-handler 的机制(因为它并非使用 ::operator new 来配置内存， 所以不能直接使用C++ new-handler 机制)。
(2)SGI 第一级配置器的 allocate() 和 reallocate() 都是在调用malloc() 和 realloc() 不成功 后，改调用 oom_malloc() 和oom_realloc()。
(3)oom_malloc() 和 oom_realloc() 都有内循环，不断调用“内存不足处理例程”，期望某次 调用后，获得足够的内存而圆满完成任务，哪怕有一丝希望也要全力以赴申请啊，如果用户并 没有指定“内存不足处理程序”，这个时候便无力乏天，真的是没内存了，STL 便抛出异常。或 调用exit(1) 终止程序。

2.6 第二级配置器 __default_alloc_template剖析

第二级配置器多了一些机制，专⻔针对内存碎片。内存碎片化带来的不仅仅是回收时的困难，配置也是一个负担，额外负担永远无法避免，毕竟系统要划出这么多的资源来管理另外的资源，但是区块越小，额外负担率就越高。

图5. 索取内存，需要cookie记录大小 ### 2.6.1 SGI 第二级配置器到底解决了多少问题呢? 简单来说 SGI第二级配置器的做法是:**sub-allocation (层次架构):** 前面也说过了，SGI STL 的第一级配置器是直接使用 malloc()， free(), realloc() 并配合类似 C++ new-handler 机制实现的。第二级配置器的工作机制要根据区块的大小是否大于 128bytes 来采取不同的策略，这种方法叫做层次配置。

图6. 层次配置

图7. 内存池原理

二级配置器内存池的原理主要涉及两个方面：内存池的管理和两级配置器的使用。
（1）首先，内存池的主要作用是在应用程序初始化时分配一块连续的内存空间，并将其划分为多个固定大小的块（也称为“内存池对象”）。这些块可以被反复使用，从而避免了频繁地向操作系统请求新的内存空间。当应用程序需要分配新的内存时，它可以直接从预先分配好的内存池中取出一个可用的块，而不是向操作系统申请。这样可以减少系统开销，提高程序效率，同时也可以避免内存碎片和泄漏等问题。
（2）其次，二级配置器则是对内存池管理的一种优化策略。它采用两级策略来配置内存：当所需内存区块小于某个阈值（如128字节）时，使用第二级配置器进行管理。这个配置器会一次性配置一大块内存，并维护对应的空闲链表（free-list）。当下次有相同大小的内存需求时，直接从空闲链表中取出。如果有小的内存区块被释放，它们会被回收到空闲链表中，以供后续使用。这种策略有效地避免了由于太多小区块造成的内存碎片问题，同时减少了配置时的额外负担。
具体来说，二级配置器会维护多个空闲链表，每个链表管理不同大小的内存块。例如，可以维护16个空闲链表，分别管理大小为8、16、24…120、128字节的数据块。当需要分配内存时，根据所需大小计算索引，从对应的空闲链表中取出内存块。当内存块被释放时，它会被回收到对应的空闲链表中。
最后，内存池的管理涉及对内存空间的分配和释放。当向系统申请一块内存放入内存池时，会使用start和end指针来标记这块空间的起始和结束位置。每分配一部分内存，start指针就会向后移动相应的距离。当start和end指针重合时，表示内存池中的空间已全部分配完毕。释放内存时，需要将释放的内存块归还到内存池中，并更新start指针的位置。
综上所述，二级配置器内存池的原理通过预分配连续内存空间、划分固定大小的块、使用两级配置器以及维护空闲链表等方式，实现了对内存的高效管理和利用，避免了内存碎片和泄漏等问题，提高了程序的运行效率。

2.6.2 自由链表自由在哪?又该如何维护呢?

我们知道，一方面，自由链表中有些区块已经分配给了客端使用，所以 free_list 不需要再指向它们;另一方面，为了维护 free-list，每个节点还需要额外的指针指向下一个节点。
那么问题来了，如果每个节点有两个指针?这不就造成了额外负担吗?本来我们设计 STL 容 器就是用来保存对象的，这倒好，对象还没保存之前，已经占据了额外的内存空间了。
STL给出的解决办法是：

union obj{union obj* free_list_link;char client_data[1]
}

在 union obj 中，定义了两个字段，再结合上图来分析:
从第一个字段看，obj 可以看做一个指针，指向链表中的下一个节点;
从第二个字段看，obj 可以也看做一个指针，不过此时是指向实际的内存区。
一物二用的好处就是不会为了维护链表所必须的指针而造成内存的另一种浪费，

在二级配置器中的自由链表（free-list），**“自由”**体现在链表中的内存块是未被应用程序当前使用的，即它们是“空闲”的，随时可以被分配给需要内存的空间。自由链表的存在允许内存块在被释放后能够被回收和重用，而不是直接归还给操作系统，从而提高了内存的使用效率。
自由链表的维护主要涉及以下几个方面：
(1) 插入操作：当释放一个内存块时，该内存块会被插入到相应的自由链表中。通常，链表会按照内存块的大小进行划分，每个链表管理特定大小的内存块。因此，释放内存块时，需要根据其大小计算它应该插入到哪个链表中。
(2) 删除操作：当应用程序请求分配内存时，二级配置器会从自由链表中删除一个内存块，并将其分配给应用程序。这通常涉及到从链表中取出第一个节点（或根据某种策略选取一个节点）并更新链表的结构。
(3) 链表合并：如果两个相邻大小的自由链表都只有少量的内存块，为了提高内存管理的效率，可能会将它们合并成一个更大的链表。这样可以减少链表的数量，简化管理。
(4) 内存块合并：当连续的内存块都被释放时，可以考虑将它们合并成一个更大的内存块，以减少碎片并便于后续的分配。
(5) 内存块分割：当请求的内存大小与自由链表中现有内存块的大小不完全匹配时，可能需要将现有的内存块分割成两部分，一部分用于满足当前的请求，另一部分作为新的空闲内存块加入自由链表。
(6) 链表大小调整：随着程序的运行，某些大小的内存块可能会被频繁地申请和释放，导致某些链表特别长或特别短。此时，可以根据实际情况调整链表的大小，例如通过合并或分割链表来平衡内存的使用。
(7) 内存泄露检查：定期检查自由链表中的内存块是否都被正确管理，防止因为编程错误导致的内存泄露。
为了实现这些操作，二级配置器通常会维护一些数据结构来跟踪每个链表的状态，例如链表的头指针、链表长度、已分配和未分配的内存块数量等。这些数据结构可以帮助配置器高效地管理内存块，确保它们能够在需要时被正确地分配和回收。
总的来说，自由链表的维护涉及到内存块的插入、删除、合并和分割等操作，以及链表本身的调整和优化。这些操作共同确保了内存的有效利用和程序的稳定运行。

2.6.3 第二级配置器的部分实现内容

enum{__ALIGN = 8};                        //小型区块的上调边界
enum{__MAX_BYTES = 128};                  //小型区块的上限
enum{__NFREELISTS = __MAX_BYTES/__ALIGH}; //free_lists的个数template <bool threads,int inst>
class __default_alloc_template{
private:
//ROUND UP
static size_t ROUND_UP(size_t bytes){return (((bytes)+ __ALIGN_1) & ~(__ALIGN-1));
}
private:union obj{ //free lists的节点构造union obj * free_list_link;char clinet_data[1]};
private://16个free-listsstatic obj* volatile free_list[__NFREELISTS];//根据区块大小，决定使用第n号listsstatic size_t FREELIST_INDEX(size_t bytes){return (((bytes) + __ALIGN -1)/__ALIGN -1);}
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;  //内存池起始位置
static char* end_free;    //内存池结束位置
static char* 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>
char *__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};
}

2.7空间配置函数allocate()

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

2.7.1空间配置函数allocate()实现原理：

allocate()代码实现了一个简单的内存分配策略，它首先检查请求的内存大小是否超过预设的阈值，如果是则调用另一个配置器进行分配。对于小块内存，它使用一组free lists来快速分配和回收固定大小的内存块。当free list为空时，它会调用 refill 函数来重新填充free list。这种策略有助于减少内存碎片，并提高小块内存的分配和回收效率。

2.7.2空间配置函数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 lists,准备重新填充 free lstsvoid *r = refill(ROUND_UP(n));return r;}//调整free lists*my_free_list = result->free_list_link;return(result);
};

图8. allocate()函数工作原理

2.8 空间释放函数 deallocate()

身为一个配置器，__default_alloc_template 拥有配置器标准接口函数 deallocate()。该函数首先判断区块大小，大于 128bytes就调用第一级配置器， 小于 128bytes就找出对应的free lists，将区块进行回收。

2.8.1空间释放函数 deallocate()实现原理：

这个函数是一个自定义内存分配器的一部分，用于将释放的内存块添加到适当的空闲链表中，以便将来可以重新使用。对于大于某个阈值的内存块，它使用另一个（可能是更通用的）分配器来释放内存。这种自定义的内存分配器通常用于优化特定类型的内存使用，例如小对象的快速分配和释放。

2.8.2空间释放函数 deallocate()代码实现：

//p不可以是0
static void *allocate(void* p,size_t n){obj *q = (obj*)p;obj *volatile *my_free_list;//大于128就调用第一级配置器if(n > (size_t)__MAX_BYTES){malloc_alloc::deallocate(p,n);return ;}//寻找对应的free listmy_free_list = free_list + FREELIST_INDEX(n);//调整free list，收回区块q->free_list_link = *my_free_list;*my_free_list = q;
}

图9. deallocate()函数工作原理

2.9 重新填充 free lists

先前说过的allocate()当它发现freelist 中没有可用区块了时， 就调用 refill(}，准备为freelist重新填充空间.新的空间将取自内存池(经由
chu出_alloc()完成)。缺省取得20 个新节点(新区块)，但万一内存池空间不 足，获得的节点数(区块数)可能小于 20:

2.9.1重新填充 free lists()实现原理：

这个函数的主要目的是为自定义内存分配器“refill”空闲链表。它首先分配一个较大的内存块（chunk），然后将其分割成多个较小的对象，并将这些对象链接成一个空闲链表。最后，它返回第一个对象的地址给调用者，以便该对象可以被分配给客户端。这种策略通常用于优化内存分配和释放，特别是在需要频繁分配和释放小块内存的情况下。

2.9.2重新填充 free lists()代码实现：

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

/* 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.                                         */
template <bool threads, int inst>
void* __default_alloc_template<threads, inst>::refill(size_t n)
{int nobjs = 20;char * chunk = chunk_alloc(n, nobjs);obj * __VOLATILE * my_free_list;obj * result;obj * current_obj, * next_obj;int i;if (1 == nobjs) return(chunk);my_free_list = free_list + FREELIST_INDEX(n);/* Build free list in chunk */result = (obj *)chunk;*my_free_list = next_obj = (obj *)(chunk + n);      // my_free_list 跳过第一块内存  从第2块开始     result指向第一块  返回给客户端for (i = 1; ; i++) {current_obj = next_obj;next_obj = (obj *)((char *)next_obj + n);if (nobjs - 1 == i) {                           // 19 块空间 放到相应的 free_list 里面   current_obj -> free_list_link = 0;break;} else {current_obj -> free_list_link = next_obj;}}return(result);
}

2.10 内存池 memory pool

首先，我们要知道从内存池中取空间给 free_list 使用，是 chunk_alloc() 在工作，它是怎么工 作的呢?
我们先来分析 chunk_alloc() 的工作机制:chunk_alloc() 函数以 end_free – start_free 来判断内存池的“水量”。具体逻辑如下。

图10. chunk_alloc()函数工作原理 如果第一级配置器的 malloc() 也失败了，就发出 bad_alloc 异常。

2.10.1内存池 memory pool实现原理：

图11. memory_pool()函数工作原理 举个例子： 假设程序一开始，客端就调用 chunk_alloc (32, 20), 于是 malloc()配置 40 个 32 bytes 区块，其中第 1 个交出，另 19 个交给free_list[3]维护，余 20 个留给内存池。接下来客端调用chunk_alloc(64,20)，此时 free_list[7]空空如也，必须向内存池要求支持。内存池只够供应 ( 32*20)/64=10 个 64 bytes 区块，就把这 10 个区块返回，第 1 个 交给客端，余 9 个由 free_list[7]维护。此时内存池全空。接下来再调用 chunk_alloc(96, 20)，此时 free_list[11]空空如也，必须向内存池要求支持， 而内存池此时也是空的，于是以 malloc()配置40+n (附加量)个96bytes区块，其中第 1 个交出，另 19 个交给 free_list[11]维护，余 20+n (附加量)个区块 留给内存池。

2.10.2内存池 memory pool代码实现：

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);//利用剩下的一点点零头.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);if (0 == _S_start_free) {size_t __i;_Obj* __STL_VOLATILE* __my_free_list;_Obj* __p;//看free-list是否还有内存区块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;return(_S_chunk_alloc(__size, __nobjs));                //反复压榨内存}}//执行到了这一步，说明没内存了，_S_end_free初始化置于零，并调用第一级配置器配置内存重新设定_S_start_free。_S_end_free = 0;    _S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);}_S_heap_size += __bytes_to_get;_S_end_free = _S_start_free + __bytes_to_get;//return(_S_chunk_alloc(__size, __nobjs));}
}

3、内存 基本处理工具

STL定义了五个全局函数，分别是construct(),destroy(),uninitialized_copy(),uninitialized_fill(),
uninitialized_fill_n()。构造，析构函数已经说过，现在考虑后面3个函数。

3.1 uninitialized_copy

std::uninitialized_copy()
std::uninitialized_copy() 用于从输入范围复制元素到未初始化的内存区域。它接收两个输入迭代器（表示要复制的元素的范围）和一个指向目标内存区域的原始指针。
函数原型可能类似于：

template<class InputIt, class ForwardIt>  
ForwardIt uninitialized_copy(InputIt first, InputIt last, ForwardIt result);

first 和 last 定义了输入范围的开始和结束。
d_first 是指向目标内存区域的原始指针。
这个函数会将 [first, last) 范围内的所有元素复制到从 d_first 开始的内存区域，并返回指向目标区域中最后一个复制元素的下一个位置的原始指针。

3.2 uninitialized_fill

std::uninitialized_fill() 用于在未初始化的内存区域中填充指定值。它接收一个原始指针（指向目标内存区域的开始）和一个表示要填充的值的参数，以及要填充的元素数量。
函数原型可能类似于：

template<class ForwardIt, class T>  
void uninitialized_fill(ForwardIt first, ForwardIt last, const T& value);

first 和 last 定义了目标内存区域的开始和结束。
value 是要填充的值。
这个函数会将 [first, last) 范围内的所有元素初始化为 value。

3.3 uninitialized_fill_n

std::uninitialized_fill_n() 类似于 std::uninitialized_fill()，但它允许你指定要填充的元素数量，而不是通过两个迭代器来定义范围。
函数原型可能类似于：

template<class ForwardIt, class Size, class T>  
ForwardIt uninitialized_fill_n(ForwardIt first, Size n, const T& value);

first 是指向目标内存区域的原始指针。
n 是要填充的元素数量。
value 是要填充的值。
这个函数会将从 first 开始的 n 个元素初始化为 value，并返回指向最后一个填充元素的下一个位置的原始指针。

4、总结

天堂有路你不走，地狱无门你自来。

5、参考

1、《STL源码剖析》
2、《C++八股文小贺》（图片均来自于他）