CSCI.1200 Computer Science II
Summer, 2002
Worksheet 4
Pointer Arithmetic

Reading: Deitel & Deitel, sections 5.1 - 5.8

Memory Leaks

A memory leak is a situation in which memory assigned to your program can no longer be accessed because there is no pointer pointing to it. Here is a trivial example.

int *p;
p = new int[3];
int i;
for (i = 0; i < 3; ++i) 
    p[i] = i;
p = new int[10];

The memory allocated by the first call to new can no longer be accessed by your program because there is no pointer pointing to it.

Suppose the first call to new allocated memory at address 10000, and the second call to new allocated memory at address 15000. This can be diagrammed like this.

Memory leaks will not cause any short term problems with the running of your program (memory leaks are usually completely invisible). But if your program runs for a long time and has lots of memory leaks, eventually, the system will run out of memory and your program will crash.

The ``stranded memory" is called garbage.

If you have allocated some memory from the heap to your program by using new, and you will not need this memory any more, you should return this memory to the heap with the delete operation. The keyword delete is followed by a pointer which points to memory obtained by using new.

   int *p;
   p = new int;
   // do stuff with p
   delete p;

The syntax to delete an array is delete [] p.

Deleting memory is one way to avoid memory leaks. You should delete memory that you have allocated using new when you are finished using it.

Alert: After you have released the memory pointed to by a pointer using delete, make sure that you do not try to access that memory again, since the memory pointed to no longer belongs to your program. This is called a dangling pointer error and can cause your program to crash (or worse, give strange results).

Note that the delete operation does not change the value of a pointer. It is a good habit to follow up a delete operation by setting the pointer to NULL immediately afterwards. Note also that you can only delete memory that was obtained with new (i.e., you cannot delete variables or arrays declared in your program).

Note that if two or more pointers are pointing to the same memory, and that memory is deleted, references to any of these dangling pointers will result in errors as shown below.

    float *p, *q;
    p = new float[100];
    q = p;                // p and q both point to the same memory
    for (i = 0; i < 100; ++i)
       cin >> q[i];       // read in 100 floating point numbers from stdin
    delete [] p;          // delete the memory
    cout << q[17];        // error, q now points to inaccessible memory

Exercise 1: In the following program, identify all of the lines which would produce memory leaks, dangling pointer errors, or memory exception errors. Also show what would be printed. It helps to draw a diagram like that on the first page, and keep adding to it or modifying it as you proceed through the code.

#include <iostream>
using namespace std;
int main()
{
    float *p1, *p2, *p3, *p4;
    float d = 2.67;
    int i;
    p1 = new float[3];
    for(i = 0; i < 3; ++i) {
       p1[i] = d;
       d += 1.0;
    }
    p2 = p1;
    *p2 = 6.54;
    *p3 = 3.33;

    for (i = 0; i < 3; ++i) 
        cout << p1[i] << ' ';
    cout << endl;
    delete p1;
    *p2 = 12.4;
    p1 = new float[5];
    d = 4.2;
    for(i=0;i<5;i++) {
       p1[i] = d;
       d += 1.0;
    }
    p4 = new float[5];
    d = 7.8;
    for (i = 0; i < 5; ++i) {
       p4[i] = d;
       d += 1.0;
    }
    p1 = p4;
    p2 = p4;
    for (i = 0; i < 5; ++i) 
        cout << p1[i] << ' ';
    cout << endl;
    return 0;
}

Arithmetic on pointers

In the previous worksheet, we saw a number of operations that could be done on pointers. These included the following:

• the assignment operator =
• the is equal operator ==
• ths is not equal operator !=
• the deferencing operator *

You can also use some arithmetic operators on pointers. Here is an example of the use of the ++ operator to cause a pointer to go through an array, one element at a time:

    float *p, *q;  //declare pointers to a floating point variable
    p = new float[20];  // get enough contiguous memory for 20 floats
                        // p points to this newly allocated memory
    q=p;                // p and q point to the same address
    *q = 1.23;          // assign 1.23 to the first of these 20 cells
    q++;                // increment q.  It now points to the second cell
    *q = 4.56;          // p[1] is assigned the value 4.56
    q++;
    *q = 7.89;          // p[2] is assigned the value 7.89 
    // etc.

The ++ operator can be combined with other operations, just as it can with numeric arithmetic. The following is equivalent to (but harder to understand than) the code above:

    float *p = new float[20];
    float *q = p;
    *q++ = 1.23;
    *q++ = 4.56;
    *q++ = 7.89;
    // etc.

This same computation can be done with the + operator instead. In that case, the pointer remains in the same place, unlike pointer q above. Here is yet another way to go through the the array:

    float *p = new float[20];
    *p = 1.23;
    *(p+1) = 4.56;
    *(p+2) = 7.89;
    // etc.

Pointer arithmetic automatically adjusts for the size of the data type that a pointer points to. For example, if float *p is pointing to memory starting at location 10000 in the example above, p+1 refers to the memory location 10000 plus the size of a float, which on our systems is four bytes. Ordinarily, though, you don't need to know how big they are.

If you do have need to know these sizes, the built-in operator sizeof can tell you how many bytes of memory a variable or data type takes up. Some examples, with sizes from our Intel/Windows systems:

    int i;   int iray[6];  int * iptr;
    cout << sizeof(i);       // prints 4, the size of an int
    cout << sizeof(iray);    // prints 24, 4 bytes times 6 elements
    cout << sizeof(iptr);    // prints 4, the size of any pointer variable
    cout << sizeof(double);  // prints 8, the size of a double

Exercise 2: Write a complete C++ program that stores powers of two in contiguous memory. Your program should first prompt the user for the maximum power of 2 (hint: $2^{30}$ is the largest power that an int can hold), then dynamically allocate enough memory to hold the powers of 2 up to that number, and store the values. To make sure that you have done this correctly, go through the array and print out the values using cout. Instead of using an array index (an integer in square brackets), you should use pointer arithmetic to assign and retrieve the values. If the user had entered 5, the output should look like this:

0    1
1    2
2    4
3    8
4   16
5   32

Relationship between pointers and arrays

When you declare an array variable, it is really a pointer. The following two statements are equivalent in many ways.
char s[80];
and
char *s = new char[80];

Just as you can use array syntax on a block of memory obtained from the heap using new, you can also use pointer arithmetic on an array. Here is an example:

   float s[80];
   float *t;
   t = s+3;
   *t = 4.4;   // equivalent to s[3] = 4.4;

This can be diagrammed as follows.

(We are assuming that a float takes four bytes to store. Remember, you do not need to know the sizes of data types to work with pointer arithmetic.)

In general, s[i] is equivalent to *(s+i).

Alert: The parentheses above are required to duplicate the effect of the array brackets. The following example shows what happens if you leave them out:

    int i[3] = {1, 5, 9};
    cout << *(i+1) << endl; // prints 5 -- this is the same as i[1]
    cout << *i+1 << endl;   // prints 2 -- (*i) + 1, which is 1 + 1

There are also some differences between char s[80] and char *s = new char[80]. In the former case, s cannot be reassigned to point to other memory, sizeof(s) = 80, and its memory cannot be freed using delete. In the latter case sizeof(s) = 4 (for 32 bit architectures like the Intel Pentium), and you must take care not to create a memory leak and to properly delete the memory when you are finished using it.

So when do you use an array versus allocating memory with new? Arrays are better if you know exactly what size the array can be, and can fill in a definite number. If the size must be determined based on a number typed by the program user or by the size of an input file, then a pointer and new are appropriate.

Other operations on pointers

So far, we have seen the following operations on pointer variables:

* dereferencing or indirect addressing. Get the value at the address pointed to by the pointer.
= assigns a value to a pointer.
+ adds an integer value to a pointer, similar to array indexing
++ increments the address that a pointer points to so that it points to the next cell in an array.
== tests if two pointers are pointing to the same address.
!= tests if pointers are pointing to different addresses.

In addition, we have seen that the operator & returns the address of a variable.

There are a number of other operations which are allowed on pointers.

-- decrements a pointer so that it is pointing to the previous cell in an array.
- subtracts an integer from a pointer.

The following are valid operators, but are rarely needed:

> checks if one pointer address is greater than another
< less than
>= greater than or equal to
<= less than or equal to

Review After using new to obtain memory for an array of some data, there are three ways of accessing individual elements in the array. The following three examples do exactly the same thing.

example 1

int *p = new int [10];
for (int i = 0; i < 10; ++i) 
    p[i] = 0;

example 2

int *p = new int [10];
for (int i = 0; i < 10; ++i)
    *(p+i) = 0;

example 3

int *p = new int [10];
int *q = p;
for (int i = 0; i < 10; ++i)
    *q++ = 0;

Alert: You should always maintain a pointer to the start of the block of memory; otherwise, it is difficult or impossible to get or change data in it or to free it when it is no longer needed. The following example loses the pointer to the start of the array.

example 4

// bad code; don't do this
int *p = new int[10];
for (int i = 0; i < 10; ++i)
    *p++ = 0;
// Note that p now points to the first address past the end
// of the array, and it is difficult to get to data in the array

Pointers and functions

You can pass pointers as arguments to functions, and you can return pointers from functions. Here is a code fragment that shows the syntax of passing pointers as arguments and returning pointers.

// In calling function
char *p;
p = new char[80];
...
FunctionOne(p)
...
char *q;
q = FunctionTwo();
...

// end of calling function

void FunctionOne(char *s) { 
...
}

char *FunctionTwo() {
   char *s;
   ...
   return s;
}

This code fragment uses pointers to chars, but of course you could use any types of pointers. Note that when a pointer is passed as an argument to a function, the function does not know how much memory the pointer is pointing to (if any). Thus your program has to either pass a second integer argument which tells the function how much valid memory the pointer points to, or else use a convention such as '\0' to indicate the end of the array.

Exercise 3: Write three versions of the function
bool IsInString(char *s, char target)
This function returns true if the character target is in the string s and false if target is not in s. Recall that all character strings are terminated with the character `\0'.

The three versions should use the three search methods described above. The first should use array notation (that should be very easy). The second version should use pointer-plus-integer arithmetic (i.e., use a pointer plus an integer that you increment) to go through the string. The third version should use a second pointer which is initialized to the start of the string, and this pointer should be incremented.

Exercise 4: It often happens that a program needs to be able to store an arbitrarily large number of elements in contiguous memory. There is a trade off between run time and wasted memory. A call to new is fairly time consuming, and so you don't want to make too many calls to it, but on the other hand, you don't want to allocate a lot of memory that you may not need.

Here is a commonly used method for dealing with these two contradictory needs. Start by allocating enough space for 100 elements. Whenever the currently allocated space fills up, allocate new memory twice as large, copy the current elements to the new space, then free up the old space. Thus, the first call to new, made initially, will allocate 100 elements, the second call will allocate 200 elements, the third call will allocate 400 elements, the fourth call will allocate 800 elements, and so on.

Write a program to do this. You should generate a sequence of random integers of size 1,000, 5,000, and 10,000 to test your program.

After you have filled up the array, print them out to make sure that your program works correctly.

Solution to exercise 1

#include <iostream>
using namespace std;
int main()
{
    float *p1, *p2, *p3, *p4;
    float d = 2.67;
    int i;
    p1 = new float[3];
    for(i = 0; i < 3; ++i) {
       p1[i] = d;
       d += 1.0;
    }
    p2 = p1;
    *p2 = 6.54;
    //   *p3 = 3.33;  //memory exception error

    for (i = 0; i < 3; ++i) 
      cout << p1[i] << ' '; // prints 6.54 3.67 4.67
    cout << endl;
    delete p1;
    //    *p2 = 12.4;  // dangling pointer error
    p1 = new float[5];
    d = 4.2;
    for(i=0;i<5;i++) {
       p1[i] = d;
       d += 1.0;
    }
    p4 = new float[5];
    d = 7.8;
    for (i = 0; i < 5; ++i) {
       p4[i] = d;
       d += 1.0;
    }
    p1 = p4;// memory leak
    p2 = p4;
    for (i = 0; i < 5; ++i) 
      cout << p1[i] << ' '; // prints 7.8 8.8 9.8 10.8 11.8
    cout << endl;
    return 0;
}