以下笔记为jjyaoao本人制作，欢迎借鉴学习和提出相关建议，转载需要标明出处www.jjyaoao.space

2.向量

接口与实现

抽象数据类型：即自定义的class

数据结构：解决某类问题的可靠模板

ADT即为说明书，也就是接口

Vector

Vector的底层实现

构造器与析构器

使用一次构造器，销毁一次 [] _elem，以便重新调用新的内存空间，_size还需要初始化哈，虽然好像int本身初始化就是0安。

copyFrom函数实现

可扩充容量

静态

动态

算法与策略

无序向量

插入

#include <iostream>
#include "vector.h"


template <typename T>
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++;
}

删除

区间删除

单删除

代码实现

#include "vector.h"
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;
	}
}
template <typename T>
T Vector<T>::remove(Rank r) {
	T e = _elem[r];
	remove(r, r + 1);
	return e;
}

查找

#include "vector.h"
template <typename T>
Rank Vector<T>::find(T const& e, Rank lo, Rank hi)const {
	while ((lo < hi--) && (e != _elem[hi]));
	return hi;
}

归一化-去重

繁琐+错误版

复杂度

优化

template <typename T> Rank Vector<T>::uniquify() { //有序向量重复元素剔除算法（高效版）
0002    Rank i = 0, j = 0; //各对互异“相邻”元素的秩
0003    while ( ++j < _size ) //逐一扫描，直至末元素
0004       if ( _elem[i] != _elem[j] ) //跳过雷同者
0005          _elem[++i] = _elem[j]; //发现不同元素时，向前移至紧邻于前者右侧
0006    _size = ++i; shrink(); //直接截除尾部多余元素
0007    return j - i; //向量规模变化量，即被删除元素总数
0008 }

有序向量

有序性

唯一化

低效

复杂度

高效

复杂度

二分查找

接口

语义约定

A版本实现

// 二分查找算法（版本A）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
0002 template <typename T> static Rank binSearch ( T* S, T const& e, Rank lo, Rank hi ) {
0003    while ( lo < hi ) { //每步迭代可能要做两次比较判断，有三个分支
0004       Rank mi = ( lo + hi ) >> 1; //以中点为轴点（区间宽度的折半，等效于宽度之数值表示的右移）
0005       if      ( e < S[mi] ) hi = mi; //深入前半段[lo, mi)继续查找
0006       else if ( S[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找
0007       else                  return mi; //在mi处命中
0008    } //成功查找可以提前终止
0009    return -1; //查找失败
0010 } //有多个命中元素时，不能保证返回秩最大者；查找失败时，简单地返回-1，而不能指示失败的位置

复杂度

改进:B版本

C版本[我的最爱]

FibSearch实现

思想

#include "fibonacci/Fib.h" //引入Fib数列类
0002 // Fibonacci查找算法（版本A）：在有序向量的区间[lo, hi)内查找元素e，0 <= lo <= hi <= _size
0003 template <typename T> static Rank fibSearch ( T* S, T const& e, Rank lo, Rank hi ) {
0004     //用O(log_phi(n = hi - lo)时间创建Fib数列
0005    for ( Fib fib ( hi - lo ); lo < hi; ) {  //Fib数列制表备查；此后每步迭代仅一次比较、两个分支
0006       while ( hi - lo < fib.get() ) fib.prev(); //自后向前顺序查找（分摊O(1)）
0007       Rank mi = lo + fib.get() - 1; //确定形如Fib(k) - 1的轴点
0008       if      ( e < S[mi] ) hi = mi; //深入前半段[lo, mi)继续查找
0009       else if ( S[mi] < e ) lo = mi + 1; //深入后半段(mi, hi)继续查找
0010       else                  return mi; //在mi处命中
0011    } //成功查找可以提前终止
0012    return -1; //查找失败
0013 } //有多个命中元素时，不能保证返回秩最大者；失败时，简单地返回-1，而不能指示失败的位置