MTH 4300: Algorithms, Computers, and Programming II

Pointers

Address of a Memory

The command
int x;
in C++ code is the way for a programmer to present the following request to the computer:
Please give me the memory that can hold one integer. This memory will be called x. When in future I ask to store or read from this memory, I will refer to it as x.
If in the future we issue the command x=30; we are essentially giving the following request to the computer:
Place the value 30 in the memory location that we agreed to call x.
When we issue the command
x=x+27
we are asking for the following 3 actions:
1) Dear computer, read the content of the memory location that we call x. 2) Add number 27 to whatever this content was. 3) Place the obtained sum to the memory location that we call x.
We like to call the memory locations using beautiful names such as x, and the computer is OK with helping programmers call the memory whatever they want. However, internally, it has numerical addresses assigned for locations in the memory. We may think of them as license plates. C++ allows us to see this address. We may do this by asking the computer to print the value &x (this can be read as address of x).
 std::cout << &x << std::endl;
You will notice that it prints non-sensical word containing both letters and numbers. It actually prints in hexadecimal system. If you really want to see the address as a number in decimal system, you can convert it to long and type
 std::cout << (long)(&x) << std::endl;
The above program can be summarized as
// addressPrinting.cpp 
// compile with 
// c++ addressPrinting.cpp -o addPrinting 
// execute with 
// ./addPrinting 
#include <iostream>
int main(){
 int x;
 std::cout <<  (long)(&x) << std::endl;
}
You will notice that every time you execute the program it will print a different address. Every time the program is loaded to and executed from a different place in memory.

Mutator problem

An example when addresses are useful is when we want to modify the variables inside the functions. Functions that change their arguments are called mutators. Let us assume that we want to write the function that accepts the integers x and y and is required to add the number 1 to x and the number 2 to y.
A naive approach would be the following.
// mutatingNaive.cpp
// compile with
// c++ mutatingNaive.cpp -o mNaive 
// execute with
// ./mNaive
#include <iostream>
void addOneToXAndTwoToY(int x, int y){
 x=x+1;
 y=y+2;
}
int main(){
 int x,y;
 x=5; y=7;
 addOneToXAndTwoToY(x,y); 
 std::cout <<  "x=" << x << " and y=" << y << std::endl;
}
After executing the code, you will receive the output
x=5 and y=7
which means that x and y are not changed by the function. In order to see what happened behind the scene we will analyze the code starting with the function main().
Step 1. The line int x,y; requires two memory locations from the computer and asks the computer to accept internal names x and y for these memory locations.
Step 2. The line addOneToXAndTwoToY(x,y); calls the function addOneToXAndTwoToY and passes the value 5 instead of the first argument and the value 7 instead of the second.
Step 3. When the function is called, the function can be thought of as a separate new program within the program. The declaration specifies that it will require two memory locations for two integers. The function will want to call them x and y. These happens to be the same names as the names used by the main function but these will be brand new memory locations. They will contain the values 5 and 7.
Step 4. The value inside the location x within the function gets increased to \(6\), while the value x inside the main program stays 5.
Step 5. Similarly, the value inside the location y within the function gets increased to \(9\), while the value y from main() stays 7.
Step 6. The function finishes its execution and deletes its variables x and y. So, the values 6 and 9 that we were after are actually wiped out.
Step 7. The main function ends its job by printing 5 and 7 to the standard output.

Using pointers to solve the mutator problem

C++ copies the arguments to the functions. Hence, if we want to create functions that are mutators, we need to use a trick: We will not use variables as arguments of the functions. The arguments of the functions will be addresses of variables. In other words, we will call the function in the following way
 
addOneToXAndTwoToY(&x,&y); 
Once the function is executed, it will receive the address and then the function will access the locations of these address and modify their contents.
If we just make the above modification to our code, it won‘t compile. The reason is that &x and &y are not of type int and the declaration
void addOneToXAndTwoToY(int x, int y)
expects integers. They quantities &x and &y are called pointers to int. Beginner-friendly programming languages would spell out this variable type and introduce a descriptive names for such variable types, and in friendly languages the function declaration would look something like
void addOneToXAndTwoToY(pointer_to_int pX, pointer_to_int pY) // incorrect declaration 
However, C, C++, and most of its descendants use int* to denote the pointer to integer, and the declaration must be
void addOneToXAndTwoToY(int* pX int* pY) // correct declaration
This creates a confusion with novices because the same symbol * is used for different purposes. When we write 7*8 we are multiplying the numbers \(7\) and \(8\). However when we write int* pX; we are issuing a command
Dear computer, please give me enough memory to store an address of an integer. We will call the content of this memory by the name pX.
To make the matters worse, * does not have to be affixed to int, and each of the following is correct: int * pX, int* pX, int *pX;.
We need to modify the code inside the function so that it now accesses the location with the address pX and increases its content by 1. The function also must access the location with the address pY and increase its value by 2. A gentle language would use a syntax that looks something like
void addOneToXAndTwoToY(int* pX, int* pY){
 content(pX)=content(pX)+1; // not C++, unfortunately 
 content(pY)=content(pY)+2; // not C++, unfortunately 
}
The designers of C++ thought that content is too long to type, and they decided for something shorter. Unfortunately, they decided to use * and now instead of content(pX) we write *pX. The updated correct code is given below
// mutatingCorrect.cpp
// compile with
// c++ mutatingCorrect.cpp -o mCorrect 
// execute with
// ./mCorrect
#include <iostream>
void addOneToXAndTwoToY(int* pX, int* pY){
 (*pX)=(*pX)+1;
 (*pY)=(*pY)+2;
}
int main(){
 int x,y;
 x=5; y=7;
 addOneToXAndTwoToY(&x,&y);
 std::cout <<  "x=" << x << " and y=" << y << std::endl;
}

Accessing the content from the pointer

As we have seen in the previous section, *pX is used to access the content of the memory location whose address is pX. The following code is another example of accessing the location of the variable x using its address.
// pointersIntro01.cpp
 // compile with
 // c++ pointersIntro01.cpp -o pIntro01
 // execute with
 // ./pIntro01
 #include <iostream>
 int main(){
 int x;
 int *pX;
 x=30;
 pX=&x;
 std::cout << "pX="  <<  pX  << std::endl;
 std::cout << "*pX=" <<  *pX  << std::endl;
 *pX=45;
 std::cout << "x=" << x << std::endl;
 return 0;
 }

Allocating and freeing memory

In previous examples the pointers were used as addresses to the memory locations already occupied by other variables. For instance, pX=&x; results in pX pointing to the memory location occupied by x.
It is possible for a pointer to contain an address that is not assigned to the other variable that the programmer has requested from the computer.
Consider the following code, that you should not try to compile and execute.
// DANGEROUS CODE - DO NOT COMPILE/EXECUTE
#include <iostream>
int main(){
 int *pX;
 pX=(int*)(100);
 std::cout << *pX << std::endl;
 return 0;
}
In the lines above we assign to pX the memory address \(100\). Then we attempt to print the content of this address. Usually, the operating system will return an error, or the program may crash. Namely, the address \(100\) is likely given to some other program and we are not allowed to access it. In contrast, when we wrote pX=&x; then the address &x is an address to which we have the right of access. This is the address we received after issuing a command int x; in which we requested from the computer to give us a memory location to store an integer.
We may use the command new to request a memory location. The command pX=new int; requests a location for one integer. The address of the obtained location is then stored in pX. After allocating the memory with new we are allowed to access it with *pX. When we no longer need the memory we return it to the computer using the command delete pX;. The computer can later assign this returned memory to other program or to our own program if we ask again.
// pointersNew.cpp
 // compile with
 // c++ pointersNew.cpp -o pNew
 // execute with
 // ./pNew
 #include <iostream>
 int main(){
 int *pX;
 pX=new int;
 *pX=37;
 (*pX)+=17;
 std::cout << *pX << std::endl;
 delete pX;
 return 0;
}

Memory leak

Memory leak is a dangerous bug that computer programs can have. It occurs when a programmer fails to return the memory allocated using the pointer new. The following few lines of code show an example of a memory leak.
int *pX;
pX=new int;
*pX=37;
pX=new int;
*pX=73;
delete pX;
There are two commands of the form pX=new int;. After the first one, the computer gave us a memory to store one integer. We chose to store \(37\). However, when we called the command pX=new int; for the second time, then the computer issued us a new memory. The variable pX stores now the address of this new memory, while nobody else points to our good old number one 37. The memory location that holds the number 37 is lost forever. Nobody points to that memory and the computer still thinks that our program needs it. The computer will not allocate this memory to some other process, and since we don‘t have a way to access it again, until our program is turned of (or the computer restarted), we have permanently occupied a piece of RAM memory that nobody else is allowed to use.
Memory leaks are especially dangerous when they occur within recursion or a loop. The entire RAM memory of the computer can go missing within. a nanosecond.
The following youtube video is an interesting introduction to pointers in C. When watching the video keep in mind that pointers in C are slightly different that instead of new they use malloc. Here is the link to the video.

Linked lists

Linked lists are used when the programmers do not know the size of the memory that the program will need. The memory requirement are often determined by the user who executes the program.
Consider the problem in which the user enters the integers one by one until the users enters \(-9\). At that time the program needs to add \(7\) to each of the integers and print the new integers in order in which the user has entered them.
We will create a structure called linked list. The main ingredient is an object of the class ListNode. The list node consists of two pieces of data: content and a pointer pointerToNext that keeps the address of the next element of the list. The declaration of the function is
class ListNode{
 public:
 int content;
 ListNode *pointerToNext;
};
When the user enters the integers we will keep them in a linked list. The list will be kept by having the pointer to its first element. This pointer will be called head. The last node in the list will have a special value, nullptr, assigned to its component pointerToNext. The value nullptr points nowhere and it will signify to us that we are at the end of the list. The ListNode is declared with
ListNode *head;
After the above declaration it points nowhere, and when the user enters the first number (that we will call input) we will allocate the memory for the first ListNode and set its content to input. We will set the pointerToNext component of this node to contain the value nullptr because in the very beginning this first list element is at the same time the last element. The following code accomplishes the input of the first element of the list.
int userInput;
ListNode *head;
std::cout << "Insert the first element of the list: ";
std::cin>>userInput;
head=new ListNode;
(*head).content=userInput;
(*head).pointerToNext=nullptr;
The user needs to supply the remaining elements of the list. Since we must keep the address of the first element of the list, we need a new variable, other than head to facilitate the creation of the list. We will use the name runner to call this new pointer. The pointer runner will keep track of the last element of the list that is entered. Some people like to call it tail. In the beginning runner needs to point at the exact same location as head. This is accomplished with
ListNode *runner;
runner=head;
When the user gives us the next value in userInput we first check whether it is \(-9\). If it is, we will not put this in our list. Instead, we will finish the data entry. If the userInput is a value other than \(-9\), we need to create a new node whose content is userInput. We also need to link this new node to the end of the current list. Since runner points to the tail of the list, our while loop has to look like this
while(userInput!=-9){
 std::cout << "Insert an element of the list (-9 for the end): ";
 std::cin>>userInput;
 if(userInput!=-9){
             // *runner is the last node in the list (tail)
             // (*runner).pointerToNext is currently nullptr
             // We now allocate new memory for ListNode and make
             // (*runner).pointerToNext to contain the address
             // of this new ListNode
 (*runner).pointerToNext=new ListNode;

              // runner is no more pointing to the tail
              // The next line updates the runner to point
              // to the newly created tail
 runner=(*runner).pointerToNext;
            
             // We now set the content of the tail
 (*runner).content=userInput;
             // and make sure that the tail‘s pointer
             // to the the next is set to nullptr
 (*runner).pointerToNext=nullptr;
 }
}
Once the list is created we will start from head, add 7 to each term and print the result on standard input. _/p_
    std::cout << "List printout: " << std::endl;
    runner=head;
    while(runner!=nullptr){
        std::cout << 7+(*runner).content << " ";
        runner=(*runner).pointerToNext;
    }
    std::cout << std::endl;
The final task is to free the memory occupied by our list. This time we have to start from the back of the list and delete the terms. This is elegantly accomplished using recursion. In each step we perform two steps in this precise order
Step 1. clean the tail
Step 2. delete the memory occupied by the current head.
Notice how tricky the Step 1 is. It will recursively first call the cleaning of the tail of tail. We will create the function freeTheMemory and apply it to head. The function looks like this
void freeTheMemory(ListNode *runner){
     if( runner!=nullptr){
         freeTheMemory((*runner).pointerToNext);
         delete runner;
 }
}
The entire code is given below. You may notice that the compilation of the code requires the addition of compiler flag -std=C++11. The reason is that we are using nullptr that is supported only in C++11 standard. More explanation is provided below.
 // linkedList.cpp
 // compile with
 // c++ linkedList.cpp -o lList -std=c++11
 // execute with
 // ./lList
 #include <iostream>
 class ListNode{
 public:
 int content;
 ListNode *pointerToNext;
};
 void freeTheMemory(ListNode *runner){
 if( runner!=nullptr){
 freeTheMemory((*runner).pointerToNext);
 delete runner;
 }
}
 int main(){
 int userInput;
 ListNode *head;
 std::cout << "Insert the first element of the list: ";
 std::cin>>userInput;
 head=new ListNode;
 (*head).content=userInput;
 (*head).pointerToNext=nullptr;
 ListNode *runner;
 runner=head;
 while(userInput!=-9){
 std::cout << "Insert an element of the list (-9 for the end): ";
 std::cin>>userInput;
 if(userInput!=-9){
 // *runner is the last node in the list (tail)
 // (*runner).pointerToNext is currently nullptr
 // We now allocate new memory for ListNode and make
 // (*runner).pointerToNext to contain the address
 // of this new ListNode
 (*runner).pointerToNext=new ListNode;
            
 // runner is no more pointing to the tail
 // The next line updates the runner to point
 // to the newly created tail
 runner=(*runner).pointerToNext;

 // We now set the content of the tail
 (*runner).content=userInput;
 // and make sure that the tail‘s pointer
 // to the the next is set to nullptr
 (*runner).pointerToNext=nullptr;
         }
     }
 
     std::cout << "List printout: " << std::endl;
     runner=head;
     while(runner!=nullptr){
   std::cout << 7+(*runner).content << " ";
 runner=(*runner).pointerToNext;
 }
 std::cout << std::endl;

 // FREEING THE MEMORY
 freeTheMemory(head);
 return 0;
}
Example. The user input consists of integers. The input \(-9\) is the end, and unless it is the first integer, it is not to be considered the part of the input. Create a linked list from the numbers that the user has entered. The user enters another integer. If this integer is in the list, delete its first occurrence from the list and print the remaining list. If it is not in the list, print the original list.