如何在自定义动态扩容数组模块中减少realloc调用次数？

你当前的DSA模块在添加元素时采用内存翻倍的扩容策略，能有效减少扩容时的realloc调用，但删除元素的缩容逻辑会导致几乎每次删除都触发realloc，严重影响性能。从你的示例表格可以看到，连续删除单个元素时，每次都会触发内存重新分配。

当前问题分析 #

你的dsa_remove_size_handle逻辑中，只要已分配内存大于新已使用内存的2倍就会触发缩容。这意味着只要已使用内存占比低于50%，就会立刻缩容到2倍已使用大小，导致频繁调用realloc。

优化方案 #

要保留扩容翻倍的规则，同时减少缩容的realloc调用，核心是设置缩容的滞后阈值：只有当已使用内存远低于已分配内存的某个比例（比如1/4）时，才触发缩容，并且缩容后的大小保持为当前已使用内存的2倍（和扩容策略对齐）。这样可以避免连续删除少量元素时的频繁缩容，同时保证内存不会过度浪费。

具体规则：

• 仅当已分配内存 > 4 * 新已使用内存时，才触发缩容
• 缩容后的大小设置为2 * 新已使用内存（最小不低于初始的2倍元素大小）

修改后的代码 #

#define DSA_USED_SIZE(dsa) ((dsa->length) * (dsa->elementSize))

typedef struct DSA
{
    void *data;
    size_t length;
    size_t allocatedSize;
    size_t elementSize;
} DSA;

// 添加元素前的内存处理（保留原扩容逻辑）
int dsa_add_size_handle(DSA *dsa, size_t addSize)
{
    if (dsa->allocatedSize >= DSA_USED_SIZE(dsa) + addSize)
    {
        return 1;
    }

    size_t newSize = 2 * (DSA_USED_SIZE(dsa) + addSize);
    void *temp = realloc(dsa->data, newSize);
    if (temp == NULL)
    {
        perror("_dsa_add_size_handle: ");
        return 0;
    }
    dsa->data = temp;
    dsa->allocatedSize = newSize;
    return 1;
}

// 删除元素后的内存处理（优化缩容逻辑）
int dsa_remove_size_handle(DSA *dsa, size_t removeSize)
{
    size_t newUsedSize = DSA_USED_SIZE(dsa) - removeSize;
    // 仅当已分配内存超过新已使用内存的4倍时，才触发缩容
    if (dsa->allocatedSize <= 4 * newUsedSize)
    {
        return 1;
    }

    size_t newSize = 2 * newUsedSize;
    if (newSize == 0)
    {
        newSize = 2 * dsa->elementSize;
    }
    void *temp = realloc(dsa->data, newSize);
    if (temp == NULL)
    {
        perror("_dsa_remove_size_handle: ");
        return 0;
    }
    dsa->data = temp;
    dsa->allocatedSize = newSize;
    return 1;
}

效果验证 #

用你提供的示例场景测试优化后的逻辑：

直到已使用内存降至7时，4*7=28 < 32，此时才会触发缩容到14，大幅减少了realloc的调用次数。

额外建议 #

• 如果需要更严格的内存控制，可以调整缩容阈值（比如1/3），但1/4是平衡性能和内存占用的常用值
• 该策略能很好适配大多数使用场景，避免在频繁删除少量元素的场景下过度触发内存重新分配

内容的提问来源于stack exchange，提问作者Ertugrul