For this you need to have a clear concept of Heap memory allocation. In part one, I have given a small introduction to it but I'd repeat here.
Heap is a dynamic memory and by dynamic I mean the one that has the ability to contract or expand. In case of arrays, you had to define the size of it while writing the program say 10, 20, 100 etc. But what if you do not know that how many inputs are you gonna have? Say, you are making a program for daily customer entries of a restaurant that stores the name of the customers who visited that specific day. Now you don't know if there are going to be 10 or 100. If you make array of 10 size then you might run out of space and if you make it of 100, there maybe only 5 entries and the rest of the memory goes to waste. Now, to avoid these we make dynamic arrays using dynamic pointers.
Normally, you initialize arrays as :
int arr[5] = {1,2,3,4,0};
But the here :
int* arr = new int[5];
int* is the same as pointers of stack i.e. since you are making a dynamic array for int data type, you use int*. new is the command that tells the program to create this pointer on heap. int is again the type of data stored in the pointer and 5 is the size of the array. (Right now, I have hard-coded the size but we'll make it dynamic in real ways later. )
Now let's see an example,
void main()
{
int cap = 5; //capacity of the array that is 5 in the start
int count = 0; //the number of elements stored right now that is 0 in beginning
int* arr = new int[cap]; //made dynamic array of capacity size
int x; //we'll take input through this
//here I am gonna write a program that will keep taking input of integers till we enter -1
cin >> x;
while (x != (-1))
{
if (count < cap) //if the entries have not outnumbered capacity i.e. still space available
{
arr[count] = x; //store at count position e.g. in first attempt at 0 then 1 and so on
count++; //increment the count
} //end of if
else //this else condition is when the entries have exceeded the size i.e. (count > cap)
{
//now we shall have to increase the capacity, a good way is to double it, though you can increase by one too but I prefer doubling it so that my program remains efficient
int* temp = new int[cap * 2]; //making a temporary array
//Note : Every time you have to make an increase or decrease, you'll have to re-make the array
// this is because arrays are consecutive, you had capacity of 5 e.g. you had hired 5 flats in the start
//now you don't know, the owner has probably given the 6th one to someone else
//you can't break this continuity of your flats array so when you need 6 flats, you can't just hire next one that is already taken
//you will have to re-locate i.e. buy 6 flats somewhere else, shift your all data of the first 5 there
// and now you have 6 in consecutive so you can add data into 6th too
//similarly, if you in next few days have to get a 7th flat, you will have to re-locate again
//Here I have made a temporary of double the size of the previous array and store my data there, actually copy
for (int i = 0; i < cap; i++) //copying the all the data to new temp
{
temp[i] = arr[i]; //with same sequence, 0th element of arr to 0th location in temp
}
//now arr was my address card, I will have to replace the address there with the new one
delete [] arr; //deleting my DATA from the previous location,
// the syntax [ ] allows us to delete the data on the address 'arr', using " delete arr; " won't work because we don't have the permission to delete the location
// e.g. we can remove our luggage from the flat but we can't destroy it :p
//not using [ ] gives syntax error
arr = temp; //replacing address on the address card
cap = cap * 2; //updating capacity
arr[count++] = x; //storing the recent input that wasn't stored due to insufficient memory in 'if' loop
} //end of else
cin >> x;
} //end of while
} //end of main
In this way, we have created our first array that can expand it's size. Next on, we'll work on shrinking too.
Remember, this increase in capacity by double (whatever is happening in else) will happen every time we exceed capacity e.g. when we get 6th input we make capacity 5*2=10. When it takes 11th input, 10*2 = 20 and so on. This while loop will stop only when we have -1 in the input.
Location of Data and the Pointer itself :
The pointer 'arr' is stored on the Stack but the data that it points to is stored on the Heap in case of dynamic array but in simple Stack arrays, the pointer (address) and the data both were stored on the Stack. Do not mix it up!
The pointer 'arr' is stored on the Stack but the data that it points to is stored on the Heap in case of dynamic array but in simple Stack arrays, the pointer (address) and the data both were stored on the Stack. Do not mix it up!
//I have let 101,102, etc as the addresses of boxes on the Heap but in actual they are in hexadecimals. This just to show that they are consecutive.
See the Image above!
If you have any questions then you can comment below. Thank you for Reading! :)
0 comments:
Post a Comment