【数据结构（邓俊辉）学习笔记】向量01——接口与实现

0.意图

一方面是将工作学习中零星的知识点串起来，另一方面向量是其他数据类型的基础，比如栈队列等，所以基础知识打捞。

1、概述

介绍vector向量的接口与实现

2 从数组到向量

理解：
抽象与泛化：按照面向对象思想中的数据抽象原则，可对以上的数组结构做一般性推广，使得其以上特性更具普遍性。
管理维护更加简化：内存缩放均由内部判断。
元素类型可灵活选取，便于定制复杂数据结构：不再限定同一向量中的各元素都属于同一基本类型，它们本身可以是来自于更具一般性的某一类的对象。另外，各元素也不见得同时具有某一数值属性，故而并不保证它们之间能够相互比较大小。

3 向量ADT接口

这些为基础操作接口，后续扩充接口多为扩展和变形。所以了解清楚基础接口非常重要。

4 Vector 模板类

以上向量操作接口，可能有多种具体的实现方式，计算复杂度也不尽相同。

using Rank = unsigned int; //秩
#define DEFAULT_CAPACITY  3 //默认的初始容量（实际应用中可设置为更大）

template <typename T> class Vector { //向量模板类
protected:
   Rank _size; Rank _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 ); //扫描交换
   void bubbleSort ( Rank lo, Rank hi ); //起泡排序算法
   Rank maxItem ( Rank lo, Rank hi ); //选取最大元素
   void selectionSort ( Rank lo, Rank hi ); //选择排序算法
   void merge ( Rank lo, Rank mi, Rank hi ); //归并算法
   void mergeSort ( Rank lo, Rank hi ); //归并排序算法
   void heapSort ( Rank lo, Rank hi ); //堆排序（稍后结合完全堆讲解）
   Rank partition ( Rank lo, Rank hi ); //轴点构造算法
   void quickSort ( Rank lo, Rank hi ); //快速排序算法
   void shellSort ( Rank lo, Rank hi ); //希尔排序算法
public:
// 构造函数
   Vector ( Rank c = DEFAULT_CAPACITY, Rank s = 0, T v = 0 ) //容量为c、规模为s、所有元素初始为v
   { _elem = new T[_capacity = c]; for ( _size = 0; _size < s; _elem[_size++] = v ); } //s<=c
   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; } //判空
   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 ( 0 >= _size ) ? -1 : search ( e, 0, _size ); }
   Rank search ( T const& e, Rank lo, Rank hi ) const; //有序向量区间查找
// 可写访问接口
   T& operator[] ( Rank r ); //重载下标操作符，可以类似于数组形式引用各元素
   const T& operator[] ( Rank r ) const; //仅限于做右值的重载版本
   Vector<T> & operator= ( Vector<T> const& ); //重载赋值操作符，以便直接克隆向量
   T remove ( Rank r ); //删除秩为r的元素
   Rank remove ( Rank lo, Rank hi ); //删除秩在区间[lo, hi)之内的元素
   Rank insert ( Rank r, T const& e ); //插入元素
   Rank insert ( T const& e ) { return insert ( _size, 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 ); } //整体置乱
   Rank dedup(); //无序去重
   Rank uniquify(); //有序去重
// 遍历
   void traverse ( void (* ) ( T& ) ); //遍历（使用函数指针，只读或局部性修改）
   template <typename VST> void traverse ( VST& ); //遍历（使用函数对象，可全局性修改）
}; //Vector
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
54
55

通过模板参数T，指定向量元素的类型。使其可以存放各种数据类型，更加通用。
Vector类中包含基本接口外的其他接口，判空接口empty()，区间删除接口 remove ( lo, hi )，有序向量接口sort（）多为基础接口的扩展和变形。

5 构造与析构

向量对象的构造与析构，将主要围绕私有变量量_capacity、_size和数据区_elem[]的初始化与销毁展开。
向量中秩为r的元素，对应于内部数组中的_elem[r]，其物理地址为_elem + r

5.1默认构造方法

根据初始容量向系统申请空间，创建数组_elem[]；若容量未明确指定，则使用默认值DEFAULT_CAPACITY。规模的变量_size初始化为0。

 Vector ( Rank c = DEFAULT_CAPACITY, Rank s = 0, T v = 0 ) //容量为c、规模为s、所有元素初始为v
   { _elem = new T[_capacity = c]; for ( _size = 0; _size < s; _elem[_size++] = v ); } //s<=c
1
2

5.2基于复制的构造方法

以某个已有的向量或数组为蓝本，进行（局部或整体的）克隆

复制构造接口如下

 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 ); } //区间
1
2
3
4

公用的基础接口为copyFrom（）方法，接口与实现

template <typename T> //T为基本类型，或已重载赋值操作符'='
void Vector<T>::copyFrom ( T const* A, Rank lo, Rank hi ) { //以数组区间A[lo, hi)为蓝本复制向量
   _elem = new T[ _capacity = max<Rank>( DEFAULT_CAPACITY, 2 * ( hi - lo ) ) ]; //分配空间
   for ( _size = 0; lo < hi; _size++, lo++ ) //A[lo, hi)内的元素逐一
      _elem[ _size ] = A[ lo ]; //复制至_elem[0, hi - lo)
} //用const修饰，保证A中的元素不致被篡改；运行时间 = O(hi-lo)
1
2
3
4
5
6

copyFrom()首先根据待复制区间的边界，换算出新向量的初始规模；再以双倍的容量，为内部数组_elem[]申请空间。最后通过一趟迭代，完成区间A[lo, hi)内各元素的顺次复制。
若忽略开辟新空间所需的时间，运行时间应正比于区间宽度，即O(hi - lo) = O(_size)。
默认的运算符"="不足以支持向量之间的直接赋值，重载向量的赋值运算符。

5.3 析构方法

同一对象只能有一个析构函数，不得重载。

只需释放用于存放元素的内部数组_elem[]，将其占用的空间交还操作系统。

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

_size和 _capacity的内部变量无需做任何处理，他们将作为向量对象的一部分被系统收回，此后及无需也无法被引用。
若不计系统用于空间回收的时间，整个析构过程只需O（1）。

若向量中的元素是指向动态分配对象的指针或引用，故在向量析构之前应该提前释放对应的空间。
工作中经验来看，autosar c++中要求使用智能指针，好处一是内存占用小，二是当引用计数为0时，可以自动释放。