【低成本扩容】动态扩容实战指南

面对扩容操作时，下面这种操作是否也会迷惑你？下面来为大家解惑~

size_t newcapacity = 2*_capacity > (_size + len)?2*_capacity:(_size+len);
//len为即将插入的字符串有效字符个数//_size为当前字符串有效字符个数//_capacity为当前容量大小//newcapacity为扩容后容量大小

一、为什么需要动态扩容？

静态数组（如 C 语言的int arr[10]）的容量是固定的，一旦存储的元素数量超过容量，就会发生溢出。而动态数组（如 C++ 的vector、Java 的ArrayList）需要支持灵活添加元素，因此必须在容量不足时自动扩容。

但扩容的过程是 "昂贵" 的：

• 需要申请一块更大的内存空间
• 把原有元素复制到新空间
• 释放旧空间的内存

如果每次添加元素都只扩容 1 个单位，会导致频繁扩容（添加 n 个元素可能需要 n 次扩容），时间复杂度会退化到O(n²)（每次复制元素的成本累积）。

二、为什么选择 "翻倍扩容"（2 * _capacity）？

这是一种避免频繁扩容的优化策略：

• 每次扩容时直接将容量翻倍，能保证后续多次添加元素都不需要再次扩容
• 从数学上可以证明，这种策略能让单次添加元素的平均时间复杂度降为O(1)（ amortized O(1)）

例如：

• 初始容量为 1，添加 1 个元素后扩容到 2
• 再添加 1 个元素（总 2 个），下次添加时扩容到 4
• 再添加 2 个元素（总 4 个），下次添加时扩容到 8
• 以此类推，每扩容一次，能支持的新增元素数量也翻倍

这种 "批量扩容" 的思路，用少量的空间冗余换取了时间效率的极大提升。

三、为什么还要考虑 "_size + len"？

当一次性添加大量元素（len很大）时，如果固执地用 "翻倍扩容" 可能导致空间浪费：

• 假设当前容量_capacity=100，已存储_size=50个元素
• 现在要一次性添加len=200个元素，此时_size + len = 250
• 如果按翻倍扩容（2*100=200），容量仍然不够，还需要再次扩容
• 因此直接扩容到_size + len（250），既满足需求又避免不必要的空间浪费

这是一种 "按需扩容" 的补充策略，防止在批量添加元素时出现 "扩容不足" 或 "过度扩容" 的问题。

四、代码本质

• 小规模添加元素时，用 "翻倍扩容" 减少扩容次数，优化时间效率。
• 大规模添加元素时，用 "按需扩容" 确保刚好够用，优化空间效率。