2.1 向量

线性序列(Sequence)：向量(Vector)与列表(List)
抽象数据类型(Abstract Data Type, ADT)：数据模型及定义在该模型上的一组操作
数据结构(Data Structure)：基于特定语言实现ADT的算法

C/C++中，数组A[]中的元素与[0, n)一一对应，反之，每个元素均由索引唯一指代，并可直接访问，A[i]物理地址 = A + i × s，s为单个元素占用的空间量，故亦称为线性数组(Linear Array)。
向量是数组的抽象与泛化，由一组元素按线性次序封装而成，元素与[0, n)内的秩(rank)一一对应(call-by-rank, 循秩访问)，元素类型不限于基本类型，可参与复杂数据结构的定制与实现。

向量ADT接口
size() 报告向量当前规模
get(r) 获取秩为r的元素
put(r, e) 用e替换秩为r元素的值
insert(r, e) e作为秩为r元素插入，原后继元素依次后移
remove(r) 删除秩为r的元素，返回该元素中原存放对象
disordered() 判断所有元素是否已按非降序排列
sort() 按非降序排列各元素
find(e) 查找目标元素e
search(e) 在有序向量中查找目标元素e，返回不大于e且秩最大的元素
deduplicate() 删除重复元素
uniquify() 删除有序向量重复元素
traverse() 遍历向量并统一处理所有元素，处理方法由函数对象指定

Vector模板类

typedef int Rank; // 秩
#define DEFAULT_CAPACITY 3 // 默认初始容量
template <typename T> class Vector { // 向量模板类
    private:
        Rank _size; // 规模
        int _capacity; // 容量
        T* _elem; // 数据区
    protected:
        /* ... 内部函数 */
    public:
        /* ... 构造函数 */
        /* ... 析构函数 */
        /* ... 只读接口 */
        /* ... 可写接口 */
        /* ... 遍历接口 */
}；

构造与析构

Vector(int c = DEFAULT_CAPACITY) { // 默认
    _elem = new T[_capacity = c];
    _size = 0;
}

Vector(T const *A, Rank lo, Rank hi) { // 数组区间复制
     copyFrom(A, lo, hi);
}

Vector(Vector<T> const &V, Rank lo, Rank hi) { // 向量区间复制
     copyFrom(V._elem, lo, hi);
}

Vector(Vector<T> const &V) { // 向量整体复制
     copyFrom(V._elem, 0, V._size);
}

~Vector() { // 释放内部空间
    delete [] _elem;
}

// 基于复制的构造
template <typename T> // T为基本类型，或已重载赋值操作符"="
void Vector<T>::copyFrom(T* const A, Rank lo, Rank hi) {
    _elem = new T[_capacity = 2 * (hi - lo)]; // 分配空间
    _size = 0; // 规模清零
    while (lo < hi) // A[lo, hi)元素逐一
        _elem[_size++] = A[lo++]; // 复制至_elem[0, hi - lo)
}