【C++】数据结构——向量_c++向量

参考书籍：《数据结构（C++语言版）》邓俊辉著

向量（vector）是最基本的线性数据结构——序列（sequence）中的一种。向量中。所有数据项的物理存放位置与其逻辑次序一致，其逻辑次序被称作秩（rank）。

C++中已经有实现向量的库<vector>，我们不使用该库，而是仿照它实现一种基于向量的抽象数据类型（Abstract Data Type，ADT）。

ADT接口

下面列出需要实现的接口：

Vector模板类

下面定义Vector模板类：

typedef int Rank;
#define DEFAULT_CAPACITY 3

template <typename T>
class Vector
{
protected:
    Rank _size;                                  //元素个数
    int _capacity;                               //实际空间
    T *_elem;                                    //元素指针
    void copyFrom(T const *A, Rank lo, Rank hi); //从A中复制区间[lo, hi)
    void expand();                               //空间不足时扩容
    void shrink();                               //装填因子过小时压缩空间
    bool bubble(Rank lo, Rank hi);				 //冒泡排序的基本操作，扫描交换
public:
    //构造函数
    Vector(int c = DEFAULT_CAPACITY, int s = 0, T v = 0)
    {
        _elem = new T[_capacity = c];
        for (_size = 0; _size < s; _elem[_size++] = v)
            ;
    }
    Vector(T const *A, Rank n) { copyFrom(A, 0, n); }                           //从数组复制
    Vector(T const *A, Rank lo, Rank hi) { copyFrom(A, lo, hi); }               //复制数组区间
    Vector(Vector<T> const &V) { copyFrom(V._elem, 0, V._size); }               //拷贝构造
    Vector(Vector<T> const &V, Rank lo, Rank hi) { copyFrom(V._elem, lo, hi); } //复制向量区间
    //析构函数
    ~Vector() { delete[] _elem; } //删除数组
    //只读接口
    Rank size() const { return _size; }                                               //返回最大秩
    bool empty() const { return !_size; }                                             //判空
    int disordered() const;                                                           //返回逆序数
    Rank find(T const &e) const { return find(e, 0, _size); }                         //无序向量整体查找
    Rank find(T const &e, Rank lo, Rank hi) const;                                    //无序向量区间查找
    Rank search(T const &e) const { return (_size <= 0) ? -1 : search(e, 0, _size); } //有序向量整体查找
    Rank search(T const &e, Rank lo, Rank hi) const;                                  //有序向量区间查找
    //可写入接口
    T &operator[](Rank r) const;                         //重载[]操作符，使其能够像数组一样引用元素
    Vector<T> &operator=(Vector<T> const &);             //重载=操作符，使其能够向数组一样赋值
    T remove(Rank r);                                    //删除秩为r的元素
    Rank insert(Rank r, T const &e);                     //在秩为r的位置插入元素e
    Rank insert(T const &e) { return insert(_size, e); } //在末尾插入元素e
    void sort(Rank lo, Rank hi);                         //对[lo, hi)区间排序
    void sort() { sort(0, _size); }                      //整体排序
    void unsort(Rank lo, Rank hi);                       //对[lo, hi)区间置乱
    void unsort() { unsort(0, _size); }                  //整体置乱
    int deduplicate();                                   //无序去重
    int uniquify();                                      //有序去重
    //遍历操作
    void traverse(void (*)(T &)); //使用函数指针操作
    template <typename VST>
    void traverse(VST &); //使用函数对象操作
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

对于只读的接口，尽量将其声明为const类型。

初始化函数

由于向量的特性，我们选择数组这一结构作为向量类的基本元素单元，因为数组在内存中的物理地址与其逻辑次序一致。

构造函数在类声明中已经内联的实现了，下面实现内部的复制函数：

template <typename T>
void Vector<T>::copyFrom(T const *A, Rank lo, Rank hi)
{
    _elem = new T[_capacity = 2 * (hi - lo)]; //申请空间
    _size = 0;                                //规模置零
    while (lo < hi)
    {
        _elem[_size++] = A[lo++]; //逐个复制
    }
}
1
2
3
4
5
6
7
8
9
10

根据模板参数T的不同，向量模板会自动请求合适的内存。

运算符重载

我们目前只需要重载=赋值操作符和[]取元素操作符：

template <typename T>
Vector<T> &Vector<T>::operator=(const Vector<T> &V)
{
    delete[] _elem;	//删除原有空间，因为下面会申请新的空间
    copyFrom(V._elem, 0, V._size);
    return *this; //返回值为引用便于链式赋值
}
1
2
3
4
5
6
7

返回值为引用，这样就可以实现链式赋值（即连等）。

template <typename T>
T &Vector<T>::operator[](Rank r) const
{
    return _elem[r];
}
1
2
3
4
5

动态空间管理

在可用空间足够小时扩容，在剩余空间足够大时缩容，一般发生在向量修改前后：

template <typename T>
void Vector<T>::expand()
{
    while (_size == _capacity) //若实际规模等于容量
    {
        T *oldElem = _elem;
        _elem = new T[_capacity <<= 1]; //申请两倍的新的空间
        for (int i = 0; i < _size; i++)
        {
            _elem[i] = oldElem[i]; //若T为非基本类型，则该类型需重载=操作符
        }
        delete[] oldElem; //释放原空间
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

扩容两倍的空间，这是有理论依据的。当发生足够多次的插入操作时，每次将容量扩大一倍的平摊时间成本最低，为O(1)。

template <typename T>
void Vector<T>::shrink()
{
    while (_size << 2 < _capacity) //若实际规模不到容量的1/4，则缩容
    {
        T *oldElem = _elem;
        _elem = new T[_capacity >>= 1]; //申请原来一半的空间
        for (int i = 0; i < _size; i++)
        {
            _elem[i] = oldElem[i]; //若T为非基本类型，则该类型需重载=操作符
        }
        delete[] oldElem; //释放原空间
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

装填因子 = _size / _capacity ，我们选择25%作为装填因子的下限。

逆序与置乱

在必要时，可以将向量重新随机排序（需要先引入<random>库）：

template <typename T>
void Vector<T>::unsort(Rank lo, Rank hi)
{
    T *V = _elem + lo; //调整指针
    for (Rank i = hi - lo; i > 0; i--)
        std::swap(V[i - 1], V[rand() % i]);
}
1
2
3
4
5
6
7

对应的，我们可以查询某个序列的逆序数：

template <typename T>
int Vector<T>::disordered() const
{
    int n = 0;
    for (int i = 1; i < _size; i++)
        if (_elem[i - 1] > _elem[i])
            n++;
    return n;
}
1
2
3
4
5
6
7
8
9

排序

排序算法是向量无序转有序的关键，该类算法多种多样，这里目前只实现比较简单的冒泡排序：

template <typename T>
void Vector<T>::sort(Rank lo, Rank hi)
{
    while (!bubble(lo, hi--))
        ; //当返回sorted=true时，停止扫描
}
1
2
3
4
5
6

下面我们实现扫描交换的算法：

template <typename T>
bool Vector<T>::bubble(Rank lo, Rank hi)
{
    bool sorted = true;
    while (++lo < hi)
        if (_elem[lo - 1] > _elem[lo])
        {
            sorted = false; //判断说明下次扫描可能还会出现逆序
            std::swap(_elem[lo - 1], _elem[lo]);
        }
    return sorted; //只有本次扫描没有出现逆序，则下次一定不会出现逆序，可终止扫描
}
1
2
3
4
5
6
7
8
9
10
11
12

插入与查找

插入单个元素，届时检查容量是否支持该次插入操作，不支持时需要扩容：

template <typename T>
Rank Vector<T>::insert(Rank r, T const &e)
{
    expand(); //若需要，先扩容
    for (int i = _size; i > r;)
        _elem[i] = _elem[i - 1]; //整体后移一位，从后向前
    _elem[r] = e;
    _size++;
    return r;
}
1
2
3
4
5
6
7
8
9
10

这是对于无序向量查找的实现，顺次查询：

template <typename T>
Rank Vector<T>::find(T const &e, Rank lo, Rank hi) const
{
    while ((lo < hi--) && (e != _elem[hi]))
        ; //当匹配到对应的e后停止，并返回秩
    return hi;
}
1
2
3
4
5
6
7

有序向量查找

二分查找是查找有序序列常见的思路，对于分切点的选取，我们给出两种策略：

1. 区间中点作为切割点（三分支，比较两次）：

template <typename T>
static Rank binSearch(T *A, T const &e, Rank lo, Rank hi)
{
    while (lo < hi)
    {
        Rank mi = (lo + hi) >> 1; //取区间中点
        if (A[mi] > e)
            hi = mi; //若中点值大于目标值，转移至前驱区间[lo, mi)
        else if (A[mi] < e)
            lo = mi + 1; //若中点值小于目标值，转移至后继区间(mi, hi)
        else
            return mi; //若中点值等于目标值，返回中点的秩
    }
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

对该算法可行性的检验可以通过列举一些退化的例子，如只有三个元素：<、<、=或<、<、>，以及=、>、>和<、>、>。

需要注意的是，最后一个元素实际不参与比较或根本不存在，只是一个哨兵元素。

2. 斐波拉契（黄金分割）分段点：

二分查找本质上是一种“减而治之”的查找策略，它并不约束查找中点（mi）的位置。我们可以按照黄金分割比来确定mi的位置：

设向量长度为 n = fib(k) - 1

算法的复杂度基本仅来源于中值的比较，这两种查找方式都是O(logn)级的时间复杂度。但准确来说，以黄金分割率确立的查找策略比前者优于一个常数级。

由于是三分支的查找，至少需要设置两次比较，若目标项在向量首段，则每次迭代需要进行一次比较；若在末段，则需比较两次（因为转向后继区间的代码位于else if，想要转向后继区间，必须先执行if段的代码，这是无法避免的）。

相比于等分策略，黄金分割策略加长了前驱区间（只需一次比较）的长度，即减少了需比较两次的情况，因此理论上性能更优。当然我们也有其他提升性能的方法，比如改进成两分支。

删除

区间批量删除：

template <typename T>
int Vector<T>::remove(Rank lo, Rank hi)
{
    if (lo == hi)
        return 0;
    while (hi < _size)
        _elem[lo++] = _elem[hi++]; //整体前移，若删除区间大于其后缀区间，未覆盖部分不做处理，下次缩容时自动消除
    _size = lo;                    //确定新界限
    shrink();                      //若装填因子过小，缩容
    return hi - lo;                //返回删除元素的个数
}
1
2
3
4
5
6
7
8
9
10
11

单个删除操作：

template <typename T>
T Vector<T>::remove(Rank r)
{
    T re_elem = _elem[r]; //备份将被删除的元素
    remove(r, r + 1);
    return re_elem;
}
1
2
3
4
5
6
7

我们将区间批量删除作为单个删除的子操作，因为批量删除操作相比执行多次单个删除操作所需的时间成本更低。

去重

对于无序向量，只能逐次检查，每次删除一个重复元素：

template <typename T>
int Vector<T>::deduplicate() //无序向量去重
{
    int oldSize = _size; //记录原规模
    Rank i = 1;
    while (i < _size)   //从前向后依次检查，保证每次最多检查到一个重复元素
        (find(_elem[i], 0, i) < 0) ? i++ : remove(i); //若查找到，删除该元素并检查其后继元素
    return oldSize - _size;
}
1
2
3
4
5
6
7
8
9

从前向后逐渐扩大查重范围。

对于有序向量，我们有更方便的去重方式，因为元素都是依次排好的：

template <typename T>
int Vector<T>::uniquify() //有序向量去重
{
    Rank i = 0, j = 1;
    while (j < _size)
        (_elem[i] == _elem[j]) ? j++ : _elem[++i] = _elem[j++]; //查询到首个不重复元素并将其赋值到i的后继位置
    _size = ++i; //重新对规模赋值，未被覆盖的元素不做处理，或等到内存动态规划时删除
    shrink();  //装填因子过小时缩容
    return j - i;
}
1
2
3
4
5
6
7
8
9
10

从前向后依次检查，可批量的删除重复的元素：

这里的删除并不是实际执行的操作，仅通过将不重复的元素赋值到一起，忽略重复的元素来实现。

遍历（批量）操作

我们为两种批量操作都提供了接口：

1. 遍历向量，对每个元素执行函数指针提供的操作：

template <typename T>
void Vector<T>::traverse(void (*visit)(T &))
{
    for (int i = 0; i < _size; i++)
        visit(_elem[i]); //使用传入的函数指针处理
}
1
2
3
4
5
6

2. 遍历向量，对每个元素执行函数对象（一种重载()操作符的特殊类，其实例对象可以像函数一样调用）提供的操作：

template <typename T>
template <typename VST>
void Vector<T>::traverse(VST &visit)
{
    for (int i = 0; i < _size; i++)
        visit(_elem[i]); //使用传入的函数对象处理
}
1
2
3
4
5
6
7

我们可以自定义函数指针和函数对象来执行批量的任务。