Arrays and Pointer to arrays : One Dimension

In this snippet we will look at manipulating pointers to single-dimensional arrays with ease. For this we first need to review one-dimensional arrays.Subsequent snippet will cover multidimensional arrays.


***************************
Manipulating simple arrays
***************************

Suppose we have the following two declarations

int array[10];

and

int * parray[10];

Diagrammatically, the difference between the two arrays  is as shown below
two figures.

Figure-1:

              +——————————+
array [0]      |   int    |
              +——————————+
array [1]      |   int    |
              +——————————+
array [2]      |   int    |
              +——————————+
array [3]      |   int    |
              +——————————+
array [4]      |   int    |
              +——————————+
array [5]      |   int    |
              +——————————+
array [6]      |   int    |
              +——————————+
array [7]      |   int    |
              +——————————+
array [8]      |   int    |
              +——————————+
array [9]      |   int    |
              +——————————+




Figure-2:


             +——————————+         +——————————+
parray[0]     |  int *   |  ——————>|   int    | *parray[0]
             +——————————+         +——————————+
+——————————+
parray[1]     |  int *   |  —————————————————————————————————>  |   int
| *parray[1]
             +——————————+           +——————————+
+——————————+
parray[2]     |  int *   |  ————————>|   int    | *parray[2]
             +——————————+           +——————————+              +——————————+
parray[3]     |  int *   |  —————————————————————————————————> |   int    |
*parray[3]
             +——————————+          +——————————+               +——————————+
parray[4]     |  int *   |  ——————> |   int    | *parray[4]
             +——————————+          +——————————+
+——————————+
parray[5]     |  int *   |  ———————————————————————————————————>|   int
| *parray[5]
             +——————————+           +——————————+
+——————————+
parray[6]     |  int *   |  ————————>|   int    | *parray[6]
             +——————————+           +——————————+              +——————————+
parray[7]     |  int *   |  —————————————————————————————————> |   int    |
*parray[7]
             +——————————+          +——————————+               +——————————+
parray[8]     |  int *   |  ——————> |   int    | *parray[8]
             +——————————+          +——————————+
+——————————+
parray[9]     |  int *   |  —————————————————————————————————>  |   int
| *parray[9]
             +——————————+
+——————————+


           int * implies int pointer



In the first declaration we access the ith int in the array by performing array[i]. In the second declaration, we access the ith integer (though this int is not part of the array) by performing     *parray[i]., In the second declaration, the ith int pointer (which are elements of the array parray) can be accessed by performing  parray[i] 


***************************
Dual Nature of array names:
***************************

Array names have dual nature. Sometimes it signifies the whole array. That
is why, given

TYPE  array_name[M];

We can find the size of the array by printing out  sizeof (array_name). For
example:

Given

long     array_of_long[100] ;

Then, the size of array  array_of_long  is given by  sizeof(array_of_long.
Hence the array name signifies the whole array.

At other times the array name behaves as a pointer. The C compiler creates
a  pointer whose name is again the array name itself. And this points to
the first element of the array. Thus given:

TYPE array_name[M];

Then array_name points to the first element, i.e.  array_name[ 0 ].  Note
that the elements of the array is of the type TYPE.   array_name[ 0 ] can
be anything, an int, char, struct etc.

Diagrammatically, this can be viewed as:
Figure-3:

+——————————————+         +——————————+
|  array_name  | ——————> |   TYPE   | array_name[0]
+——————————————+         +——————————+
                        |   TYPE   | array_name[1]
                        +——————————+
                        |   TYPE   | array_name[2]
                        +——————————+
                        |   TYPE   | array_name[3]
                        +——————————+
                        |   TYPE   | array_name[4]
                        +——————————+
                        |   TYPE   | array_name[5]
                        +——————————+
                             .
                             .
                             .
                             .
                        +——————————+
                        |   TYPE   | array_name[M-1]
                        +——————————+


***************
Variable names:
***************

When we declare an array as below:

TYPE array_name[M];

The compiler provides  the following variable names.

array_name[0], array_name[1],  . . . . ,  array_name[M-1].

These variable names can be manipulated  like any other variable. It should
be noted that the M number of variables are of the type TYPE.


*****************************
Incrementing the array names:
*****************************

We saw earlier that in the case of single dimensional array, the array name
(in our example this is array_name) is also a pointer to the first element,
which in our examples is  array_name[0].

We can't increment the contents of the array name, which is a constant, but
we can do, for example

p = array_name + 1;

When we do this, p points to the next element, i.e.,  array_name[1].

In general, if we do:

p = (array_name + i)

Then p points to the ith element, i.e.,   array_name[i]

This result is important, which states that:

( array_name + i )  points to element  array_name[i] .



*******************************************************************
Relationship between index and pointer in single dimensional array:
*******************************************************************

We know that if p points to some object, then *p is that object
Thus, it follows that- since

(array_name + i ) points to array_name[i] ,

therefore, it follows that

*(array_name + i)  =   array_ name[i]

the above relation, rewritten as below is the heart and soul of arrays and
pointers

array_name[i] =  *(array_name + i)

An important corollary happens when we put i=0,  we have

array_name[0] =  *array_name


**************************************
Alternative declaration of array name:
**************************************

If we have a general single dimensional array declaration

TYPE array_name[M];

Then the array name can be considered to behave as the following
declaration. Because array_name points to an element of type TYPE.

TYPE *array_name;  /* i.e., array name points to TYPE */

Thus, there are two ways we can write a prototype of a function in which
the pointer array_name is passed.

The first method is
void f( TYPE  array_name[] );

the second method is
void f( TYPE  *array_name );



****************************************
Pointers to arrays (single dimensional):
****************************************

A pointer to a single dimensional array is declared as, for example,

char  (*p)[10] ;

Here  p points to the  whole array of 10 characters, as shown in the
diagram below



+——————————————+         +——————+
|      p       | ——————> | char |  0
+——————————————+         +——————+
                        | char |  1
                        +——————+
                        | char |  2
                        +——————+
                        | char |  3
                        +——————+
                        | char |  4
                        +——————+
                        | char |  5
                        +——————+
                        | char |  6
                        +——————+
                        | char |  7
                        +——————+
                        | char |  8
                        +——————+
                        | char |  9
+——————————————+         +——————+
|    p+1       | ——————> | char |
+——————————————+         +——————+
                        | char |
                        +——————+
                            .
                            .
                            .


Since  p points to an array of  10 chars therefore (*p) is the array of 10
chars. That is, (*p) means the whole array of 10 characters. And just to
confirm that-  we can print out sizeof(*p) we get 10 bytes.

This also means, as per our earlier snippet, if we increment p by 1, the
value will change by 10 bytes.


***************
The  Technique:
***************
Let us look at a few tricks for manipulating pointers to an array.

Before coming to the tricks, The basics are that:
any single dimensional array declaration has the following declaration

TYPE     array_name[M] ;

While pointer to an array type of declaration has the syntax.

TYPE     ( *pointer_to_array )[M] ;

If we compare the two we can see that , (*pointer_to_array) is nothing but
the array name. What this means is that wherever results we had with
respect to array_name previously, if we substitute it by
(*pointer_to_array) we will get the same result. This is the basis of the
trick. We will now apply this and see a few more methods.


We will use the following examples to show the methods.

We will compare the following two declarations to explain the methods.

char   (*p)[10] ;

char    array_name[10];

In the above case     (*p) is the name of the array

Therefore:
1.    Size of the array array_name is given by sizeof(array_name).  Since
(*p) is the name of the array, therefore size of array (*p) is given by
sizeof(*p).


2.    The compiler creates the following memory variables array_name[0],
array_name[1], array_name[ 2], .... ,  array_name[M-1] where they hold a
char. Similarly, the compiler creates the following variable (*p)[0],
(*p)[1], (*p)[2]  .... ,  (*p)[M-1], where each of the variable holds a
char.


3.    Just as array_name points to array_name[0], similarly, (*p) points to
(*p)[0].

If we perform (array_name + 1) it will point to array_name[1]. Similarly,
if we do  (*p)+1 it will point to (*p)[1]. Which means that;

(*p)[1] =  *((*p)+1)

 In general we have:

 (*p)[i] =  *((*p)+i)

A corollary of this is:

(*p)[0]  =  **p


4.    However the following analogy fails in the case of pointer to arrays.
We said that, if there is a declaration as below;

TYPE array_name[M];
then, if we wish to  pass array_name as a parameter in the function, then
there can be two ways of writing the prototype;

void f( TYPE  array_name[] );

or

void f( TYPE  *array_name );

The first method works for pointer to array, but the second method does not
work.

Thus, if we wish to pass a pointer to a single dimensional array in a
function, then function prototype should be

void f( TYPE  (*p)[] )


This will not work:
void f( TYPE  **p)



Of course, in all the  above examples of pointer to arrays we have assumed
that we have initialized ‘p’ correctly, may be by the pointer we get by a
malloc or some other means.

The following program will show more inputs about manipulating pointers to
arrays,


#include

main()
{
 int arrray[10] = {0,1,2,3,4,5,6,7,8,9};

 int (*p)[10];

 int i;

 p = (int (*)[10]) arrray;     /* initialize p by casting array */

  for(i=0;i<10;i++)
      printf("%d, %d, %d \n",arrray[i], (*p)[i], *((*p)+i));

}


We will see the output as:

0, 0, 0
1, 1, 1
2, 2, 2
3, 3, 3
4, 4, 4
5, 5, 5
6, 6, 6
7, 7, 7
8, 8, 8
9, 9, 9

which proves that  all the expressions in the printf statement are
identical.


This little trick works in the following case too.

Suppose we have

int (**q)[10];
If we have initialized q correctly then (**q) is the name of the array.
Therefore

1.  Size of array  is   sizeof(**q)

2.  The following variables are created (**q)[0], (**q)[1],  ....,
(**q)[9].

3.  (**q) points to (**q)[0] and in general  (**q)[i]  =  *((**q)+i)


The following code will show  what we have meant so far.

The data structure used in the following code is shown here:



+——————————————+         +——————————————+         +——————+
+——————————————+
|      q       | ——————> |       p      | ——————> | int  |  <—————— |
arry      |
+——————————————+         +——————————————+         +——————+
+——————————————+
                                                 | int  |  8
                                                 +——————+
                                                 | int  |  12
                                                 +——————+
                                                 | int  |  16
                                                 +——————+
                                                 | int  |  20
                                                 +——————+
                                                 | int  |  24
                                                 +——————+
                                                 | int  |  28
                                                 +——————+
                                                 | int  |  32
                                                 +——————+
                                                 | int  |  36
                                                 +——————+
                                                 | int  |  40  bytes
                       +——————————————+          +——————+
                       |    p+1       | ——————>  | int  |
                       +——————————————+          +——————+
                                                 | int  |
                                                 +——————+
                                                     .
                                                     .
                                                     .

sizeof(*p) = 40 bytes,  assuming 32-bit integer.




#include

main()
{
 int arry[10] = {0,1,2,3,4,5,6,7,8,9};

 int (*p)[10];

 int (**q)[10];

 int i;


 p = (int(*)[10])arry;   /* initialize p with pointer array */

 q = &p;      /* initialize q with the address of p */

  for(i=0;i<10;i++)
      printf("%d, %d, %d, %d, %d, %d \n",
        arry[i], *(arry+i), (*p)[i], *((*p)+i), (**q)[i], *((**q)+i));

}
======================================
Result:
0, 0, 0, 0, 0, 0
1, 1, 1, 1, 1, 1
2, 2, 2, 2, 2, 2
3, 3, 3, 3, 3, 3
4, 4, 4, 4, 4, 4
5, 5, 5, 5, 5, 5
6, 6, 6, 6, 6, 6
7, 7, 7, 7, 7, 7
8, 8, 8, 8, 8, 8
9, 9, 9, 9, 9, 9

 As we see all the expressions in the printf statement have the same
meaning.


In the next snippet, we will discuss about pointers to two-dimensional
arrays.

Preventing Precedence Errors: EqualitytInequality

A very commonly observed precedence error during usage of expressions is inadequate parenthesizing.  Here we take examples of Equality/Inequality expressions:

if(var1 & var2 == 0)

The above is incorrect because == has a higher precedence than &, therefore in the above expression  var2==0  will be computed first, which is a bool. Then that bool will be bit_AND'ed with var1.  And this was not our intention.

The correct way  is:

if((var1 & var2) == 0)

In practice, the test for equality/inequality must be the last logical operation, but it can happen otherwise, if there are operators of lower precedence than  ==  or   !=  in the expression.

If we recall our three liner:

S—U—Ari

Re—Bit—Lo—C

Assignment—Comma

The  “e”  in Re stands for equality/inequality, and when they are there in an expression with operators of lower precedence then the  ==  or !=  will get executed earlier. To change the order of evaluation we need to appropriately parenthesize these operators. These operators(with precedence lower than  ==  and   != )  are   Bit—Lo—C—Assignment—Comma.   In practice we will find bit and assignment operator mixed with  ==  and   != operators.

So when we see this mixture, i.e.,==  or  !=, &,  | ,  ^, =   in a statement,  parenthesis are to be taken care.

The following are some examples where precedence errors are very common.

a)    Test if FLAG_A is clear in message incorrect

if(message & FLAG_A == 0)

correct

if((message & FLAG_A) == 0)

b)    Test if FLAG_ A is set in message  incorrect

if(message & FLAG_A != 0)

correct

if((message & FLAG_A) != 0)

c)    Test if all flags are clear incorrect

if ( message & (FLAG_A | FLAG_B | FLAG_C) == 0)

 correct

if (( message & (FLAG_A | FLAG_B | FLAG_C)) ==0)

d)    Incorrect

if ( c = getchar() != EOF)

correct

if (( c = getchar()) != EOF)

In all the above cases, parenthesizing is to be done for operands with precedence lower than  == or !=  so that they are executed earlier.

In short, when and expression has   equality/inequality operator as the final operand and we see that there are operators in the expression whose precedence levels and are still lower than equality / inequality, then we should get the parenthesis correct. The operators with lower precedence than  “Re” are  Bit—Lo—C—Assignment—Comma

How to measure the size of a variable

Let us go through a small test to find out if this entire snippet is really worth reading. The test begins now.  We should complete it in 60 seconds!

Consider these  declarations in a code.

     char x, y, *p, **pp;
     char  *array[5], arr[5];
     char  *f(int), **g(int) ;

   struct node  a, b,* h(int); / * assume the size of node is 20 */

Then, what will be the values of the following?

1.    sizeof(x)
2.    sizeof(y)
3.    sizeof(*p)
4.    sizeof(p)
5.    sizeof(**pp)
6.    sizeof(*pp)
7.    sizeof(pp)
8.    sizeof(* array [0])
9.    sizeof(array[0])
10.   sizeof(arr [5] )
11.   sizeof(*f(5))
12.   sizeof(f(5))    /* is the size of a function?! */
13.   sizeof(**g(6))
14.   sizeof(*g(6))
15.   sizeof(g(6))
16.   sizeof(a)
17.   sizeof(*b)
18.   sizeof(b)
19.   sizeof(*h(5))
20.   sizeof(h(5))


Considering that size of char is 1 byte and pointers have a size of 4 bytes. Here  are the answers.

1.    1 byte
2.    1 byte
3.    1 byte
4.    4 bytes
5.    1 byte
6.    4 bytes
7.    4 bytes
8.    1 byte
9.    4 bytes
10.   1 byte
11.   1byte
12.   4 bytes
13.   1 byte
14.   4 bytes
15.   4 bytes
16.   20 bytes
17.   20 bytes
18.   4 bytes
19.   20 bytes
20.   4 bytes

We are almost sure; we got all the answers right, but did we beat the clock? Did we do it within 60 seconds?

Well! Here is how to get the measure on size really fast… For this we need to remember the following two things. 

First: refresh what we discussed in the “Moving the Stars” snippet. That virtual equal to sign helps a lot in getting the size right. Second: Any pointer of any type has the size 4 bytes (we are by default considering 32 bit machines. The pointer size can, of course, change with machines.)

Let us answer the questions we put earlier…

Question 1 and Answer:
     We have
      char x;

     Which can be read as
      char = x

     Therefore,
      sizeof(x) = sizeof(char) = 1

Question 2 and Answer:
     As above, the answer is again 1 byte

Question 3 and Answer:
     Given
      char *p;
     What is the sizeof(*p)?

     Because char = *p, therefore
      sizeof(*p)= sizeof(char) = 1

Question 4 and Answer:
     Given
      char  *p;
     What is the sizeof(p)?

     Because char *  = p, therefore,
      sizeof(p) = sizeof(char *) = 4

Question 5 and Answer:
     Given
      char **pp;
     What is the sizeof (**pp)?

     Because char = **pp, therefore
      sizeof (**pp) = sizeof (char) = 1

Question 6 and Answer:
     Given,
      char **pp;
      What is the  sizeof(*pp)?

     Because char * =*pp, therefore
      sizeof(*pp) = sizeof(char *) = 4

Question 7 and Answer:
     Given,
      char **pp,
     What is the sizeof (pp)?

     Because char ** = p, therefore
      sizeof(p) = sizeof(char **) = 4


Question 8 is interesting, because we are apparently trying to find the size of a function, which is unusual. But we can compute the size of functions. However what it means is the size of its return values.

Let us take up Question 8 and Answer:

     Given char * f(int); what is sizeof(*f(5));

     Because char = * f(int), therefore
      sizeof (* f(5)) = sizeof(char) = 1


Question 9 and Answer:

     Given  char *f(int) what is  sizeof(f(5))?

     Because  char * = f(int), therefore       sizeof (f(5)) = sizeof(char *) = 4.


Now that we know what we mean by size of a function, the remaining questions should be easy to answer quickly. Let's do it to be sure. This trick works with any C/C++ declarations.

By the way, why do we need to know the size of any variable correctly, the answer is to malloc correctly to get the correct amount of memory. If we give a wrong size for memory allocation, chances are that we will take days
to find out why the program misbehaves in strange ways.

This snippet has helped to explain in detail the aspects of sizeof.

Refresh your Pointers knowledge

This little piece of literature will let us prevent a category of defects related to pointers. But first, let us take a small test. It will help us to decide if the entire snippet  is really worth reading. So here are the questions.

Consider, following are some of the declarations in a piece of code.
     int x , y, *p, **pp ;
   int *array[5], arr[5];
   int *f(int), **g(int);

Now, for which of the following eight statements the compiler will complain and for which it will not complain?
Let us try the test; check if we can hit it right in less than sixty seconds!
1.    x = y;
2.    *p = array [0];
3.    *p = **pp;
4.    x = f (4);
5.    p = *g (3);
6.    array [0] = arr[0];
7.    arr [0] = * array [1];
8.    array [5] = **g (3);


Here are the answers. For all odd number statements 1,3,5… .. the compiler will not complain.
For all even number statements 2,4,6… . The compiler will complain.

Let us now figure out quickly some of the mistakes we saw earlier. The way to find  what works and what does not, is rather simple. That is because, we can consider a C/C++ declarations as an equation with an “=” sign, across which you can move the stars!

Let's hold on! We will see what we meant above

Let us consider the declaration  int * x;

Let's imagine an "equal to" sign in between as follows

     int = * x ; /* this one tells you that *x is int */

We can move the star across the “=” sign, as shown here:

     int * = x ; /* this one tells that x is an integer pointer or a
pointer to an integer*/


One more example will make things clearer.

     int ** y

Let's imagine it as:

     int = **y   (this means  **y is an integer).


After moving one star across:

     int * = *y ( this means that *y is an integer pointer).

After moving one more star across:
     int ** = y,  this means that y is an integer pointer pointer.



Now , let us combine the above two examples
      In the first example we saw  *x  is an integer
     In the second example we saw that  **y  is also an integer.

So, the compiler will not complain, if we write
     *x = **y
          or
     **y = *x

Similarly,
     x = * y   is also ok with the compiler because both the sides are
int *.

By now we have seen, how to quickly find what will work and what will not work by  MOVING THE STARS!
It is a good idea to have a look at the declarations for minimizing related defects.

Let us go back to the quiz questions we discussed earlier. We will go through the answers quickly by using this  MOVING THE STARS! method.

We have copied and pasted the declarations over here for easy reference:
     int x , y, *p, **pp ;
     int *array[5], arr[5];
     int *f(int), **g(int);

1.    x = y  is correct, because both sides are int
2.    *p = array [0] is wrong, because LHS is int but RHS is  int *
3.    *p = **pp    is correct because both sides are int.
4.    x = f (4) is wrong because LHS is  int and RHS is int *.
5.    p= *g (3) is correct because both sides are int *
6.    array [0] = arr [0] is wrong because LHS is int *  but RHS is  int.
7.    arr [0] = * array [1]   is correct, because both sides are  int.
8.    array [5] = ** g (3) is wrong, because LHS is  int*  while RHS is int.


Experience shows that regularly using this little trick helps in writing as well as reading code faster.
Of course, it also helps us in reducing mistakes.