Skip to main content

Chapter 48: Mini Allocator

核心问题与阅读主线

本章导读5 个核心小节 · 附自检与总结

C++ 容器不能用 new T[n] 把“申请存储”和“默认构造对象”绑成一步,必须把底层存储分配与元素生命周期拆成两层。Mini Allocator 通过 allocate、deallocate、construct、destroy 与 allocator_traits 统一适配入口,使容器在扩容、回滚和复用容量时精确控制状态变迁。

全章共用场景样本

贯穿材料贯穿场景

本章贯穿材料是 mini_vector 的扩容路径:先为新容量申请未初始化存储并逐个构造元素,中途抛异常则逆序销毁已建前缀并释放新存储,全部成功后才销毁旧元素、归还旧存储并提交新指针。

标准语义以 cppreference 的 std::allocator 与 std::allocator_traits 为准(教学简化代码不代表 libstdc++、libc++ 或 MSVC STL 源码)。

48.1 实现 allocate​

allocate(n) 返回对齐满足 T、可容纳 n 个 T 的未初始化存储指针;在 construct 执行前,区域内不存在有效 T 对象。

#include <cstddef>
#include <limits>
#include <new>
#include <type_traits>
#include <utility>

template <class T>
class mini_allocator {
public:
using value_type = T;
using pointer = T*;
using const_pointer = const T*;
using size_type = std::size_t;
using difference_type = std::ptrdiff_t;

template <class U>
struct rebind {
using other = mini_allocator<U>;
};

[[nodiscard]] pointer allocate(size_type n) {
if (n == 0) {
return nullptr;
}
if (n > max_size()) {
throw std::bad_array_new_length{};
}

const size_type bytes = n * sizeof(T);
if constexpr (alignof(T) > __STDCPP_DEFAULT_NEW_ALIGNMENT__) {
return static_cast<pointer>(::operator new(bytes, std::align_val_t{alignof(T)}));
} else {
return static_cast<pointer>(::operator new(bytes));
}
}

[[nodiscard]] constexpr size_type max_size() const noexcept {
return std::numeric_limits<size_type>::max() / sizeof(T);
}
};

mini_allocator<T> 在分配阶段守住三项契约:

  • 溢出检查:n > max_size() 时抛出 std::bad_array_new_length,防止 n * sizeof(T) 回绕导致申请过小缓冲区而破坏堆。
  • 对齐分派:alignof(T) > __STDCPP_DEFAULT_NEW_ALIGNMENT__ 时转交带 std::align_val_t 的 ::operator new;释放协议由 allocator 内部封装,容器只保存 (p, n)。
  • 扩容隔离:mini_vector::reserve(new_cap) 第一步取得的 new_data 只是临时资源,原有 data_、size_、capacity_ 保持不变。

边界与误区

注意

allocate(n) 仅提供原始存储,在 construct 之前读取 p[i] 属于未定义行为。此外,标准 std::allocator<T>::allocate 在 C++20 起支持常量求值(须同次求值内释放),且 n == 0 允许返回非空但不可解引用的指针;教学版仅保留运行期路径并在 n == 0 时返回 nullptr。

48.2 实现 deallocate​

deallocate(p, n) 只释放存储、不执行析构。教学版未实现 C++23 allocate_at_least,传入的 n 必须严格等于当初传给 allocate(n) 的数量。

void deallocate(pointer p, size_type n) noexcept {
if (p == nullptr) {
return;
}

if constexpr (alignof(T) > __STDCPP_DEFAULT_NEW_ALIGNMENT__) {
::operator delete(p, n * sizeof(T), std::align_val_t{alignof(T)});
} else {
::operator delete(p, n * sizeof(T));
}
}

释放端通过 sized delete 传入 n * sizeof(T) 与对齐参数,与 allocate 对称;这也是 mini_vector 必须保存 capacity_ 的原因。

析构依赖有效对象与底层存储同时存在,因此必须先 destroy 再 deallocate。注意图中 LiveObjects 允许处于“仅前 i 个元素已构造”的中间态:

四个原语的职责与状态边界对比如下:

原语职责层状态迁移匹配与异常边界
allocate(n)原始存储无存储 → RawStorage校验溢出与对齐;失败不改容器状态
construct(p + i, args...)对象生命周期RawStorage 槽位 → LiveObjects就地构造;抛异常时仅 [0, i) 有效
destroy(p + i)对象生命周期LiveObjects → RawStorage析构并保留存储;禁对未建槽位调用
deallocate(p, n)原始存储RawStorage → 无存储p、n 与对齐协议须匹配原 allocate

核心判断

构造第 i 个元素抛异常时,只能销毁已建前缀 [0, i) 再释放整段存储;未构造的 [i, n) 槽位从未进入 T 的生命周期,严禁调用析构。

48.3 实现 construct​

construct 在已分配的 T* 地址上用 placement new 就地创建对象,不二次分配内存:

template <class... Args>
void construct(T* p, Args&&... args) {
::new (static_cast<void*>(p)) T(std::forward<Args>(args)...);
}

该实现围绕三项细节展开:

  • 屏蔽类重载:static_cast<void*>(p) 强制调用全局 placement ::operator new(std::size_t, void*),绕开 T 自定义的 operator new。
  • 完美转发:std::forward<Args>(args)... 保留实参值类别,支持 emplace_back 原位构造。
  • C++20 标准替代:std::construct_at 提供标准库入口并支持 constexpr 求值,现代 allocator_traits 默认分支可直接选用。

append_one 演示尾部构造与计数提交顺序:

template <class T, class Alloc>
void append_one(T*& data, std::size_t& size, Alloc& alloc, const T& value) {
alloc.construct(data + size, value);
++size;
}

边界与误区

注意

++size 必须位于 construct 之后。若先递增 size 再构造,构造抛异常会把未初始化槽位纳入 [0, size),容器析构时就会对未构造内存调用 ~T()。

48.4 实现 destroy​

destroy 调用 p->~T() 结束对象生命周期并保留底层存储供复用或释放(如 clear() 销毁 [0, size_) 后保留 capacity_):

void destroy(T* p) noexcept(std::is_nothrow_destructible_v<T>) {
p->~T();
}

不同析构特征的处理边界如下:

  • 平凡析构类型:编译器可消去无副作用的 ~T(),但容器仍须更新 size_ 将槽位逻辑移出有效集合。
  • 非平凡析构类型:必须在对象有效期内显式调用 destroy,确保句柄、锁或嵌套容器清理链执行。

批量清理或异常回滚时,容器通常按构造逆序销毁区间 [first, last):

template <class T, class Alloc>
void destroy_range(T* first, T* last, Alloc& alloc) noexcept {
while (last != first) {
--last;
alloc.destroy(last);
}
}

扩容迁移 [new_data, new_data + constructed) 时若后续元素构造失败,容器先调用 destroy_range(new_data, new_data + constructed, alloc) 再 deallocate(new_data, new_capacity),旧容器状态不受影响。

48.5 实现 allocator_traits 简化版​

容器直接写 alloc.construct 会强耦合分配器成员函数。allocator_traits 负责探测可选成员并提供默认回退,把容器与分配器的交互收拢为统一入口。

下面用 C++17 std::void_t 探测分配器是否自带 construct 与 destroy:

template <class, class, class...>
struct has_member_construct : std::false_type {};

template <class Alloc, class U, class... Args>
struct has_member_construct<
Alloc,
U,
std::void_t<decltype(std::declval<Alloc&>().construct(
std::declval<U*>(), std::declval<Args>()...))>,
Args...
> : std::true_type {};

template <class, class, class = void>
struct has_member_destroy : std::false_type {};

template <class Alloc, class U>
struct has_member_destroy<
Alloc,
U,
std::void_t<decltype(std::declval<Alloc&>().destroy(std::declval<U*>()))>
> : std::true_type {};

教学版 mini_allocator_traits<Alloc> 统一暴露类型别名、rebind_alloc、存储操作与构造/销毁回退:

template <class Alloc>
struct mini_allocator_traits {
using allocator_type = Alloc;
using value_type = typename Alloc::value_type;
using pointer = value_type*;
using size_type = std::size_t;

template <class U>
using rebind_alloc = typename Alloc::template rebind<U>::other;

static pointer allocate(Alloc& alloc, size_type n) {
return alloc.allocate(n);
}

static void deallocate(Alloc& alloc, pointer p, size_type n) noexcept {
alloc.deallocate(p, n);
}

template <class U, class... Args>
static void construct(Alloc& alloc, U* p, Args&&... args) {
if constexpr (has_member_construct<Alloc, U, void, Args&&...>::value) {
alloc.construct(p, std::forward<Args>(args)...);
} else {
::new (static_cast<void*>(p)) U(std::forward<Args>(args)...);
}
}

template <class U>
static void destroy(Alloc& alloc, U* p) {
if constexpr (has_member_destroy<Alloc, U>::value) {
alloc.destroy(p);
} else {
p->~U();
}
}
};

教学版与标准库 std::allocator_traits 的边界差异如下:

特性维度mini_allocator_traits(教学版)std::allocator_traits(标准库)
pointer 类型固定为 value_type*(仅裸指针)优先 Alloc::pointer,缺省经 std::pointer_traits 推导(支持 fancy pointer)
rebind_alloc依赖 Alloc::template rebind<U>::other无内嵌 rebind 时自动将 Alloc<T, Args...> 改绑为 Alloc<U, Args...>
construct / destroy成员探测优先,回退 placement new / p->~U()成员探测优先;C++20 默认采用 std::construct_at / std::destroy_at
传播与等价策略省略完整提供 POCCA/POCMA/POCS、is_always_equal 与 select_on_container_copy_construction

将 mini_allocator_traits 接回贯穿路径,mini_vector::reserve 遵循“建新块 → 失败回滚 → 清旧块 → 提交状态”的顺序:

template <class T, class Alloc = mini_allocator<T>>
class mini_vector {
using traits = mini_allocator_traits<Alloc>;

T* data_ = nullptr;
std::size_t size_ = 0;
std::size_t capacity_ = 0;
Alloc alloc_{};

public:
void reserve(std::size_t new_capacity) {
if (new_capacity <= capacity_) {
return;
}

T* new_data = traits::allocate(alloc_, new_capacity);
std::size_t constructed = 0;

try {
for (; constructed != size_; ++constructed) {
traits::construct(alloc_, new_data + constructed, data_[constructed]);
}
} catch (...) {
while (constructed != 0) {
--constructed;
traits::destroy(alloc_, new_data + constructed);
}
traits::deallocate(alloc_, new_data, new_capacity);
throw;
}

for (std::size_t i = size_; i != 0; --i) {
traits::destroy(alloc_, data_ + (i - 1));
}
traits::deallocate(alloc_, data_, capacity_);

data_ = new_data;
capacity_ = new_capacity;
}
};

排查顺序

核查容器内存代码固定四步:1) 指针指向 RawStorage 还是 LiveObjects;2) deallocate 数量是否与 capacity_ 严格配对;3) 异常回滚边界 constructed 是否仅覆盖已构造前缀;4) 是否统一经由 traits 访问 allocator。

最小自检任务​

动手自检先独立判断

阅读下面 reserve 片段,判断构造第 2 个新元素抛异常后,哪些对象需要析构、哪段存储需要释放,以及旧 mini_vector 状态是否已改变。

T* new_data = traits::allocate(alloc_, 4);
std::size_t constructed = 0;

try {
for (; constructed != size_; ++constructed) {
traits::construct(alloc_, new_data + constructed, data_[constructed]);
}
} catch (...) {
while (constructed != 0) {
--constructed;
traits::destroy(alloc_, new_data + constructed);
}
traits::deallocate(alloc_, new_data, 4);
throw;
}

本章知识点总结​

  • 存储与对象分离

    allocate 返回满足 T 大小与对齐的未初始化存储,生命周期直到 construct 成功才开始。

  • 容量配对与对齐

    deallocate(p, n) 须传回原申请数量 n,over-aligned 类型由 allocator 内部配对 std::align_val_t 版 operator new/delete。

  • 就地构造与提交

    construct 通过 static_cast<void*>(p) 与完美转发调用 placement new,容器须在构造成功后再递增 size_。

  • 逆序销毁与复用

    destroy 调用 p->~T() 结束生命周期但保留存储;批量清理通常逆序执行以贴合提交边界。

  • 强异常安全扩容

    reserve 失败时只销毁已建前缀 [0, constructed) 并释放新存储,全部成功后先清旧缓冲再提交新指针。

  • traits 统一适配

    allocator_traits 借助 std::void_t 探测成员函数并提供默认回退,解耦容器与具体分配器接口。

  • 教学实现边界

    本章省略 fancy pointer、POCCA/POCMA/POCS 传播策略、C++20 常量求值分配与 C++23 allocate_at_least。