If several problems have solutions that are generally similar, but differ in some details, a good technique to use is "indirection". That is, in the places where the details differ, replace those details by an indirect reference to the details.

The consequence is that much (maybe almost all) of the code doesn't have to change when applied to each of the problems.

How can indirect references be coded in C++?

Answer: By using a pointer type.

A pointer value is just a memory address of some other value. Suppose this other value has type int. Then the type of the pointer is pointer to int.

Here is how to declare a variable p of type pointer to int.

      int *p;  // preferred form

or

      int* p;  

or

      int * p; 
    

But how can we get values to assign to p?

One very special value is NULL. This is just the address 0.

It is special because this location is protected and provides no access (read or write) to the contents of address 0. Consequently, it is useful to think of this address as meaning the pointer with value NULL is initiallized but is not pointing to any value - don't try to get the value!!

The address operator, & is a unary prefix operator. Its value is the address of its operand and its type is pointer to the type of its operand

For example, given the declaration

	  int x = 5;

      

the type of

	  &x
	

is pointer to int.

We can declare a variable of this type and use the address operator to initialize it.

	  int x = 5;
	  int *p = &x;
	

Memory is logically just a sequence of numbered locations, each one able to hold 1 byte of data. The addresses go from 0 to M - 1, where M is the total number of memory bytes available.

In general, we don't need to know the actual address values as numbers in the range 0 to M-1. But it is useful in discussing pointer types to look at some example concrete numbers as addresses.

For example suppose variables x and p are stored in consecutive memory locations. Since memory is byte addressable and an int requires 4 bytes, if x begins at address 4000, it also uses the next 3 bytes as well at 4001, 4002, and 4003. So variable p's value would be stored beginning at address 4004 as indicated in the figure below.

The actual address numbers are not so important. That is, the fact that the value stored in p might be the address 4000 is not as useful as:

The value stored in p is the address of the variable x.

The address operator wouldn't be of much use if C++ didn't provide some way of using the address to get to the value at the address.

That is, if we only have the address of the details, how do we actually access the details.

The dereferencing operator is a unary operator *. It is also a prefix operator (comes before its single operand). It uses the same operator symbol as the binary multiplication operator, but its meaning is quite different.

If p has type pointer to int, then the dereferencing operator applied to p:

	  *p
	

serves as an expression that represents not p's value, but indirectly the int value at the address stored in p.

For example, given the declarations with initialization

	    int x = 5;
	    int *p = &x;
	    double y = 3.5;
	    double *q = &y;

	  

both x and y can be changed indirectly by using the pointer variables p and q and the dereferencing operator *

A good way to think of this is that *p is an alias for x and *q, an alias for y. So the assignments using *p and *q above are equivalent to:

 x = 10;
 y = y + 1.0;
	  

A pointer variable is a variable. That is, its address value can change during program execution just as an integer value can change.

The advantage is that the same code can be executed more than once but produce different values or affect different locations by just changing the address in the pointer variable.

Here is an examle that demonstrates the technique (but not its true power).

 void f(int *p)
 {
    *p = *p + 1;
 }

 int main()
 {
   int x = 5;
   int y = 10;

   f(&x); 
   f(&y);

   // Now what is the value of x? of y?
   ...
 }
	

At the first call to function f, *p is an alias for main's x. At the second call, it is an alias for main's y.

Array elements are always stored one right after another in memory with no gaps. This makes it easy to calculate the address of the 100-th element or the 1000-th element in an array by just knowing the address of the first element and the size of each element.

Consider the following:

The name of the array here is a.

a[3] is just one element in the array and is of type int. This int begins at address 4012 and the int value at that location is 4.

But a (without the subscript) should mean the whole array.

Important note: In C++ the whole array is identified by knowing the address of the first int; that is, by the address of the first element. If the array name, a is used in an assignment or other expression, its value is calculated by converting it to address of the first element - a pointer value.

 int a[5];
 int *p;

 p = a;	    
	  

The right side of the assignment a is converted to a pointer value (the address of a[0]) and assigned to p.

Pointers can also hold the address of (i.e., point to) a value of class type.

class Car
{
  double fuel;
  double mpg;
public:
  Car();
  Car(double theMpg);

  void addGas(double amt);
  void drive(double amt);
}

int main()
{
  Car myHybrid(30);

  Car *p = &myHybrid;

  myHybrid.addGas(20);

// equivalent to:

  (*p).addGas(20);

  myHybrid.drive(100);

// equivalent to:

  (*p).drive(100);
  ...
}
	  

Warning: It would be incorrect to write

 *p.addGas(20);	    
	  

There are two operators - the dereferencing operator * and the member access operator - .

Which one executes first? That is, which one has higher precedence?

The dot operator (member access) has higher precedence. So the parentheses are necessary. The variable p is not of type Car; its type is pointer to a Car.

For a pointer to a class type, it is much more common to use a single operator, -> for member access than the two operator combination above (dereferencing operator plus the member access operator).

int main()
{
  Car myHybrid(30);

  Car *p = &myHybrid;

  myHybrid.addGas(20);

// equivalent to:

  p->addGas(20);

  myHybrid.drive(100);

// equivalent to:

  p->drive(100);
  ...
}

Declaring variables in a function creates storage for those variables when the function is called.

This kind of storage only lasts until the function returns.

This is good! The variables are only used inside the function and the storage is automatically released when the function returns!

But this isn't always what a programmer needs.

For example, this makes it difficult to write a function:

	    double *makeArray(int n);
	  

that would create an array of doubles with n elements and return a pointer to the first element of the the array.

Why? Well if the makeArray function declares a local array of size equal n and returns it, the storage for the array would disappear (be released) just as it was returned to the caller. Released (or free) memory is likely to be reused for another purpose and so any data stored in it could be overwritten very soon.

The new operator is also a unary prefix operator. Its single operand is a type expression as used in variable declarations and it allocates new memory storage of the same size as required by the expression. It returns (evaluates to) the beginning address of this memory storage.

So the type of a new expression is pointer to ...

New Example 1: simple types

    int *p;

    p = new int;

    *p = 5;

    cout << *p << endl;

	  

What variable *p an alias for here?

Answer: none. When new is used, it returns the address of an unnamed chunk of memory of the right size to store values of the specified type.

The only way to access this value may likely be using the pointer and the dereferencing operator.

Class types can be used with new. But just as with declarations, a constructor must be used so that the class value that new creates is properly initialized.:

 Car *p;
 Car *r;

 p = new Car(20);
 r = new Car(); // or new Car;

 p->drive(100);
 r->addGas(16);

	  

An integer can be added to a pointer and the result is again an address. The idea is that if a pointer p stores the address of some integer, then p + 1 should be the address of the next integer!

Since an integer is typically 4 bytes, to calculate the actual address computed by p + 1, the integer is scaled (multiplied by) 4 (the size of an integer).

For example, if p is initialized with the address of an array element a[0], then p+1 will be the address of a[1].

Pointer arithmetic and the dereferencing operator make it possible to use subscripts on pointers just as with arrays.

For example, with the declarations below, p has value &a[0] and

 *p       is the same as a[0]	    
 *(p +1)  is the same as a[1]
 *(p + 2) is the same as a[2]
 ...
	  

Actually C++ interprets subscripts for ordinary arrays using pointer arithmetic and the dereferencing operator

 a[0] is just *a
 a[1] is just *(a + 1)
 a[2] is just *(a + 2) 
 ...
	  

So it is also allowed to use subscripts on pointers and

 p[0] is just *p
 p[1] is just *(p + 1)
 p[2] is just *(p + 2)
 ... 	    
	  

So what is the difference between an array a and a pointer p?

 int a[100];
 int *p;	    
	  

Here is a function that sorts n integers in the array passed to a:

 void sort(int a[], int n)
 {
   for(int len = n; len > 1; len--) {
     int maxpos = 0;
     for(int i = 1; i < len; i++) {
	if ( a[i] > a[maxpos] ) {
           maxpos = i;
        }
     }
     int tmp = a[maxpos];
     a[maxpos] = a[len-1];
     a[len-1] = tmp;
   }
 }    

But in C++ the way an array is passed is by passing the address of the first element. So the type of the receiving parameter is just a pointer and the sort function could equivalent be declared like this:

 void sort(int *a, int n);	    
	  

The new operator also has a version that can allocate an array of elements. The address of the first of these elements is the value returned by this version of new.

Example: Create an array of 100 doubles and store the beginning address in a pointer, dp

 double *dp;

 dp = new double[100];
	    
	  

This is called a dynamic array, because the size doesn't have to be know before execution. For example, we could read the desired size and then create the array using new:

 double *dp;
 int sz;

 cout >> "Enter desired number of array elements: ";
 cin << sz;

 dp = new double[sz];
 ...
	  

We can now use this feature of dynamic arrays to provide an excellent solution to the restriction that array sizes must be known when a program is written (compile time)! This makes programs much more robust and flexible.

The point is that we want to use this program with any file of numbers. The number of values in the file can vary and so it is not known when the program is written.

How can we do this?

• Initially create a dynamic array of size, say 10.
• Keep track of the array size and how many elements have been stored in it.
• If the array fills up
  • create another one of twice the size
  • copy the values from the old array into the new array
  • insert the new item and increment the element count

Problem: This causes a memory leak!

If a function uses new to allocate memory, this memory is not released when the function returns!

It is the C++ programmer's responsibility to explicitly release memory when it is no longer used.

The delete operator is a unary operator that returns no value. Its operand must evaluate to the address of a memory location that was returned previously by the new operator!

Example 1: Create an integer with new,use it then release it.

 int *p = new int;
 cin >> *p;
 ... 
 delete p; 

Note: delete p doesn't delete p! It releases the memory whose address is stored in p.

Example 2: Create an array of doubles, do something with them (not shown), the relase the dynamic array.

double *q = new double[1000];

for(int i = 0; i < 1000; i++) {
   q[i] = sqrt(i);
}
...
delete [] q;

It is annoying to have to include the [] when releasing the memory for a dynamic array, but the close connection between pointers and arrays creates a subtle difference between including the square brackets, [], and not. So we are stuck with including the square brackets for 99.9999% of the the cases we want to delete a dynamic array.

This example will illustrate the key steps in creating and using a dynamic array. It implements the ideas above for reading and sorting an unknown number of integer values.