2.2 可扩充向量

静态空间管理：开辟内部数组_elem[]并使用一段地址连续的物理空间
若采用静态空间管理策略，容量_capacity固定，则有明显缺陷：
(1)上溢(overflow)：_elem[]不足以存放所有元素，而此时系统仍有足够空间
(2)下溢(underflow)：装填因子(load factor) λ = _size / _capacity << 50%
一般的应用环境中很难准确预测空间的需求量

动态空间管理：即将发生上溢时适当扩大内部数组的容量
扩容算法实现

template <typename T>
void Vector<T>::expand() { // 向量空间不足时扩容
    if (_size < _capacity) return; // 未满员时不必扩容
    _capacity = max(_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 * INCREMENT >> 2个元素，则在第(m - 1) * INCREMENT + 1次插入时，均需要扩容，不计申请空间操作，扩容过程中复制原向量的时间成本为(m - 1) * INCREMENT（算术级数），总耗时O(n²)，单次扩容分摊成本为O(n)

// 容量加倍策略
T* oldElem = _elem;
_elem = new T[_capacity << 1]; // 追加固定容量

最坏情况：在初始容量为1的满向量中，连续插入n = 2^m >> 2个元素，则在第2^m-1次插入时，均需要扩容，扩容过程中复制原向量的时间成本为2^m-1（几何级数），总耗时O(n)，单次扩容分摊成本为O(1)

平均复杂度或期望复杂度(average / expected complexity)：根据数据结构各种操作出现概率的分布，将对应的成本加权平均。各种可能的操作作为独立事件分别考查，割裂了操作间的相关性与连贯性，往往不能准确评判数据结构与算法的真实性能。
分摊复杂度(amortized complexity)：对数据结构连续实施足够多次操作，所需总体成本分摊至单次操作。从实际可行的角度对一系列操作作整体考量，更加真实的刻画可能出现的操作序列，可以更精准的评判数据结构与算法的真实性能。