#ifndef VECTOR_H
#define VECTOR_H #include <algorithm> template<typename Object>
class Vector
{
private:
int theSize; //实际数据大小
int theCapacity; //实际容器容量大小
Object *objects; //基本数组
public:
enum { SPACE_CAPACITY = }; //默认容量大小 explicit Vector(int initSize = ) //单参数构造函数要用explicit()避免类型在后台转换
: theSize(initSize), theCapacity(initSize + SPACE_CAPACITY) {
objects = new Object[theCapacity];
}
Vector(const Vector& rhs) : objects(NULL) { //复制构造函数--调用operator=对已有的Vector进行复制
operator = (rhs);
}
~Vector() {
delete[] objects;
} const Vector& operator = (const Vector& rhs) //重载赋值运算符
{
if (this != &rhs) //避免复制自身--混淆检验
{
delete []objects; //删除旧的内存空间
theSize = rhs.size(); //生成同样的样本大小
theCapacity = rhs.theCapacity; //生成同样的容量大小 objects = new Object[capacity()]; //生成与所复制的Vector同样容量的新数组
for (int k = ; k < size(); k++)
objects[k] = rhs.objects[k];
}
return *this;
} void resize(int newSize)
{
if (newSize > theCapacity) //重置大小
reserve(newSize * + ); //新大小
theSize = newSize;
} //扩容
void reserve(int newCapacity)
{
if (newCapacity < theSize) //至少和（样本大小）一样大
return; Object *oldArray = objects; //oldArray--用于复制旧数组内容
objects = new Object[newCapacity];
for (int k = ; k < theSize; k++)
objects[k] = oldArray[k]; theCapacity = newCapacity;
delete []oldArray;
} Object& operator[] (int index)
{
return objects[index];
}
const Object& operator[] (int index) const
{
return objects[index];
} bool empty() const {
return size() == ;
} int size() const {
return theSize;
}
int capacity() const {
return theCapacity;
}
//在数据尾端插入元素
void push_back(const Object& x) {
if (theSize == theCapacity)
reserve( * theCapacity + );
objects[theSize++] = x;
} //在index位置前端插入数据data
void insert(int index, const Object& data) {
if (theSize == theCapacity)
reserve( * theCapacity + );
for (int i = theSize; i >= index; i--) {
objects[i] = objects[i - ];
}
objects[index] = data;
theSize++;
} void pop_back() {
theSize--;
} //区间删除 [lo, hi) --- 左闭右开！！ --- 删除索引从 1,2..k
int remove(int lo, int hi) {
if (lo == hi) return ;
while (hi < theSize) {
objects[lo++] = objects[hi++]; //[hi,theSize)顺次前移 hi-lo 位
}
theSize = lo;
return hi - lo; //返回被删除元素数目
}
//重载删除一个指定位置元素--删除r位置元素，[r,r+1). 如果先写删除单个元素函数，删除区间时会低效.
Object remove(int r) {
Object oldElem = objects[r];
remove(r, r + );
return oldElem; //返回删除的元素
} //order the vector
//二分查找--有序向量
int Search(Object &elem, int lo, int hi) {
while (lo < hi) { //不变性: A[0,lo) <= e < A[hi,n)
int mid = (lo + hi) >> ; // 以中点为轴
(elem < objects[mid]) ? hi = mid : lo = mid + ; // [lo,mi) 或 (mi,hi)
} // 出口时,A[lo = hi]为大于elem的最小元素
return --lo; // lo-1即为不大于elem的元素的最大秩
} /*mergesort()归并排序
/*无序向量的递归分解，两个有序的子序列合成大的子序列*/
void mergeSort(int lo, int hi) {
if (hi - lo < ) return;
int mid = (lo + hi) >> ;
mergeSort(lo, mid); //对前半段排序
mergeSort(mid, hi); //对后半段排序
merge(lo, mid, hi); //归并
} //归并---O(nlogn), T(n) = 2T(n/2) + O(n)
void merge(int lo, int mid, int hi) {
//A用来存放合并后的向量，B，C进行比较(前后子向量比较)
Object *A = objects + lo; //合并后的向量A[0,hi-lo) = objects[lo,hi)
int lb = mid - lo;
Object *B = new Object[lb]; //前子向量 B[0,lb) = objects[lo,mi)
for (int i = ; i < lb; B[i] = A[i++]); //复制前子向量
int lc = hi - mid;
Object *C = objects + mid; //后子向量
for (int i = , j = , k = ; (j < lb || k < lc);) {
//B[i], C[k]中小者转至A的末尾.
//因为C本来就占据A中，不需要考虑提前耗尽情况
if ((j < lb) && (k >= lc || C[k] >= B[j])) //C[k]已无或不小
A[i++] = B[j++];
if ((k < lc) && (j >= lb || B[j] >= C[k])) //B[k]已无或不小
A[i++] = C[k++];
}
delete []B;
} //有序向量的去重, 重复的元素必定紧邻,每个区间只保留单个---每次常数，累计O(n)
int uniquify() {
int i = , j = ; //各对互异,"相邻"元素的秩,逐一扫描,直至末元素
while (++j < theSize) {
//跳过雷同者,发现不同元素时，向前移至紧邻元素
if (objects[i] != objects[j]) objects[++i] = objects[j];
}
theSize = ++i;
return j - i; //返回被删除元素总数
} //得到尾元素
const Object& back() const {
return objects[theSize - ];
} typedef Object * iterator;
typedef const Object * const_iterator; iterator begin() {
return &objects[];
}
const_iterator begin() const {
return &objects[];
}
iterator end() { //尾后的不存在的指针
return &objects[size()];
}
const_iterator end() const {
return &objects[size()];
} }; #endif // VECTOR_H
/************************************************************************/
/* Vs2013, c++11标准编写 测试vector.h */
/************************************************************************/
#include <iostream>
#include <cstring>
#include "Vector.h"
using namespace std; int test[] = { }; void Merge(int *test, int lo, int mid, int hi);
void MergeSort(int *test, int lo, int hi) {
if (hi - lo < ) return;
int mid = (lo + hi) >> ;
MergeSort(test, lo, mid); //对前半段排序
MergeSort(test, mid, hi); //对后半段排序
Merge(test, lo, mid, hi); //归并
} //归并---O(nlogn), T(n) = 2T(n/2) + O(n)
void Merge(int *test, int lo, int mid, int hi) {
//A用来存放合并后的向量，B，C进行比较(前后子向量比较)
int *A = test + lo; //合并后的向量A[0,hi-lo) = int s[lo,hi)
int lb = mid - lo;
int *B = new int [lb]; //前子向量 B[0,lb) = int s[lo,mi)
for (int i = ; i < lb; B[i] = A[i++]); //复制前子向量
int lc = hi - mid;
int *C = test + mid; //后子向量
for (int i = , j = , k = ; (j < lb || k < lc);) {
//B[i], C[k]中小者转至A的末尾.
//因为C本来就占据A中，不需要考虑提前耗尽情况
if ((j < lb) && (k >= lc || C[k] >= B[j])) //C[k]已无或不小
A[i++] = B[j++];
if ((k < lc) && (j >= lb || B[j] >= C[k])) //B[k]已无或不小
A[i++] = C[k++];
}
delete[]B;
} int main()
{
//用来测试 非模板写的 归并排序 算法
/*int Test[13] = { 1, 5, 2, 3, 6, 8, 9, 10, 13, 12, 4, 7, 11 };
MergeSort(Test, 0, 13);
for (int i = 0; i < 13; i++)
cout << Test[i] << " ";
cout << endl;*/ Vector<int> testOne;
int testData, cnt, index;
cout << "输入数字数目: ";
cin >> cnt;
cout << "输入 " << cnt << "个数: ";
while (cnt-- && cin >> testData)
{
testOne.push_back(testData);
} cout << "显示所有元素: ";
for (int i = ; i < testOne.size(); i++) {
cout << testOne[i] << " ";
}
cout << endl; cout << "\n输入插入元素位置(0...k)和插入的数值: ";
cin >> index >> testData;
testOne.insert(index, testData);
cout << "显示所有元素: ";
for (int i = ; i < testOne.size(); i++) {
cout << testOne[i] << " ";
}
cout << endl; cout << "\n输入删除元素位置(0...k): ";
cin >> index;
testOne.remove(index);
cout << "显示所有元素: ";
for (int i = ; i < testOne.size(); i++) {
cout << testOne[i] << " ";
}
cout << endl; cout << "\n归并排序向量元素: \n"; testOne.mergeSort(, testOne.size());
cout << "显示所有元素: ";
for (int i = ; i < testOne.size(); i++) {
cout << testOne[i] << " ";
}
cout << endl; cout << "\n(有序向量)(二分查找:)输入查找元素: ";
cin >> testData;
cout << "查找位置返回(不大于查找元素的最大的秩): "
<< testOne.Search(testData, , testOne.size()) << endl; cout << "\n(有序向量)去除重复元素: \n"; testOne.uniquify();
cout << "显示所有元素: ";
for (int i = ; i < testOne.size(); i++) {
cout << testOne[i] << " ";
}
cout << endl; return ; }