内存池简述
在C++的STL的容器中的容器如vector、deque等用的默认分配器(allocator)都是从直接从系统的堆中申请内存，用一点申请一点，效率极低。这就是设计内存池的意义，所谓内存池，就是一次性向系统申请一大片内存（预分配内存），后续谁要用内存，就从这个内存池中获取一部分内存(Slot空间槽)，回收也是换回内存池中，这样就不用频繁地直接和系统交互，提高效率；
数据结构
整体结构
+-----------------------------------------------------------------+
| Header | Body |
+-------------------+-------------------+-----+-------------------+
| 链表指针(next) | 填充(padding) | Slot1 | Slot2 | ... | SlotN |
+-------------------+-------------------+-----+-------------------+
^ ^ ^
| | |
blockHeader bodyStart currentSlot_被释放的Slot通过freeSlot来管理:
freeSlot的结构
Slot3<-Slot2<-Slot1^|
freeSlot
描述：
- 一个Block分为Header部分和Body部分，Header部分存着指向下一个Block的地址，Body部分存着许多Slot；
- Slot之间是没有直接关系的，当有数据（不空）的时候，Slot存的就是数据，当Slot被释放之后交给freeSlot来管理，此时释放后的Slot存的是指向下一个释放后的Slot的地址；
Slot的数据结构，初始的时候存数据，被释放之后存下一个Slot的地址：
Slot的结构
union Slot_{value_type element; // 存储数据时使用Slot_ *next; // 空闲时作为链表指针};
代码解读
main.cpp
#include <iostream>
#include <stack>
#include <vector>
#include <chrono> //高精度计时库
#include "MemoryPool.h"using namespace std;// using是C++的重命名，类似与C的typedef，using更安全
// MemoryPool是分配器，分配器放到vector顺序容器中
// template <typename T>
// using PoolStackContainer = vector<T, MemoryPool<T>>;// 再把PoolStackContainer作为stack的底层容器
// template <typename T>
// using PoolStack = stack<T, PoolStackContainer<T>>;// 上面的合起来写
template <typename T>
using Stack = std::stack<T, vector<T>>; //为了单一变量，Stack和PoolStack的底层容器都设置成vector(std::stack默认的底层容器是deque)
template <typename T>
using PoolStack = std::stack<T, std::vector<T, MemoryPool<T>>>;
//using PoolStack = std::stack<T, std::deque<T, MemoryPool<T>>>;int main(){// 测试内存池分配/释放MemoryPool<int> pool;//新建一个内存池int *p1 = pool.allocate(); //这里一个p就是一个slotpool.construct(p1, 42); // 构造对象std::cout << "*p1 = " << *p1 << std::endl;pool.destroy(p1); // 销毁对象pool.deallocate(p1); // 释放内存// 性能对比：内存池 vs std::allocatorconst int N = 1000000;auto start_time1 = std::chrono::high_resolution_clock::now();//stdStack<int> std_stack;Stack<int> std_stack;for (int i = 0; i < N; ++i)std_stack.push(i); // 使用std::allocatorauto end_time1 = std::chrono::high_resolution_clock::now(); //高精度计时std::chrono::duration<double> time1 = end_time1 - start_time1;auto start_time2 = std::chrono::high_resolution_clock::now();PoolStack<int> pool_stack;for (int i = 0; i < N; ++i)pool_stack.push(i);auto end_time2 = std::chrono::high_resolution_clock::now();std::chrono::duration<double> time2 = end_time2 - start_time2;std::cout << "Test finished." << std::endl;std::cout << "栈用时: " << time1.count() << std::endl;std::cout << "内存池栈用时: " << time2.count() << std::endl;for (int i = 0; i < 1000;i++){//这个代码输出第1000个数字，判断二者的里面的值是否相同，进而判断是否成功插入std_stack.pop();pool_stack.pop();}cout << std_stack.top() << endl;cout << pool_stack.top() << endl;return 0;
}
MemoryPool.h
#ifndef MEMORY_POOL_H
#define MEMORY_POOL_H#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <utility>
//ifndef MEMORY_POOL_H 文件是否被包含的唯一标识，避免该被重复引入template <typename T, size_t BlockSize = 4096>
class MemoryPool{
public://这里的MemoryPool是个分配器，因此要满足STL接口的命名规范，如value_type,pointer,const_pointer...typedef T value_type;typedef T* pointer;typedef const T* const_pointer;typedef T& reference;typedef size_t size_type;typedef ptrdiff_t difference_type;// rebind模板，支持不同类型的allocatortemplate <typename U>struct rebind{using other = MemoryPool<U, BlockSize>;};public:MemoryPool() noexcept; //noexcept，发生错误直接中断，不抛出异常~MemoryPool() noexcept;//分配内存，返回内存地址pointerpointer allocate(size_type n = 1, const_pointer hint = nullptr);void deallocate(pointer p, size_type n = 1);template <typename U, typename... Args>//构造函数，第一个参数放allocate分配的内存地址，二个参数放要存在这个内存中的东西void construct(U *p, Args &&...args);//Args &&...args是函数参数包template <typename U>//销毁函数，传入要释放的内存地址void destroy(U *p);size_type max_size() const noexcept;//计算总共有多少个Slotprivate:// 联合体，被占用的时候存的是数据，被释放之后存的是下一个Slot的地址，被释放之前每个Slot的地址是顺序存放的，因此之间没有也不用next指针联系，被释放之后统一将被释放的Slot给freeSlot来管理，这个时候存的就是指针，后续还要从内存池中获取内存的时候优先分配被释放的Slot；union Slot_{//因为数据和指针在这里不需要同时存在，用union可以节省空间value_type element; // 存储数据时使用Slot_ *next; // 空闲时作为链表指针};//STL的语言风格，成员变量后面都会加一个下划线typedef char* data_pointer_; // 原始内存指针（用于计算偏移）typedef Slot_* slot_pointer_; // Slot指针//这里解释一下两个指针之间的区别，data_pointer_是char*类型的，如果data_pointer_++就是加一个字节，而slot_pointer_是Slot_*类型的，slot_pointer_++就是加sizeof(Slot*)个字节，用前者就是为了在内存对齐（填充内存）的时候方便计算处理到底要填充多少个字节；// 关键指针（管理内存块和空闲槽）slot_pointer_ currentBlock_; // Block链表头指针slot_pointer_ currentSlot_; // 当前Block的第一个可用Slotslot_pointer_ lastSlot_; // 当前Block的最后一个可用Slotslot_pointer_ freeSlots_; // 空闲Slot链表头指针size_type padPointer(data_pointer_ p, size_type align) const noexcept;//计算要填充多少个字节void allocateBlock(); // 申请新的Block内存块static_assert(BlockSize >= 2 * sizeof(Slot_), "BlockSize too small!");//C++11引入的编译时断言机制，当第一个参数（语句）为假，会输出第二个参数，并且编译中断，如果用if的话要等到运行时才判断，编译时断言机制可以在编译的时候就中断，提高效率；
};// 包含实现文件，模板类的特殊处理
#include "MemoryPool.tcc"#endif // MEMORY_POOL_Htcc文件是模板实现文件
MemoryPool.tcc
// 构造和析构
template <typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::MemoryPool() noexcept//这里实现MemoryPool类中的MemoryPoll()构造函数，地址初始化为空: currentBlock_(nullptr), currentSlot_(nullptr), lastSlot_(nullptr), freeSlots_(nullptr) {
} // 参数列表// 析构函数，释放的是整个Block的内存
template <typename T, size_t BlockSize>
MemoryPool<T, BlockSize>::~MemoryPool() noexcept{slot_pointer_ curr = currentBlock_; // 这里的currentBlock_是MemoryPool类中的成员变量，因为已经进入到类的作用域内while (curr != nullptr){slot_pointer_ next = curr->next; // Block的next指针存储的是前一个Block的地址operator delete(reinterpret_cast<void *>(curr)); // 释放Block内存，此时的curr是悬空指针，operator delete区别于delete是operator delete释放的是operator new分配的内存，delete释放内存+自动调用析构函数，operator delete只释放内存，不调用析构函数；operator delete要求接受一个void*类型的地址，因此用reinterpret_cast对curr类型转换；curr = next;}
}// 内存池对齐计算(padPointer)
template <typename T, size_t BlockSize>
typename MemoryPool<T, BlockSize>::size_type // 返回类型是MemoryPool中的size_type，typename用于明确告诉编译器，一个依赖于模板参数的名称是一个类型，MemoryPool<T, BlockSize> 是一个模板类，其成员 size_type的定义依赖于模板参数T和BlockSize。在模板被实例化前，编译器无法确定size_type是一个类型（如using size_type = size_t）还是一个静态成员变量（如static size_t size_type）。
MemoryPool<T, BlockSize>::padPointer(data_pointer_ p, size_type align) const noexcept{// uintptr_t addr = reinterpret_cast<uintptr_t>(p);// return (addr - align) % align;uintptr_t addr = reinterpret_cast<uintptr_t>(p); // unitptr_t是一个存储无符号地址（整数）的类型，方便地址计算（更安全）size_type remainder = addr % align;return remainder == 0 ? 0 : (align - remainder); // 这里的align是对齐目标，也就是说如果align=4,那么要求地址是4的整数倍，比如addr=13,align=4,那么(align - addr) % align = （4-13）% 4 = 1， 那么addr只需要补上（align-1）=3，即addr=13+3=16就是4的整数倍;
}// 申请新Block，当前Block已经没有Slot可以分配的时候就申请新的Block(allocateBlock)
template <typename T, size_t BlockSize>
void MemoryPool<T, BlockSize>::allocateBlock(){// 先用data_pointer_再转换成slot_pointer_，虽然可以直接写成分配slot_pointer_，但是这样写语义更明确：先初始化内存块，再结构化槽位data_pointer_ newBlock = reinterpret_cast<data_pointer_>(operator new(BlockSize));// operator new只分配内存，不构造对象，区别于new，new即分配内存也构造对象；operator new分配一个大小为BlockSize的内存// 将新的Block加入链表（头插）slot_pointer_ blockHeader = reinterpret_cast<slot_pointer_>(newBlock);blockHeader->next = currentBlock_;currentBlock_ = blockHeader;// 计算Block主体部分的起始地址（跳过链表指针占用的Slot）data_pointer_ bodyStart = newBlock + sizeof(slot_pointer_); // newBlock是新的Block的起始地址，Header部分存的就是指向下一个Block的地址，即slot_pointer_，因此newBlock+sizeof(slot_pointer_) 偏移到Body的起始地址size_type align = alignof(slot_pointer_);// alignof获取slot_pointer_的对齐要求，返回的是slot_pointer_及Slot_* 指针本身的对齐值，32位系统是4,64位系统是8size_type padding = padPointer(bodyStart, align); // 计算填充量// 确定可用Slot的范围，currentSlot是内存对齐后可以真正存储数据的slot的起始地址currentSlot_ = reinterpret_cast<slot_pointer_>(bodyStart + padding);data_pointer_ blockEnd = newBlock + BlockSize;lastSlot_ = reinterpret_cast<slot_pointer_>(blockEnd - sizeof(Slot_)); // 计算最后一个Slot的起始地址
}//内存分配
template <typename T, size_t BlockSize>
typename MemoryPool<T, BlockSize>::pointer // 返回类型是pointer
MemoryPool<T, BlockSize>::allocate(size_type n, const_pointer hint){// 处理连续分配请求if (n > 1){// 特殊处理连续内存请求（此处简化实现，实际需考虑内存对齐）data_pointer_ newMem = reinterpret_cast<data_pointer_>(operator new(n * sizeof(Slot_)));return reinterpret_cast<pointer>(newMem);}// 单对象分配逻辑，优先从空闲链表获取Slotif (freeSlots_ != nullptr){pointer result = reinterpret_cast<pointer>(freeSlots_);freeSlots_ = freeSlots_->next;return result; // 如果分配的是int*类型，那么此时result就是int*类型的地址}if (currentSlot_ >= lastSlot_){ // 如果当前Block无空闲Slot，检查是否需要申请新BlockallocateBlock();}return reinterpret_cast<pointer>(currentSlot_++); // 顺序加就是下个Slot的位置，这里的++就是+sizeof(currentSlot_)
}// 内存释放
template <typename T, size_t BlockSize>
void MemoryPool<T, BlockSize>::deallocate(pointer p, size_type n){if (n > 1){operator delete(p); // 直接释放整块内存return;}if (p != nullptr){slot_pointer_ slot = reinterpret_cast<slot_pointer_>(p);// 将释放的Slot加入空闲链表（头插）slot->next = freeSlots_;freeSlots_ = slot;}
}// 对象构建与销毁
template <typename T, size_t BlockSize>
template <typename U, typename... Args>
void MemoryPool<T, BlockSize>::construct(U *p, Args &&...args){// 使用placement new语法在已分配的内存上构造对象；// placement new语法格式: new (addressx) Type(arguments...)，address是已分配了内存的地址，Type是对象类型，arguments是构造函数的参数new (p) U(std::forward<Args>(args)...); // 完美转发参数，`std::forward<Args>(args)...`固定写法
}template <typename T, size_t BlockSize>
template <typename U>
void MemoryPool<T, BlockSize>::destroy(U *p){p->~U(); // 显式调用析构函数
}// 计算最大可用Slot数
template <typename T, size_t BlockSize>
typename MemoryPool<T, BlockSize>::size_type
MemoryPool<T, BlockSize>::max_size() const noexcept{// 无符号整数运算：-1转换为size_type即是最大值，计算机以补码的形式存储数据，-1的补码转换成无符号是最大的size_type maxBlocks = static_cast<size_type>(-1) / BlockSize;// 单个Block可用Slot数 = (BlockSize - 链表指针占用) / Slot大小size_type slotsPerBlock = (BlockSize - sizeof(slot_pointer_)) / sizeof(Slot_);return slotsPerBlock * maxBlocks; // 总可用Slot数
}运行结果：
*p1 = 42
Test finished.
栈用时: 0.0114187
内存池栈用时: 0.0306049
998999
998999
补充
为什么要加个U?
为了拓展性，U可能是T的子类；
class Animal {}; // T=Animal
class Cat : public Animal {}; // U=CatMemoryPool<Animal> pool;
Animal* p = pool.allocate();//比如这里分配的Animal的内存，可以放入Cat
pool.construct<Cat>(p); // 在Animal的内存上构造Cat（多态）
| 容器名 | 作用 | 第二个模板参数是？ |
|---|---|---|
stack | 容器适配器 | 底层容器（如 deque<T>） |
queue | 容器适配器 | 底层容器 |
priority_queue | 容器适配器 | 底层容器 |
vector | 顺序容器 | 分配器（如 allocator<T>） |
deque | 顺序容器 | 分配器 |
list | 顺序容器 | 分配器 |
| 操作 | 作用 | 是否调用析构函数 | 适用场景 |
|---|---|---|---|
operator delete(p) | 仅释放内存 | ❌ 不调用 | 底层内存管理（如内存池） |
delete p | 释放内存 + 调用析构函数 | ✅ 调用 | 普通对象释放 |
delete[] p | 释放数组内存 + 调用每个元素的析构函数 | ✅ 调用 | 对象数组释放 |
