Chapter 7: Allocator System
核心问题与阅读主线
Allocator 将容器的结构不变量、元素生命周期与“内存从何取得、如何批量分配与归还”的策略解耦。无论底层是连续数组(std::vector<T>)还是节点网络(std::list<T>、std::map<K, V>),容器都通过同一套 allocator 协议管理原始存储与异常安全回滚。
全章共用场景样本
全章的贯穿场景是“带状态 allocator 的 std::vector<Trace> 扩容”:先申请未初始化原始存储,再逐个构造元素;扩容时迁移旧元素,若途中构造失败则销毁已构造的新前缀并归还新存储,提交成功后才销毁旧元素并释放旧存储。
本文聚焦 C++ 标准语义与常见实现模式(libstdc++、libc++、MSVC STL 另有各自内部类型与优化分支)。标准接口参考:std::allocator_traits、uninitialized memory algorithms、std::pmr::polymorphic_allocator。
7.1 allocator 作为容器内存策略
Allocator 是容器模板参数中的内存策略对象。以 std::vector<T, Alloc> 为例,Alloc 只介入原始存储的取得、归还与对象构造;容器本身仍负责 size、capacity、迭代器边界、元素顺序和异常安全提交点。
下面用只计数、仍走全局 operator new/operator delete 的 CountingAllocator 观察 std::vector<Trace> 的扩容分配:
#include <cstddef>
#include <limits>
#include <memory>
#include <new>
#include <vector>
struct Trace {
int value{};
explicit Trace(int v) : value(v) {}
Trace(const Trace&) = default;
Trace(Trace&&) noexcept = default;
Trace& operator=(const Trace&) = default;
Trace& operator=(Trace&&) noexcept = default;
};
template<class T>
struct CountingAllocator {
using value_type = T;
int* allocation_count{};
CountingAllocator() noexcept = default;
explicit CountingAllocator(int& counter) noexcept : allocation_count(&counter) {}
template<class U>
CountingAllocator(const CountingAllocator<U>& other) noexcept
: allocation_count(other.allocation_count) {}
T* allocate(std::size_t n) {
if (n > std::numeric_limits<std::size_t>::max() / sizeof(T)) {
throw std::bad_alloc{};
}
if (allocation_count) {
++*allocation_count;
}
return static_cast<T*>(::operator new(n * sizeof(T)));
}
void deallocate(T* p, std::size_t) noexcept {
::operator delete(p);
}
template<class U>
bool operator==(const CountingAllocator<U>& rhs) const noexcept {
return allocation_count == rhs.allocation_count;
}
template<class U>
friend struct CountingAllocator;
};
int main() {
int allocations = 0;
std::vector<Trace, CountingAllocator<Trace>> values{CountingAllocator<Trace>{allocations}};
values.emplace_back(1);
values.emplace_back(2);
values.emplace_back(3);
}
Allocator 在容器设计中承担三项核心职责:
- 隔离内存来源:默认
std::allocator<T>转交全局分配函数;自定义 allocator 可将“申请n个T存储”的请求路由至预分配缓冲区、共享内存、arena、对象池或调试分配器。 - 解耦结构与存储粒度:
vector申请连续多元素存储;list、map等节点式容器为单个内部节点申请存储,二者的分配频率、缓存局部性与失败回滚路径截然不同。 - 暴露源码关键入口:在容器源码中看到
allocator_type、alloc_traits、allocate、construct、destroy、deallocate、rebind_alloc时,即可直接定位分配对象层级与生命周期边界。
边界与误区
std::vector<Trace> 与 std::vector<Trace, CountingAllocator<Trace>> 属于不同静态类型。引入自定义 allocator 会改变容器类型签名,直接影响函数接口、成员变量类型与 ABI 边界。
7.2 allocate、deallocate、construct 与 destroy
allocate(n) 返回可容纳 n 个 T 的未初始化原始存储,虽类型为 T*,但对象生命周期尚未开始。元素位置必须在四段状态之间严格推进:
原语(std::allocator_traits) | 状态迁移 | 对象生命周期 | 异常与清理要求 |
|---|---|---|---|
allocate(alloc, n) | 无存储 → 原始存储 | 尚未开始 | 后续构造前若失败,仅需 deallocate |
construct(alloc, p, args...) | 原始存储 → 有效对象 | 正式开始 | 构造成功后抛异常,须先 destroy 再 deallocate |
destroy(alloc, p) | 有效对象 → 原始存储 | 正式结束 | 禁止对未构造或已销毁位置重复调用 |
deallocate(alloc, p, n) | 原始存储 → 无存储 | 已结束 | 指针 p 与数量 n 须与原 allocate 匹配 |
容器源码通过 std::allocator_traits 统一驱动上述原语,而非直接手写 placement new:
#include <memory>
#include <string>
void build_one_string() {
using Alloc = std::allocator<std::string>;
using Traits = std::allocator_traits<Alloc>;
Alloc alloc;
std::string* p = Traits::allocate(alloc, 1);
try {
Traits::construct(alloc, p, "allocator path");
Traits::destroy(alloc, p);
Traits::deallocate(alloc, p, 1);
} catch (...) {
Traits::deallocate(alloc, p, 1);
throw;
}
}
围绕这套原语有三个关键工程细节:
- 异常分支的阶段隔离:
build_one_string()中若construct抛异常,p处对象尚未建立,故catch仅执行deallocate;一旦构造成功,退出前必须先destroy再deallocate,混用会析构未建立对象或直接释放有效对象存储。 - 接口演进与替代:C++11 引入
std::allocator_traits统一调用入口;C++17 起 allocator 成员函数construct/destroy逐步退场,C++20 起推荐使用std::construct_at显式开始生命周期,但源码中allocator_traits::construct语义一致。 - 为何拆分
new T与保留n:new T(args...)将分配与构造绑为单步,无法表达vector扩容的“批量申请 + 逐个迁移 + 前缀回滚”;deallocate(p, n)传回n(vector传capacity,节点容器传1)则供分池或调试分配器按尺寸回收与校验。
7.3 allocator_traits、rebind 与 propagation
std::allocator_traits<Alloc> 是标准容器访问 allocator 的统一适配层。若容器直接写 Alloc::pointer、Alloc::construct 或 Alloc::rebind,就会死绑到特定接口形状;traits 为缺省成员提供标准回退,并补齐类型推导与节点改绑:
- 类型补齐:allocator 可自定义
pointer、const_pointer、size_type、difference_type(例如共享内存中的偏移量“类指针”);缺省时由allocator_traits自动推导出T*等常规类型。 - 节点改绑(rebind):用户传入的是元素级
Alloc<T>,而list/map实际分配list_node<T>或tree_node<Value>,容器通过allocator_traits<Alloc>::rebind_alloc<Node>完成转换。
下面用简化链表存储展示 rebind_alloc 的用法:
#include <memory>
#include <utility>
template<class T>
struct ListNode {
ListNode* prev{};
ListNode* next{};
T value;
template<class... Args>
ListNode(ListNode* p, ListNode* n, Args&&... args)
: prev(p), next(n), value(std::forward<Args>(args)...) {}
};
template<class T, class Alloc = std::allocator<T>>
class MiniListStorage {
using Node = ListNode<T>;
using NodeAlloc = typename std::allocator_traits<Alloc>::template rebind_alloc<Node>;
using NodeTraits = std::allocator_traits<NodeAlloc>;
NodeAlloc node_alloc_;
public:
template<class... Args>
Node* create_node(Args&&... args) {
Node* node = NodeTraits::allocate(node_alloc_, 1);
try {
NodeTraits::construct(node_alloc_, node, nullptr, nullptr, std::forward<Args>(args)...);
return node;
} catch (...) {
NodeTraits::deallocate(node_alloc_, node, 1);
throw;
}
}
void destroy_node(Node* node) noexcept {
NodeTraits::destroy(node_alloc_, node);
NodeTraits::deallocate(node_alloc_, node, 1);
}
};
MiniListStorage 将 Alloc 改绑为 NodeAlloc 来分配含链接指针与 T 的 ListNode<T>。在标准库源码中看到 rebind_alloc<__node> 或 __node_alloc_traits 时,即可确认当前 allocator 操作位于内部节点层,而非用户元素层。
除类型适配外,allocator_traits 还通过四个属性决定容器拷贝、移动、交换时能否直接接管对方存储:
| Traits 成员 | 影响操作 | 值为 true | 值为 false |
|---|---|---|---|
propagate_on_container_copy_assignment | 拷贝赋值 | 目标随源更新 allocator(不等时先释放旧存储) | 保留目标原有 allocator,按自身策略复用或重分配 |
propagate_on_container_move_assignment | 移动赋值 | 先释放旧存储并更新为源 allocator,再直接接管源存储指针 | 保留目标 allocator;仅两端等价时可接管,否则须逐元素迁移 |
propagate_on_container_swap | swap 交换 | 随内部存储一并交换两端 allocator | 不交换 allocator(要求两端 allocator 相等,否则无法安全互释) |
is_always_equal | 跨实例互释判定 | 任意实例总是等价,可直接互释存储 | 带状态资源身份;须运行时比较 == 才能确认能否接管与释放 |
排查顺序
定位赋值或移动耗时异常时按四步排查:1) 查 propagate_on_container_* 是否传播;2) 否则查 is_always_equal 或 == 是否等价;3) 等价或传播时直接接管存储(常数成本),不等价才逐元素迁移;4) 逐元素迁移须核查异常时是否保留原状态。
7.4 raw memory algorithm 与 uninitialized 操作
当目标区域仅有原始存储而尚未构造对象时,需使用 raw memory 算法:std::uninitialized_copy、std::uninitialized_move、std::uninitialized_fill 负责批量构造,std::destroy、std::destroy_n 负责批量析构。
以 vector 扩容为例,旧缓冲中 [old_begin, old_end) 为有效对象,[old_end, old_cap) 与新申请的 [new_begin, new_cap) 均为未初始化存储,扩容迁移主路径如下:
核心判断
提交点(切换容器内部指针)之前,旧缓冲区始终代表容器的唯一有效状态,新缓冲区只是候选存储;图中的“新前缀”即新块中已构造完毕但尚未提交的区间。
以下简化迁移函数展示了扩容中追踪已构造前缀的回滚机制:
#include <memory>
#include <utility>
template<class T, class Alloc>
T* relocate_to_new_storage(Alloc& alloc, T* first, T* last, std::size_t new_capacity) {
using Traits = std::allocator_traits<Alloc>;
T* new_first = Traits::allocate(alloc, new_capacity);
T* new_current = new_first;
try {
for (T* current = first; current != last; ++current, ++new_current) {
Traits::construct(alloc, new_current, std::move_if_noexcept(*current));
}
return new_first;
} catch (...) {
for (T* p = new_first; p != new_current; ++p) {
Traits::destroy(alloc, p);
}
Traits::deallocate(alloc, new_first, new_capacity);
throw;
}
}
代码中 new_current 精确标定了已建立生命周期的前缀边界:异常时仅对 [new_first, new_current) 调用 destroy,避免析构 [new_current, new_first + new_capacity) 这段尚未构造的原始存储。std::uninitialized_copy 与 std::uninitialized_move 正是将“循环构造 + 异常时销毁已建前缀”封装为标准算法语义。
| 算法族 | 目标位置前置状态 | 执行动作 | 异常安全语义 |
|---|---|---|---|
普通算法(std::copy / std::move / std::fill) | 已有有效对象 | 调用赋值运算符(operator=) | 不负责销毁目标区间已有对象 |
Raw memory 算法(std::uninitialized_copy / std::uninitialized_move / std::uninitialized_fill) | 仅未初始化存储 | 调用构造函数(开始对象生命周期) | 异常时自动销毁本次已构造前缀并继续抛出 |
批量销毁算法(std::destroy / std::destroy_n) | 已有有效对象 | 逐个调用析构函数(不归还存储) | 使区间退回原始存储状态 |
边界与误区
严禁混用普通赋值算法与 raw memory 构造算法:在未初始化存储上使用 std::copy 会对未开始生命周期的内存执行赋值;在已有有效对象上使用 std::uninitialized_copy 会绕过析构直接覆盖对象状态。
7.5 pool allocator、polymorphic allocator 与 std::pmr
Pool allocator 通过空闲链表复用同尺寸或近似尺寸内存块,改变高频小对象分配的成本模型:
- 节点式容器(
list、map、unordered_map):频繁单节点分配可直接转为空闲链表摘挂,显著减少通用堆调用与碎片。 - 连续容器(
vector):主要开销在连续大块重分配与元素迁移,池化收益需结合容量增长与缓存局部性评估。
C++17 引入 std::pmr::polymorphic_allocator<T>,内部持有 std::pmr::memory_resource*,将内存策略从编译期静态模板参数转为运行期多态资源:
#include <array>
#include <memory_resource>
#include <string>
#include <vector>
void build_names() {
std::array<std::byte, 4096> buffer{};
std::pmr::monotonic_buffer_resource arena{buffer.data(), buffer.size()};
std::pmr::vector<std::pmr::string> names{&arena};
names.emplace_back("red");
names.emplace_back("black");
names.emplace_back("tree");
}
std::pmr::vector<std::pmr::string> 包含两层分配:外层 vector 的元素数组与每个 pmr::string 的字符缓冲区。polymorphic_allocator 通过 uses-allocator construction 将 &arena 自动透传给嵌套对象,使两层存储都出自同一 arena。
不同分配策略与 std::pmr 资源的选型取舍如下:
策略 / memory_resource | 对容器静态类型的影响 | 释放与同步特性 | 适用场景 |
|---|---|---|---|
默认 std::allocator<T> | 标准默认类型 | 无状态,转交全局分配函数 | 通用默认路径 |
自定义模板 PoolAlloc<T> | 改变容器类型签名,易导致类型分裂 | 静态派发,无虚函数开销 | 极热路径、编译期固定池策略 |
std::pmr::monotonic_buffer_resource | 保持 std::pmr 统一静态类型 | 按增长块分配,单个释放不回收;随资源销毁/重置统一释放 | 请求级/解析任务中的集中生命周期临时对象图 |
std::pmr::unsynchronized_pool_resource | 保持 std::pmr 统一静态类型 | 管理多尺寸空闲块池,无锁 | 单线程或外部已串行化的高频小对象分配 |
std::pmr::synchronized_pool_resource | 保持 std::pmr 统一静态类型 | 管理多尺寸空闲块池,带线程同步成本 | 多线程共享资源的高频节点式容器 |
边界与误区
std::pmr 以虚函数派发与显式生命周期管理换取静态类型稳定。无论使用 pool allocator 还是 std::pmr,底层池或 memory_resource 的生命周期必须严格长于所有关联容器及嵌套对象,且需借助相等比较与传播标志保证块只归还给原所属池。
7.6 allocator 对容器实现与 mini allocator 的影响
Allocator 无法改变容器承诺的抽象复杂度,但会影响分配常数成本、碎片、缓存局部性与锁竞争;容器本身决定分配单位,并始终持有元素生命周期与结构不变量:
| 对比维度 | std::vector | std::list | std::map |
|---|---|---|---|
| 分配单位 | 连续元素数组(一次 n 个 T) | 单个链表节点(rebind_alloc<Node>) | 单个红黑树节点(rebind_alloc<Node>) |
| 核心路径 | 申请新块 → 迁移元素 → 提交三指针 | 分配并构造节点 → 链接前后指针 | 分配并构造节点 → 比较定位 → 插入与旋转修复 |
| 异常安全难点 | 批量迁移中销毁已建新前缀并保留旧块 | 节点构造成功后才接入链表,失败即释放单节点 | 构造或比较器抛异常时维持原树结构完整 |
| 局部性与稳定性 | 连续内存局部性高;扩容使迭代器失效 | 节点离散;局部插入且节点地址与迭代器稳定 | 节点离散;旋转修复期间节点地址与迭代器稳定 |
一个最小可用 allocator 只需满足五项基础入口:value_type、跨类型拷贝构造(template<class U> Alloc(const Alloc<U>&))、allocate、deallocate 与相等比较(operator==)。类模板 template<class T> 的 rebind 可由 allocator_traits 自动推导;特殊场景再显式补充 rebind、pointer、传播标志或 is_always_equal。
下面的 MiniAllocator 以 counter_ 作为状态标识实现相等比较,未声明传播标志故沿用 allocator_traits 默认规则:
#include <cstddef>
#include <limits>
#include <new>
template<class T>
class MiniAllocator {
public:
using value_type = T;
MiniAllocator() noexcept = default;
explicit MiniAllocator(int& counter) noexcept : counter_(&counter) {}
template<class U>
MiniAllocator(const MiniAllocator<U>& other) noexcept : counter_(other.counter_) {}
T* allocate(std::size_t n) {
if (n > std::numeric_limits<std::size_t>::max() / sizeof(T)) {
throw std::bad_alloc{};
}
if (counter_) {
++*counter_;
}
return static_cast<T*>(::operator new(n * sizeof(T)));
}
void deallocate(T* p, std::size_t) noexcept {
::operator delete(p);
}
template<class U>
bool operator==(const MiniAllocator<U>& rhs) const noexcept {
return counter_ == rhs.counter_;
}
private:
template<class U>
friend class MiniAllocator;
int* counter_{};
};
结合 MiniAllocator 读容器源码时,关注点因分配单位而异:
- 追踪
vector:依次定位状态注入、allocate(n)对应新capacity、allocator_traits::construct逐元素迁移、异常时已建新前缀销毁,以及提交后旧元素与旧块释放。 - 追踪
list/map:转至rebind_alloc<Node>节点层,依次定位节点分配与值构造、未接入结构前失败的单节点释放,以及比较器或插入定位异常时旧结构的保持。
源码排查顺序
阅读容器 allocator 源码四步路径:1) 确定分配单位是元素还是内部节点;2) 区分当前处于存储阶段还是对象生命周期阶段;3) 核查 allocator_traits 的 rebind、传播标志与等价性;4) 落回容器提交点、迭代器稳定性与内存局部性。
最小自检任务
阅读下面代码,只根据本章内容判断三个问题:
storage取得后,内存中是否已经存在两个Widget对象?- 第二个
Widget构造失败时,清理循环会销毁哪些对象? - 最后释放存储时,为什么必须向
deallocate传回2?
#include <memory>
#include <stdexcept>
struct Widget {
int value{};
explicit Widget(int v) : value(v) {
if (v == 2) {
throw std::runtime_error{"bad widget"};
}
}
};
void build_two() {
using Alloc = std::allocator<Widget>;
using Traits = std::allocator_traits<Alloc>;
Alloc alloc;
Widget* storage = Traits::allocate(alloc, 2);
Widget* current = storage;
try {
Traits::construct(alloc, current, 1);
++current;
Traits::construct(alloc, current, 2);
++current;
} catch (...) {
for (Widget* p = storage; p != current; ++p) {
Traits::destroy(alloc, p);
}
Traits::deallocate(alloc, storage, 2);
throw;
}
for (Widget* p = storage; p != current; ++p) {
Traits::destroy(alloc, p);
}
Traits::deallocate(alloc, storage, 2);
}
本章知识点总结
- 策略与结构解耦
allocator 作为容器模板的内存策略入口,只负责原始存储来源与构造协议,容器仍掌管结构不变量、元素生命周期与异常安全提交点。
- 四段生命周期隔离
allocate取得未初始化存储,construct开启生命周期,destroy结束生命周期,deallocate归还存储时必须传回原指针与匹配的申请数量n。 - traits 与类型改绑
std::allocator_traits统一补齐默认类型与构造/销毁入口;节点式容器通过rebind_alloc<Node>将元素 allocator 转为内部节点 allocator。 - 传播与等价判定
propagate_on_container_*、is_always_equal与运行时==共同决定容器拷贝、移动、交换时能否直接接管存储或必须逐元素迁移。 - 批量初始化与提交点
uninitialized_copy/move/fill在原始存储上批量构造,失败时只销毁已建前缀[new_first, new_current);vector扩容直到提交新指针前都保留旧缓冲有效。 - 池化与 pmr 取舍
pool allocator 降低高频小块节点分配成本;
std::pmr通过运行期memory_resource*消除容器静态类型分裂,代价是虚函数派发与显式资源生命周期管理。 - 容器差异与排查主线
vector难点在连续块批量迁移与前缀回滚,list/map难点在节点层rebind与结构接入;源码排查依次锁定分配单位、存储/对象阶段与 traits 规则。