2.3 无序向量

元素访问（循秩访问）
通过V.get(r)与V.put(r, e)接口已然可以读写向量元素，但就便捷性而言，远不如数组元素的访问方式A[r]，需要重载下标操作符"[]"

template <typename T> // 0 <= r < _size
T & Vector<T>::operator[](Rank r) const {return _elem[r];}

对外V[r]即对应于内部V._elem[r]

插入

template <typename T> // e作为秩为r元素插入，0 <= r <= _size
Rank Vector<T>::insert(Rank r, T const & e) {
    expand(); // 若有必要，扩容
    for (int i = _size; i > r; i--) // 自后向前
        _elem[i] = _elem[i - 1]; // 后继元素顺次后移一个单元
    _elem[r] = e; // 置入新元素
    _size++; // 更新规模
    return r; // 返回秩
}

区间删除

template <typename T> // 删除区间[lo, hi)，0 <= lo <= hi <= _size
int Vector<T>::remove(Rank lo, Rank hi) {
    if (lo == hi) return 0; // 出于效率考虑，单独处理退化情况
    while (hi < _size) _elem[lo++] = _elem[hi++]; // [hi, _size)顺次前移hi - lo位
    _size = lo; // 更新规模
    shrink(); // 若有必要，缩容
    return hi - lo; // 返回被删除元素数目
}

查找
无序向量：T为可判等的基本类型，或已重载操作符"=="或"!="
有序向量：T为可比较的基本类型，或已重载操作符"<"或">"

template <typename T> // 0 <= lo < hi <= _size
Rank Vector<T>::find(T const & e, Rank lo, Rank hi) const {
    while ((lo < hi--) && (e != _elem[hi])); // 逆向查找，在命中多个元素时可返回秩最大者
    return hi; // hi < lo为失败，否则hi即命中元素的秩
}

单元素删除

// 可视作区间删除操作[r] = [r, r + 1)
template <typename T> // 删除向量中秩为r的元素，0 <= r < _size
T Vector<T>::remove(Rank r) {
    T e = _elem[r];  // 备份被删除元素
    remove(r, r + 1); // 调用区间删除算法
    return e; // 返回被删除元素
}

唯一化

template <typename T> // 删除重复元素，返回被删除元素数目
int Vector<T>::deduplicate() { // 低效算法
    int oldSize = _size; // 记录原规模
    Rank i = 1; // 自_elem[1]开始
    while (i < _size) // 自前向后逐一考查元素_elem[i]
        (find(_elem[i], 0, j) < 0) ? i++ : remove(i); // 在前缀中查找重复者，若无则继续考查，否则删除重复者
    return oldSize - _size; // 向量规模变化量，即删除元素数目
}

遍历

// 利用函数指针机制，只读或局部性修改
template <typename T>
void Vector<T>::traverse(void (*visit)(T&)) {
    for (int i = 0; i < _size; i++)
        visit(_elem[i]);
}

// 利用函数对象机制，可全局性修改
template <typename T> template <typename VST>
void Vector<T>::traverse(VST& visit) {
    for (int i = 0; i < _size; i++)
        visit(_elem[i]);
}