数据结构与算法（2）向量

1.接口与实现

我们首先需要辨析一组非常相关但是又非常容易弄混的概念，也就是抽象数据类型以及数据结构。那么什么是Abstract Data Type呢？以及什么是Data Structure呢？可以从字面上给出定义，抽象数据类型就是在一组数据的模型上定义的一组操作。数据结构则是基于某种特定的语言真正实现的一套完整的算法。

Data Type数据类型，比如在高级程序设计语言中int也就是整型，这就是一个数据类型，而float也是，还有char，诸如此类地。这种数据类型能够让我们能定义其中的一个成员，比如n是一个整数，从此以后我们就可以使用它了，我们也可以定义x是一个浮点数，c是一个字符。

int n;
float x;
char c;

凡是这样指定了某一个元素是来自于某一个数据类型，或者说属于某一个数据类型，那么它就自然地具有了这种数据类型的特点，包括支持相应地处理方法，比如说运算。那么这里那些操作的运算具体是如何实现的，我们并不知道，我们也并不需要知道，这是最重要的。

把这样的一个概念抽象出来施加到我们所将要实现的数据结构上，比如这一章要介绍的vector。我们希望在使用的时候能够参照数据类型的这种形式，把它等同地当作是一个数据类型，比如可以用类似的方法来定义一个vector结构，包括下一章将要介绍的List。

这种使用方法使得我们可以将数据结构与数据类型等同起来，我们只需要知道它所提供的那些操作，比如说向量的查找、排序，而不需要去关心它其中的细节，比如说这些操作是如何实现的。那么从这个意义上讲，它就是一个经过了抽象以后的数据类型，所以称之为Abstract Data Type。

举个例子：可以将数据结构比喻成某种产品，比如说汽车，相关的有两类人，首先是用户，我们笼统地称之为应用Application，另一类人是汽车这种产品的设计和制造者，称之为实现Implementation。这两类人所关心的以及他们的职责是不同的，作为用户而言，他只关心这种产品的外在特性，能够提供的功能；而实现者则需要对这些功能以及特性具体如何落实负责。在这二者之间实际上是有某种形式的一个协议，也就是使用说明书，产品手册。而这种手册或者说明在数据结构的使用者与数据结构内部算法的设计者之间，达成了这么样一个协议，两类人可能互不见面，互不相识，但是他们通过这样一个规范，可以很好地彼此沟通，并且有效地合作。

1.1.向量ADT

1.1.1.从数组到向量

向量实际上是C++等高级编程语言中数组这种数据组织形式的一个推广和泛化。实际上在这些高级程序设计语言中所谓的数组实际上就是一段连续的内存空间，它被均匀地划分为若干个单元，而每一个单元都与0到n之间的某一个整数编号相互彼此对应。这里我们也同样延用此前已经约定的习惯，虽然最后这个第n个元素，实际上未必存在，我们还是把它虚拟地放在这儿作为哨兵，以帮助我们对很多问题的思考，并且使得我们很多算法的实现能够得以简化。

• C/C++语言中，数组A[ ]中的元素与[0,n)内的编号一一对应。

既然每一个这样的元素都与这些编号是一一对应的，所以反过来我们通过合法区间内的编号都可以唯一地来指代并且访问对应的那个元素。一旦知道这个元素的下标i，就可以从A也就是这段存储区域的首地址出发，再向后以s作为间隔去数出i步，就可以得到某一个特定的单元。正因为所有这些元素的物理地址可以按照这样一个线性的方程来确定。所以我们也称之为线性数组（linear array）。

• 反之每个元素均由（非负）编号唯一指代，并可直接访问。A[i]的物理地址 = A + i×s，s为单个元素占用的空间量。

• 向量是数组的抽象与泛化，由一组元素按线性次序封装而成：

  • 各元素与[0, n)内的秩（rank）一一对应
  • 元素的类型不限于基本类型
  • 操作、管理维护更加简化、统一于安全
  • 可更为便捷地参与复杂数据结构的定制与实现

1.1.2.向量ADT接口

按照抽象数据类型的规范，向量结构必须提供一系列的操作接口，可以通过这些操作接口对向量做各种操作，同时也只能通过这些操作接口对向量进行操作，这里的接口功能非常的丰富。

比如说与其它的数据结构一样向量也可以看作是一组元素的集合，所以size( )实际上返回的是其中元素的总数，称之为这个数据结构的规模。也可以从中取特定的元素get(r)，也可以修改其中特定的元素put(r, e)，甚至插入insert(r, e)或者是删除某个元素remove(r)。我们也可以判定一下其中的元素是否已经有序排列disordered( )，如果没有有序排列，可以调用相应的接口使之有序排列sort( )。

我们也可以在它尚未有序排列的时候，按某种算法找到其中特定的元素find(e)，也可以在已经有序的前提下按照某种方式，来找到其中的元素search(e)。当然为了展示一些算法的实现我们也附加了一些其它的功能，比如说能够在无序和有序的情况下分别剔除这个数据集中的重复元素：deduplicate( )和uniquify( ) 。最后也是非常重要的一个接口就是如何对这个数据集中的元素逐一地进行枚举，并且访问一遍traverse( )，称之为遍历。

1.1.3.ADT接口操作实例

下面举例说明ADT接口的实现。

最开始向量与任何一个数据结构一样，初始化的时候都是不包含任何实质的内容的，我们称它是一个空的向量。接下来调用插入操作insert，它在rank为0的这个位置上插入一个元素9，所以向量的组成将由空变成包含一个元素9。接下来继续调用insert接口，在0号这个位置上rank为0的这个位置上插入一个元素4，原来的元素9将会后移一位。同样地，我们也可以调用插入接口在rank为1的位置上插入5，在这个位置上出现了5，而它的后继统一地向后后移了一位。我们也可以调用put接口，这个接口的意思是修改，它会把当前rank为1的那个位置上的元素数值，由原来的5修改为2。我们也可以通过get这个接口获取秩为某一特定值的元素，比如说秩为2的那个元素，实际上就是2这个位置上的9，因此会返回9。

remove接口的参数是2，这说明它希望在原来这个向量中将rank为2的这个元素，把它剔除掉，剔除之后，会把这个被剔除的元素的值作为输出返回，即返回2，同时它的所有的后继与插入时候的操作的现象相反，会向前平移一个单元。当这个时候我们调用size的时候，因为这里所包含的元素总共是6个，所以它会返回6。

我们可以看到在整个这个操作的过程中向量都确实具有这么样一个特点，就是它在逻辑上，甚至在物理上必然是彼此紧邻的排列的，所有的元素之间没有任何的缝隙。需要注意的是无论是此前所介绍的这些接口，还是后面所要介绍的接口，就目前而言，我们并不关心它的具体实现方法，我们关心的只是它的操作语义。

接下来我们可以通过disordered()这个接口来检测向量的有序性，或者更准确地讲它的无序性。在此前介绍bubble sort算法的原理的时候，曾经指出包括向量在内的序列是否有序，当且仅当其中是否存在紧邻的逆序对。那么这里总共有6个元素，共定义了5组紧邻对，其中有3组，也就是4和3、7和4、和9和6是逆序的，disordered会返回逆序对的个数，即是3，只要这个数值不是0，就说明它尚未构成有序的序列。

对于这样的一个无序向量我们已经可以通过find接口，来查找其中特定的某个元素，比如说9。可以看到9号元素是位于rank为4的位置，因此find会返回4。同样地，也可以查找比如说5，我们发现5并不存在，这个时候我们统一地约定返回一个数值是-1，这个-1肯定不是一个合法的rank，表示查找失败。接着我们可以通过sort这个接口对整个向量排序，接下来再调用disordered()这个接口，它已经没有任何逆序的紧邻对了，所以返回0。

对于有序向量，我们可以通过另一套接口，也就是search来进行查找。比如说可以首先通过search，然后引用9来查找数值为9的元素，这个元素的rank为5，因此返回的是5。那么如果查找8会怎么样呢？向量中并没有8，这里我们采用了另一种约定：如果没有找到这个元素，我们要找的是不超过这个元素的最大的那个元素的值。对这个例子而言不超过8的最大的元素实际上就是7，而7的秩是4，所以search(8)会返回4。同样 我们如果要去查找10的话会返回不超过10的最大的那个元素也就是9的秩5，因此search(10)会返回5。

另一种特殊情况：查找一个全局都没有而且小于全局的最小的那个元素的数比如说1，我们会假设在-1的rank这个位置上有一个假想的哨兵，它的数值是负无穷，所以search(1)返回的是-1。这样一套约定可以使得我们在语义上更加的明确，使得我们在后续的操作过程中可以便利地来搭建不同的算法。还有一点要注意的是：在有些时候，我们要查找的元素尽管有，但是它却有多次出现，比如说这个4 出现了两次，那这个时候会返回什么呢？同样跟这里的语义所定义吻合的是，我们要返回其中不超过4这个目标元素的最后边那个元素，所以如果有两个甚至多个4的话，我们会取其中rank最大的那个元素把它的rank返回，对这个例子而言也就是2号元素，因此search(4)会返回2。

最后，uniquify()对于一个有序的向量把所有的重复的元素，比如说4都剔出掉，只保留一个拷贝。

1.2.vector模板类

有上述接口规范之后，我们就可以遵照这种规范来学习如任何具体地在C++语言平台上实现这样一种向量模板类vector结构。首先约定用int来定义这里所说的秩这种概念，接下来会首先采用一种基本的扩容方式，它的初始容量需要设定，这里不妨取它的DEFAULT_CAPACITY取作3，在实际应用中完全可以取更大的一个数。

下面通过template这种方式给一个模板参数T，它的意思可以认为是定义了一个vector这样的模板类。其中的元素类型是什么可以是将来指定的任何名字现在叫作T的类型。所以与其说它写的是一个类，不如说这个模板类给的是一系列的类，我们可以根据实际需要直接地生成相应的vector类。在模板类里面有一些私有的，也就是封装和隐藏起来的变量，比如说其内部会记忆它到底有多少个元素有一个_size ，以及它目前的容量_capacity，还有
包括真正存放元素的一个空间_elem。其它的内部函数以及公开的接口函数会在后边陆续学到。

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 ); //扫描交换
  void bubbleSort ( Rank lo, Rank hi ); //起泡排序算法
  Rank max ( 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 ( int c = DEFAULT_CAPACITY, int 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的元素
  int 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 ); } //整体置乱
  int deduplicate(); //无序去重
  int uniquify(); //有序去重

// 遍历
  void traverse ( void (* ) ( T& ) ); //遍历（使用函数指针，只读或局部性修改）
  template <typename VST> void traverse ( VST& ); //遍历（使用函数对象，可全局性修改）
}; //Vector

vector模板类的原理：整个vector结构是被封装起来，能供来自各种应用的用户使用的操作接口就是interface框中vector，~vector，insert，remove等等，它们就相当于vector结构的使用说明书，它告诉我们这里提供了哪些操作渠道、途径，通过这种接口规范直接使用。经过了这样地一个剥离之后，使得我们的应用和实现相互之间可以很好的分工，又同时很好的协作。
那么具体内部怎么实现的呢？可以看出其实是开辟了一个名字叫作_elem的数据区，它的容量至少要足以容纳所存放的有效数据，对外而言的每一个元素都通过某种形式转译为内部这段数据区中的，实际上是这个有效的数据区（_size）中的某一个元素，由此实现了对内部数据项的封装。

1.2.1构造与析构

作为一种数据结构与所有的类一样，vector也首先需要解决构造和析构的问题。向量的默认的构造实际上只需指始初始的容量就可以了，如果没有指定会按照默认的容量，指定一个数值。在内部的操作其实就是通过new申请一个长度为c，基本类型就是模板参数T的一段连续的数据空间。在创建了这样一个空间之后，我们把这个空间的首地址交给内部的_elem记下来。这个时候虽然它有一定的空间，但是其中有效的数据是没有的，所以这就是为什么_size初始化是0。

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

当然还有其它的一些构造的方法，比如如果已经有一组以数组的形式存放的数据，我们也可以将其中从lo到hi的这段区间中的元素取出来作为初始向量，可以看到它是通过调用一个叫作copyFrom()的内部接口实现的。同样地 它还重载了其它的一些形式，比如被复制的元素可能是来自于一个数组，而是来自于一个本身已经被封装了的向量，我们可以从这个向量的_elem区域中去读取出来，并且同样调用copyFrom()来做这件事。所以这里有区间的复制，也可以有对整个向量的一个克隆。

Vector(T const *A, Rank lo, Rank hi)
  { copyForm(A, lo, hi);}           //数组区间复制
Vector(Vector<T> const &V, Rank lo, Rank hi)
  { copyForm(V._elem, lo, hi);}     //向量区间复制
Vector(Vector<T> const &V)
  { copyForm(V._elem, 0, V._size);} //向量整体复制

内部操作接口copyForm( )的工作原理以及过程可以通过下图示意，工作原理以及过程，可以通过这个图来示意。一般地我们需要从一个数组A中将介于lo到hi之间的元素整体复制到当前仍然为空的一个向量中，具体的操作大概分为两步，首先在向量内部开辟出足够的空间，接下来再将区间内的元素逐一地复制过来。

这个过程可以描述并且实现为下面的C++代码：首先申请足够多的空间，这里需要再强调一下这个区间的宽度可以直接通过lo和hi之间的一个减法得到，这是因为当我们在描述一个区间的时候往往是用左闭右开的形式，所以换而言之这个lo是在这个区间中最靠左的那个元素，而hi是在右侧第一个不属于这个区间的那个元素，尽管hi这个元素有可能压根就不存在。但是我们不妨把它统一地理解成是一个哨兵，这样的话我们就可以通过，hi减lo直接得到区间的宽度。

这里给计算出的宽度再乘个2，也就是说我们实际开辟的空间是我们需要复制的空间的两倍，而不是恰好那么多。这样做的主要的目的在于预留了一些空间之后，就可以使得我们在接下来足够长的时间之内，不会因为有必要扩容而打断我们的计算过程。

template <typename T> //元素类型
void Vector<T>::copyFrom (T const* A, Rank lo, Rank hi)//以数组区间A[lo, hi)为蓝本复制向量
{ 
  _elem = new T[_capacity = 2 * ( hi - lo ) ]; _size = 0; //分配空间，规模清零
  while ( lo < hi ) //A[lo, hi)内的元素逐一
  _elem[_size++] = A[lo++]; //复制至_elem[0, hi - lo)
}

接下来还需要对这个向量的有效规模进行初始化 把它清为0。

再接下来 就是复制过程也就是说我们对于lo和hi中间的每一个Rank，都要从A这个数组中取出对应的元素，并将它们顺次的存入到_elem，对应的区间里面去。整体循环构成了这个操作的最重要的部分，所以我们也可以看出算法的复杂度主要是来自于这样一个循环。这样一个主体的复杂度是取决于被复制元素的个数，或者说这个复制区间的宽度，也可以认为是这个向量通过复制被创建之后的初始规模。

析构函数只需要把这个曾经动态分配获得的数据区域释放掉，归还给操作系统。

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

这样的话我们就完成了向量这种最基本的结构作为一种模板类它的最基本的一些接口，接下来会学习功能更为复杂的其它的接口。

2.可扩充向量

与所有的数据结构一样，向量也可以认为是一组数据项的集合，换而言之，它首先必须能够自适应地在规模上适应其中所包含的元素个数的变化，这一节集中讨论它的可扩充性能。向量本身并不具有这种性能，我们需要采取一些策略。就目前的设计方案而言，我们的向量并不具备可扩充的性能，究其原因在于它采用的 实际上是所谓的静态空间管理的策略。

2.1.静态空间管理

具体来说，它实际上在内部只不过是设置了一个私有的数组，这个数组所占有的那段连续的地址空间会被用来存放若干个对外界而言可见的，或者是有效的元素。这些元素的总数，或者说它们所占用的逻辑空间的数，用_size来表示，而整个物理空间的大小是由_capacity来确定的。

这里的问题是_capacity一旦确定,按照目前的方案它就将一成不变，而这样一种策略显然存在明显的不足。这种不足体现在两个方面：第一 是有可能会出现所谓的上溢overflow，也就是说随着有效元素（个数）的增加，总会出现这样的可能，使得整个_elem所占用的物理空间已经不足以存放需要存放的元素组。尽管这个时候在系统的其它的部分仍然有足够多的空间可以用于存放这些元素，但是限于_capacity是固定的，我们不能直接做到这一点。

另一种情况虽然不是很严重，但是也是会造成一定的空间的效率低下，我们称之为下溢underflow。具体来说就是有可能我们开辟了一个比较大的空间，但是在整个这个数据结构的生命期内真正存放于其中的数据却寥寥无几，从而使得装填因子指标会非常非常的小，这个装填因子其实就是有效元素个数，也就是_size ，去除以可用于存放元素的空间总数_capacity，也可以理解成是空间的利用率有可能不到一半，甚至远远地低于一半，那么在这种时候空间效率非常低下。

很遗憾如果我们坚持采用这样一种固定容量的策略，我们在实际的一般应用环境中，很难在事先就预测到我们需要用多少空间，也就是说这种空间不足以及空间浪费的情况，都有可能发生甚至经常发生。

那么如何使得向量可以自适应地根据实际需要来动态地调整自己的容量呢？而且这种调整的过程既能保证足够同时又不致使得因为开辟的空间过多而导致空间效率的低下。

2.2.动态空间管理

为了解决上述的问题，我们需要把刚才所采用的静态空间管理策略改变为所谓的动态空间管理策略，就是如果在某个时刻，某一个向量即将发生上溢，那么我们就适当地扩大内部数组的容量，使之足以容纳新的元素。按照这样一种策略向量的生命期可以大致由下面一组图来表示。

最开始的时候向量所存放的有效元素还不是很多，还不致于出现上溢的情况，这时候可以从容应对。但是剩余的空间有可能会逐步地被占用，直到某一个关键时刻，内部数组有可能已经饱和，这时就存在一个风险也就是说再插入一个元素的话，就会导致上溢。为此我们可以动态的申请另一段存放空间，当然它的大小应该比原来的有所增长。接下来我们要把原先已经存放好的那些有效元素，逐一地按次序地复制过来，从而使得它们对外界而言依然保持原貌。新多出来的这些空间就足够用以存放新需要插入的元素，而原来所占用的空间将在此之后被释放并且归还给系统。上述这样一个完整的调整过程可以描述并且实现为下面的c++的代码：

template<typename T>
void Vector<T>::expand() {    //向量空间不足时扩容
	if (_size < _capacity) return;   //尚未满员时，不必扩容
	_capacity = max(_capacity, DEFAULT_CAPACITY);   //不低于最小容量
	T* oldElem = _elem;
	_elem = new T[_capacity <<= 1];  //容量加倍
	for (int i = 0; i < _size; i++)  //复制原向量内容
		_elem[i] = oldElem[i];       //T为基本类型，或已重载复制操作符'='
	delete[] oldElem;   //释放原空间
}

首先要判断现在是否处于即将发生上溢的临界状态，它的标志就是_size是否还继续严格地小于_capacity。如果是还不存在上溢的风险，可以直接返回，所以这里隐含着有一个else，即接下来_size虽然不一定大于_capacity，但是至少会出现等于_capacity的情况。

这时我们要做的是将原来的那个数据域做一个备份，接下来以原先的容量（注意这里是左移一位，相当于加倍）加倍的一个新的容量来申请一段动态空间，并且将这段空间交由原来的_elem来指示。接下来是复制，对从原先的那个数据域中逐一地取出各项，并且将其转移至新的这个数据域中对应的位置。在整体赋值完之后，原先的这个空间已经没有任何存在的意义了，所以通过delete操作将它释放。

其实对于尚未封装的数组同样可以采用上述的这样的一个策略，而对于向量而言，这里调整的优势体现在向量整体的封装性上。因为对于一般的数组，如果它经过了动态的重新分配地址，那么原先指向它内部的某些元素的一些指针就有可能会出现无效，即虽然它能指向一个地址但其中并没有存放所需要的数值。但是对于向量而言经过了这样的封装以后就安全了，因为无论是此前此后我们在访问某一个具体的元素的时候，在内部都是通过_elem这个统一的指示器来标识空间的起点。从这一点也可以看出进行封装以后的一个好处。

那么为什么要采用一个容量加倍的策略呢？采用其他策略，比如适当增加背部数组的容量，是否也可行呢？

2.2.1.容量递增策略

实际上情况并不那么简单，我们不妨以其中的一种典型的策略，即容量递增策略，来做一个对比。就是每当发现
当前的内部数组即将发生上溢我们并不是对它进行容量的加倍，而只是在原来的容量的基础上追加一个固定的数额，这样看起来并没有什么问题。在代码上只需将原来的_capacity*2变成_capacity追加一个固定的数额，记为INCREMENT，简记作$I$。下面来考虑这个策略的效率。

• 在即将上溢之前，追加固定大小的容量

T* oldElem = _elem;
_elem = new T[_capacity += INCREMENT];

• 最坏情况：在初始容量0的空向量中，连续插入$n = m * I$个元素（远大于2）
• 于是，在第$1, I+1, 2I+1, 3I+1,……$次插入时都需要扩容
• 即便不计申请空间操作，各次过程中复制原向量的时间成本依次为：$0,I,2I,\dots,(m-1)I$（算术级数）
• 总体耗时 = $I\times(m-1)\times m/2=O(n^2)$，每次扩容的分摊成本为$O(n)$。

2.2.2.容量加倍策略

• 在即将上溢之前，使容量加倍

T* oldElem = _elem;
_elem = new T[_capacity <<= 1];   //容量加倍

• 最坏情况：在初始容量1的的满向量中，连续插入$n=2^m$个元素
• 于是，在第$1，2,4,8,16,32，\dots$次插入时都需要扩容
• 各次扩容过程中复制原向量的时间成本依次为：$1,2,4,8,\dots,2^m$ （几何级数）
• 总耗时 = $O(n)$，每次扩容的分摊成本为$O(1)$。

造成两种方法每次扩容分摊成本的时间复杂度出现很大差别的原因，可以用下图说明。实际上在向量规模不断递增
达到某一固定的数值之前，如果采用的是递增式的增容策略，那么所需增容的操作必然是按当时的规模呈算数级数的形式分布。反过来如果是以倍增式的策略来进行的扩容，那么只需要进行其中的少数几次扩容就够了，具体来说就是这些以紫色标明的，可以看到要远远小于原先的数目，而且随着数组规模的增加，这种差异会更加的明显。

我们不妨将这两种策略所对应的性能列成如上面的一张表。在时间方面，在达到一个固定的规模n之前，累计所用的扩容时间：递增策略要多达$O(n^2)$，而倍增策略只需要$O(n)$，如果从分摊的意义上讲分摊到每一次扩容所需要的时间：前者是$O(n)$， 而后者是$O(1)$。可以看到就时间而言，容量加倍策略具有巨大的优势。而在空间方面，前一种策略似乎要非常好，因为它总是每次增加一个固定的数额，所以随着向量规模的增加，整个空间的利用率会越来越接近于百分之百。而加倍策略未必能做到百分之百，但是它至少有个底线，至少是50%，只有在它即将发生上溢，而因此刚刚通过加倍扩容的那个瞬间时才会是50%。所以相对而言，可以理解为倍增策略是通过在空间的效率上做了一个适当的牺牲，来换取在时间方面的巨大的收益，显然收益要远远大于损失。

2.3.平均分析 vs. 分摊分析

平均复杂度或期望复杂度（average/expected complexity）

根据数据结构各种操作出现概率的分布，将对应的成本加权平均。

• 各种可能得操作，作为独立事件分别考查；
• 割裂了操作之间的相关性和连贯性；
• 往往不能准确地评判数据结构和算法的真实性能。

分摊复杂度（amortized complexity）

对数据结构连续地实施足够多次操作，所需总体成本分摊至单次操作。

• 从实际可行的角度，对一系列操作做整体的考量；
• 更加忠实地刻画了可能出现的操作序列；
• 可以更为精确地评判数据结构和算法的真实性能

3.无序向量

回顾前两节，我们以向量为例给出了数据结构定义的一种通用方法，即模板，大致格式如下：

template <typename T> Vector { ...... };

这种方法实际上定义了 一系列的Vector，在使用的时候可以灵活指定它的类型。如果尖括号里是int的，那这个Vector实际上是a Vector of integers，即由一系列的整数组成的向量。更重要的是 在以后我们将利用这种方式来构造更为复杂的数据结构，比如可以把某些数据结构作为基本的组成元素来构成向量，举个例子在后面的学习中会定义二叉树Binary Tree这样一种数据结构，如果把BinTree作为基本的元素来构成Vector，那我们就可以构成一个由一系列的二叉树构成的一个线性序列，也就是A Vector of Binary Trees，取个形象的名字可以叫它forest 森林。在后面介绍霍夫曼编码的时候也会用到这种技巧，通过采用统一的模板式的方法，可以使得数据结构的定义非常的规范，而且更重要的是它们可以互相的融合组合，便捷地搭建更为复杂的数据结构。

Vector<int> myVector1;
Vector<float> myVector2;
Vector<char> myVector3;

Vector<BinTree> forest;

这一节我们将围绕向量的最基本的形式，即无序向量来展开。无序向量不一定是说其中的元素没有顺序，甚至有时候其中的元素是根本就不可能排成顺序。在这样的一个前提下我们将研究如何来定义并且实现相应的操作接口。

3.1.循秩访问

通过V.get(r)和V.put(r, e)接口，固然可以读，写向量元素，但便捷性远不如数组元素的下标式访问方式A[r]。通过重载下标操作符“ [ ] “，便可沿用数组的下标方式访问向量元素。对于任何一个指定的Rank r，只需在内部数据区中取出对应的第r号元素，此后凡是需要引用向量中的某个特定的比如说Rank为r的这个元素，就可以直接以这样一种类似于数组下标的形式进行引用。

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

此后，对外的V[r]即对应于与内部的V._elem[r]。这种引用可以作为右值，以这种类似数组形式进行运算并且将运算的结果，向左侧赋值给某一变量；而反过来计算的结果也可以赋值给向量中某一个元素，也就是作为左值，因为这个接口返回值是一个引用。

• 右值：T x = V[r] + U[s] * W[t]

• 左值：V[r] = （T) (2*x + 3)

需要注意的是这里我们对入口参数r并没有做过多的检查，而是简易地在入口处增设了一个断言，用以提醒使用者保证入口参数r能够在合理的范围之内，但在真正的实际应用中，要做更为严格的处理。

3.2.插入

向量的插入算法具体来说就是如何将某一个特定的元素插入到向量的特定位置，在原来向量中因为所有的元素都必须是紧邻排列的，所以为了能够插入新的元素我们需要做一个调整，也就是将对应这个位置之后的所有的那些元素，称作它的后继，整体的构成一个后缀，进行一个整体的右移操作。这个right shift操作效果就是所有的后缀元素都向右移动一个单元，从而空出一个单，此时才可以将指定的那个元素纳入其中，从而完成插入。

整个算法可以描述并且实现如下的C++代码：

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;      //返回秩
}

右移操作可以通过for循环完成，每个元素确实都是后移一位，当所有的后移完成之后，再将新的那个元素纳入到rank所指的位置上，当然同时还要更新整个向量的规模。

有两个需要注意的地方：第一，在for循环的方向是从最后一直向前不断地递减，也就是说整个的移动的方向虽然是向右，但是所有元素移动的先后次序却是后优先的，用图来表示也就是最后这个元素先移动，接下来是次后这个元素，再往前一直直到最前面的那个元素。这是必要的，如果把这个次序颠倒过来会有危险，会出现数据在无意中被覆盖的问题。

第二个主要注意的是expand()，即扩容操作，这是有必要的。因为确实在某些时候这个向量可能已经是满载的，所以为了插入新元素，在后移的过程中必然会出现上溢的情况，在这种时候就需要对向量进行扩容处理，比如上节的容量加倍策略，这样一件事情完全由expand()完成。

3.3.删除

3.3.1.区间删除

我们先考虑一个通用的一个版本，即区间删除，具体来说就是在某个向量中，我们要将介于lo和hi之间的一系列的元素成批地从中剔除掉。因为向量要求所有的元素始终都是彼此紧邻排列的，所以不应该在删除之后留下这个缝隙，换而言之，我们需要将它后继的那些元素（如果有的话）统一地向前或者说向左移动来填补这段空白。其实可以反过来看到如果能够完成这样的一个左移的话，那么实际上也就相当于把这些元素给剔除或者叫覆盖掉了，所以关键的任务在于如何实现这个左移。

这样的一个过程可以实现为下面代码：

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

代码中最关键的是while循环，它会遍历整个后缀，并且将其中的每一个元素逐一地取出，向前转移到合适的位置。比如第一个转移的是hi这个位置上的这个元素，它将被转移到lo这个位置，紧接着是hi+1转移到lo+1，hi+2转移到lo+2，直到最后。

同样有两个问题需要强调说明：第一个问题，在整个移动的过程中，所有这些元素参与移动的先后次序，同样也是很敏感的，或者说不能更改的，与插入算法完全颠倒，插入算法是自后向前，而区间删除算法是越往前的元素越优先参与移动，所以我们也可以认为它是一个自前向后的前移操作。如果把这个次序颠倒过来是有风险的，比如两者，即前缀的原来的那个位置和后来的那个位置中间有相互重叠的部分，如果优先移动后面的那个元素，那么就有可能会造成重叠区间的元素在无意中被覆盖掉。

第二点是shrink()这个历程的调用，它是某种意义上讲的缩容，这种操作在实际应用中并不是必须的，我们往往可以忽略它。

3.3.2.单元素删除

上一小节中实现了区间的批量删除的接口，所以我们不妨把单元素的删除视作是整个区间操作的特例。具体来说
，就是要将任何一个由单个元素构成的区间视作是由 r 到 r+1所定义的左闭右开的那段区间。这样就可以很简明地调用用此前重载的那个remove接口，只不过这里的参数改变为 r 和 r+1，与我们刚才的那种转换相对应。同理算法所进行的操作就是所有的后缀向前移动一个单位。

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

那么反过来，基于remove(r)接口，通过反复的调用，实现remove(lo, hi)是否可行呢。理论上是可行的，对于一个特定的一段从 lo 到 hi的区间，我们可以对其中的每一个元素分别去调用一次单元素删除接口，从而完成整体的删除操作。但是正如我们一直强调的，数据结构更多关注的是效率，而从效率上看这样做是非常差的。

首先考虑单元素删除本身的效率，最重要的实际上是这段区间也就是被删除元素的那些后继们，统一地要向前移动一次，这也是它的复杂度的来源。因此它的时间复杂度是取决于它的后继的个数，即为n-hi，最坏情况下是$O(n)$。如果按这种方式反复调用，有可能会导致$O(n^2)$的复杂度，在效率上是不能接受的。

3.4.查找

查找即是按照某种特定的条件，从向量中找出特定的元素。首先我们要明确两个概念：判等与比较，对于任何的两个元素，我们来判断它们是否是相等，或者是比较它们之间谁大谁小，这两个操作并不是所有的类型都天然支持的。所以这里我们做一个假设：向量中元素的类型是基本类型，或者向量元素这个类已经重载了对应的判等的操作符或者是比较的操作符。无序向量可以一般性地认为它只支持判等操作，而对于有序向量，要求要更高一点，它还需要支持其中的元素能够相互比较大小。

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

无序向量的查找过程可以描述为下图，如果查找的区间范围是 lo 到 hi 的话，就从 hi 出发逆向地、逐一地取出
向量中的各个元素与目标元素进行比对，如果不相等就忽略它，进而考察它的前驱，所以整个的工作会亦步亦趋地逐个地遍历向量中的所有的元素。

经过这样一个逆向地扫描的过程，我们很有可能在中间的某一步找到所需要的那个目标，即查找成功；如果一直持续到最后，在试图越过lo也就是合法的最左侧的边界的时候，就可以断定整个查找是失败的。这个算法可以通过下面的代码实现：

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

需要注意的是，find函数返回的都是最终停止的那个位置，有可能是合法的一个位置。也可能是刚刚越过左边界的那个非法的位置。而具体判别是否成功可以交给上层的调用者，因为他通过这个秩是否是合法就可以判断查找是否成功，如果是成功的话这样一个秩将可以被高层的算法进一步地利用。

我们也可以看出这个算法的复杂度有很大的变化空间，在最好的情况下，可能在第一个元素位置上就顺利地命中
所以这时复杂度是常数$O(1)$；但是在最坏的情况下，比如一直持续到比较后才发现这个元素，甚至一直持续到最终也没有发现我们的目标元素，为此在这个过程中我们需要扫描的元素可能会与向量的规模相当，复杂度就会是$O(n)$。

这样一种在最好和最坏情况下相差极其悬殊的算法，叫作输入敏感算法（input-sensitive），即它的复杂度具体是多少与输入时候数据的配置紧密相关。

• 输入敏感（input-sensitive）：最好$O(1)$，最差$O(n)$。（对本例而言）

3.5.唯一化问题

无序向量的唯一化问题，即是把其中重复的元素都剔除掉，使得每一组重复的元素只保留一个拷贝。在很多实际的应用中都能够找到唯一化的影子，比如在网络搜索的环境中有很多个不同的结点所分工完成的局部的搜索结果，可能会含有大量的重复的元素，我们需要将其中重复的元素剔除掉，从而得到一份记忆完整同时又不冗余的搜索报告。这样一个算法大致可以通过这样的一个图示来表示它的原理：

对于一个向量，我们总是把它分为三个部分，以当前的这个元素为界，当前这个元素自己是一部分，它的前驱所构成的前缀是一部分，以及对称地，所有的后继是一部分。每一次我们遇到一个新的元素，都在它的前缀中去进行查找，这可以通过find操作来完成的，如果能够找到雷同的元素，比如在某个位置上出现了一个x，就可以把这个元素剔除掉。反之，经过查找以后，如果这个元素没有出现，那么我们就可以把它保留下来，同时再去考察它的下一个元素。这个算法可以由下面的代码实现：

template<typename T>   //删除重复元素，返回被删除元素数目
int Vector<T>::deduplicate() {
	int oldSize = _size;  //记录原规模
	Rank i = 1;      //从_elem[1]开始
	while (i < _size)   //自前向后逐一考查各元素_elem[i]
		(find(_elem[i], 0, i) < 0) ?   //在前缀中寻找雷同者
		i++   //若无雷同者则继续考查其后继
		: remove(i);    //否则删除雷同者（可以是多个）
	return oldSize - _size;  //返回向量规模变化量，即删除元素总数
}

3.5.1.正确性

那么我们如何给出这个算法正确性的严格证明呢？同样根据第一章学到的知识，我们通过挖掘算法所具有的不变性和单调性，来证明一个算法最终的正确性。

首先来证明不变性，我们发现在这个算法运行的任何一个时刻，如果当前所对应的是第i个元素V[i]的话，那么在它所对应的那个前缀中所有的元素必然是彼此互异，即不包含重复元素。当算法开始时i=1，它的前缀只有V[0]。

其余的一般情况下可以用数学归纳法来予以证明：假设当时的状态是第i个元素e，它的前缀是从0到i的区间。按照数学归纳法我们假设在此前不变性是成立的话，那么接下来，无非两种情况，即当前的这次对应的查找成功或者失败。

如果是失败，即在它的前缀中不含元素e，算法给出的处理方法是直接令i++，也就是我们已经指向了它的下一个元素，而将刚才那个元素e归入了新的这个前缀中。既然e和此前的那些前缀是互不重复的，所以将e归入这样的一个区间以后，这个区间必然是不含重复元素的。

反之如果如果查找成功，e出现在它的前缀中，按照算法流程会将它剔除掉，也就是通过删除操作使得后继的元素整体地向前移动，从而使得原先它的直接后继变为当前的这个元素，并且算法继续地运转下去。经过了这样一次迭代之后当前的这个元素虽然换了，但是它的前缀并没有换，这个前缀所具有的元素互异的性质也依然会保持下来。

算法运行到最终是覆盖整个向量，到那时我们所说的当前的元素其实就是最末尾的那个哨兵元素，而它的前缀其实就是整个向量，那么它的前缀中不包含重复的元素其实也就相当于整体的向量中不包含重复的元素，这正是我们这个算法的功能唯一化所要求的，所以在最终这个不变性必然会转化为我们所需要的正确性

接着我们证明单调性，这个算法的主体是由一个while循环构成的，随着反复的while迭代:

• 当前元素前缀的长度单调非降，且迟早增至_size
• 当前元素后缀的长度严格单调下降，且迟早减至0

所以算法待处理元素的个数会严格单调减少，算法必然终止，且至多迭代$O(n)$轮。

3.5.2.复杂度

这个算法的主体是while循环，而在while循环中真正能够造成有效复杂度的是find操作和remove操作，其中find操作是对于当前的元素的整个前缀而言的，而remove操作恰好对称是相对于当前这个元素的后继而言的。所以每一次while循环所需要的成本也就是find和remove两类操作的成本，累计起来也不会超过整个向量的长度，即$O(n)$线性步。而while循环最多会迭代$O(n)$轮，所以这个算法累计起来最多不超过$O(n^2)$的时间复杂度，这也是最坏情况。

这个算法也可以进一步的优化。

3.6.遍历

遍历就是按照某种事先约定的操作（称之为visit），对向量中的每一个元素逐一地、统一地执行一次。所以这里涉及到两个问题：第一，如何来指定或者来描述这样一个visit操作；第二，如何将它传递到向量内部的每一个具体的元素。

通常有两种方法：第一种是使用函数指针，也就是说可以对于vector这样一个类定义一个traverse接口，作为它的参数visit本身就是一个函数的指针。所以为了兑现这样的一个遍历操作我们只需要逐一地取出向量中由这个i确定的每一个元素通过这个函数指针找到这个函数，并且对这个元素实施这个函数所指定的操作。

template<typename T>
void Vector<T>::traverse(void(*visit)(T&)){   //函数指针
	for (int i = 0; i < _size; i++)
		vist(_elem[i]);
}

第二种方式是使用函数对象，也就是说我们指定的这个参数visit，本身就是一个对象，它的作用就是用来模拟一个操作一个函数的一个行为方式。所以同样地，我们也可以对这个向量中的每一个元素都逐一地取出，并且转交给这样一个函数对象，通过它来实施具体地、统一地操作。

template<typename T> template<typename VST>
void Vector<T>::traverse(VST& visit) {       //函数对象
	for (int i = 0; i < _size; i++)
		vist(_elem[i]);
}

这两种方法其实是非常接近，但是也有一些重要的区别，相对而言，后一种方式的通用性更强。

下面通过一个实例来了解如何通过函数对象，实现刚才所说的具体地遍历。比如说，我们可以考虑将向量中的所有的元素统一地各自+1。为此我们只需要实现一个对应功能的函数对象，它本身也是以一个类的形式给出来的。这里为了简化起见使用了struct，而没有进行过多的封装。这个对象最重要的一个作用或者说唯一的作用就是重载了它的圆括号操作符()，从而使得它在行为上与一个函数非常的类似，而具体的功能就是把每一个参数e做一个+1操作。

template<typename T>    //假设T可直接递增或已重载操作符“++”
struct Inciease {       //函数对象：通过重载操作符"()"实现
	virtual void operator()(T & e) { e++; }   //加一
};

在实现了这样一个对应的类之后，就可以通过调用vector统一遍历接口traverse，将我们刚刚编写的这个函数对象以参数的形式传入就可以实现相应的功能，也就是把向量中的每一个元素统一地加一。

template<typename T>
void increase(Vector<T> & V) {
	V.traverse(Increase<T>());   
}