手写 List 容器源码优化：减少内存操作

在实现动态数组类 List 时，核心优化目标是减少内存分配/拷贝次数。以下是关键优化点及实现：

优化策略

1. 预分配机制

   • 维护 capacity 和 size 双指针
   • 扩容时按几何增长（如 1.5 倍），避免每次添加元素都重新分配
   • 缩容时设置阈值（如 size < capacity/4）

2. 内存复用

   • 删除元素时不立即释放内存，仅标记为可复用
   • 插入时优先使用预留空间

3. 批量操作优化

   • 批量插入时一次性扩容到位
   • 使用 memmove 替代循环拷贝

C++ 优化实现

template <typename T>
class OptimizedList {
private:
    T* data;           // 数据存储
    size_t size;       // 当前元素数量
    size_t capacity;   // 预分配容量
    const float GROW_FACTOR = 1.5f;  // 扩容因子

    void resize(size_t new_capacity) {
        T* new_data = new T[new_capacity];  // 一次性分配
        std::move(data, data + size, new_data);  // 移动语义
        delete[] data;
        data = new_data;
        capacity = new_capacity;
    }

public:
    OptimizedList() : data(nullptr), size(0), capacity(0) {}
    
    ~OptimizedList() { delete[] data; }

    // 添加元素（内存复用核心）
    void push_back(const T& value) {
        if (size >= capacity) {
            resize(capacity ? static_cast<size_t>(capacity * GROW_FACTOR) : 4);
        }
        data[size++] = value;
    }

    // 批量插入优化
    void insert_batch(size_t index, const T* values, size_t count) {
        if (size + count > capacity) {
            resize(size + count);  // 精确扩容
        }
        // 移动已有元素
        std::memmove(data + index + count, 
                    data + index, 
                    (size - index) * sizeof(T));
        // 批量拷贝新元素
        std::copy(values, values + count, data + index);
        size += count;
    }

    // 删除元素（延迟缩容）
    void remove(size_t index) {
        std::move(data + index + 1, data + size, data + index);
        size--;
        // 缩容阈值：使用率低于25%
        if (size > 0 && capacity / size >= 4) {
            resize(capacity / 2);
        }
    }
};

关键优化说明

1. 移动语义
   使用 std::move 替代拷贝构造，在扩容时将元素所有权转移而非复制：

   std::move(data, data + size, new_data);  // 零拷贝转移
   

2. 内存复用指标
   通过 capacity/size 比率控制内存：

   • 扩容触发：$ size \geq capacity $
   • 缩容条件：$ \frac{capacity}{size} \geq 4 $

3. 批量操作优化
   批量插入时间复杂度从 $O(n^2)$ 降至 $O(n)$： $$ \text{时间开销} = \underbrace{O(\text{扩容})}{\text{均摊 } O(1)} + \underbrace{O(\text{移动})}{O(n)} $$

性能对比

最佳实践：在嵌入式系统或高频交易场景中，可预先调用 reserve() 分配足够内存，彻底消除运行时分配开销。