欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

笔记,Vector类模板的基本功能

程序员文章站 2022-07-14 19:50:01
...

有基本的查找,排序,插入,删除区间,扩容,减容等
放在博客上主要是为了以后学习方便查找一些,实际上并没有上面参考价值,许多STL模板中有的东西我这并没有。

#include <bits/stdc++.h>
using namespace std;

typedef int Rank;
#define DEFAULT_CAPACITY 3
template < typename T > class Vector {
	private:
//		Rank _size;//元素个数 
//		int _capacity;//当前最大容量 
//		T* _elem;//存放的数据 
	protected:
		//内部函数 
	public:
		Rank _size;//元素个数 
		int _capacity;//当前最大容量 
		T* _elem;//存放的数据 
		Vector ( int c = DEFAULT_CAPACITY ) {
			_elem = new T[_capacity=c];
			_size = 0;
		}
		Vector ( T const *A, Rank lo, Rank hi ) {
			copyFrom (A, lo, hi);
		}//从数组中复制
		Vector ( Vector< T > const & V, Rank lo, Rank hi ) {
			copyFrom(V._elem, lo, hi );
		}//从向量区间复制
		Vector ( Vector< T > const & V ) {
			copyFrom(V._elem, 0, V._size);
		}//从向量整体复制
		void copyFrom(T* const A, Rank lo, Rank hi) {
			_elem = new T[_capacity=2*(hi-lo)];
			_size = 0;
			while ( lo < hi)
				_elem[_size++] = A[lo++];
		}//上述的copyFrom函数
		
		
		void expand () {
			if(_size < _capacity )	return ;
			_capacity = max(_capacity,DEFAULT_CAPACITY);
			T* oldElem = _elem;
			_elem = new T[_capacity<<=1];//使扩容的时间变成logn,但是牺牲了空间效率, 
			for(int i = 0; i < _size; i++ )
				_elem[i] = oldElem[i];
			delete [] oldElem;//删除数组时一定要有”[]“号 
		}//扩容
		
		void shrink() {
			if (_size >= _capacity/2)	return ;
			T* oldElem = _elem;
			_elem = new T[_capacity>>=1];
			for(int i = 0; i < _size; i++)
				_elem[i] = oldElem[i];
			delete [] oldElem;
		}//减容,增加空间利用率,但不是必须的 
		
		
		//对于有升序容器的查找 
		int binsearch(T const & e,Rank lo,Rank hi) {
			while(lo < hi) {
				Rank mid = (lo+hi) >> 1;
				if ( _elem[mid] < e)	lo = mid+1;
				else if ( _elem[mid] > e)	hi = mid;
				else	return mid;
			}
			return -1;
		}//有序向量的二分查找,查找区间是[lo,hi)
		int upperbound(Rank lo,Rank hi,const T & e) {
			while(lo < hi) {
				Rank mid = (lo+hi) >> 1;
				if(_elem[mid] <= e)	lo = mid+1;
				else	hi = mid;
			}
			return lo;
		}//查找大于e的第一个元素的下标 
		int lowerbound(Rank lo, Rank hi, const T & e) {
			while(lo < hi) {
				Rank mid = (lo+hi)>>1;
				if(_elem[mid] < e)	lo = mid+1;
				else	hi = mid;
			}
			return lo;
		}//查找大于等于e的第一个元素的下标, 
		
		
		
		int find(T const A) {
			for(int i = 0; i < _size; i++)
				if(_elem[i] == A)
					return i;
			return -1;
		}//得到数值为A的下标,如果没有找到,返回-1
		int find(T const &e,Rank lo,Rank hi) {
			while((lo < hi-- ) && _elem[hi] != e);
			return hi;
		}//返回的hi<lo代表查找失败 
		//两个函数互为重载关系,当有查找区间时则是下面的,
		//没有查找区间则是上面的全局查找。无序查找 
		
		
		
		operator [] (Rank r) {
			return _elem[r];
		}//通过数组的访问形式访问Vector中的元素
		
		void 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;
		}//在秩是r的位置插入e
		
		
		int remove(Rank lo, Rank hi) {
			if(lo == hi)	return 0;
			while(hi < _size) _elem[lo++] = _elem[hi++];
			_size = lo;
			shrink ();
//			return hi-lo;
		}//移除[lo,hi)之间的元素
		T remove(Rank r) {
			T e = _elem[r]; 
			remove (r, r+1);
			return e;
		}//删除单个元素,可以转换为删除[r,r+1)
		int discoriered() const {
			int n = 0;
			for(int i = 1; i < _size; i++)
				n+=(_elem[i-1] > _elem[i]);//记录相邻两个元素是降序的,不符合升序要求
			return n;//n是统计数量, 
		}//查看是否是严格符合升序 
		
//		int uniquify() {
//			int oldSize=_size;
//			int i=0;;
//			while(i<_size-1)
//				(_elem[i]==_elem[i+1]) ? remove(i+1):i++;
//			return oldSize-_size;
//		}//低效保证有序的唯一性,每次调用remove的复杂度是O(n),整体是O(n*n) 
		int uniquify() {
			int i = 0, j = 0;
			while(++j < _size)
				if( _elem[i] != _elem[j]) _elem[++i] = _elem[j];
			_size = ++i;
			shrink();
			return j - i;//表示删除的元素个数 
		}//保证有序唯一的高效做法 ,时间复杂度是O(n)
		
		
		
		
		//排序升序, 
		void Sort(Rank lo,Rank hi) {
			switch( rand() % 6 ) {//随机选择排序算法. 
				case 0: quicksort( lo, hi); break; 
				case 1: bubblesort1( lo, hi); break;
				case 2: bubblesort2( lo, hi); break;
				case 3: bubblesort3( lo, hi); break;
				case 4: selectsort( lo, hi); break;
				case 5: mergesort( lo, hi); break;
			}
		}
		void bubblesort1(Rank lo, Rank hi ) {
			for(int i = lo; i < hi; i++)
				for(int j = i+1; j < hi; j++)
					if(_elem[j] < _elem[i])
						swap(_elem[i] , _elem[j]);
		}//最初始的版本,也是没有优化的版本, 
		void bubblesort2(Rank lo,Rank hi) {
			while( !bubble2(lo, hi--)); 
		}
		bool bubble2(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;
		}//每次吧最大的放到后面去,遍历一遍没有逆序,返回true,结束程序上面bubblesort。
		void bubblesort3(Rank lo,Rank hi) {
			while(lo < (hi = bubble3 (lo,hi) ) );
		}
		Rank bubble3(Rank lo, Rank hi) {
			Rank last = lo;
			while(++lo < hi)
				if(_elem[lo-1] > _elem[lo]) {
					last = lo;
					swap(_elem[lo-1], _elem[lo]);
				}
			return last;
		}//这个是上面的升级版, 
		void selectsort(Rank lo, Rank hi) {
			for(; lo < hi; lo++)
				for(int j = lo+1; j < hi; j++)
					if(_elem[j] < _elem[lo])
						swap(_elem[j], _elem[lo]);
		}
		void mergesort(Rank lo,Rank hi) {//每次mergesort都是排列其[lo,hi)的元素 
			if(hi-lo < 2)	return ;
			int mid = (lo + hi) >> 1;
			mergesort(lo, mid);
			mergesort(mid, hi);
			merge(lo, mid, hi);
		}
		void merge(Rank lo,Rank mid,Rank hi) {
			T* A = _elem+lo;
			int lb = mid-lo;
			T* B = new T[lb];
			for(Rank i = 0;i < lb; B[i] = A[i++]);
			int lc = hi - mid;
			T* C = _elem + mid;
			for(Rank i = 0, j = 0, k = 0; (j < lb) || (k < lc);) {
				if( (j < lb) && ( lc <= k || ( B[j] <= C[k]) ) )	A[i++] = B[j++];
				if( (k < lc) && ( lb <= j || ( C[k] <B [j]) ) )	A[i++] = C[k++];
			}
		}
		void quicksort(Rank lo, Rank hi) 
		{
			if(lo >= hi - 1)	return ;
			Rank i = lo - 1, j = hi;
			T x = _elem[lo + hi >> 1];
			while(i < j) {
				do i++ ;	while(_elem[i] < x);
				do j-- ;	while(_elem[j] > x);
				if(i<j)	swap(_elem[i], _elem[j]);
			}
			quicksort(lo, j);
			quicksort(j, hi);
		}
};
int main() {
	Vector<int>a;
	int b[10] = {10,9,8,7,6,5,4,3,2,1};
	a.copyFrom(b,0,10);
	for(int i = 0; i < a._size; i++)
		cout << a._elem[i] << " ";
	cout << endl;
	a.Sort(0, 10);
	for(int i = 0; i < a._size; i++)
		cout << a._elem[i] << " ";
	cout << endl;
	cout << a.find(1) << endl;
	cout << a[a.find(1)] << endl;
	cout << a[9] << endl;
	cout << a.find(3,0,10) << endl;
	a.insert(0,0);
	for(int i = 0; i < a._size; i++)
		cout << a._elem[i] << " ";
	cout << endl;
	cout << a.discoriered() << endl;
	cout << a.binsearch(10,0,a._size) << endl;
	cout << a.upperbound(0,a._size,5) << endl;
	cout << a.lowerbound(0,a._size,5) << endl; 
	return 0;
}