可扩充向量

静态管理空间

_capacity固定, 存在不足:

1, 上溢(overflow）, _elem[]不足以存放元素
2, 下溢(underflow), _elem[]中元素寥寥无几
装填因子(load factor) = size/ capacity << 50% 空间利用率低

动态管理空间

蝉的哲学：每过一段时间，身体生长，以致于无法外壳容纳自己的身体，退去一层外壳，但之以容纳新的外壳。

即将发生上溢，适当扩展容量

扩容算法实现

最终的扩容代码如下:

template <typename T>
void Vector<T>::expand() {
  if (_size < _capacity) return;    // 容量未到达不必扩容
  _capacity = max(_capacity, DEAFAULT_CAPACITY);    // 不小于最小容量
  // 存储旧元素, 新数组容量扩大
  T* old_elem = _elem; _elem = new T[_capacity <<= 1];
  for (int i = 0; i < _size; i++) {
    _elem[i] = old_elem[i];   // 复制原数组到新数组的对应位置
  }
  delete [] old_elem;    // 释放原数组的对应空间，归还系统
}

另外尝试两种出现BUG的代码：

/* my test code
template <typename T>
void Vector<T>::expand() {
  if (_size == _capacity) {   // 规模到达最大容量时
    // 创建一个容量更大的数组
    T* _new_elem = new T[_capacity *= 1.2];  // ERROR:没有delete又重新new了一个
    Rank _tmp_size = _size;
    _size = 0;
    // 复制原数组到新数组的对应位置
    copyFrom(this->_elem, 0, _tmp_size);
    // 释放原数组的对应空间，归还系统
    delete [] _elem;
  }
}
*/

/* 最终版本的expand()中, new一个数组储存旧元素, 下面new一个数组, 作为扩容数组
template <typename T>
void Vector<T>::expand() {
  if (_size < _capacity) return;    // 容量未到达不必扩容
  _capacity = max(_capacity, DEAFAULT_CAPACITY);    // 不小于最小容量
  // 存储旧元素, 新数组容量扩大
  T* new_elem = new T[_capacity <<= 1];
  for (int i = 0; i < _size; i++) {
    new_elem[i] = _elem[i];   // 复制原数组到新数组的对应位置
  }
  // ERROR:不能直接赋值, 需要copyFrom(), 这里对_elem的更新不直接, 先新后旧的原则
  _elem = new_elem;      // ERROR:当前数组元素更新为新数组元素, 可T类型还没有operator=()
  delete [] new_elem;    // 释放临时数组的对应空间，归还系统
}
*/

第二种错误代码分析：

备份一份旧的, 把当前的刷成新的。

创建一份新的, 把旧的拷贝过去，在赋值给旧的。这种方法做了多余的操作。

封装的好处

得益于向量的封装, 尽管扩容之后数据区的物理地址有所改变, 却不致出现野指针, 封装后，上述通过_elem统一的指示器标记起点.

为何必须采用容量加倍

递增式扩容

加倍式扩容

递增式扩容

_elem = new[T = _capacity + INCREMENT];     // 追加固定大小量

每次扩容, 复制原向量的成本
I, 2I, 3I, … (m-1)I // 算术级数

算术级数:从某个数开始, 以固定间隔为
单位, 不断的线性递增，总和成为算术级数。总和和末项成平方关系

总耗时 = I (m-1) m/2 = O(n^2), 每次O(n)

加倍式扩容

1, 2, 4, 8, 16…2^m 次扩容 // 几何级数
几何级数与末项等阶, O(n)

总耗时O(n), 每次扩容分摊成本为O(1)

空间上的牺牲, 在时间上获得巨大的收益。

分摊复杂度

平均分析 vs 分摊分析

平均分析(average/ expected complexity)
独立事件, 割裂相关性
往往不能准确反应。

分摊分析(amortized complexity)
连续的, 足够多的操作。
实际可行，整体考量。
更为真实反应。