C++自定義簡單的內存池

內存池簡述

在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_H

tcc文件是模板實現文件
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`	釋放數組內存 + 調用每個元素的析構函數	? 調用	對象數組釋放