Saturday, August 17, 2013

Pointers in C++

Motivation : The main reason pointers are used in C++ is because they are the memory managers.They are your only hope if you want  Dynamic Memory Allocation in your code (which is much more common than you believe ). Additionally you can save a considerable amount of time when you are working with large objects(will explain later). They are your buddies if you want to implement ADTs(what is ADT ? ) like tree, link list, queue and many many more. They can be used to implement efficient function calls. There are many more advantages of pointers. In short pointers give you supreme control over memory.

Beware : This is the first time i am including this heading because there are certain things that you all should know about Pointers before start using them : 
1> Venturing into unknown territory : Improper use of pointers can lead them to point to invalid locations(say a location that is currently in use by the OS) and hence the program will produce unexpected results and exceptions.

2> Code Readability : Too much use of pointers can lead to the code becoming a bit messy and hence can lead to maintenance problems.

3> Validity : Sometimes modifying a data structure(by say : inserting and deleting) may result in the pointers of that data structure to point to invalid locations.

4> Security : Sometimes pointers can be used to hack into C++ programs that is why C++ is not the language of choice when it comes to networking.



Definition : It is a variable that stores the memory address of variables of it's type.

Syntax : 
Declaration : 
               data_type *pointer_name;
Initialization : 
               data_type variable_name = val;
               pointer_name  = &variable_name;

let's look at the following pic to understand the syntax better:
1> This step is a simple variable creation named ia which is initialized to the value of 5.
2> This step creates a pointer of type int. Notice the * symbol for telling c++ that it is a pointer and not a normal variable. 
3> This is the most important line among the three lines lets look at it in more details in the pic below : 





Now, what do we do to extract the value of the variable that a pointer is pointing at. It's simple we use what is known as the 'value of' operator represented syntactically by '*'

Syntax : 
                 *(pointer_name);

Note : if you use (pointer_name) you get the address stored in the pointer.

look at the following simple program : 


#include<iostream>
#include<conio.h>
using namespace std;
int main(){
 int ia = 5;
 int *iptr = &ia;
 cout<<"\n\n\n  address of a = "<<iptr<<"value of a = "<<*iptr;
 getch();
}
output : 



pointer arithmetic : You can perform only one arithmetic operations between    pointers of same type(without using the '*' symbol) i.e. subtraction. It returns the no. of blocks between the address pointed by the  two pointers . where the size of block is the size of the data type of the pointer.

But you can do a lot more if you use the '*' symbol.
Now, lets look at a program to modify the value of variables using pointers.



#include<iostream>
#include<conio.h>
using namespace std;
int main(){
 int ia = 5, ib = 6;
 int *iaptr = &ia, *ibptr = &ib;
 cout<<"\n\n  ia + ib = "<<(*iaptr) + (*ibptr);
 cout<<"\n\n  ia - ib = "<<(*iaptr) - (*ibptr);
 cout<<"\n\n  ia * ib = "<<(*iaptr) * (*ibptr);
 cout<<"\n\n  ia / ib = "<<(*iaptr) / (*ibptr);
 getch();
}

output  : 





                        Arrays and Pointers

In c++ arrays and pointers have a striking resemblance. In fact the name of an array in c++ is nothing but a constant pointer having the same type as the array.
The operator [] can be defined in terms of pointer as follows :
array_name[i] = *(array_name + i) (this is the actual way in which the elements of the array are accessed in constant time)
note : so a[i] can be replaced with *(a+i) any and every where.

The following program shows how a basic array can be accessed using pointers 

#include<iostream>
#include<conio.h>
using namespace std;
int main(){
 int a[5];
 cout<<"\n\n  Enter Elements : ";
 for (int i = 0; i < 5; i++) {
  cin>>*(a+i);
 }
 cout<<"\n\n  The Elements are : ";
 for (int i = 0; i < 5; i++) {
  cout<<*(a+i)<<" ";
 }
        for (int i = 0; i < 5; i++) {
  *(a+i) = 2*3;
 }
        cout<<"\n\n  The Elements are : ";
 for (int i = 0; i < 5; i++) {
  cout<<*(a+i)<<" ";
 }

 getch();
}

So, actually what is the step (array_name+i) doing :


I hope the picture makes every thing clear. If not then in simple english the 
instruction (array_name + i) moves the pointer i steps ahead of the address pointed by the pointer array_name where the step length is equal to the size of the data type  of the array.

Note : remember that array names are constant pointers you cannot modify them i.e. operations like ++a, a++ are not allowed.


Types of pointers c++ supports several types of pointers : 
1> normal pointer.
2> pointer to constant variable.
3> constant pointer to a variable.
4> constant pointer to a constant variable.

look at the program to understand them clearly(i have skipped normal pointers).

#include<iostream>
#include<conio.h>
using namespace std;
int main(){
 int i = 10;
 const int ci = 10;
 const int *pci = &ci; //pointer to a constant integer(or atleast it thinks so)
 //allowed operations are:
 cout<<"\n\n  ++pci : "<<++pci;
 cout<<"\n\n   *pci : "<<*pci;
 //not allowed
 //++(*pci);
 int * const cpi = &i; //constant pointer to any type of integer
 //allowed operations are:
 cout<<"\n\n  ++cpi : "<<++(*cpi);
 cout<<"\n\n   *cpi : "<<*pci;
 //not allowed
 //++cpi;
 const int * const cpci = &ci; //constant pointer to constant integer(or atleast it thinks so)
 //allowed operations are:
 cout<<"\n\n   *cpi : "<<*cpci;
 //not allowed
 //++(*cpci);
 //++cpci;
 //++cpi;
}

Now, lets look at 2d Arrays : 2D Arrays  have two kinds of implementation in memory. 
1> Row Major :  Elements are arranged in rows and the rows are kept after one another.
2> Column Major : Elements are arranged in columns and the columns are kept after one another.


Now, lets look at a more detailed pic of Row Major representation of a 2D Array.
When we declare a 2D array without using dynamic memory allocation like :

int arr[3][3];

you may think that arr is a double pointer(**arr) but it is actually not so. It has been made to look like a double pointer and have a syntax like double pointer. So, actually what is it :

The above diagram looks exactly like a 1D array. So, what is the difference between this and a 1D array :
Well it is the way the '+' operator behaves under different conditions.

Here the '+' has different meaning when used with (array_name) and 
*(array_name)

look at the following pic to understand this whole thing clearly :



when you use the '+' with the array_name it skips the whole row and when used with *(array_name) it provides the more rational behaviour as you expect from a pointer.

if array_name was a double pointer then :
 array_name+2 = address(array_name) + 2*sizeof(data type of pointer)
but that is not the case so it is not a double pointer.



                      Dynamic Memory allocation

Motivation : Let's say you are writing a library management system and one of the features of the software requires you to add members dynamically, i.e. you cannot know the number of users before hand. This is a serious problem because if you take a look at all the language tools we have studied so far none of them has the capability to solve this problem. So c++ provides what is known as  Dynamic Memory allocation.

Definition : This is the process of allocating memory from 'the heap' during the runtime of the program as and when required.
To understand what is 'the heap' lets look at the following pic :



This is a Memory layout of  a process(What is a Process?).
So, the heap is a region of memory allocated to every program by the OS. So, that memory can be extracted from it during runtime as and when required.

The tool provided by C++ to manage heap memory is the 'new' and the 'delete' operator

Syntax : 
               data_type *pointer_name = new data_type ; //for single block
               data_type *pointer_name = new data_type [no. of blocks]; //multiple blocks

look at the pic below for a better understanding :





























The 'new' operator returns a pointer having the type  you requested it to allocate. So, without the use of pointers you can never allocate memory dynamically. 
The 'new' operator can also take an additional argument in '[]' which mentions the no. of blocks you want to allocate. The blocks have contiguous allocations in memory.

The following program creates a 1D Array :

#include<iostream>
#include<conio.h>
using namespace std;
int main(){
 int N, *array;
 cout<<"\n\n  Enter the size of Array : ";
 cin>>N;
 array = new int [N] ; //creating the 1D array using the new operator
 cout<<"\n\n  Enter Array Elements : ";
 for (int i = 0; i < N; i++) {
  cin>>*(array+i);
 }
 cout<<"\n\n  Array Elements are : ";
 for (int i = 0; i < N; i++) {
  cout<<*(array+i)<< " ";
 }
 getch();
}

In the above program we use the 'new' operator to allocate N blocks of int type. 

The Delete operator : Like the name suggests it is used to deallocate the memory block that is allocated with the help of  the 'new' operator.

Syntax : 
               delete pointer_name; //for a single block.
               delete[] pointer_name; //for a collection of blocks.

#include<iostream>
#include<conio.h>
using namespace std;
int main(){
 int N, *array;
 cout<<"\n\n  Enter the size of Array : ";
 cin>>N;
 array = new int [N] ; //creating the 1D array using the new operator
 cout<<"\n\n  Enter Array Elements : ";
 for (int i = 0; i < N; i++) {
  cin>>*(array+i);
 }
 cout<<"\n\n  Array Elements are : ";
 for (int i = 0; i < N; i++) {
  cout<<*(array+i)<< " ";
 }
 delete[] array;
 getch();
}

This is the same program as the one above it with the only difference of the 
use of 'delete'  operator. We have used the collection version of the delete operator as we want to delete the whole array.

The Memory Leak : What actually is a memory leak???
 It is nothing but the phenomenon where the allocated memory is not cleaned up properly.just imagine a software that allocates  memory on the go. Now, let'st  assume  that there is memory  leak  in the program. which keeps  on eating the memory available to the program and after some time you will run out of memory and the program will complain out of memory. This problem is more severe if your program is huge and cannot be fitted in the memory at once  (like games). It will be a disaster. So, memory management is an important part of every C++ software. 

look at the program below that goes on allocating memory without deallocating it.
#include<iostream>
#include<conio.h>
using namespace std;
int main(){
 int N = 100000, *array;
 while(1) {
  cout<<"\n Allocating : "<<100000*4/1024<<" KB memory";
  array = new int [N];
 }
 getch();
}


Below is the snippet of the output :





































What you see here is known as an Exception(we will study about them later). If you look at the window on the right hand size it shows bad_allocation exception that means the call to allocate a new block of memory failed. 

Now, lets look at the revision(memory managed) of the above code with an additional call to delete to deallocate the allocated space.

#include<iostream>
#include<conio.h>
using namespace std;
int main(){
 int N = 100000, *array;
 while(1) {
  cout<<"\n Allocating : "<<100000*4/1024<<" KB memory";
  array = new int [N];
  delete[] array;
 }
 getch();
}

What i showed above is a trivial case of memory management. There are certainly many more examples of memory leak where it is very difficult to even detect the memory leak let alone correct it.


Beware of the Dangling Pointer :  The dangling pointer is a pointer which refers to a location that has been invalidated by some operation in the program but despite all this it still continues to point at the invalid location which now belongs to the operating system and any attempt to modify the contents of the location will lead to unpredictable and unknown behaviour.

look at the program below to understand the concept more clearly.

#include<iostream>
#include<conio.h>
using namespace std;
int main(){
 int *ia = new int;
 *ia = 5;
 cout<<"\n\n  ia : "<<ia;
 cout<<"\n\n  *ia : "<<*ia; //correct accessing the content of a valid location
 cout<<"\n\n  ++(*ia) : "<<++(*ia); //correct modifying the content of a valid location
 delete ia; // the block is deallocated but the pointer ia is still pointing to the invalid location
 cout<<"\n\n  after the call to delete : ";
 cout<<"\n\n  ia : "<<ia;
 cout<<"\n\n  *ia : "<<*ia; //incorrect accessing the content of a invalid location
 cout<<"\n\n  ++(*ia) : "<<++(*ia); //incorrect modifying the content of a invalid location
 getch();
}

Below is the snippet of the ouput :



As you may have noticed, that after the call to delete. The content of the ia pointer becomes invalid. So, ia becomes a dangling pointer. 

Solution : Make ia a 'NULL' pointer after the call to delete.

Syntax : 
               pointer_name = NULL;

note : NULL is a macro defined  in header file std  and it has a value of 0. Making a pointer point to 'NULL' means it is pointing to nothing.

look at the program to see the solution in action.
#include<iostream>
#include<conio.h>
using namespace std;
int main(){
 int *ia = new int;
 *ia = 5;
 cout<<"\n\n  ia : "<<ia;
 cout<<"\n\n  *ia : "<<*ia; //correct accessing the content of a valid location
 cout<<"\n\n  ++(*ia) : "<<++(*ia); //correct modifying the content of a valid location
 delete ia; // the block is deallocated but the pointer ia is still pointing to the invalid location
 ia = NULL; //make ia point to null so that it does not point to the invalidated location
 cout<<"\n\n  after the call to delete : ";
 cout<<"\n\n  ia : "<<ia;
 cout<<"\n\n  *ia : "<<*ia; //incorrect accessing the content of a invalid location
 cout<<"\n\n  ++(*ia) : "<<++(*ia); //incorrect modifying the content of a invalid location
 getch();
}
here is the snippet of the output :






















































Thus this simple initiative of making the ia pointer point to NULL pays in the long run. Now you may argue that what is the use of this step if it results in an exception being thrown. It has a huge advantage and it is the fact that it is throwing an exception an telling you that you have done something that you should not have done. As a result you can correct your mistake. Incase of large software projects this is a huge advantage(as searching the error may take a lot of time).


Creating a 2D Array with the new operator : When we create a 2D array with the help of new operator it will looks different in memory and also the underlying concept of how it works is different. We really require a double pointer here.

Syntax : 
          data_type **pointer_name = new data_type* [NUMROWS];
          for(int i = 0; i < NUMROWS; i++)
                 pointer_name[i] = new int [NUMCOLUMNS];

Note : This is one way  of doing it. You may do in any other way that you feel comfortable.
NUMROWS : number of rows.
NUMCOLUMNS : number of columns.  

Array of pointers  : It is nothing but an array where every element of the array is a pointer.

Note :  The 'array_name' of an array of pointers is a double pointer since it points to the base address of the array i.e. it holds the address of the first element of the array which is a pointer.

What we did at first was create an array of pointers having [NUMROWS] elements. In the next step we iterate through each element of the array and assigned to them  an array of integers  using 'new' having [NUMCOLUMNS] elements.
So, if this seems complicated do not worry the following diagram will make it clear :

Now, lets try to understand the access mechanism. With the pic below.
























So, we see that though the behaviour of dynamic 2D array and the one created statically are same. But their underlying principle and working mechanism is entirely different.

let's look at a program to understand it more carefully.


#include<iostream>
#include<conio.h>
using namespace std;
int main(){
 int **array, NUMROWS, NUMCOLUMNS;
 cout<<"\n\n  Enter Rows : ";
 cin>>NUMROWS;
 cout<<"\n\n  Enter Columns : ";
 cin>>NUMCOLUMNS;
 array = new int* [NUMROWS]; 
 for (int i = 0; i < NUMROWS; i++) {
  array[i] = new int[NUMCOLUMNS];
 }
 cout<<"\n\n  Enter Array Elements : ";
 for (int i = 0; i < NUMROWS; i++) {
  cout<<"\n\n  Enter row no. "<<i<<" : ";
  for (int j = 0; j  < NUMCOLUMNS; j ++) {
   cin>>*(*(array+i)+j); //equivalent to a[i][j]
  }
 }
 cout<<"\n\n  Array Elements are : ";
 for (int i = 0; i < NUMROWS; i++) {
  cout<<"\n\n  ";
  for (int j = 0; j  < NUMCOLUMNS; j ++) {
   cout<<*(*(array+i)+j)<<" "; //equivalent to a[i][j]
  }
  cout<<"\n";
 }
 getch();
}

Snippet of the output : 


Function Pointer : A function pointer is a pointer that can point to a specific type of function and it can be used to mimic the call to a function.

Syntax : 
                return_type (*function_pointer_name) (arguments);
                 function_pointer_name = & function_name
               


#include<iostream>
#include<conio.h>
using namespace std;
double square(double x)  {
 return (x*x);
}
double cube(double x) {
 return (x*x*x);
}
double (*functionPointer)(double ); // function pointer that can point to a function that has return type double and takes an argument of type double.
int main(){
 int choice;
 double n;
 cout<<"\n\n  Enter Choice (1 for square) and (2 for cube) : ";
 cin>>choice;
 switch(choice) {
 case 1 :
  cout<<"\n\n  Enter n : ";
  cin>>n;
  functionPointer = &square;
  cout<<"\n\n  square ("<<n<<") : ";
  break;
 case 2:
  cout<<"\n\n  Enter n : ";
  cin>>n;
  functionPointer = &cube;
  cout<<"\n\n  cube ("<<n<<") : ";
  break;
 default :
  cout<<"\n\n  Wrong option!!";
 }
 cout<<functionPointer(n);
 getch();
}