向量—vector 底层实现

旧城等待， 2022-05-21 08:51 207阅读 0赞

最为基本的线性结构统称为序列，根据其中数据项的逻辑次序与其物理存储地址的对应关系不同，又可进一步地将序列区分为向量(vector)和列表(list)。

在向量中，所有数据项的物理存放位置与其逻辑次序完全吻合，此时的逻辑次序也称为秩(rank)。

在列表中，逻辑上相邻的数据项在物理上未必相邻，而是采用间接定址的方式通过封装后的位置(position)相互引用。

Vector模板类

/*************************************************************************
    	> File Name: vector.h
    	> Author: amoscykl
    	> Mail: amoscykl@163.com 
    	> Created Time: 2018年07月02日 星期一 20时51分45秒
     ************************************************************************/
    
    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);		//归并排序算法
    	Rank partition(Rank lo, Rank hi);		//轴点构造算法
    	void quickSort(Rank lo, Rank hi);		//快速排序算法
    	void heapSort(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; }	//判空
    	int disordered() const;					//判断向量是否已排序
    	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;			//重载下标操作符，可以类似于数组形式引用各元素
    	Vector<T> & operator = (Vector<T> const& );	//重载赋值操作符，以遍直接克隆向量
    	T remove ( Rank r );					//删除秩为r的元素
    	int remove(Rank lo, Rank hi);			//删除区间之内的元素
    	Rank insert(Rank r, T const& e);		//插入元素
    	Rank insert(T const& e ) { return insert (_size,e); }	//默认作为末元素插入
    	void sort(Rank lo, Rank hi);			//对区间排序
    	void sort() { sort(0,_size); }			//整体排序
    	void unsort (Rank lo, Rank hi );		//对区间置乱
    	void unsort { unsort(0, _size); }		//整体置乱
    	int deduplicate();						//无序去重
    	int uniquify();							//有序去重
    //遍历
    	void traverse( void (* ) (T &) );				//遍历:使用函数指针 
    	template <typename VST> void traverse (	VST& );	//遍历：使用函数对象
    };	//Vector

基于复制的构造方法：

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) 
    		_elem[_size++] = A[lo++];			//复制至_elem[0,hi-lo]
    }

重载向量复赋值操作符：

template <typename T> Vector<T>& Vector<T>::operator= (Vector<T> const& V) { //重载
    	if (_elem )	  delete [] _elem;			//释放原有内容
    	copyFrom(V._elem, 0, V.size() );		//整体复制
    	return *this;							//返回当前对象的引用，以便链式赋值
    }

动态空间管理

1.静态空间管理

内部数组所占物理空间的容量，若在向量的生命期内不允许调整，则称作静态空间管理策略。该策略的空间效率难以保证。一方面，容量固定，可能会导致溢出；另一方面，即使预留出部分空间，但是很难明确界定一个合理的预留量。

上述copyFrom()方法，即使将容量取作初始规模的两倍，但仍有溢出的风险。

向量实际规模与其内部数组容量的比值（\_size/\_capacity）称作装填因子，它是衡量空间利用率的重要指标。

因此需要改用动态空间管理策略。其中有效的方法就是使用所谓的可扩充容量。

2.动态空间管理

扩容算法expand()

template <typename T> void Vector<T>::expand() {	//向量空间不足时扩容
    	if (_size < _capacity ) return;			//尚未满员时，不必扩容
    	if (_capacity < DEFAULT_CAPACITY ) _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;						//释放原有空间
    }

缩容算法shrink()

向量的实际规模可能远小于内部数组的容量，当装填因子低于某个阀值，称数组发生了下溢，发生下溢时也有比要适当缩减内部数组容量，提高空间利用率。

template <typename T> void Vector<T>::shrink() {	//装填因子过小时压缩向量所占空间
    	if (_capacity < DEFAULT_CAPACITY << 1) return;	//不致收缩到DEFAULT_CAPACITY一下 
    	if (_size << 2 > _capacity) return ;			//以25%为界
    	T* oldElem = _elem;	  _elem = new T[_capacity >>= 1];		//右移一位，容量减半
    	for (int i = 0; i < _size; i++) _elem[i] = oldElem[i];		//复制原向量内容
    	delete [] oldElem;								//释放原空间
    }

重载向量操作符\[\]

template <typename T> T& Vector<T>::operator[] (Rank r) const	//重载下标操作符
    { return _elem[r]; }

无序向量元素查找接口find()

template <typename T>				//无序向量的顺序查找：返回最后一个元素e的位置；失败时，返回lo-1
    Rank Vector<T>::find(T const& e, Rank lo, Rank hi) const {
    	while( (lo < hi -- ) && (e != _elem[hi] ) );		//从后向前，顺序查找 
    	return hi;						//若hi < lo, 则意味着失败；否则hi即命中元素的秩
    }

向量元素插入接口insert()

template <typename T>				//将e作为秩为r元素插入
    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;						//返回秩
    }

区间删除：remove(lo,hi)

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

单元素删除remove(r)

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

有序性甄别

template <typename T> int Vector<T>::disordered() const {	//返回向量中逆序相邻元素对的总数
    	int n = 0;						//计数器
    	for (int i = 1; i < _size; i ++)	//逐个检查_size-1 对相邻元素
    		if (_elem[i-1] > _elem[i] )  n++;		//逆序则比较
    	return n;						//向量有序当且仅当n=0
    }

唯一化

有序向量uniquify()接口的高效实现

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

查找

统一接口search()

template <typename T>       //在有序向量[lo,hi]内，确定不大于e的最后一个节点的秩
    Rank Vector<T>::search (T const& e, Rank lo, Rank hi) const {
        return ( rand() % 2) ?  //按各50%的概率随机使用二分查找或Fibonacci查找
            binSearch(_elem, e, lo, hi) : fibSearch (_elem, e, lo, hi);
    }

二分查找（版本A）

//二分查找
    template <typename T>  static Rank binSearch(T* A, T const& e, Rank lo, Rank hi) {
    	while( lo < hi) {	//每步迭代可能要做两次比较判断，有三个分支
    		Rank mi = ( lo + hi) >> 1;		//以中点为轴点
    		if( e < A[mi] ) hi = mi;		//深入前半段[lo,hi)继续查找
    		else if (A[mi] < e)	lo = mi + 1;	//深入后半段(mi,hi)继续查找
    		else	return mi;				//在mi处命中
    	}	//成功查找可以提前终止
    	return -1;							//查找失败
    }		//有多个命中元素时，不能保证返回秩最大者。

Fibonacci查找

略......

排序器

统一入口

template <typename T> void Vector<T>::sort (Rank lo, Rank hi) {	//向量区间[lo,hi]排序 
    	switch( rand() % 5) {	//随机选取排序算法，可根据具体问题的特点灵活选取或扩充
    		case 1: bubbleSort ( lo, hi); break;		//气泡排序
    		case 2: selectionSort (lo, hi); break;		//选择排序
    		case 3: mergeSort (lo,hi);	break;			//归并排序
    		case 4: heapSort (lo,hi);	break;			//堆排序
    		default: quickSort (lo,hi); break;			//快速排序
    	}
    }

冒泡排序

//起泡排序
    template <typename T>		//向量的起泡排序
    void Vector<T>::bubbleSort( Rank lo, Rank hi)
    { while ( !bubble(lo, hi--) ); }	//逐躺做扫描交换，直至全序 
    
    //扫描交换
    template <typename T> bool Vector<T>::bubble (Rank lo, Rank hi) {	//一趟扫描交换
    	bool sorted = true;		//整体有序标志
    	while (++lo < hi)		//自左向右，逐一检查各对相邻元素
    		if ( _elem[lo-1] > _elem[lo] ) {	//若逆序，则意味着尚未整体有序，并需要通过交换使局部有序
    			sorted = false;
    			swap( _elem[lo-1],_elem[lo]);
    		}
    	return sorted;			//返回有序标志
    }

归并排序

归并排序的主体结构属典型的分治策略，可递归地描述和实现如代码：

//归并排序
    template <typename T>		//向量归并排序
    void Vector<T>::mergeSort (Rank lo, Rank hi) {
    	if (hi - lo < 2)	return ;	//单元素区间自然有序，否则...
    	int mi = ( lo + hi ) / 2;		//以中点为界
    	mergeSort ( lo, mi ); mergeSort ( mi, hi );		//分别排序
    	merge(lo,mi,hi);				//归并
    }
    
    template <typename T>		//有序向量的归并
    void Vector<T>::merge ( Rank lo, Rank mi, Rank hi )	{	//各自有序的子向量[lo,mi)和[mi,hi)
    	T* A = _elem + lo;		//合并后的向量A[0,hi-lo) = _elem[lo,hi)
    	int lb = mi - lo;	T* B = new T[lb];		//前子向量B[0,lb) = _elem[lo,mi)
    	for ( Rank i = 0; i < lb; B[i] = A[i++] ) 
    		;	//复制前子向量
    	int lc = hi - mi;	T* C = _elem + mi;		//后子向量C[0,lc_ = _elem[mi,hi)
    	for (Rank i = 0, j = 0, k = 0; ( j < lb ) || ( k < lc) ; ) { //B[j]和C[k]中的小者绪至A末尾}
    		if ( ( j < lb ) && ( ! ( k < lc ) || (B[j] <= C[k] ))) A[i++] = B[j++];
    		if ( ( k < lc ) && ( ! ( j < lb ) || (C[k] <  B[j] ))) A[i++] = C[k++];
    	}
    	delete [] B;		//释放临时空间B
    }		//归并后得到完整的有序