前言标准容器vector、list、map都要申请和释放内存。这些内存从哪里来标准库并没有写死而是抽象成一个可替换的组件——分配器allocator。容器只依赖分配器提供申请 N 个元素的空间释放这块空间两个动作具体策略malloc、内存池、共享内存、竞技场 arena全部交给外部决定。这个设计的意义在于把内存策略与数据结构解耦。一个用自由链表free list做小对象缓存的分配器能让std::listint的性能提高数倍而容器代码一行都不用改。本文从分配器的抽象接口讲起讲清allocator_traits为什么存在、rebind解决什么问题再给出一份可直接编译运行的自定义分配器实现。一、为什么需要分配器抽象先看裸new/delete的三个问题每次都向操作系统或通用堆申请。std::listint插入 100 万个节点 100 万次operator new每次都要走堆管理器加锁、查找空闲块开销巨大。内存碎片。大量小对象反复申请释放会把堆切得七零八落最终总空闲够但拿不出连续块。每个对象都带元信息。通用堆为了free时需要知道大小通常在每个块前面放一个 header小对象的额外开销比例极高一个 16 字节的对象可能要额外 16 字节 header。分配器允许我们针对具体场景做优化。经典的 SGI STL 二级分配器思路是大于 128 字节走一级直接malloc小于等于 128 字节走二级按 8 字节对齐切成 16 个自由链表。这就是分配器存在的第一个理由。第二个理由是对象的构造与释放要分开。容器扩容时需要申请原始内存 → 在上面逐个构造元素两步。如果只有new构造和分配就绑死了vector扩容时就没法做到多申请一块把旧元素 move 过去再析构旧的只能每个元素都重新构造一遍。二、分配器的接口演进2.1 从重接口到最小接口早期std::allocator要求提供一整套成员allocate/deallocate/construct/destroy/max_size/rebind。C17 起construct、destroy、max_size被弃用C20 正式删除。原因是这些成员本就可以由std::allocator_traits提供默认实现强制要求反而增加了编写自定义分配器的负担。2.2 C11 之后的最小接口现代分配器只需要四个要素成员作用value_type元素类型allocator_traits据此推导allocate(n)分配n * sizeof(T)字节返回未构造的原始内存deallocate(p, n)释放从allocate得到的空间拷贝构造 /operator判断两个分配器实例能否互相释放内存如果自定义分配器只提供 allocate / deallocatestd::allocator_traits会自动补上construct、destroy、max_size、select_on_container_copy_construction、rebind等一大堆默认行为。这就是allocator_traits的核心价值——向后兼容 减轻实现负担。2.3 allocator_traits 与 rebind为什么容器不直接调用alloc.allocate(n)而要通过std::allocator_traitsAlloc::allocate(alloc, n)为了在不改变分配器定义的前提下给它补上缺失的成员为了统一调用点让标准库可以后续演进例如增加allocate_at_least。rebind解决的问题std::listT的节点类型是ListNodeT不是T。容器拿到的是allocatorT却需要allocatorListNodeT。allocator_traitsAlloc::rebind_allocU就是从Alloc得到元素类型换成U的分配器的标准途径。templateclass Tstruct MyAlloc {using value_type T;T* allocate(std::size_t n);void deallocate(T* p, std::size_t n);// 现代写法提供模板化拷贝构造rebind 由 traits 自动完成templateclass U MyAlloc(const MyAllocU) noexcept {}};// allocator_traitsMyAllocint::rebind_allocdouble MyAllocdouble注意那个templateclass U MyAlloc(const MyAllocU)转换构造函数——它是让rebind_alloc能工作的关键少了它容器会在编译期报无法从 MyAllocint 转换到 MyAllocNode。三、有状态分配器与传播策略分配器可以携带状态比如指向同一个内存池的指针。要让它工作所有rebind出来的版本都必须能访问到同一份状态templateclass Tclass PoolAlloc {public:using value_type T;explicit PoolAlloc(Pool* pool) noexcept : pool_(pool) {}templateclass UPoolAlloc(const PoolAllocU other) noexcept : pool_(other.pool()) {} // 传递状态T* allocate(std::size_t n);void deallocate(T* p, std::size_t n) noexcept;Pool* pool() const noexcept { return pool_; }private:Pool* pool_;};templateclass T, class Ubool operator(const PoolAllocT a, const PoolAllocU b) noexcept {return a.pool() b.pool(); // 能互相释放的前提同一个池}为什么必须重载因为std::vector在 move 赋值时如果两个容器的分配器不相等就不能把内存块直接偷过来必须逐元素搬移。分配器相等是可以偷内存的必要条件。几个传播 traits决定容器拷贝/移动/交换时分配器怎么处理traits含义propagate_on_container_copy_assignment拷贝赋值时用源分配器替换自己的propagate_on_container_move_assignmentmove 赋值时是否可替换true才能偷内存is_always_equal所有实例都相等 → 容器可以省掉存储分配器的空间空基类优化std::allocator的is_always_equal为true因此std::vectorint默认不额外存储分配器对象sizeof(std::vectorint)仍是 3 个指针。四、代码实战实战 1最小的可用分配器// minimal_alloc.cpp — g -stdc17 minimal_alloc.cpp -o minimal_alloc#include cstddef#include iostream#include memory#include new#include vectortemplateclass Tstruct LoggingAlloc {using value_type T;LoggingAlloc() noexcept default;templateclass U LoggingAlloc(const LoggingAllocU) noexcept {} // rebind 必需T* allocate(std::size_t n) {std::cout allocate n * sizeof(T) bytes\n;return static_castT*(::operator new(n * sizeof(T))); // 只分配不构造}void deallocate(T* p, std::size_t n) noexcept {std::cout deallocate n * sizeof(T) bytes\n;::operator delete(p); // 只释放不析构}};templateclass T, class Ubool operator(const LoggingAllocT, const LoggingAllocU) noexcept { return true; }int main() {std::vectorint, LoggingAllocint v;for (int i 0; i 10; i) v.push_back(i);std::cout size v.size() cap v.capacity() \n;return 0;}运行输出能直观看到vector的倍增扩容过程容量按 1、2、4、8、16 增长每次扩容都伴随一次allocate加一次deallocate。这也顺便解释了为什么vector要reserve。实战 2一个定长块自由链表分配器freelist allocator这是 SGI STL 二级分配器的核心思想写一个简化版本// freelist_alloc.cpp — g -stdc17 freelist_alloc.cpp -o freelist_alloc#include cstddef#include iostream#include list#include vector// 每个空闲块**复用自身的存储**保存 next 指针 —— 零额外开销// 这是自由链表分配器的精髓不为链表节点额外分配内存struct FreeNode {FreeNode* next;};templatestd::size_t BlockSize, std::size_t ChunkCount 64class FixedPool {public:FixedPool() default;FixedPool(const FixedPool) delete;FixedPool operator(const FixedPool) delete;~FixedPool() {// 只释放 chunk 链表块本身跟着 chunk 一起释放while (chunks_) {void* p chunks_;chunks_ *static_castvoid**(chunks_);::operator delete(p);}}void* allocate() {if (!free_) refill();FreeNode* node free_;free_ node-next; // 摘下头节点 —— O(1)return node;}void deallocate(void* p) noexcept {auto* node static_castFreeNode*(p);node-next free_; // 头插归还 —— O(1)free_ node;}// 槽位大小必须 指针大小否则存不下 next// 并且向上取整到 max_align_t 的倍数保证每一块都满足最大对齐static constexpr std::size_t slotSize() {constexpr std::size_t base BlockSize sizeof(FreeNode) ? sizeof(FreeNode) : BlockSize;constexpr std::size_t align alignof(std::max_align_t);return (base align - 1) / align * align;}private:void refill() {// 一次向系统申请一大块切成 ChunkCount 个块挂到自由链表上const std::size_t slot slotSize();char* raw static_castchar*(::operator new(slot * ChunkCount));// 用第一块的空间保存 chunk 链表指针*reinterpret_castvoid**(raw) chunks_;chunks_ raw;for (std::size_t i 1; i ChunkCount; i) {auto* node reinterpret_castFreeNode*(raw i * slot);node-next free_;free_ node;}}FreeNode* free_ nullptr;void* chunks_ nullptr;};// 把 pool 引用注入到分配器里templateclass T, class PoolTclass PoolAlloc {public:using value_type T;explicit PoolAlloc(PoolT* pool) noexcept : pool_(pool) {}templateclass UPoolAlloc(const PoolAllocU, PoolT other) noexcept : pool_(other.pool()) {}T* allocate(std::size_t n) {if (n ! 1) {// 池只服务于单元素分配list/map 节点批量走通用堆return static_castT*(::operator new(n * sizeof(T)));}return static_castT*(pool_-allocate());}void deallocate(T* p, std::size_t n) noexcept {if (n ! 1) { ::operator delete(p); return; }pool_-deallocate(p);}PoolT* pool() const noexcept { return pool_; }private:PoolT* pool_;};templateclass T, class U, class Pbool operator(const PoolAllocT, P a, const PoolAllocU, P b) noexcept {return a.pool() b.pool();}templateclass T, class U, class Pbool operator!(const PoolAllocT, P a, const PoolAllocU, P b) noexcept {return !(a b);}int main() {// list 节点的真实大小由实现决定这里取一个上界即可using NodePool FixedPoolsizeof(void*) * 4;NodePool pool;{using Alloc PoolAllocint, NodePool;std::listint, Alloc lst{Alloc(pool)};for (int i 0; i 5; i) lst.push_back(i);std::cout list size lst.size() \n;} // list 析构节点全部归还到 pool但 pool 不向系统释放return 0;}这个分配器的意义在于100 万次push_back只向系统申请1000000 / 64 ≈ 15625次大块把堆操作次数降低两个数量级而且因为块大小固定几乎不产生碎片。实战 3C17 的 pmr —— 标准库自带的多态分配器如果不方便给每个容器写分配器类型参数可以用std::pmrpolymorphic memory resourcealignas(std::max_align_t) unsigned char buffer[4096]; // 栈上缓冲区std::pmr::monotonic_buffer_resource pool{buffer, sizeof(buffer)};std::pmr::vectorint v{pool}; // 只传运行期指针for (int i 0; i 100; i) v.push_back(i); // 完全不碰全局堆// pool 析构时整块回收无需逐次 freepmr把分配器从类型的一部分变成运行期对象所有pmr容器共享同一个类型运行时通过memory_resource指针分派。代价是每个容器多存一个指针且分派走虚函数。常见坑点坑点 1allocate 之后立刻构造对象templateclass TT* allocate(std::size_t n) {T* p static_castT*(::operator new(n * sizeof(T)));for (std::size_t i 0; i n; i) new (p[i]) T(); // ❌ 分配器不该构造return p;}分配器只负责原始内存构造是容器或construct_at的事。在分配器里构造会让reserve被迫构造全部元素语义就错了deallocate时容器还会先析构再交给分配器造成双重析构。✅ 正确写法只分配不构造。T* allocate(std::size_t n) { return static_castT*(::operator new(n * sizeof(T))); }void deallocate(T* p, std::size_t) noexcept { ::operator delete(p); }坑点 2分配器生命周期短于容器std::vectorint, PoolAllocint, PoolT makeVec() {PoolT pool; // ❌ 局部对象std::vectorint, PoolAllocint, PoolT v{PoolAllocint, PoolT(pool)};return v; // 返回后 pool 已析构v 持有悬空指针}✅ 正确写法分配器持有的池必须活得比容器久静态存储期或由调用方持有。坑点 3allocate 的 n 与 deallocate 的 n 不一致标准要求deallocate(p, n)的n与allocate(n)相同。有状态池分配器如果按n走不同代码路径如实战 2 里n ! 1的分支一旦不匹配就会拿operator delete去释放池里的块或者反过来——立刻崩溃。最后提醒一句std::allocator直接使用::operator new现代 glibc / jemalloc / tcmalloc 对小对象已有很好的缓存。除非 profile 显示分配确实是瓶颈否则不要盲目替换。先测量再优化。总结概念要点最小接口value_typeallocatedeallocate 转换构造 operatorallocator_traits补齐默认实现让自定义分配器只需写两个函数rebind容器需要把allocatorT变成allocatorNodeT有状态分配器必须重载operator且生命周期要够长传播 traits决定容器拷贝/移动时能否偷内存pmr类型无关的多态分配器代价是多一个指针分配器的价值不在能编译而在把内存策略变成可插拔的一等公民。理解了容器只认 allocate/deallocate 与 construct/destroy你就理解了标准库几乎所有容器的内存行为。 
长河君 · 2026/10/15 4:11:47 · 阅读 1.2k C++中分配器allocator的实现
前言标准容器vector、list、map都要申请和释放内存。这些内存从哪里来标准库并没有写死而是抽象成一个可替换的组件——分配器allocator。容器只依赖分配器提供申请 N 个元素的空间释放这块空间两个动作具体策略malloc、内存池、共享内存、竞技场 arena全部交给外部决定。这个设计的意义在于把内存策略与数据结构解耦。一个用自由链表free list做小对象缓存的分配器能让std::listint的性能提高数倍而容器代码一行都不用改。本文从分配器的抽象接口讲起讲清allocator_traits为什么存在、rebind解决什么问题再给出一份可直接编译运行的自定义分配器实现。一、为什么需要分配器抽象先看裸new/delete的三个问题每次都向操作系统或通用堆申请。std::listint插入 100 万个节点 100 万次operator new每次都要走堆管理器加锁、查找空闲块开销巨大。内存碎片。大量小对象反复申请释放会把堆切得七零八落最终总空闲够但拿不出连续块。每个对象都带元信息。通用堆为了free时需要知道大小通常在每个块前面放一个 header小对象的额外开销比例极高一个 16 字节的对象可能要额外 16 字节 header。分配器允许我们针对具体场景做优化。经典的 SGI STL 二级分配器思路是大于 128 字节走一级直接malloc小于等于 128 字节走二级按 8 字节对齐切成 16 个自由链表。这就是分配器存在的第一个理由。第二个理由是对象的构造与释放要分开。容器扩容时需要申请原始内存 → 在上面逐个构造元素两步。如果只有new构造和分配就绑死了vector扩容时就没法做到多申请一块把旧元素 move 过去再析构旧的只能每个元素都重新构造一遍。二、分配器的接口演进2.1 从重接口到最小接口早期std::allocator要求提供一整套成员allocate/deallocate/construct/destroy/max_size/rebind。C17 起construct、destroy、max_size被弃用C20 正式删除。原因是这些成员本就可以由std::allocator_traits提供默认实现强制要求反而增加了编写自定义分配器的负担。2.2 C11 之后的最小接口现代分配器只需要四个要素成员作用value_type元素类型allocator_traits据此推导allocate(n)分配n * sizeof(T)字节返回未构造的原始内存deallocate(p, n)释放从allocate得到的空间拷贝构造 /operator判断两个分配器实例能否互相释放内存如果自定义分配器只提供 allocate / deallocatestd::allocator_traits会自动补上construct、destroy、max_size、select_on_container_copy_construction、rebind等一大堆默认行为。这就是allocator_traits的核心价值——向后兼容 减轻实现负担。2.3 allocator_traits 与 rebind为什么容器不直接调用alloc.allocate(n)而要通过std::allocator_traitsAlloc::allocate(alloc, n)为了在不改变分配器定义的前提下给它补上缺失的成员为了统一调用点让标准库可以后续演进例如增加allocate_at_least。rebind解决的问题std::listT的节点类型是ListNodeT不是T。容器拿到的是allocatorT却需要allocatorListNodeT。allocator_traitsAlloc::rebind_allocU就是从Alloc得到元素类型换成U的分配器的标准途径。templateclass Tstruct MyAlloc {using value_type T;T* allocate(std::size_t n);void deallocate(T* p, std::size_t n);// 现代写法提供模板化拷贝构造rebind 由 traits 自动完成templateclass U MyAlloc(const MyAllocU) noexcept {}};// allocator_traitsMyAllocint::rebind_allocdouble MyAllocdouble注意那个templateclass U MyAlloc(const MyAllocU)转换构造函数——它是让rebind_alloc能工作的关键少了它容器会在编译期报无法从 MyAllocint 转换到 MyAllocNode。三、有状态分配器与传播策略分配器可以携带状态比如指向同一个内存池的指针。要让它工作所有rebind出来的版本都必须能访问到同一份状态templateclass Tclass PoolAlloc {public:using value_type T;explicit PoolAlloc(Pool* pool) noexcept : pool_(pool) {}templateclass UPoolAlloc(const PoolAllocU other) noexcept : pool_(other.pool()) {} // 传递状态T* allocate(std::size_t n);void deallocate(T* p, std::size_t n) noexcept;Pool* pool() const noexcept { return pool_; }private:Pool* pool_;};templateclass T, class Ubool operator(const PoolAllocT a, const PoolAllocU b) noexcept {return a.pool() b.pool(); // 能互相释放的前提同一个池}为什么必须重载因为std::vector在 move 赋值时如果两个容器的分配器不相等就不能把内存块直接偷过来必须逐元素搬移。分配器相等是可以偷内存的必要条件。几个传播 traits决定容器拷贝/移动/交换时分配器怎么处理traits含义propagate_on_container_copy_assignment拷贝赋值时用源分配器替换自己的propagate_on_container_move_assignmentmove 赋值时是否可替换true才能偷内存is_always_equal所有实例都相等 → 容器可以省掉存储分配器的空间空基类优化std::allocator的is_always_equal为true因此std::vectorint默认不额外存储分配器对象sizeof(std::vectorint)仍是 3 个指针。四、代码实战实战 1最小的可用分配器// minimal_alloc.cpp — g -stdc17 minimal_alloc.cpp -o minimal_alloc#include cstddef#include iostream#include memory#include new#include vectortemplateclass Tstruct LoggingAlloc {using value_type T;LoggingAlloc() noexcept default;templateclass U LoggingAlloc(const LoggingAllocU) noexcept {} // rebind 必需T* allocate(std::size_t n) {std::cout allocate n * sizeof(T) bytes\n;return static_castT*(::operator new(n * sizeof(T))); // 只分配不构造}void deallocate(T* p, std::size_t n) noexcept {std::cout deallocate n * sizeof(T) bytes\n;::operator delete(p); // 只释放不析构}};templateclass T, class Ubool operator(const LoggingAllocT, const LoggingAllocU) noexcept { return true; }int main() {std::vectorint, LoggingAllocint v;for (int i 0; i 10; i) v.push_back(i);std::cout size v.size() cap v.capacity() \n;return 0;}运行输出能直观看到vector的倍增扩容过程容量按 1、2、4、8、16 增长每次扩容都伴随一次allocate加一次deallocate。这也顺便解释了为什么vector要reserve。实战 2一个定长块自由链表分配器freelist allocator这是 SGI STL 二级分配器的核心思想写一个简化版本// freelist_alloc.cpp — g -stdc17 freelist_alloc.cpp -o freelist_alloc#include cstddef#include iostream#include list#include vector// 每个空闲块**复用自身的存储**保存 next 指针 —— 零额外开销// 这是自由链表分配器的精髓不为链表节点额外分配内存struct FreeNode {FreeNode* next;};templatestd::size_t BlockSize, std::size_t ChunkCount 64class FixedPool {public:FixedPool() default;FixedPool(const FixedPool) delete;FixedPool operator(const FixedPool) delete;~FixedPool() {// 只释放 chunk 链表块本身跟着 chunk 一起释放while (chunks_) {void* p chunks_;chunks_ *static_castvoid**(chunks_);::operator delete(p);}}void* allocate() {if (!free_) refill();FreeNode* node free_;free_ node-next; // 摘下头节点 —— O(1)return node;}void deallocate(void* p) noexcept {auto* node static_castFreeNode*(p);node-next free_; // 头插归还 —— O(1)free_ node;}// 槽位大小必须 指针大小否则存不下 next// 并且向上取整到 max_align_t 的倍数保证每一块都满足最大对齐static constexpr std::size_t slotSize() {constexpr std::size_t base BlockSize sizeof(FreeNode) ? sizeof(FreeNode) : BlockSize;constexpr std::size_t align alignof(std::max_align_t);return (base align - 1) / align * align;}private:void refill() {// 一次向系统申请一大块切成 ChunkCount 个块挂到自由链表上const std::size_t slot slotSize();char* raw static_castchar*(::operator new(slot * ChunkCount));// 用第一块的空间保存 chunk 链表指针*reinterpret_castvoid**(raw) chunks_;chunks_ raw;for (std::size_t i 1; i ChunkCount; i) {auto* node reinterpret_castFreeNode*(raw i * slot);node-next free_;free_ node;}}FreeNode* free_ nullptr;void* chunks_ nullptr;};// 把 pool 引用注入到分配器里templateclass T, class PoolTclass PoolAlloc {public:using value_type T;explicit PoolAlloc(PoolT* pool) noexcept : pool_(pool) {}templateclass UPoolAlloc(const PoolAllocU, PoolT other) noexcept : pool_(other.pool()) {}T* allocate(std::size_t n) {if (n ! 1) {// 池只服务于单元素分配list/map 节点批量走通用堆return static_castT*(::operator new(n * sizeof(T)));}return static_castT*(pool_-allocate());}void deallocate(T* p, std::size_t n) noexcept {if (n ! 1) { ::operator delete(p); return; }pool_-deallocate(p);}PoolT* pool() const noexcept { return pool_; }private:PoolT* pool_;};templateclass T, class U, class Pbool operator(const PoolAllocT, P a, const PoolAllocU, P b) noexcept {return a.pool() b.pool();}templateclass T, class U, class Pbool operator!(const PoolAllocT, P a, const PoolAllocU, P b) noexcept {return !(a b);}int main() {// list 节点的真实大小由实现决定这里取一个上界即可using NodePool FixedPoolsizeof(void*) * 4;NodePool pool;{using Alloc PoolAllocint, NodePool;std::listint, Alloc lst{Alloc(pool)};for (int i 0; i 5; i) lst.push_back(i);std::cout list size lst.size() \n;} // list 析构节点全部归还到 pool但 pool 不向系统释放return 0;}这个分配器的意义在于100 万次push_back只向系统申请1000000 / 64 ≈ 15625次大块把堆操作次数降低两个数量级而且因为块大小固定几乎不产生碎片。实战 3C17 的 pmr —— 标准库自带的多态分配器如果不方便给每个容器写分配器类型参数可以用std::pmrpolymorphic memory resourcealignas(std::max_align_t) unsigned char buffer[4096]; // 栈上缓冲区std::pmr::monotonic_buffer_resource pool{buffer, sizeof(buffer)};std::pmr::vectorint v{pool}; // 只传运行期指针for (int i 0; i 100; i) v.push_back(i); // 完全不碰全局堆// pool 析构时整块回收无需逐次 freepmr把分配器从类型的一部分变成运行期对象所有pmr容器共享同一个类型运行时通过memory_resource指针分派。代价是每个容器多存一个指针且分派走虚函数。常见坑点坑点 1allocate 之后立刻构造对象templateclass TT* allocate(std::size_t n) {T* p static_castT*(::operator new(n * sizeof(T)));for (std::size_t i 0; i n; i) new (p[i]) T(); // ❌ 分配器不该构造return p;}分配器只负责原始内存构造是容器或construct_at的事。在分配器里构造会让reserve被迫构造全部元素语义就错了deallocate时容器还会先析构再交给分配器造成双重析构。✅ 正确写法只分配不构造。T* allocate(std::size_t n) { return static_castT*(::operator new(n * sizeof(T))); }void deallocate(T* p, std::size_t) noexcept { ::operator delete(p); }坑点 2分配器生命周期短于容器std::vectorint, PoolAllocint, PoolT makeVec() {PoolT pool; // ❌ 局部对象std::vectorint, PoolAllocint, PoolT v{PoolAllocint, PoolT(pool)};return v; // 返回后 pool 已析构v 持有悬空指针}✅ 正确写法分配器持有的池必须活得比容器久静态存储期或由调用方持有。坑点 3allocate 的 n 与 deallocate 的 n 不一致标准要求deallocate(p, n)的n与allocate(n)相同。有状态池分配器如果按n走不同代码路径如实战 2 里n ! 1的分支一旦不匹配就会拿operator delete去释放池里的块或者反过来——立刻崩溃。最后提醒一句std::allocator直接使用::operator new现代 glibc / jemalloc / tcmalloc 对小对象已有很好的缓存。除非 profile 显示分配确实是瓶颈否则不要盲目替换。先测量再优化。总结概念要点最小接口value_typeallocatedeallocate 转换构造 operatorallocator_traits补齐默认实现让自定义分配器只需写两个函数rebind容器需要把allocatorT变成allocatorNodeT有状态分配器必须重载operator且生命周期要够长传播 traits决定容器拷贝/移动时能否偷内存pmr类型无关的多态分配器代价是多一个指针分配器的价值不在能编译而在把内存策略变成可插拔的一等公民。理解了容器只认 allocate/deallocate 与 construct/destroy你就理解了标准库几乎所有容器的内存行为。