STL 空间配置器 – 七葉の喫茶ステラ

函数对象

函数对象（也称为仿函数）是 C++ 中的一种概念，它允许对象表现得像函数一样。这意味着可以像调用普通函数那样调用这些对象。函数对象可以是以下几类：

重载了函数调用运算符的类创建的对象：用户自定义的类，通过重载 operator() 运算符，可以创建出自己的函数对象。这些对象可以有状态（即数据成员），也可以是无状态的。
函数名：在 C++ 中，函数名本身可以作为函数指针使用，因此可以直接作为函数对象。例如，如果有一个函数 int add(int a, int b)，那么可以直接使用 add 作为函数对象，如 add(2, 3)。
函数指针：函数指针是指向函数的指针，它们自然也可以作为函数对象使用。
std::function： std::function 是 C++11 引入的一个模板类，它可以存储、复制、调用任何可调用对象（包括函数、lambda 表达式、函数对象等）。
Lambda 表达式： Lambda 表达式是 C++11 引入的一种便捷的匿名函数语法，它可以创建出可调用的对象。

空间配置器（Allocator）在 C++ 标准库容器中负责管理容器的内存分配和释放。空间配置器的设计和实现对于容器的性能有着直接的影响。在 C++标准库的实现中，空间配置器通常采用两级配置器的设计，以提高内存分配的效率。

一级空间配置器通常是一个简单的 malloc_allocator_template，它直接使用系统的 malloc 和 free 函数来分配和释放内存。这种方式简单直接，适用于大块内存的分配，因为它直接与操作系统的内存管理器交互，避免了重复的系统调用。

二级空间配置器则更为复杂，它根据申请的内存大小采用不同的策略：

大内存分配：
当申请的内存块大于 128 字节时，二级空间配置器仍然使用一级空间配置器，即 malloc_allocator_template，因为它在大块内存分配上更为高效。
小内存分配：
当申请的内存小于 128 字节时，二级空间配置器使用内存池（Memory Pool）加上自由链表（Free List）的结构。这种设计利用了小对象频繁分配和释放的特点，通过预先分配一大块内存（内存池），并将其分割成固定大小的小块（如 32 字节），然后将这些小块存储在自由链表中。

这种设计的关键在于，它通过减少系统调用的次数来提高内存分配的效率。具体来说，内存池被分为多个区域，每个区域对应一种特定的小块大小。例如，下标为 3 的区域会按照 32 字节为单位分配内存，每次分配时会一次性分配一大块内存，并将其分割成多个 32 字节的小块，然后将这些小块存储在自由链表中。当需要 32 字节的内存时，直接从该链表中取出一个小块即可。

内存池的设计进一步优化了内存分配的性能。它通过预先分配一大块内存来避免频繁的系统调用，同时通过将小块内存组织成链表来快速响应内存请求。这种设计减少了内存碎片，提高了内存的使用效率。

内部碎片：由操作系统的内存管理机制（如页式、段式、段页式）引起的，操作系统分配的内存单元通常比申请的内存块大，因此会有一部分未被利用的空间。虽然无法完全避免，但可以通过算法优化减少其影响。
外部碎片：指堆内存中未被使用的、大小不等的内存碎片。这些空间由于太小而无法满足当前的内存申请请求，但总体上它们加起来可能足够大，因此如何有效利用这些外部碎片是提高内存使用效率的关键。