Introduction to Computer Science - C++

Strings, Pointers and More Arrays

        Now that you have learned what an array is, it should be clear that just as you can make an array of int's or float's, you can also make an array of char's. The special thing about an array of char's though, is that an array of char's is capable of storing words or sentences. If you make an array of characters and then put a NULL at the end, you have created a special array called a string.

A string is a NULL terminated array of chars*.

cin and cout are built to work with strings. That means that if you give, for example, cout the name of a NULL terminated char array, it will print out the entire array until the NULL is reached. If, however, you supply cout with a regular char array (i.e. one which is not NULL terminated) it will print beyond the end of the array. It will continue printing the junk in memory after the array until it reaches a NULL somewhere in that junk. Make sure to only give cout or cin a single character or correctly formed string.

Strings are not so hard to create. Any set of character literals inside quotation marks is automatically followed by a NULL, so it is a string. It can be assigned to an array of chars and then that array will be a string. Let's see an example of the power of cin and cout with strings.


int main()
{

char ar[60]="greg";
cout<<ar;
//// ar="hheeee"; //illegal
cin >>ar;
cout<<ar;

return 1;
}
In this example I created an array of 60 characters (actually, while the array has 60 spaces, I can only use 59 of them for the letters of a string because I need one for a NULL at the end).

Then I assign the array the literal string "greg". (This can ONLY be done when the array is declared, not afterward.) The first four spaces of the string contain the letters greg and the fifth space contains a NULL character. The remaining 55 characters in the array are not used and therefore contain unknown or junk data.

Then I overwrite the array with whatever the user types in. (Note: If he types more than 59 character I will over-run my array.)

Then I can print out the new contents of the array. Notice how cin and cout are smart enough to print the entire array when I give them the name of the array. This will not work with an int or float array. It only works with a NULL terminated character array. This is because the cin and cout functions know to read until they reach a NULL. Since int, float, short, etc. arrays are not necessarily NULL terminated, cin and cout have no way to know when the end is reached. Therefore they cannot print regular arrays. However, they can of course print the individual elements of an array.

Ok, now we have a string. But since the string is actually just an array of characters I can mess around with it. For example, I can print the array in backward order. First, I will show you how to print it in forward order. (This is actually what the function cout does when you give it an array name, but we will print each element ourselves manually instead of using cout's built-in capabilities.)


int printString( char myString[] )
{
int i;
for ( i = 0; myString[i] != NULL; i++)
  { cout << myString[i];
  }
return 1;
}

This function starts at the beginning of the array it is passed and keeps printing out the letters one at a time until it reaches the end of the array. ( Remember string arrays always end with a NULL, so the NULL will be my clue to know when the array is over.)

To print the array backward I first have to find the end of the array. So I will count till I get the end of the array and then work backward. Let's see the example:


int reversePrintString( char myString[] )
{
int i;
for ( i = 0; myString[i] != NULL; i++);
for ( ; i >= 0; --i)
  { cout << myString[i];
  }
return 1;
}
Notice that first I do a loop that does nothing except increment i till it reaches the end of the array. Then I create another loop to print the array from its last element to its first element.

I can also do other things, like, for example, find the first 'p' in the string. Or for example, change the original string by, say, taking any lowercase t's in the array and making them into capital T's. Let's see this second example.


int t_to_T( char myString[] )
{
for (int i = 0; myString[i] != NULL; i++)
  {
    if (myString[i]=='t')
        {
        myString[i]='T';
        }
  }
return 1;
}

As we explained in the section on arrays, the changes made here will affect the original array in the calling function. And notice, I did not print out the string in the function. I simply changed the string. If I would want to print out the array I would do that in the calling function, the main() function for example:


int main()
{
char charlie[100]="this is a test string.";
t_to_T( charlie);
cout << charlie;
return 1;
}

Notice that when I called t_to_T I passed the name of my string, charlie. I did not have to use and should not use the [ ] 's . Also notice that the string is much larger than it needs to be. This is ok, but I have wasted some 75 char's.

Array Copying

We know that the assignment operator ( = ) will copy the value of one data-type into a variable. For example I can write:
short p = 90; But the assignment operator will not copy an entire array. The following example will not compile because I am trying to copy a whole array into another array:


int main()
{
short lucy[10]={34,5,34,64,36,2,634,8,17,20};
short linus[10];
linus=lucy;
return 1;
}
In order to accomplish an array copy I need to loop through the entire array copying each element from one array into the other array one at a time. Let's see this example.

int main()
{
short i;
short lucy[10]={34,5,34,64,36,2,634,8,17,20};
short linus[10];
for( i=0;i<10;i++)
   linus[i]=lucy[i];
return 1;
}
If I were to write a function to copy an array to another array, I would need to also pass the size of the array so that I would know when to stop copying. Here is an example of a function to copy an array of shorts, ar1 into another array of shorts, ar2.

void shortArrayCopy( short ar1[], short ar2[], short size )
{
short i;
for ( i = 0; i < size; i++)
  {
    ar2[i]=ar1[i];
  }
return ;
}
Now, if I were to write the same function to copy one string into another string, I could do it without knowing the size of my string. Instead, I could use the fact that there is a NULL character at the end of the string to know when to stop copying. Since every string ( but not necessarily every char array) ends in a NULL, I can write a function to copy the contents of one string into another string without knowing the size of either array.

Here is a string copy function:


void stringCopy( char str1[] , char str2[])
{
int i;
for (i = 0; str1[i] != NULL; i++)
  {
    str2[i]=str1[i];
  }
str2[i]=NULL;
return;
}
Notice that I continue my for loop until I reach the NULL at the end of the string str1. Also note that I need to copy a NULL into my newly copied array. I need to do this because the loop will fail to copy the NULL from str1. So str2 will remain without a NULL at its end. If I leave it that way it will be a normal char array, but it won't be a string. In order to make sure it can be used as a string I need to make it a string. I do this by adding a NULL to the end. I know where the end is because I have counted my way through the array str1 using i as my counter. Therefore, I can copy a NULL into the i'th place of array str2.
Remember that you cannot use the = operator to copy an entire array whether it be a float array or even a string.

Pointers

If I declare a variable, let's say int a = 70; we know that the computer will find a block of memory and associate it with "a" such that any number I assign to "a" will be put into that block of memory. How can I find out where this memory location is? C++ provides a safe and easy way to do this. We use the ampersand &.

If I write:

int a = 70;
cout<< &a;
I will get a weird looking number on my screen which will represent the location in the computer's memory of "a". The function of the ampersand & in this case is to extract the address of "a". This may not seem very useful but later on it will be very useful. Right now you just need to understand what the & does. It is the basis for the next topic.

In the above example I merely printed that weird number. What if I wanted to store it in a variable. What type would that variable be? I can't use a simple int since this number is not really a regular int. It is the address of an int. It is a new type, an address of an int type. To declare a variable of this type we write:

int *p;
Now "p" is a variable of this special type which is capable of storing the address of an int. When I actually use "p" I no longer need to write the star *. I simply write p and the computer knows what type p is, just the same way as it knows what type "a" is. In order to create a variable capable of storing the address of a float, I would write something like this:
float *ppp;
In fact, all the primitive data-types in C++ have their own distinct "address of" types.

To store the address of "a" in "p" and then print it, I would write the following:

int a = 70;
int *p;
p = &a;
cout << p;

In the above example "p" is called a pointer because while it is not "a" it does point to the location of "a" in memory. Any variable we declare with a star * is a pointer to the type of variable declared. Thus, "ppp" is a float pointer. This is just a short hand way to say that "ppp" is a type capable of containing the address of a float. Now we will see that we can access a variable by means of its address. This is called dereferencing the pointer. This does not seem very useful at the moment, but it is very useful and we will see why.

Dereferencing

Let's say I have the address of a certain space in memory, how can I access or change its contents? For example, can I change "a" by means of "p"? The answers is yes, but I need to use a special operator, the asterisk *. (Yes, this is the same * we use in a pointer declaration, so it can be confusing. But this operator is only used not in a declaration.) By placing a star before "p" I indicate that I am refering to the content that the memory space "p" points to. In short hand this is called dereferencing "p". Here is an example which changes "a" from 70 to 90 by means of dereferencing "p":

int a = 70;
int *p;
p = &a;
*p = 90;
cout << a;

The " *p = 90; " in the above example means go to the place to which "p" points and go to the contents of that place and assign it the value 90. Since "p" points to the location of "a" , the contents of that location is "a". So "a" will be assigned the value 90. The use of the asterisk * to dereference a pointer should not be confused with its use in declaring a pointer. These two operations have nothing in common except their use of the asterisk symbol. This often confuses students. It would have been clearer if the inventors of C++ had used two different symbols for these two different operations, but they didn't.

If you ever by mistake tried to print an array of int's all at once using cout like this

int a[] = {1,2,3,4,5,6,7,8,9,10};
cout << a;
you probably notice you got a weird number on the screen and not your array contents. That number is the address in memory of the first element of your array. In general we should know that the name of an array is a pointer to its first element. We can use this fact in an interesting way. Remember that we cannot copy the values of one array to another except by copying each and every individual element of the array into the other array. But that doesn't mean we cannot assign another pointer to our array name. Look at the following code segment:
int a[]={34,14,25,3,64,29,45};
int i, *p;
p = a;
for(i=0; i < 7; i++)
    cout << p[i];
In this example, we print the elements of array "a" by referencing it through "p". Using the assignment operator = has not made a duplicate copy of the array, it has merely cause another pointer to point to the same array. Any changes made to the array via "p" will affect the array as accessed via "a" as well. This is because there is only one copy of the array in the computer memory.

You may ask yourself is there a data-type capable of storing the address in memory of "p" in the above example? In the above example, "p" is a pointer to an int. What type can store the address of this type? A regular int pointer (int *) won't do the trick. You will need to use a type designed to store an address of an address. This is known as a double pointer because it points to a pointer. You declare something of this type like this:
int ** pptr;
Now "pptr" can store the address of "p" like this:
pptr = &p;
You may guess correctly that this process can go on and on. We can have a pointer to a double pointer. And so on. But generally we will never need much more than a double pointer. Later we will see a practical use of double pointers.

Pointer As Function Parameters

Pointer Arithmatic

You can also reference an array by using pointers. Since the name of the array is a pointer to the first element of the array you can access the first element of the array by dereferencing like this:
int myArray[3];
*myArray =8;
The above line should be read as "the contents of the thing pointed to by the pointer myArray is assigned the value 8". And since array elements follow one after the other in memory, you can access the second element in the array like this:
int myArray[3];
*(myArray+1) =8;
This should be read as "the contents of the thing one after the thing pointed to by the pointer myArray is assigned the value 8". By adding one to the address of the first element of the array I got the address of the second element of the array. Remember the elements of the array are located in contiguous spaces in memory, so the address of the second element is exactly one more than the address of the first element. Once I have this address I can dereference it and change its contents. Thus we have two alternate methods of manipulating arrays: the normal array notation [] and the pointer arithmetic notation.

Dynamic Allocation of Memory

We have seen that we must decide the size of an array at the time of its declaration. Thus we must write:
float farray[100];
But we cannot write:
short size;
cin >> size;
float farray[size];
When the compiler sees an array declaration, he must know what size array to create from memory. These are static arrays. If we are to decide the size of an array during the program execution, we must have a way to create arrays dynamically. For this purpose we use the special command new. The new command returns a pointer to a new block of memory created at run time. This new block of memory can be of a size determined during program execution. Here is an example using new:
short * arrayPtr, size;
cin >> size;
arrayPtr = new short[size];
Since new returns a pointer, I created a pointer to store the location of my new memory block. I can access this memory the same way I would access a normal array. I can use array dereferencing like this:
arrayPtr[0] = 340;
or I can use pointer dereferencing notation. The pointer "arrayPtr" points to the first element of the array just like the name of an array points to the first element of an array. So for most practical purposes I have an ordinary array just like I had when I declared a static array. But I have created this array dynamically, i.e. at run time.

The new command can also be used to create a single variable at run time. Here is how to use new to create one variable:

float *ptr;
ptr=new float;
*ptr=3.1415;
You will notice that this float has no name, it only has a pointer to it. Therefore if I want to access it I need to use the dereference operator *. I can't access by its name like an ordinary data type since it has no name.

I can also supply the new float (or what ever data type I create) with a value at creation time. I do this like this:

float *ptr;
ptr=new float(3.1415);

Since "ptr" is a variable like any variable it can be used to point at one thing and then at another thing and so on. It is re-usable. So, for example, I can write the following:

float *ptr;
ptr=new float(3.1415);
ptr=new float(200.5);
Now, in this case ptr is pointing only to the second float I have created. How can I make ptr point back to the first float I created? I can't! I can't access that first float in any way. I have lost all knowledge of where it is in memory and I can never regain that information. This is called a memory leak. The memory assigned to the first float created is still in use by my program and I have no way to free it. Doing this repeatedly can cause a computer to run out of memory. Therefore, before you re-assign a pointer to a new piece of memory, you must free or delete the old data from memory. To do this you must use the delete command. Here is an example:
float *ptr;
ptr=new float(3.1415);
delete ptr; ptr=new float(200.5);
Note that the pointer is not deleted. The command delete frees the memory a pointer points to but does not delete the pointer itself. Use delete only on memory created with the new command. Since the pointer is not itself deleted, I may use it again, which I in fact do in the very next line of code.

Arrays created with the new command must also be deleted. In short, any time you create memory blocks with the new command, you must free them again with the delete command. Here is an example of creating and freeing an array dynamically:

int * arrayPtr;
int size;
cin >> size;
arrayPtr = new int[size];
delete [] arrayPtr;
arrayPtr = new int[size+10];
delete [] arrayPtr;
Notice that I deleted all the memory I created with new. There were two calls to new and so I called delete twice as well.

Multi-dimensional Arrays

So far we have had examples of array which are sets of variables. In these examples there has been one index for each element. If we would represent these arrays graphically they could be drawn as a row of numbers in boxes, like this:

index
0
1
2
3
4
5
6
7
8
9
values
20
17
2
34
61
2
75
93
32
8
Such and array is called one dimensional because it can be drawn in a linear or one-dimensional fashion. There also exists the possibility of making 2 or more dimensional arrays. These are also called multi-indexed or multi-subscripted arrays.

For example, a two dimensional array could be declared in the following way:

int myArray[10][3];
This will create an array of size 10 by 3 int's - a total of 30 int's will be created. I chose a 10 by 3 array. You can make an array of any size you like simply by changing the numbers you use in the array declaration. You could make an array of 3 by 10 or an array of 100 by 2 or 100 by 100, and so on.

When arrays are created, their elements are not assigned any initial values. Therefore we can't know what is in each cell of the array. It will likely be zero, but we can't be sure. We will call this content junk since it is meaningless data. I indicate this junk with the question mark. The above array could be drawn like this:

index
0
1
2
3
4
5
6
7
8
9
012
???
???
???
???
???
???
???
???
???
???

We access elements of two dimensional arrays by using 2 indexes. For example, if we wanted to assign the value 18 to the element at position 4 down and 2 across in the above array we would write something like this (remember, indexes start with 0 so the 4th row is index number 3):

myArray [3][1] = 18;

This would change the array in the following way:

index
0
1
2
3
4
5
6
7
8
9
012
???
???
???
?18?
???
???
???
???
???
???

Essentially, we now have a set of 30 integers which we can access (change or printed etc.) by using two sets of indices. The name of the array ( myArray ) refers to this whole set of integers.

We can also make arrays of 3 or 4 dimensions though these are impossible to draw in two dimensions, and they are bit harder to imagine in your mind. To think of a 3 dimensional array imagine a 2 dimensional array and then think of each cell in that array itself containing many elements. A three dimensional array is created in the following way:

int myArray[10][10][3];

This will create an array named myArray containing 300 integers. We can access any element of this array by using 3 indices. For example, if we wanted to assign the value 312 to the element at position 3 down and 7 across and 2 in, we would write something like this

myArray [2][6][1] = 312;

Once you grasp this you might be then able to think one more step. Imagine each element of your 3 dimensional array as containing not just one element, but a whole set of elements. It is quite hard to imagine anything more than 3 dimensions, but theoretically, you can have 4, 5, 6, 7, etc. dimensional arrays. In practice you should never use more than a 3 dimensional array for three reasons: (1) They will use up a lot of memory even with relatively small indexed ( an even sided 4 dimension array of size 100 integers will have 100,000,000 integers in it, or 400 mb of data ) (2) You will make errors (3) You will confuse anyone trying to read your code. Even using 3 dimensional arrays is not really advisable.

Dynamic Allocation of 2 Dimensional Arrays

We have seen that we can allocate a one dimensional array dynamically by using the new command. The same is true for a two or three dimensional array. But it is more complicated. First we have to think how a two dimensional array will be stored in memory. It is stored as a set of one dimensional array. Since each of these one dimensional arrays has one pointer to it, we need to create a set of pointers. This is done by creating an array of pointers. Here is how to create an array of 10 int pointers:

int *ptrArray[10];

Then we need to make each of these pointers point to a new array. To do this, we simply loop through all the pointers and assign each one a new array. Here is an example of creating 10 int arrays of 100 ints each and using our array of pointers to point to them:
int *ptrArray[10], i;
for(i=0;i < 10; i++)
    ptrArray[ i ] = new int [100];

I could then assign values to the array by using the normal method of dereferencing a 2 dimensional array. Here is how to assign values to this new 2-D array:
ptrArray[0][0]=130;
ptrArray[0][1]=108;
ptrArray[9][87]=24530;

And so on...

I can also use variable to create this 2-D array. Thus I can have the user enter the array size. To do this I need to have a pointer to my array of pointers. For this I will need to use one of those double pointers we discussed above. I need a double pointer because the name of my array of pointers points to the first element in that array. Since that element is a pointer (just like all the elements in that array) the thing that points to it must be a pointer to a pointer, or in other words a double pointer. Here is an example of creating a fully dynamic 2-D array where the user decides its size:
int **ptrArray, height, length, i;
cout << "Length? ";
cin >> length;
cout << "Height? ";
cin >> height;
ptrArray= new int* [height];
for(i=0;i < height; i++)
    ptrArray[ i ] = new int [length];

To free this memory when I am done with it, I will need to loop just as I did when I created the array. Here is how this is done:
for(i=0;i < height; i++)
    delete [] ptrArray[ i ];
delete [][] ptrArray;

Notice that I also freed the double pointer. I did this by using delete followed by two sets of []'s. This indicates that the double pointer ptrArray should be deleted.

Reference Parameters

void change_me(int & someint) { if (someint == 0) someint=1; else someint=0; return; } int main() { int p =0; change_me(p); cout<<p; } This function will actually work. It will change the value of p in the main function. It works because the &er; causes the variable someint to function like a pointer even though we use it like a regular int variable. This saves a lot of writing versus using pointer style notation and pointers.

*Note: There are other types of strings like the class String and strings where the first element contains the value of the length of the string, but for the purposes of this chapter, this is the relevant definition.

Function Pointers

Just as we have said that the name of an array is a pointer to the first element in the array so too, a function name is pointer to the beginning of the code where the function is stored in memory. Therefore, I can pass a function as a parameter to another function. In the following example doOtherFunct is a function whose sole ability is to run another function. It can run any function that it is passed so long as that function returns an integer and accepts as parameters two integers.

int doOtherFunct( int param1, int param2, int(*otherFunct)(int, int))  //line 1
{
int p = (*otherFunct)(param1, param2);                                      //line 3
return p;                                                                   //line 4
}
Notice that I used parenthesis in the parameter list (line 1) to group the funtion name with the star. This indicates that my function expects a function pointer (function name) to be passed and not an integer pointer (The * would group with the int if I had not used parenthesis). The * in line 3 is dereferencing the funtion so that I may call it.

Exercises

  1. Write a function which is passed two float arrays and their size. It should copy the contents of array1 into array2. Call the function floatCopy.
  2. Write a function which is passed two strings. It should copy string1 into string2, but in reverse order.
  3. Write a function which is passed one string and one char. It should return a pointer to the first occurrence of that character in the string.
  4. Write a function to compare two strings. Return a positive value integer if the first string alphabetically precedes the second. Return a negative value if string two precedes string one and return 0 if they are identical. Do this using pointer notation (not index [ ] notation).
  5. Write a function which is passed two char pointers and prints all the chars in memory between the two pointers.
  6. Write a function called sum. the function should take two pointers to ints. It should put the value of the sum of the two ints into the first int. it should return void.
  7. write a function called swap. It should take two pointers to floats and swap the values from the first float to the second and from the second to the first. After this function is called in the main() the actually variables in the main will have switched their values.
  8. Write a function which is passed a string. It should capitalize every letter in the string. Characters which are not letters, such as ?,#.; etc. should be left unchanged. You might want to look up the ascii values of the letters and characters, but this is not neccessary.
  9. Write a function which is passed an array of int's and the size of that array. It should then create a new array of size "size+1". It should then copy the contents of the old array into the new array, leaving the last element blank. The function should be called expandArray.
  10. Write a function which is passed two shorts representing the length and height of a 2-D array. The function should create such an array using new. It should also return a double pointer which points to the newly created array.
  11. Write a function to append one string to the end of a second string. The parameters of this function should be two strings as indicated by two char pointers (not arrays). You can however use array notation when copying the arrays.

© Nachum Danzig November 2003 - December 2009