手写vector

看过JDK源码，现在自己想实现一个vector。

最开始的时候，我大概构想了一下怎么设计，一种是设置一个指针数组来存放对象，这样修改的时候可以不用大量的元素复制，但后来仔细想了想，它需要设置一个额外的位示图显示对应位置的元素情况，不划算，所以最终也是采取了JDK源码的设计思路。即，数组初始长度设置为10,以后快溢出之前将数组扩容为原先的1.5倍。

#include <iostream>

#include <cstring>

using namespace std;

class Vector {

	private :

			 int *myVector;

			 int vectorSize;

			 int length; // if vectorSize >= length need extendCapacity

	public:

			 Vector() {

			 	length = 10;

			 	myVector = new int[length];

			 	vectorSize = 0;

			 }

			 Vector(int nowSize, int value) {

			 	vectorSize = nowSize;

			 	length = nowSize > length ? nowSize : length;

			 	myVector = new int[nowSize];

			 	memset(myVector, value, nowSize);

			 }

			 ~Vector() {

			 	delete myVector;

			 	myVector = NULL;

			 }

			 int rangeCheck(int index);

			 void push_back(int value);

			 int size();

			 int erase(int index);

			 bool empty();

			 int insert(int index, int value);

			 void show();

			 void ensureCapacity();

			 void CopyFrontToEnd(int *Dst, int from, int *Src, int start, int cnt);//从前往后复制

			 void CopyEndToFront(int *Dst, int from, int *Src, int start, int cnt); //从后往前复制

};

void errPrint(int errorType) {

	if (errorType == 1) {

		cout << "index > size\n";

	}

	else if(errorType == -1) {

		cout << "index < 0\n";

	}

}

void Vector::CopyFrontToEnd(int *Dst, int from, int *Src, int start, int cnt) {

	for(int i = start; i < start + cnt; ++i) {

		Dst[from++] = Src[i];

	}

}

void Vector::CopyEndToFront(int *Dst, int from, int *Src, int start, int cnt) {

	for(int i = start - 1; i >= start - cnt; --i) {

		Dst[from--] = Src[i];

	}

}

void Vector::ensureCapacity() {

	if(vectorSize >= length) {

		int *tmp = new int[length * 3 / 2];

		length *= 3 / 2;

		CopyFrontToEnd(tmp, 0, myVector, 0, vectorSize);

		myVector = tmp;

	}

}

int Vector::rangeCheck(int index) {

	if (index > vectorSize) {

		return 1;

	}

	if (index < 0) {

		return -1;

	}

	return 0;

}

void Vector::push_back(int value) {

	ensureCapacity();

	myVector[vectorSize++] = value;

}

int Vector::size() {

	return vectorSize;

}

int Vector::erase(int index) {

	int checkOut = rangeCheck(index);

	if(checkOut != 0)

		return checkOut;

	CopyFrontToEnd(myVector, index, myVector, index + 1, vectorSize - index - 1);

	--vectorSize;

}

bool Vector::empty() {

	return vectorSize == 0 || myVector == NULL;

}

int Vector::insert(int index, int value) {

	int checkOut = rangeCheck(index);

	if(checkOut != 0)

		return checkOut;

	ensureCapacity();

	CopyEndToFront(myVector, vectorSize, myVector, vectorSize, vectorSize - index);

	myVector[index] = value;

	++vectorSize;

	return 0;

}

void Vector::show() {

	for (int i = 0; i < vectorSize; ++i) {

		cout << myVector[i] << " ";

	}

	cout << endl;

}

void menu() {

	cout << "1-push_back  2-size  3-erase  4-empty 5-insert 6-show\n";

}

void testVector(Vector myVector) {

	int choice, index, value, checkOut;

	menu();

	while(cin >> choice) {

		switch(choice) {

			case 1:

				cout << "cin the value you want to push_back : ";

				cin >> value;

				myVector.push_back(value);

				break;

			case 2:

				cout << "vector size = " << myVector.size() << endl;

				break;

			case 3:

				cout << "cin the index : ";

				cin >> index;

				checkOut = myVector.rangeCheck(index);

				if(checkOut == 0)

					myVector.erase(index);

				else

					errPrint(checkOut);

				break;

			case 4:

				cout << "vector empty : " << myVector.empty() << endl;

				break;

			case 5:

				cout << "cin the index and the value you want to insert: ";

				cin >> index >> value;

				checkOut = myVector.rangeCheck(index);

				if(checkOut == 0)

					myVector.insert(index, value);

				else

					errPrint(checkOut);

				break;

			case 6:

				cout << "show vector : ";

				myVector.show();

				break;

			default :

				break;

		}

	}

}

int main(int argc, char const *argv[]) {

	Vector myVector;

	testVector(myVector);

	return 0;

}

巴特西

手写vector

最新文章

热门文章