自定义 STL 分配器

Custom Stl Allocator

专题: Systems & Architecture / 系统与架构
难度: L2
来源: MyntBit

个人笔记

题目详情

C++ 标准容器默认使用 std::allocator 通过 new/delete 分配内存。自定义分配器可以将容器元素分配到预分配的内存池或共享内存中，消除系统调用开销并提升性能。

任务：实现一个与 STL 容器兼容的自定义池化分配器。

英文原题

In high-frequency trading (HFT) and low-latency financial systems, dynamic memory allocation via system calls is often too slow and unpredictable. Utilizing a pre-allocated memory pool (arena) alongside a custom STL allocator allows containers to manage memory efficiently without triggering expensive OS-level operations.
Task
Implement a MemoryPool class and a CustomAllocator<T> template that satisfies the C++11 STL Allocator concept to be used with standard containers like std::vector.

Memo

解析

问题分析

C++ 标准容器默认使用 std::allocator（调用 new/delete）。在高频交易中，可以使用自定义分配器替代，将容器元素分配到内存池或共享内存中，消除系统调用开销。

实现

template<typename T, size_t PoolSize = 1024>
class PoolAllocator {
    static thread_local std::array<T, PoolSize> pool_;
    static thread_local size_t used_;
public:
    using value_type = T;
    T* allocate(size_t n) {
        if (used_ + n > PoolSize) throw std::bad_alloc();
        T* p = &pool_[used_];
        used_ += n;
        return p;
    }
    void deallocate(T*, size_t) {} // 池化分配器不单独释放
    template<typename U> struct rebind { using other = PoolAllocator<U, PoolSize>; };
};
// 使用: std::vector<int, PoolAllocator<int>> vec;

复杂度与边界

时间复杂度：allocate O(1)（仅指针移动）
空间复杂度：O(PoolSize)，编译期固定
边界条件：(1) 池满时抛 std::bad_alloc (2) 线程局部存储避免锁竞争 (3) deallocate 为空——池在请求结束时整体释放 (4) 适用于 POD 和简单对象

英文解析

Analysis

C++ standard containers default to `std::allocator` (calling `new`/`delete`). In high-frequency trading, a custom allocator can replace this, placing container elements in memory pools or shared memory to eliminate system call overhead.

Solution

template<typename T, size_t PoolSize = 1024>
class PoolAllocator {
    static thread_local std::array<T, PoolSize> pool_;
    static thread_local size_t used_;
public:
    using value_type = T;
    T* allocate(size_t n) {
        if (used_ + n > PoolSize) throw std::bad_alloc();
        T* p = &pool_[used_];
        used_ += n;
        return p;
    }
    void deallocate(T*, size_t) {} // pooled allocator does not free individually
    template<typename U> struct rebind { using other = PoolAllocator<U, PoolSize>; };
};
// Usage: std::vector<int, PoolAllocator<int>> vec;

Complexity & Edge Cases

Time complexity: allocate O(1) (pointer increment only)
Space complexity: O(PoolSize), fixed at compile time
Edge cases: (1) Pool full throws std::bad_alloc (2) Thread-local storage avoids lock contention (3) deallocate is empty — pool released wholesale at request end (4) Suitable for POD and simple objects

Key Considerations

Rebinding requirement: STL containers internally rebind allocators to different value types; allocator must support rebind<OtherType>::other for correct container behavior
Propagation policy: Decide whether allocator propagates on container copy/move/swap; std::allocator_traits defaults vary — explicit policy prevents subtle bugs
Stateful vs stateless: Stateful allocators (with memory pool pointer) must propagate state; stateless allocators can be default-constructed anywhere
Equality semantics: Two allocators are equal iff memory allocated by one can be freed by the other; pool-based allocators sharing the same pool must report equality