这里用c语言代码实现为例子，哪种语言无所谓其实，主要是背后的思想

扩容算法实现

template <typename T> void Vector<T>::expand(){//向量空间不足时扩容
    if （_size < _capacity） return;//尚未满员时，不必扩容
    if (_capacity < DEFAULT_CAPACITY) _capacity = DEFAULT_CAPACITY;//不低于最小容量
    T* oldElem = _elem;_elem = new T[_capacity << =1]//容量加倍
    for (int i = 0 ; i <_size;i++)
        _elem[i] = oldElem[i] //复制原向量内容（T为基本类型，或已重载赋值操作符'='）
    delete [] oldElem;//释放原空间
}
容量递增策略
T* oldElem = _elem;_elem = new T[_capacity  += INCREMENT]//容量加倍
最坏的情况：在初始容量为0的 空 向量中 ，连续插入 n = m* I   >>2 个元素....
于是，在第 1，I+1 , 2I+1 , 3I+1 .......此次插入都需要扩容
不计算申请空间操作的时间，各次扩容过程中复制原向量需要的时间成本依次为
    0，I , 2I, 3I ,.......(M-1)*I //算术级数
    总体耗时 = I * (m-1) * m /2 = O(n^2)  每次扩容的分摊成本都 O (n)
容量加倍策略
T* oldElem = _elem;_elem = new T[_capacity << =1]//容量加倍
最坏的情况：在初始容量为1的满向量中 ，连续插入  n = 2^m    >>2 个元素....
于是，在第 1 ,2 ,4 ,8 ,16 ,.... 次插入都需要扩容
各次扩容过程中复制原向量需要的时间成本依次为
    1 ,2 ,4 ,8 ,16 ,...., 2^m = n //几何级数
    总体耗时 = O（n） 每次扩容的分摊成本都 O (1)
对比

数据结构空间扩充空间为什么总是变为原来的2倍 算法

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

结论：

综上：扩大为原来的2倍 复杂度最低相对来说，所以是两倍
tips：级数可以百度下就知道了
扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄