STL源码阅读总结从小白到大神：配置器

一、空间配置器的接口

为什么说allocator是空间配置器而不是内存配置器呢？ 因为空间不一定是内存，空间也可以是磁盘或其他辅助存储介质（可以写一个allocator直接向硬盘取空间）。

二、具备次配置里的SGI空间配置器

SGI STL 配置器与其他配置器不同

• 于标准规范也不同。

• 其名称是alloc而非allocator。

• 不接受任何参数。

写法： vector<int ,std::alloc> iv;

ps：虽然SGI STL allocator 未能符合标准规则，但不会给我们带来困扰，因为通常我们使用缺省的空间配置器，很少要指定配置器名称。

2.1 SGI标准的空间配置器： std::allocator

不建议使用，因为效率不佳，只把C++的::operator new 和 ::operator delete 做了一层薄薄的包装而已。

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

new 一个对象时：先用::operator new 配置内存在，调用构造函数构造对象。

delete 对象时: 先将对象析构，在调用::operator delete 释放内存；

为了精密分工，STL allocator将这两个阶段的操作分开。

1）内存配置 alloc::allocate()

2）内存释放 alloc::deallocate()

3）对象构造 ::construct()

4）对象析构 ::destroy()

STL 标准规则规定配置器定义于中，SGI内包含以下两个文件：

#include <stl_alloc.h> //负责内存空间的配置与释放

#include <stl_construct.h> //负责对象内容的构造与析构

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

• construct()版本一

  通过placement new运算子。

  

• destroy（）版本一（通过指针析构对象)
  
  destroy（）版本二（通过迭代器依次释放内存）

1)迭代器遍历释放内存

2）判断元素类别析构函数是否“无关痛痒”（目的提高效率）

3）析构函数（正常释放） 4）析构函数”无关痛痒“（不做任何处理）

• destroy（）版本二针对迭代器
  

流程图

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

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

2.4.1

C++ new-hander机制：要求系统在内存配置需求无法满足时，调用一个自己所指定的函数。（即在::operator new 无法创建空间时，在丢出std::bad_alloc异常状态前，会先调用由客端指定的处理历程。）总的来说new-header解决内存不足的做法有特定的模式。( SGI以malloc而非::operator new 来配置内存，所以必须仿真一个set_malloc_header(); )

注：alloc并不接受任何template型别参数

2.4.2

• 第一级配置器（ _ malloc_alloc_template 配置区块超过128比特）:

1. 源码：

malloc_based allocator比default_alloc速度慢

oom_malloc()和oom_realloc()都有内循环，不断调用“内存不足处理历程”，但是如果“内存不足处理历程”并未被客端设定，这两个函数就会调用_THROW_BAD_ALLOC丢出bad_alloc异常信息，或利用exit(1)终止程序。

设计“内存不足处理历程”是客端的责任。

• 第二级配置器（ _ default_alloc_template）：

  第二配置器多了一些机制，避免了太多小额区快造成内存碎片，从而造成配置时的额外负担。

  1. 第二级配置器做法（次层配置）：

  1）如果区块够大（超过128bytes）就移交给第一级配置器处理。

  2）如果区块小于128bytes，则使用内存池管理。

  3）每次配置一大块内存，并维护对应之自由链表（free-list），下次若再有相同大小的内存需求，就直接从自由链表中拨出。如果客户端释放归还小额区块，为了方便管理SGI第二级配置器会主动将任何小额区块的内存需求量上调至8的倍数（按字节回收），并维护16个自由链表，各自管理大小分别是8，16，24…120，128bytes。（配置器除了负责配置，也负责回收）

  2. free-list结构 （union解决了为了额外维护链表造成的负担，又实现了链表的作用）
  

  3. 源码
  

• 第一级配置器和第二级配置器的关系：

• 第一级适配器和第二级适配器包装接口和运用方式：
  simple_alloc -->data_alloctor

• 无论alloc被定义为第一级还是第二级配置器，SGI都会为它包装一个接口使其符合STL规格（SGI STL容器全部使用这个simple_alloc接口）：
  

2.5 空间配置函数allocate()

区块自free-list调出操作

2.6空间释放函数 deallocate()

free-list回收过程

2.7 重新填充free_list

当allocate()创建空间发现free_list中没有空间时。就会调用refil()从内存池中取得20个新区块/节点（通过chunk_alloc()完成）,当内存池空间不够时可能小于20个。

2.8 内存池 （memory pool）

通过调用chunk_alloc()为free_list增加新区块\节点。

1.为什么要有内存池

内存池的目的是提供高效的内存分配和释放。

• **提高性能：内存池可以提高程序的性能。**在频繁申请和释放内存的场景中，使用内存池可以减少内存分配和释放的开销。相比于每次都调用标准的内存分配函数（如malloc或new），内存池预先分配一块连续的内存空间，并将其划分为固定大小的块。程序可以直接从内存池中获取这些预分配的块，避免了频繁的系统调用，从而提高了程序的性能。
• **减少内存碎片：内存池可以减少内存碎片的产生。**在使用标准的内存分配函数时，频繁地申请和释放各种大小的内存块可能会导致内存碎片问题。而内存池将内存块固定为相同的大小，避免了不同大小的内存块交替存在导致的内存碎片问题。
• **简化内存管理：内存池可以简化内存管理。**内存池负责预分配和管理内存，程序只需要从内存池中获取或归还内存块即可。这样可以减少程序员在内存管理方面的工作量，降低出错的可能性。
• **控制内存分配：内存池可以提供一定程度的内存分配控制。**通过设置内存池的大小和分配策略，可以限制程序使用的总内存量，避免过多的内存占用。

2.过程

1）通过end_free - start_free 来判断内存池水量，如果水量充足直接调出20个区块返回给free_list。

2）如果内存池足够供应一个以上的区块，却不够20个那么就将这些区块全部拨出去，其pass by reference的nobjs参数将修改为实际拨出的区块数

3）如果一个区块也无法供应，需要利用malloc（）从堆（heap）配置内存，新注入的水量大小为需求量的两倍，在加上一个随配置次数增加而愈来愈大的附加量。

比如：配置了40个32bytes的区块，其中第一个拨出给正好需要的，19个交给free_list[3]维护，余的20个留给内存池。当客端调用64bytes区块时，如果free_list[7]为空，内存池有20个32bytes的区块/10也就是10个64bytes的区块，其中一个交给客端，剩下9个留给free_list[7]维护，这时内存池又空了…以此这样循环。这样可以减少频繁扩大内存池的次数，提高内存分配的效率。

??????注：为什么扩大是两倍量呢？??????

因为两倍量在一定程度上平衡内存使用效率和内存碎片问题

• 内存分配效率：内存池的目标是提供高效的内存分配和释放。通过以两倍数量增长，可以确保每次扩大内存池时，分配给程序的内存总量至少是当前使用量的两倍。这样可以减少频繁扩大内存池的次数，提高内存分配的效率。
• 内存碎片：内存碎片指的是未被使用的小块零散内存空间。如果每次扩大内存池时增加的量太小，可能会导致更多的内存碎片。而选择两倍量的增长，有助于减少内存碎片的产生，提高内存利用率。
• 内存对齐：在内存分配过程中，一些系统和硬件要求内存的地址对齐。通过选择两倍量进行内存池扩大，可以更好地满足内存对齐的需求，提高内存访问效率。

其实对于内存池扩大倍量没有固定值，根据实际情况可能选择其他倍量更好，只不过通常情况下二倍量是一个较为平衡和经验丰富的选择。

2.源码

2.9 内存基本处理工具

STL定义有5个全局函数，其中前两个是前面我们所说的construct()和destroy（）另外三个是uninitialized_copy()、uninitialized_fill()、uninitialized_fill_n()这三个分别对应于高层次的函数copy()、fill()、fill_n()这些都是STL的算法。SGI把他们包含在<stl_uninitialized>中

1. uninitialized_copy

该函数能将内存的配置和对象的构建分离开来。
对于输入来源范围内的每一个对象都会产生一个复制品放入输出范围中。

• 先配置内存区块，足以包含范围内的所有元素
• 使用此函数在该区块上构造元素

2. uninitialized_fill()

该函数也能将内存配置和对象的构建分离开。

3. uninitialized_fill_n()

该函数也能将内存配置和对象的构建分离开。

产生n个对象

4.三个函数的泛型版本和特化版本，对效率的特殊考虑