Vector (Dynamic Array)

Chenglei Si
Sep 7, 2018 · 2 min read

C++ Implementation of a dynamic array. Most codes are self-explanatory.

//basic operations of dynamic array
template <typename Type> class Vector {
private:
int size,length;
//size: maximum size, length: current number of elements
Type *data;
//the array storing the data
public:
//Construction
Vector(int input_size) {
size=input_size;
length=0;
data=new Type[size];
}

//Destruction
~Vector() {
delete[] data;
}

// Expand
void expand(){
Type *old_data=data;
size=size*2;
//here I double the original size
data=new Type[size];
for(int i=0;i<length;i++){
data[i]=old_data[i];
}
delete[] old_data;
}


//Insert
bool insert(int loc, Type value) {
if (loc < 0 || loc > length) {
return false;
}
if (length >= size) {
expand();
}
for (int i = length; i > loc; --i) {
data[i] = data[i - 1];
}
data[loc] = value;
length++;
return true;
}



//Search for a specific value, return its index if found, -1 otherwise
int search(const Type &value) {
for(int i=0;i<length;i++){
if(data[i]==value){
return i;
}
}
return -1;
}

//Remove
bool remove(int index) {
if(index<0||index>=length){
return false;
}
for(int i=index+1;i<length;i++){
data[i-1]=data[i];
}
length--;
return true;
}

//Traversal and print all elements
void print() {
for(int i=0;i<length;i++){
if(i>0){
cout<<" ";
}
cout<<data[i];
}
cout<<endl;
}

//get value of a specific element
Type get_data(int loc){
if(loc<0||loc>=length){
cout<<"failed"<<endl;
return 0;
}
return data[loc];
}

//change value of a specific element
bool change_data(int loc,Type new_data){
if(loc<0||loc>=length){
return false;
}
data[loc]=new_data;
return true;
}

int get_length(){
return length;
}

//shift the array k units leftard
void left_shift(int k){
if(k<=0||k>=length){
return;
}
Type *temp=new Type[k];
for(int i=0;i<k;i++){
temp[i]=data[i];
}
for(int i=k;i<length;i++){
data[i-k]=data[i];
}
for(int i=0;i<k;i++){
data[i+length-k]=temp[i];
}
delete[] temp;
}

};


//find the intersection of two increasing (sorted) arrays
void intersect(Vector<int> &listA, Vector<int> &listB, Vector<int> &intersection){
int length_A=listA.get_length(),length_B=listB.get_length();
int i_a=0,i_b=0,i_c=0;
while(i_a<length_A&&i_b<length_B){
if(listA.get_data(i_a)<listB.get_data(i_b)){
i_a++;
}
else if(listA.get_data(i_a)>listB.get_data(i_b)){
i_b++;
}
else{
intersection.insert(i_c, listA.get_data(i_a));
i_a++;
i_b++;
i_c++;
}
}
}

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade