Dynamic Array (vector)

First Why do you need a Vector/Dynamic array?

We know the array is a fixed size which means that it is not possible to add an element if the array is full

now when using the dynamic array we will solve this problem

Vector/Dynamic Array Implementation

We create a class and add main attributes (size and pointer array)

I will explain why we need a pointer later
```
class vector{
private:
	int *arr=nulptr;
	int size=0;
};
```

We are creating the constructor because creating the first array

class vector{
private:
	int *arr=nullptr;
	int size=0;
public:
	//if the user doesn't input a size
	vector(){
		size = 1;
		arr=new int[size]{}; // create int array with size = "size" and the pointer point to the beginning of the array
	//if the user input a size
	vector(int s){
		size = s;
		if(size<0) // if size is less than 0 we will set size = 1
			size=1;
		arr=new int[size]{}; // create int array with size = "size" and the pointer point to the beginning of the array
}

if the size is less than 0 we will set size = 0 if(size<0){ size=1; } create integer array with size = input size and the pointer point to the beginning of the array arr=new int[size]{};

Get Item

int get_from(int idx){
	//if the index is less than the size and greater than or equal to 0 it means the index is in the array range
	if(0 <= idx && idx < size){
		return arr[idx];
	}
	else{
		cout<<"this index is not valid\n";
}
}

Set Item

void set_in(int idx, int val){
	//if the index is less than the size and greater than or equal to 0 it means the index is in the array range
	if(0 <= idx && idx < size){
		arr[idx] = val;
	}
	else{
		cout<<"this index not valid\n";
	}
}

print all Items

We will move over inside the array item by item and every time print the element.
```
void print(){
	for(int i=0; i < size; ++i){
    	cout<<arr[i]<<" ";
	}
}
```
Insert an Item push_back()

okay, in the beginning, we know the array must be fixed size (vector is an array) then how we can insert/append/push items in the array without limitation?

simply, when we need to append an item we make a new array with a bigger size and then move all items from the old array to the new array, but if we every time create a new array with size++ and move all items from the old array to the new array so in every time we need to add an item that must repeat all this (more operations = more time),

okay, we need to reduce operations :)

so if we every time double the size we don't need to increment the size every time, but now the size is not the number of items in the vector.

size = The number of items you can store in the vector, we don't need that need size = the number of items in the vector,

so we will create a new variable called capacity = The number of items you can store in the vector,

we created two sizes
- first size (Fake/Logical size = number elements in the Vector) → called size
- second size (real size = vector capacity) → called capacity
edit push_back()
```
void push_back(int val)
   {
  //if the array is full
  if (capacity == size)
   {
   	//Double the capacity
       	capacity *= 2;
       	//create a new array with the new capacity
       	int *new_arr = new int[capacity]{};
       	//copy all items in the old_array to the new_array
       	for (int i = 0; i < size; i++)
                new_arr[i] = arr[I];
       	//delete all copied items in the old array
           delete[] arr;
   	//arr pointer points to the new array
           arr = new_arr;
       }
   //Add the new item
   arr[size] = val;
      // increment the size
      ++size;
 }
```

Insert Element

now we need to insert elements in the dynamic array how do we do it?

first, we need to take from the user index to insert elements in this index then shift all the elements on the right side of the input index one step because we can insert a new element.

example

I want to insert (10) in index 2 Now we must shift all the elements Now we can insert (10) in index 2 but every time we check if size == capacity if true we will create a new array with a new capacity like in push_back()

okay, let’s see, how to code that?

void insert_at(int val, int idx)
{
    if(idx >= 0 && idx < size){
        //if the array is full
        if (capacity == size)
        {
            //Double the capacity
            capacity *= 2;
            //create a new array with the new capacity
            int *new_arr = new int[capacity]{};
            //copy all items in the old_array to the new_array
            for (int i = 0; i < size; i++)
                new_arr[i] = arr[i];
            //delete all copied items in the old array
            delete[] arr;
            //arr pointer points to the new array
            arr = new_arr;
        }
        // //In this loop shift all the elements on the right side of index 2 one step
        for (int i = size; i > idx; --i)
        {
            arr[i] = arr[i - 1];
        }
        //insert the new item
        arr[idx] = val;
        // increment the size
        ++size;
    }
}

okay, I will explain shift elements again

1st iteration in the loop arr[i+1] = arr[i]; ”shift 5th element” --i;
2nd iteration in the loop arr[i+1] = arr[i]; ”shift 4th element” --i;
3rd iteration in the loop arr[i+1] = arr[i]; ”shift 3td element” --i;
loop is end
insert new element arr[i] = val;

ah, finally We have inserted the item successfully.

pop_back() → delete element from back

Now we need to delete elements in the Dynamic Array (vector) from the back how do we do it?

simply, change the value for the last element to zero and decrement the size okay, let’s see, how to code that?

void pop_back()
{
    // actually we do not delete items just decrement the size
    //If size = 0 can't decrement the sizeو because the size will be negative!!
    if(size > 0){
        // Decrement the size
        --size;
        // change value of the item need to delete .. you can don't do that 
        arr[size] = 0;
    }
    else{
        // clean memory
        delete[] arr;
        // change the value of the capacity because if we need to push_back items again 
        capacity = 1;
    }
}

now, the last element in the dynamic array is 1 in index 5 and size=6 so, change the value of index 5 to zero and decrement the size that is all :)

delete an element at an index

we need to create a method to delete an element at a specific index Example I need to delete an element in index 2 Simply, We will shift all the elements on the right side of index 2 one step to the left. okay, let’s see how to write this
```
void delete_at(int idx)
{
    if(idx < size && idx >= 0){
        // shift all the elements on the right side of index 2 one step to the left.
        for (int i = idx; i < size-1; ++i)
            arr[i] = arr[i+1];
        //Change the value of the last item to 0
        arr[size-1] = 0;
        // Decrement the size
        --size;
    }
}
```
Let me trace that I have that
- 1st iteration in the loop arr[2] = arr[3]; change the value of the item in index 2 (it is the item we need to delete)
- 2nd iteration in the loop arr[3] = arr[4]; change the value of the item in index 3 to 7 because 4 is now in index 2
- 3rd iteration in the loop arr[4] = arr[5]; change the value of the item in index 4 to 1 because 7 is now in index 3
- change the last item to 0 arr[5] = 0; change the value of the item in index 5 to 0 because now index 4 is the last in the dynamic array because we deleted the item
- Decrement the size --size; change the size okay, now we deleted 10 :D