Chapter 48: Mini Allocator

Mini Allocator 要解决的问题是：容器如何把“申请一段原始存储”和“在这段存储上创建元素”拆成两层可组合动作。读完本章后，读者应能定位 allocator 在容器实现中的职责，判断一段容器代码当前持有的是原始存储还是有效对象，并按固定顺序补齐申请、释放、构造、销毁和 traits 适配。

本章的贯穿材料是一段最小 mini_vector 扩容路径：先为 n 个 T 申请未初始化存储，再逐个构造元素；失败时销毁已经构造的元素，释放原始存储；成功后把新指针提交给容器状态。这个路径把 allocator 的五个接口全部串起来，也能解释为什么标准库把 allocator 放在容器模板参数里。

标准库语义上，std::allocator<T>::allocate 负责分配未初始化存储，std::allocator<T>::deallocate 负责释放对应存储，std::allocator_traits 是标准容器访问 allocator 属性和操作的统一入口。cppreference 对 std::allocator 和 std::allocator_traits 的说明可以作为接口边界来源；本章代码是教学简化实现，不代表 libstdc++、libc++ 或 MSVC STL 的真实源码。

allocator 的核心判断顺序固定为四步：先判断当前指针指向原始存储还是有效对象，再确认申请数量和释放数量是否配对，再确认构造成功数量是否被记录，最后通过 traits 让容器代码只依赖统一入口。后续小节会把这四步落到可运行的简化代码上。

48.1 实现 allocate

allocate 的输入是元素数量，输出是能够容纳这些元素的原始存储指针。这里的“原始存储”指一段对齐满足 T 要求、大小足够容纳 n 个 T 的字节区域；在 construct 执行前，这段区域里还没有任何 T 对象。容器可以在这段区域内做指针运算，但读取 p[i] 的值会越过生命周期边界。

教学版 mini_allocator<T> 先把数量转换成字节数，再调用全局 operator new。数量转换必须检查溢出，因为 n * sizeof(T) 在 std::size_t 中回绕后会申请到更小的存储，随后容器按 n 个元素写入会破坏堆。申请失败时，抛出路径交给 operator new 或显式抛出 std::bad_array_new_length，容器层只需要把“申请没有成功”视为状态未改变。

#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);
    }
};

这段代码建立了 allocator 的第一个边界：allocate(3) 返回的是“可放置 3 个 T 的位置”，这段位置尚未成为“已经有 3 个 T 的数组对象”。std::allocator<T>::allocate 在 C++20 中可用于常量求值场景，但同一常量求值内必须完成释放；教学版不覆盖这个编译期路径，只保留运行时容器实现最需要的责任边界。

对齐处理是 allocate 的实现形状之一。普通 operator new 能满足默认对齐内的对象；当 T 是 over-aligned 类型时，教学版使用带 std::align_val_t 的重载，并要求释放阶段使用匹配的 aligned delete。这个匹配关系属于 allocator 自身的私有协议，容器只保存 p 和 n，不直接选择释放函数。

贯穿到 mini_vector 时，reserve(new_cap) 的第一步只会得到一段 raw storage。此时容器的可提交状态仍然是旧的 data_ / size_ / capacity_，新指针只是临时资源。这个状态分层使扩容可以先构造新元素，等全部成功后再提交新指针。

48.2 实现 deallocate

deallocate 的输入是先前由同一个分配协议产生的指针和数量。数量必须和申请时的数量匹配；标准库在 C++23 引入 allocate_at_least 后允许在返回容量范围内释放，本章教学版没有实现这个扩展，因此 deallocate(p, n) 中的 n 必须等于当初传给 allocate(n) 的数量。

释放只处理存储，不处理对象生命周期。容器在调用 deallocate 前必须已经对所有有效元素执行 destroy。这个顺序来自对象模型：析构函数需要在有效对象上运行，释放存储之后，对象地址已经失去可用的存储基础，析构责任也失去执行位置。

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 明确传入释放路径，使读者在容器层养成保存容量的习惯。mini_vector 保存的 capacity_ 就是释放旧存储时传回 allocator 的数量。

deallocate 不应吞掉对象销毁责任。下面的状态图把 allocator 的四个动作放入同一条生命周期路径：allocate 和 deallocate 管存储，construct 和 destroy 管对象。图中的 LiveObjects 可以是部分构造状态，例如扩容过程中已经构造了前 i 个元素。

这个分层直接影响异常安全。若第 3 个元素构造失败，容器只能销毁前 2 个已经有效的元素，然后释放整段 raw storage。未构造的位置没有析构动作，因为这些位置从未进入 T 的生命周期。

48.3 实现 construct

construct 的任务是在已经分配的存储位置上启动对象生命周期。它接收一个 T* 位置和构造参数，通过 placement new 把对象创建在这个位置。placement new 是 C++ 提供的显式构造入口，它把“构造对象”放到调用者指定的地址上；它不会再次申请存储。

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

这段代码承担两件事。第一，static_cast<void*>(p) 明确进入 placement new 的地址参数形式，防止类类型重载的 operator new 干扰这个教学路径。第二，std::forward<Args>(args)... 保留构造参数的值类别，让 emplace_back 这类接口可以把实参直接转给元素构造函数。

C++20 提供了 std::construct_at，它以标准库函数形式表达同一类动作，并补充了常量求值等版本相关规则。教学版使用 placement new，是为了让读者看到 allocator 如何从地址和构造参数建立对象生命周期；在现代代码中，traits 的默认构造分支可以使用 std::construct_at 表达。

在 mini_vector 中，construct 的典型调用发生在扩容迁移和尾部插入。扩容迁移会对新存储逐个构造元素；尾部插入会在 data_ + size_ 上构造一个新元素，然后递增 size_。递增必须发生在构造成功之后，否则失败路径会把一个无效位置当成有效元素销毁。

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 表示有效对象数量，capacity 表示可容纳对象数量，construct 只把某一个 raw slot 转成 live object。

48.4 实现 destroy

destroy 的任务是在一个有效对象位置上结束对象生命周期。它调用析构函数，但保留底层存储给后续复用或释放。这个动作使容器可以先销毁元素，再决定是否释放整段容量；例如 clear() 会销毁 [0, size_) 中的元素，通常保留 capacity_。

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

对平凡析构类型，编译器或库实现可以把没有可观察效果的析构路径优化掉。语义上，容器仍然要把对应位置从“有效元素集合”中移除；状态更新由容器完成。对非平凡析构类型，destroy 必须在对象有效期间执行，否则资源成员、文件句柄、互斥量或嵌套容器的清理链不会运行。

销毁顺序影响容器的不变量。对 mini_vector 来说，销毁 [first, last) 时通常按逆序销毁，原因是后构造的元素在失败恢复时更接近当前提交边界。标准容器不总是把销毁顺序暴露成接口承诺，但实现内部需要一个稳定顺序来简化回滚。

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

destroy_range 展示了失败路径中的关键动作。若新存储上已经构造了 [new_data, new_data + constructed)，构造第 constructed 个元素失败后，容器调用 destroy_range(new_data, new_data + constructed, alloc)，再释放 new_data。旧存储尚未提交替换，旧容器状态保持可用。

48.5 实现 allocator_traits 简化版

allocator_traits 的作用是把 allocator 的可选接口整理成容器可统一调用的入口。容器若直接写 alloc.construct(p, args...)，它会强依赖 allocator 提供成员函数；容器若统一写 traits::construct(alloc, p, args...)，traits 可以先尝试成员函数，再退回到标准构造路径。标准库的 std::allocator_traits 还处理 pointer 类型、传播策略、rebind_alloc、select_on_container_copy_construction 等细节；本章只实现容器最小可用集合。

下面的检测工具用于判断 allocator 是否提供成员 construct 和 destroy。代码使用 C++17 的 std::void_t，失败时通过偏特化落到 false_type，成功时落到 true_type。

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 {};

教学版 traits 统一暴露类型、申请、释放、构造、销毁和 rebind。这样 mini_vector<T, Alloc> 只依赖 mini_allocator_traits<Alloc>，后续替换成统计型 allocator、池化 allocator 或节点 allocator 时，容器主逻辑不用改写。

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();
        }
    }
};

这段 traits 代码保留了教学目标下最小充分接口，也暴露了一个实现边界：它把 pointer 简化为 value_type*，没有支持 fancy pointer。真实 std::allocator_traits 会从 allocator 中提取 pointer，必要时通过 std::pointer_traits 生成相关指针类型。对本书的 Mini STL 路线来说，先用裸指针完成容器生命周期路径，再在后续节点式容器中讨论更复杂的 allocator 传播，学习负担更稳定。

把 traits 放回贯穿材料，mini_vector 扩容的异常安全骨架如下。代码重点是状态提交顺序：新存储构造完成前，旧状态不变；新存储构造成功后，先销毁旧元素，再释放旧存储，最后提交新指针和新容量。

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;
    }
};

这个骨架给出 Mini Allocator 的可迁移判断顺序。第一，看 data_ 指向的区域是 raw storage 还是 live objects。第二，看 capacity_ 是否能和 deallocate 的数量配对。第三，看 constructed 是否准确记录已经进入生命周期的元素数量。第四，看容器是否通过 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;
}

答案要点

若第 2 个新元素构造时抛出异常，constructed 只记录已经成功构造的元素数量，因此需要销毁 new_data[0]，不对 new_data[1] 执行析构。随后释放 new_data 对应的 4 个元素容量。旧 data_ / size_ / capacity_ 尚未被写入新值，旧元素仍然有效，容器可以继续保持原状态或把异常继续抛给调用方。

关键判断步骤是先区分 raw storage 和 live object，再用 constructed 限定销毁范围，最后用申请时的容量调用 deallocate。这道题验证的是 allocator 四个动作的责任分层：申请和释放处理存储，构造和销毁处理对象生命周期，traits 只把这些动作集中到统一调用入口。

本章知识点总结

• 原始存储：allocate 返回的是满足大小和对齐要求的存储位置，元素生命周期需要由后续构造动作启动。
• 数量配对：教学版 deallocate(p, n) 要使用当初申请时的数量，容器必须保存容量作为释放依据。
• 对齐协议：over-aligned 类型需要匹配的 aligned new 和 aligned delete，匹配关系由 allocator 封装。
• 构造边界：construct 在指定地址上用 placement new 创建对象，并把参数转发给元素构造函数。
• 提交顺序：容器应在构造成功后再递增 size_ 或提交新指针，失败路径依赖已构造数量恢复状态。
• 销毁边界：destroy 结束对象生命周期，但保留底层存储给复用或释放。
• 失败恢复：扩容失败时只销毁已经构造成功的新元素，再释放新存储，旧容器状态保持可用。
• traits 入口：allocator_traits 让容器通过统一接口访问 allocator，降低容器对具体分配器成员函数的依赖。
• 简化边界：本章 traits 使用裸指针和最小 rebind，真实标准库还处理 fancy pointer、传播策略和更多版本差异。
• 判断顺序：先看对象生命周期，再看容量配对，再看异常路径中的已构造数量，最后看容器是否经由 traits 调用 allocator。