<a name="top"></a>
[TOC]
数据结构封装
简介
向量，其实是顺序表的封装，数组的升级版，属于集合（可重复）的一种存储方式，主要特征和数组一样，随机访问，当然比数组强大的地方在于支持很多其他操作，并有自动内存管理功能，不受定长限制，有效避免使用数组常见的异常错误。
构造和析构
template <typename T>
class Vector{
protected:
Rank _size;
int _capacity;
T* _elem;
public:
///构造方法 向量初始化
Vector(int capacity = DEFAULT_CAPACITY);
void memset(T v, int size = 0);
// 数组转向量
Vector(T const* A,Rank n) {copyFrom(A,0,n);}
Vector(T const* A,Rank low,Rank high){copyFrom(A,low,high);}
// 向量直接赋值
Vector(Vector<T> const& V) {copyFrom(V._elem,0,V._size);}
Vector(Vector<T> const& V, Rank low,Rank high){ copyFrom(V._elem,low,high); }
~Vector() { delete[] _elem; }
}
为了完成构造方法，需要定义一个通用的copyFrom函数
//区间复制
template <typename T>
void Vector<T>::copyFrom(T const* A, Rank low,Rank high)
{
_elem = new T[_capacity = 2*(high - low )];
_size = 0;
while (low<high)
_elem[_size++] = A[low++];
}
当然，这里还要提供一些常函数接口，用于只读访问私有属性
///只读接口
Rank size() const {return _size;}
bool empty() const {return !_size;}
内存管理
要实现一种在元素超出最大容量自动扩容的功能:
首先要清楚，什么时候扩容呢？那必须是当前向量长度>=最大容量时。
扩容的操作，实际上也就是一个数组的拷贝
template <typename T>
void Vector<T>::expand()
{
if(_size < _capacity ) return;
if(_capacity < DEFAULT_CAPACITY ) _capacity = DEFAULT_CAPACITY;
T* oldElem = _elem;
copyFrom(oldElem,0,_capacity);
delete[] oldElem;
}
同时相对应还有缩容功能，避免内存浪费
template <typename T>
void Vector<T>::shrink()
{
///不能收缩到 DEFAULT_CAPACITY 以下 以25%为界
if (_capacity < DEFAULT_CAPACITY << 1 ) return;
if (_capacity < _size << 2) return ;
T* oldElem = _elem;
copyFrom(oldElem,0,_size);
delete[] oldElem;
}
操作符重载，元素的获取
重载的操作符主要有两个，一个赋值操作，另一个数组操作，赋值操作有点类似拷贝：
返回对象本身引用，以便可以多层赋值
template <typename T>
Vector<T>& Vector<T>::operator= (Vector<T> const& V)
{
if (_elem) delete[] _elem;
copyFrom(V._elem,0,V._size);
return *this;
}
向量元素的获取，比较简单，确认检查参数即可
template <typename T>
T& Vector<T>::operator [] (Rank r)
{
checkIndex(r); // 关于参数合法性，这里将抛出异常判断
return _elem[r];
}
向量元素的插入和删除
从插入的位置起，后面的元素全部往后移
template <typename T>
Rank Vector<T>::insert(const T& elem,Rank pos)
{
///assert: 0 <= pos <= _size
checkIndex(pos);
expand();
for (int i=_size; i >pos ;i--)
_elem[i] = _elem[i-1];
_elem[pos] = elem;
_size++;
return pos;
}
对于删除则相反，往删除那个位置移动，
这里可以扩充，使用区间删除功能：
思路就是 low 到 high 差值距离不变，区间不断向右移
/// 区间删除 返回删除元素的数目
template <typename T>
int Vector<T>::remove(Rank low,Rank high)
{
///assert: 0<= low <= high <= _size
checkIndex(low,high);
if (low == high ) return 0;
while (high < _size ) _elem[low++] = _elem[high++];
_size = low;
shrink();
return high - low;
}
这样，就搞定单个元素的删除功能了
template <typename T>
T Vector<T>::remove(Rank r)
{
checkIndex(r);
T e = _elem[r];
remove(r,r+1);
return e;
}
扩展功能
遍历
/// 遍历
template <typename T>
void Vector<T>::traverse(void (*visit)(T&))
{
for (int i=0;i<_size;i++) visit(_elem[i]);
}
template <typename T> template <typename VST>
void Vector<T>::traverse(VST& visit)
{
for (int i=0;i<_size;i++) visit(_elem[i]);
}
核心算法
有序和无序
有序向量和无序向量判别方法
（如果同时要把升序和降序辨别出来呢？如果有相等的元素呢？）
///有序向量的甄别 向量有序仅当 n == 0
template <typename T>
bool Vector<T>::disordered() const
{
int n = 0;
for (int i=1;i<_size;i++)
if (_elem[i-1] > _elem[i]) n++;
return !n;
}
查找算法
无序向量的查找
无序向量只能一次遍历查找。
标准的写法可能会是一个for循环加判断，简化后的写法可以是这样,定制一个区间查找方法，用参数代替局部变量声明。
/// 无序向量的查找 成功返回elem 的位置 失败返回 low-1
template <typename T>
Rank Vector<T>::find(T const& elem,Rank low,Rank high)
{
///assert 0<= low < high <= _size
checkIndex(low,high);
while ( (low<high--) && (elem != _elem[high]) );
return high;
}
有序向量的查找
对于有序向量，有效率的查找方式是二分查找，大体思路或许很简单，但也不要想得太简单了哦
对于这类型的二分算法，关键核心在于维护好左右区间，如左区间是[low,mid),那么右区间将会是[mid+1,high)，可能会说中间的元素去哪了？显然是已经被使用过了。
(如果左右区间包含了中间元素，结果就会在找不到的情况下出现死循环！)
下面是一个标准写法
/// 查找 [low,high)
template <typename T>
static Rank binSearchA(T* A,const T& e,Rank low,Rank high)
{
while (low < high)
{
Rank mid = (low + high)>>1;
if (e < A[mid]) high = mid;
else if (e > A[mid]) low = mid +1;
else return mid;
}
return -1;
}
只是这个过程涉及判断有些多，因此就有设计出另外一种写法，那就是只进行一次判断：
template <typename T>
static Rank binSearchC(T* A,T const& e, Rank low,Rank high)
{
while (low < high)
{
Rank mid = (low + high) >> 1;
/// 小的往左边找 大或相等 low 后移
(e < A[mid]) ? high = mid : low = mid +1 ;
}
return ( low>0 && e == A[--low]) ? low : -1;
}
只是这种写法有个问题，首先要注意最后low>0 否则如果要找的元素比所有元素小，找不到，low=0的情况返回就出错了。
这种写法的优势在于减少了平均每次判断，但不是很好，因为如果元素刚好被找着，应该直接返回更快，而这里就必须把区间二分完成才能返回。
为了简化最后一次判断，又出现的另一种写法，这种写法划分方式不同，按[low,mid)和[mid,high)划分左右区间，因此判断结束条件就不能是low < high了，因为low可能永远不会等于high，尤其是在元素找不到的时候，然而采用high-low>1判断，就必须在最后进行一次确认，否则会把存在的元素误判为不存在
template <typename T>
static Rank binSearchB(T* A,T const& e, Rank low,Rank high)
{
while (high - low > 1)
{
Rank mid = (low + high) >> 1;
/// 小的往左边找 大或相等 low 后移
(e < A[mid]) ? high = mid : low = mid;
}
return (e == A[low])? low : -1;
}
关于有序表的二分查找，重点掌握第一种写法就行了。
去重（唯一化）算法
数组去重也是常见的工作。
无序向量去重。
对于无序向量去重，只能进行一次次的遍历，基本思路就是，针对每一个元素，往下寻找是否有相同的元素，找到则删除。
[图片上传失败...(image-c5f455-1542894296727)]
根据这个思路，可以往不同的方向，设计出多种写法，比如在后半段查找，也可以去删除找到的那个元素。
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;
}
这个算法时间复杂度从表面上看上去是O(n^3) 其实是O( n^2)因为查找遍历的元素和删除移动的元素加起来其实只有一个数组长度。
因此如果对无序向量直接去重，耗时可想而知（即使是最好情况也要平方的复杂度）通常可以做排序预处理，转化为有序表再去重。
有序向量的去重
[图片上传失败...(image-3fecf5-1542894296728)]
/// 剔除有向向量重复元素 区间[i,j] 为重复元素 返回被剔除的元素个数
template <typename T>
int Vector<T>::uniquify()
{
int i = 0,j = 0;
while (j++ < _size)
{
/// 跳过雷同的元素
if (_elem[i] != _elem[j])
_elem[++i] = _elem[j]; /// 发现不同者copy
}
_size = i; shrink();
return j - i;
}
乱序
可以先设计一个区间乱序的方法，思路很简单，收窄区间，随机交换
template <typename T>
void Vector<T>::unsort(Rank low,Rank high)
{
T* V = _elem + low;
for (Rank i = high - low; i>0;i--)
swap(V[i-1],V[rand()%i] );
}
template <typename T>
void Vector<T>::unsort()
{
unsort(0,_size);
}
排序
与乱序相对的就是排序啦，排序作为最基本最基础最常用的算法，可谓是必备算法之一：常用的排序算法有5种： 插入排序，选择排序，冒泡排序，还有高效的归并排序，堆排序，快速排序等
插入排序
插入排序的原理其实就像排扑克牌一样，在一个有序向量种插入下一个元素。
一次插入的结果
template <typename T>
void Vector<T>::sortedInsert (Rank low,Rank high,T elem)
{
/// 假设 _elem[low,high-1] 有序 将elem 插入其中
while ((low<high--) && elem < _elem[high])
{
_elem[high+1] = _elem[high];
}
_elem[high+1] = elem;
}
不断扩张区间，多次插入，即可完成排序
template <typename T>
void Vector<T>::insertSort (Rank low,Rank high)
{
for(int i = low+1;i<high;i++)
sortedInsert(low,i,_elem[i]);
}
