有基本的查找，排序，插入，删除区间，扩容，减容等
放在博客上主要是为了以后学习方便查找一些，实际上并没有上面参考价值，许多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;
}