这章以向量为例,讲解了如何写接口并实现。
接口与实现
Abstract Data Type vs. Data Structure
抽象数据类型 = 数据类型 + 定义在该模型上的一些列操作
- 抽象定义, 操作和定义
- 不考虑时间复杂度,不涉及数据的存储方式
数据结构 = 基于某种特定的语言,实现 ADT 的一整套算法。
- 与复杂度密切相关
- 要考虑数据的具体存储机制
向量
向量就是抽象数据类型:从数组到向量,循秩访问。
接下来的部分,通过模板类来实现 向量 ADT 接口

- size()
- get(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() 遍历向量并统一处理所有元素
向量模板类定义
那么如何构造 向量 的模板类呢?
"myvector.h" 头文件,主要是对各种成员数据、成员函数的声明
1 | #ifndef MYVECTOR_H_INCLUDED |
可以看到模板类定义主要是以下几个部分:
- 内部函数
- 构造函数
- 析构函数
- 只读接口
- 可写接口
- 遍历接口
模板类和函数定义
先复习一下模板函数和模板类的构造,关键字 typename
typename和class的区别
在c++ Template中很多地方都用到了typename与class这两个关键字,而且好像可以替换,是不是这两个关键字完全一样呢?
相信学习C++的人对class这个关键字都非常明白,class用于定义类,在模板引入c++后,最初定义模板的方法为: template<class T>……
在这里class关键字表明T是一个类型,后来为了避免class在这两个地方的使用可能给人带来混淆,所以引入了typename这个关键字,它的作用同
class一样表明后面的符号为一个类型,这样在定义模板的时候就可以使用下面的方式了:
template<typename T>……
在模板定义语法中关键字class与typename的作用完全一样。
typename难道仅仅在模板定义中起作用吗? 其实不是这样,typename另外一个作用为:使用嵌套依赖类型(nested depended name),如下所示:
1 | class MyArray |
这个时候typename的作用就是告诉c++编译器,typename后面的字符串为一个类型名称,而不是成员函数或者成员变量,这个时候如果前面没有typename,编译器没有任何办法知道T::LengthType是一个类型还是一个成员名称(静态数据成员或者静态函数),所以编译不能够通过。
模板成员函数
定义成员函数的模板函数:
"#include "vector_functions.h""
1 | #ifndef VECTOR_CONSTRUCTOR_BY_COPYING_H_INCLUDED |
可以看到模板类和模板函数的定义,需要加上
template <typename T>...
通过主函数进行测试
"main.cpp"
1 | #include <iostream> |
所以模板类和模板函数的定义,以及使用大致就是这个样子。接下来,对类定义中的声明的成员函数进行定义。既然是作为模板类,当然函数的效率越高越好,所以会涉及到很多算法分析的内容~
可扩充向量:扩容 expand()
通过算法分析得:加倍扩容~
1 | //加倍扩容 |
需要注意的是扩容时,是重新申请地址空间,保证连续?
为什么要使用加倍策略呢?
通过平摊法分析可得加倍扩容累计增容时间是 O(n).
元素访问
需要重载下标操作符 "[]", 复习一波操作符重载
如果 T 不是内置数据类型,那么就需要对下标操作符进行重载。
1 | template <typename T> T& Vector<T>::operator[] ( Rank r ) //重载下标操作符 |
插入 insert()
- 主要是否需要扩容
- 注意元素向后移动的顺序,自后向前
删除 remove()
- 删除单个元素和删除区间
- 删除区间时,需要注意删除顺序,从左到右逐个复制
有序向量的去重
1 | template <typename T> int Vector<T>::uniquify() |

去重高效版的图解。回过头来看,实际上就是解决了一种问题,比如 5 这个元素不在是一步步向前,而是直接就到了最终的位置,这显然更高效。
有序向量的查找
减而治之:
- fibdearch
- binsearch
二分查找
1 | // 二分查找算法(版本A):在有序向量的区间[lo, hi)内查找元素e,0 <= lo <= hi <= _size |
复杂度是 1.5log(n).
fibonacci 查找
fibonacci 查找和 binary 查找本质上差不多,区别就在于 middle 的选取。在比对当前位置失败之后,我们需要比较查找元素与当前位置元素的大小,向左侧深入需要 +1, 向右侧深入需要 +2. 所以这就造成了一种不平衡。

通过公式证明,\(\lambda\) 选在何处时,复杂度最小。
二分查找改进版
二分查找的改进版: 使得向左右两侧深入的代价平衡,不能及时命中轴点所在的元素。牺牲了最好情况,但整体性能更趋于稳定。
1 | // 二分查找算法(版本B):在有序向量的区间[lo, hi)内查找元素e,0 <= lo < hi <= _size |
二分查找最终版
但是,在这之前所有的 search() 算法都未严格满足定义的语义,也就是返回 不大于 e 的元素的最后一个元素的 秩。 - 多个元素命中,必须返回 秩 最大者
- 失败时,应返回小于 e 的最大者(含哨兵 [lo-1])
1 | // 二分查找算法(版本C):在有序向量的区间[lo, hi)内查找元素e,0 <= lo <= hi <= _size |
插值查找
Interpolation search
如果有数据的先验分布,比如是均匀分布的,那么可以根据先验知识有效的提高查找效率。
\[\dfrac{mi-lo}{hi-lo} = \dfrac{e-A[lo]}{A[hi]-A[lo]}\]
这样可以更快的接近所需查找的元素。但是在小范围内,却容易被恶性分布所干扰,比如不满足均匀分布的情况下。
最好的查找方式是:插值查找 -> 二分查找 -> 顺序查找
排序
前面的查找算法都是对应于有序向量的,所以我们需要用排序算法先把向量变得有序起来,这样才能更高效的 查找 或 去重。
冒泡排序
冒泡排序:从后向前逐渐有序
其改进
- 改进一:如果在某一趟循环之后,已经完全有序了,后面的循环也就不需要了。所以需要设置设否有序的标志
- 改进二: 如果数据只是在前缀的一小部分乱序,后缀很多一部分已经有序了。这个时候我们是否还需要亦步亦趋的从后往前一步步的有序呢? 所以可以在一趟交换走完之后,标记出交换的最后位置。然后只需要考虑前缀无序的部分即可。
改进一
1 | template <typename T> //向量的起泡排序 |
自己动手实现一个整体的形式。。
1 | template <typename T> void Vector<T>::my_bubbleSort(Rank lo, Rank hi) |
改进二
1 | // 改进后的冒泡排序 |
归并排序
分治策略:
- 一分为二
- 子序列递归排序
- 合并两个子序列
代码形式就是这样:
1 | template <typename T> //向量归并排序 |
前两个比较简单,那么第三步归并(merge)怎么实现呢? 下图是个实例图解

每次只比较首个元素。
接下来具体如何实现两个子序列的归并。
把两个子序列分别是 B,C. 合并后的序列是 A. 其中复制 [lo, mi) 到 B. C 子序列不需要复制。
1 | template <typename T> //有序向量的归并 |
其中需要注意的是,将 B 和 C 接到 A 中时,跳出循环的条件是:
( j < lb ) || ( k < lc )
即两个子序列都越界了。
但其实 B 已经越界后,C 后面的并不需要一一复制到 A 中。所以这里也是可以改进的。
1 | for ( Rank i = 0, j = 0, k = 0; j < lb ; ) { //B[j]和C[k]中的小者续至A末尾 |
所以两个条件分别是:
- B 还没越界,并且 B 中元素较小, 则 B -> A
- B 已经越界,或者 B 中元素较大, 则 C -> A.
邓老师提供了一个思路,假设 B 已经越界,可以理解为在哨兵处有一个无穷大的元素,那么等同于 B 中元素始终较大。
课后习题
