🌠 作者：@阿亮joy.
🎆专栏：《吃透西嘎嘎》
🎇 座右铭：每个优秀的人都有一段沉默的时光，那段时光是付出了很多努力却得不到结果的日子，我们把它叫做扎根
👉什么是空间配置器👈
空间配置器，顾名思义就是为各个容器高效的管理空间（空间的申请与回收）的，在默默地工作。虽然在常规使用 STL 时，可能用不到它，但站在学习研究的角度，学习它的实现原理对我们有很大的帮助。注：空间配置器是内存池。
直接向堆区申请内存的有 Windows 下的 VirtualAlloc 和 Linux 下的 brk，这个一般不符合我们的需求。而 malloc 是向堆区申请内存的函数，也本质是一个内存池，可用于整个程序的内存管理。STL 的空间配置器也是内存池，其是专门服务 STL 容器的内存管理，以提高效率。
👉为什么需要空间配置器👈
前面在模拟实现 vector、list、map、unordered_map 等容器时，所有需要空间的地方都是通过 new 申请的，虽然代码可以正常运行，但是有以下不足之处：
- 空间申请与释放需要用户自己管理，容易造成内存泄漏
- 频繁向系统申请小块内存块，容易造成内存碎片
- 频繁向系统申请小块内存，影响程序运行效率
- 直接使用 malloc 与 new 进行申请，每块空间前有额外空间浪费
- 申请空间失败怎么应对
- 代码结构比较混乱，代码复用率不高
- 未考虑线程安全问题
👉SGI-STL空间配置器实现原理👈
以上提到的几点不足之处，最主要还是：频繁向系统申请小块内存造成的。那什么才算是小块内存？SGI-STL 以 128 作为小块内存与大块内存的分界线，将空间配置器其分为两级结构，一级空间配置器处理大块内存，二级空间配置器处理小块内存。
一级空间配置器
二级空间配置器
如果申请的内存大小小于 128 字节时，就走二级空间配置器。首先，看看该大小的内存对应的桶中有没有内存，如果有就直接返回；如果没有，就去调用 malloc 申请大块内存，并将大块内存切分成小块内存头插到对应的桶中。如果多次申请该大小的内存时，就能够提高效率了。
free_list 的桶和哈希桶的区别：哈希桶挂的是节点，这些节点都是一样的；free_list 的桶挂的是内存，不同的桶挂的内存大小是不一样的。因为一个指针是4个字节 或 8 个字节，而我们只需要让内存的头 4 个或 8 个字节指向下一个内存的地址，最后一块内存的头 4 个或 8 个内存指向空。
假设现在要申请 40 个字节，发现桶没有，就去看大块内存够不够 40 个字节。假设没有且再去用 malloc 申请大块内存也失败了，这时候就会去看后面的桶有没有比 40 大的内存，如果有，就将该内存切分成 40 大小的内存和更小的内存，并将该内存挂在对应的桶上。如果还是没有，那么就抛异常。
STL 的空间配置器是专门服务容器的，假设 list 的一个节点大小为 12 个字节，set 的一个节点为 16 字节。假设 list 尾插了 15 次，那么它就使用了 15 个 16 字节大小的内存（大块内存可以被切分成 20 个 所需空间的小内存）。那么现在还是剩下 5 个 16 字节大小的内存，此时 set 开始 insert，那么这 5 个内存就可以被 set 使用。假设 set insert 3 次后，list 析构了并将其内存挂回了 free_list 的桶上，那么这些内存也就可以被 set 所使用。这也是空间配置器提高效率的做法。
一个进程里面应该只有一个空间配置器，所以空间配置器可以设计成单例模式的类。SGI 的 STL 空间配置器是通过静态成员来间接实现单例模式的。
👉空间配置器的优势👈
- 频繁申请小块内存时，效率高（memory 头文件中的 allocator 就是 STL 的空间配置器，可以和 malloc 进行效率对比）。
- 一定程度上缓解了内存碎片的问题，内存碎片分为外碎片和内碎片
- 外碎片问题是由频繁向系统申请小块内存造成的。频繁向系统小块内存会造成有足够的内存，但是不连续，无法申请大块的内存。
- 内碎片问题是实际申请到的内存多于所需的内存，而多出来的内存用户也无法使用。内存块按一定的对齐规则挂起来管理，就会导致内碎片问题。比如：list 的一个节点需要 12 个字节，系统给了用户 16 个字节，多出来的 4 个字节用户也无法使用。内存池一般都会有内碎片问题，内碎片问题不是很严重。
malloc 和 内存池的对比
注：一下实现的定长内存池是高并发内存池项目中的组件，以后会详细讲解！定长内存池的空间是不释放的，因为大块内存已经被切分了好多次，无法正确释放。但是只要进程是正常结束的，也不要造成内存泄漏问题。进程正常结束，操作系统会回收内存。
// ObjectPool是针对某一类对象的定长内存池
#pragma once
#include <iostream>
#include <vector>
#include <time.h>
// 工程项目中不要将std整个命名空间展开,避免命名污染
using std::cout;
using std::endl;
// 操作系统的控制,如果是Windows系统则包含windows.h
// 如果是Linux系统,则包含brk系统调用对应的头文件
#ifdef _WIN32
#include <windows.h>
#else
//
#endif
// 因为要实现的高并发内存池要使用到定长
// 内存池,所以就不采用下方的实现方式了
// 定长内存池
//template <size_t N>
//class ObjectPool
//{};
// 直接去堆上按页申请空间(Windows的VirtualAlloc和Linux的brk)
// kpage是页数,假设一页是8KB
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
void* ptr = VirtualAlloc(0, kpage << 13, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
// linux下brk mmap等
#endif
if (ptr == nullptr)
throw std::bad_alloc();
return ptr;
}
template <class T>
class ObjectPool
{
public:
T* New()
{
T* obj = nullptr;
// 优先把还回来的内存重复使用
if (_freeList)
{
// 将_freeList强转为void**,对其解引用即可
// 得到四个字节或八个字节的地址
void* next = *((void**)_freeList);
obj = (T*)_freeList;
_freeList = next; // 指向下一块内存
}
else
{
// 剩余内存不够一个对象的大小时,则再申请大块内存
if (_leftBytes < sizeof(T))
{
_leftBytes = 128 * 1024;
// 使用VirtualAlloc是为了完全和malloc脱离
//_memory = (char*)malloc(_leftBytes);
// 假设一页是8KB,右移13位即可算出页数
_memory = (char*)SystemAlloc(_leftBytes >> 13);
if (_memory == nullptr)
{
throw std::bad_alloc();
}
}
obj = (T*)_memory;
// 保证申请的内存大小至少是一个指针的大小
// 以保证能够存下一块内存的起始地址
size_t objSize = sizeof(T) < sizeof(void*) ? sizeof(void*) : sizeof(T);
_memory += objSize;
_leftBytes -= objSize;
}
// 定位new,显式调用T的构造函数初始化
new(obj) T;
return obj;
}
void Delete(T* obj)
{
// 显示调用T的析构函数清理对象
obj->~T();
// 将_freeList强转为void**,对其解引用即可
// 得到四个字节或八个字节的地址
// 头插
*(void**)obj = _freeList;
_freeList = obj;
}
private:
// 使用char*比较方便,因为其加一就是跳过一个字节
char* _memory = nullptr; // 指向大块内存的指针
size_t _leftBytes = 0; // 大块内存在切分过程中剩余字节数
void* _freeList = nullptr; // 自由链表的头指针,自由链表中存的是返回来的内存
};
struct TreeNode
{
int _val;
TreeNode* _left;
TreeNode* _right;
TreeNode()
:_val(0)
, _left(nullptr)
, _right(nullptr)
{
}
};
void ObjectPoolTest()
{
// 申请释放的轮次
const size_t Rounds = 5;
// 每轮申请释放多少次
const size_t N = 1000000;
std::vector<TreeNode*> v1;
v1.reserve(N);
size_t begin1 = clock();
for (size_t j = 0; j < Rounds; ++j)
{
for (int i = 0; i < N; ++i)
{
v1.push_back(new TreeNode);
}
for (int i = 0; i < N; ++i)
{
delete v1[i];
}
v1.clear();
}
size_t end1 = clock();
std::vector<TreeNode*> v2;
v2.reserve(N);
ObjectPool<TreeNode> Pool;
size_t begin2 = clock();
for (size_t j = 0; j < Rounds; ++j)
{
for (int i = 0; i < N; ++i)
{
v2.push_back(Pool.New());
}
for (int i = 0; i < N; ++i)
{
Pool.Delete(v2[i]);
}
v2.clear();
}
size_t end2 = clock();
cout << "new cost time:" << end1 - begin1 << endl;
cout << "object pool cost time:" << end2 - begin2 << endl;
}
通过上图，我们很明显就能够看到 malloc 和内存池在效率上的差别。
👉空间配置器与容器结合👈
如果你觉得 STL 的空间配置器写的不好，你就可以自己写一个内存池，该内存池需要有 allocate 和 deallocate 接口，再将你写的内存池显式地传给类模板即可。
👉STL总结👈
- 从使用的角度来看，我们只需要关注 STL 的容器，算法和迭代器。
- 而从底层实现的角度来看，我们需要关注 STL 的六大组件（容器、迭代器、算法、仿函数、适配器、空间配置器），理解六大组件的内在联系。六大组件的内在联系如下图：
👉总结👈
本篇博客主要讲解了 STL 的空间配置器、定长内存池与 malloc 的效率对比以及 STL 六大组件内在联系的总结等等。那么以上就是本篇博客的全部内容了，如果大家觉得有收获的话，可以点个三连支持一下！谢谢大家！💖💝❣️
转载：https://blog.csdn.net/m0_63639164/article/details/129136234