栈分配数组实现

Stack Allocated Array

专题: General / 综合
难度: L1
来源: MyntBit

个人笔记

题目详情

在高频交易中，关键路径上的动态内存分配通常被避免，以防止系统调用引起的延迟毛刺。栈分配数组提供可预测的超低延迟，同时支持在严格最大容量范围内的动态调整。

任务：实现一个 StackArray<T, Capacity> 模板类，提供动态可调整大小但容量有上限的栈分配数组。

英文原题

In high-frequency trading (HFT), dynamic memory allocation is often avoided on the critical path to prevent latency spikes caused by system calls. A stack-allocated array provides predictable, ultra-low latency while still offering dynamic resizing up to a strict maximum capacity.
Task
Implement a StackArray<T, Capacity> template class that provides a dynamically sized array backed by a fixed-size stack allocation.
Your class should implement the following methods:

StackArray(): Initializes

解析

问题分析

动态内存分配（`new`/`delete` 或 `malloc`/`free`）可能触发系统调用，在高频交易的关键路径上引入不可预测的延迟毛刺。栈分配数组通过预分配固定大小的栈上缓冲区来避免堆分配，提供确定性的低延迟性能。

解决方案

template<typename T, size_t Capacity>
class StackArray {
    alignas(T) char buffer_[Capacity * sizeof(T)];
    size_t size_ = 0;
public:
    T& operator[] (size_t index) {
        if (index >= size_) throw std::out_of_range("Index exceeds size");
        return *reinterpret_cast<T*>(buffer_ + index * sizeof(T));
    }
    
    bool push_back(const T& value) {
        if (size_ >= Capacity) return false;
        new (buffer_ + size_ * sizeof(T)) T(value);
        ++size_;
        return true;
    }
    
    void pop_back() {
        if (size_ > 0) {
            --size_;
            reinterpret_cast<T*>(buffer_ + size_ * sizeof(T))->~T();
        }
    }
    
    size_t size() const { return size_; }
    static constexpr size_t capacity() { return Capacity; }
};

关键考虑

确定性延迟：无堆分配，无系统调用。所有操作均为 O(1)。
Placement new：使用 placement new 在预分配缓冲区上构造对象，显式调用析构函数清理。
内存对齐：`alignas(T)` 确保缓冲区满足类型 T 的对齐要求。
容量限制：超过 Capacity 时 `push_back` 返回 false（而非抛异常或动态扩展），保持延迟可预测。
边界条件：空数组 pop、满数组 push、索引越界等均需处理。
时间复杂度：所有操作 O(1)；空间复杂度：O(Capacity)。

英文解析

Analysis

Dynamic memory allocation (`new`/`delete` or `malloc`/`free`) can trigger system calls, introducing unpredictable latency spikes on critical paths in high-frequency trading. Stack-allocated arrays avoid heap allocation by pre-allocating fixed-size buffers on the stack, providing deterministic low-latency performance.

Solution

template<typename T, size_t Capacity>
class StackArray {
    alignas(T) char buffer_[Capacity * sizeof(T)];
    size_t size_ = 0;
public:
    T& operator[] (size_t index) {
        if (index >= size_) throw std::out_of_range("Index exceeds size");
        return *reinterpret_cast<T*>(buffer_ + index * sizeof(T));
    }
    
    bool push_back(const T& value) {
        if (size_ >= Capacity) return false;
        new (buffer_ + size_ * sizeof(T)) T(value);
        ++size_;
        return true;
    }
    
    void pop_back() {
        if (size_ > 0) {
            --size_;
            reinterpret_cast<T*>(buffer_ + size_ * sizeof(T))->~T();
        }
    }
    
    size_t size() const { return size_; }
    static constexpr size_t capacity() { return Capacity; }
};

Complexity & Edge Cases

Time complexity: O(1) for all push/pop/index operations on fixed-capacity stack array
Space complexity: O(Capacity) — pre-allocated, no dynamic growth
Edge cases: (1) Push on full array must reject or overwrite. (2) Pop on empty array returns error. (3) Index out of bounds is undefined without bounds checking.

Key Considerations

Deterministic latency: No heap allocation, no system calls. All operations are O(1).
Placement new: Uses placement new to construct objects in pre-allocated buffers, explicitly calling destructors for cleanup.
Memory alignment: `alignas(T)` ensures the buffer meets type T's alignment requirements.
Capacity limit: When exceeding Capacity, `push_back` returns false (rather than throwing or dynamically expanding), keeping latency predictable.
Edge cases: Empty array pop, full array push, index out of bounds all need handling.
Time complexity: all operations O(1); Space complexity: O(Capacity).