Vector (Dynamic Array)
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++;
}
}
}