3.1 The Arithmetic of Pointers

We are assigned the following programming task. We are given a vector of integers and an integer value. If the value is contained within the vector, we must return a pointer to it; otherwise, we return 0, indicating that the value is not present. Here is an implementation:

int* find( const vector<int> &vec, int value ) 


{ 


    for ( int ix = 0; ix < vec.size(); ++ix ) 


          if ( vec[ ix ] == value ) 


               return &vec[ ix ]; 


    return 0; 


} 

We test the function and are satisfied that it works. We are next assigned the task of having the function work not only with integers but also with any type in which the equality operator is defined. If you have read Section 2.7, you should recognize this task as requiring us to transform find() into a function template:

template <typename elemType> 


elemType* find( const vector<elemType> &vec, 


                const elemType &value ) 


{ 


    for ( int ix = 0; ix < vec.size(); ++ix ) 


          if ( vec[ ix ] == value ) 


               return &vec[ ix ]; 





    return 0; 


} 

Again, we test the function and are satisfied that it works. Our next assignment is to have find() work both for a vector and an array of elements of any type for which an equality operator is defined. Our first thought is to overload the function, providing an instance that takes a vector and an instance that takes an array.

We are advised against overloading in this case. With a little thought, we're told, we can implement find() so that a single instance can handle the elements of either a vector or a built-in array. Gosh, but that seems hard.

One strategy for solving a hard problem is to divide it into a number of smaller and hopefully simpler problems. In this example, our one big problem breaks down into (1) passing the elements of an array to find() without specifying the array and (2) passing the elements of a vector to find() without specifying the vector. Ideally, the solutions to these two problems contain a common solution to our initial problem.

Let's first solve the problem of the built-in array. How can we pass in the elements of an array to find() without specifying the array itself?

Programming a solution to a problem is immeasurably easier when we understand the problem that we are trying to solve. In our case, it will help to first understand how arrays are passed into and returned from functions. When I write

int min( int array[ 24 ] ) { ... } 

it seems as if min() accepts only arrays of 24 elements and that the actual array is being passed by value. In fact, neither assumption is true: The array is not copied by value, and an array of any size can be passed to min(). I know, you're thinking huh?

When an array is passed into or returned from a function, only the address of the first element is passed. The following is the more accurate declaration of min():

int min( int *array ) { ... } 

min() accepts integer arrays of any dimension: 1, 32, 1,024, and so on. The alternative would be vexing because it would require us to provide a separate instance of min() for each uniquely dimensioned array.

The pointer to the beginning of the array allows min() to begin reading the array. Somehow, we must indicate to min() when the reading of the array should stop. One way is to add an additional parameter that holds the size of the array. For example, here is our declaration of find() using this strategy:

template <typename elemType> 


elemType* find( const elemType *array, int size, 


                const elemType &value ); 

An alternative solution is to pass an address that, when reached, indicates that we have completed reading the elements of the array. (We call such a value a sentinel.)

template <typename elemType> 


elemType* find( const elemType *first, const elemType *sentinel, 


                const elemType &value ); 

One interesting aspect of this solution is that we have eliminated the declaration of the array from the parameter list ?solving the first of our smaller problems.

Let's look at how each version of find() is implemented. In the first version, we access each element in turn beginning at 0 and proceeding to size-1. The first question is this: Inasmuch as the array is passed to find() as a pointer to its first element, how do we access the elements by position? Even though we are accessing the array through a pointer, we can still apply the subscript operator exactly as we did before:

template <typename elemType> 


elemType* find( const elemType *array, int size, 


                const elemType &value ) 


{ 


   if ( ! array || size < 1 ) 


        return 0; 





   for ( int ix = 0; ix < size; ++ix ) 


         // we can apply subscript operator to pointer 


         if ( array[ ix ] == value ) 


              return &array[ ix ]; 





   return 0; // value not found 


} 

Although the array is passed to find() as a pointer to its first element, we see that individual elements can still be accessed through the subscript operator as if the array were an object. Why? In practice, subscripting is carried out by adding the index to the beginning address of the array to yield the address of the element. That address is then dereferenced to return the value of the element. For example,

array[ 2 ]; 

returns the value of the third element of the array (indexing, remember, begins at 0). The following also returns the value of the third element:

*(array + 2) 

If the address of the first element of array is 1000, what address does array+2 yield? 1002 is a reasonable answer, but it is not the correct answer. 1002 is integer arithmetic; array+2, however, represents pointer arithmetic. Pointer arithmetic adds increments of the size of the type being addressed.

Let's say that array contains integer elements. array+2, then, adds the size of two integer elements to the address of array. Under pointer arithmetic, on a machine in which an integer is 4 bytes, the answer is 1008.

When we have the address of the element, we must then dereference the address to get the value of the elements. When we write array[2], the pointer arithmetic and address dereferencing are done automatically.

Here is an alternative implementation of find() in which we address each element through a pointer. To address each element of array in turn, we increment it by 1 with each iteration of our loop. To read the element addressed, we must dereference the pointer. That is, array returns the address of the element, and *array returns its value.

template <typename elemType> 


elemType* find( const elemType *array, int size, 


                const elemType &value ) 


{ 


   if ( ! array || size < 1 ) return 0; 





   // ++array increments array by one elememt 


   for ( int ix = 0; ix < size; ++ix, ++array ) 


         // *array dereferences the address 


         if ( *array == value ) 


              return array; 


   return 0; 


} 

In this next version, we replace the size parameter with a second pointer that serves as the sentinel address. This is the version that allows us to remove the declaration of the array from the parameter list:

template <typename elemType> 


elemType* find( const elemType *first, 


                const elemType *last, const elemType &value ) 


{ 


   if ( ! first || ! last ) 


        return 0; 





   // while first does not equal last, 


   // compare value with element addressed by first 


   // if the two are equal, return first 


   // otherwise, increment first to address next element 





   for ( ; first != last; ++first ) 


         if ( *first == value ) 


              return first; 





   return 0; 


} 

This implements the first of our two programming subtasks: we've implemented find() to access each element of our array independent of the array object the elements are contained within. How might find() be invoked? The following code uses the pointer arithmetic we illustrated earlier:

int    ia[8] = { 1, 1, 2, 3, 5, 8, 13, 21 }; 


double da[6] = { 1.5, 2.0, 2.5, 3.0, 3.5, 4.0 }; 


string sa[4] = { "pooh", "piglet", "eeyore", "tigger" }; 





int    *pi = find( ia, ia+8, ia[3] ); 


double *pd = find( da, da+6, da[3] ); 


string *ps = find( sa, sa+4, sa[3] ); 

The second address marks 1 past the last element of the array. Is that legal? Yes. If we should ever try to read or write to that address, however, all bets are off. But if all we do with that address is to compare it against other element addresses, we're fine. The address 1 past the last element of the array serves as a sentinel indicating that we have completed our iteration.

How might we implement the second programming subtask, that of accessing each element of a vector independent of the vector object the elements are contained within? A vector also holds its elements in a contiguous area of memory, so we can pass find() a begin/end pair of addresses in the same way as we do for the built-in array, except in one case. Unlike an array, a vector can be empty. For example,

vector<string> svec; 

defines an empty vector of string elements. The following invocation of find(), if svec is empty, is incorrect and results in a run-time program failure:

find( &svec[0], &svec[svec.size()], search_value ); 

A safer implementation is first to confirm that svec is not empty.

if ( ! svec.empty() ) // ... ok, call find() 

Although this is safer, it is somewhat cumbersome for the user. A more uniform way of accessing the address of the first element is to wrap the operation into a function, something like the following:

template <typename elemType> 


inline elemType* begin( const vector<elemType> &vec ) 


    { return vec.empty() ? 0 : &vec[0]; } 

A second function, end(), returns either 0 or a pointer to 1 past the last element of the vector. In this way, we can safely and uniformly invoke find() for any vector:

find( begin( svec ), end( svec ), search_value ); 

Moreover, this solves our original programming task of implementing find() so that a single instance can accept either a vector or a built-in array. Again, we test the function and are satisfied that it works.

Excellent, we are told. Now extend find() so that a single instance can also support the standard library list class. Now that's hard.

A list class is also a container. The difference is that the elements of a list are linked through a pair of pointers: a forward pointer addressing the next element and a backward pointer addressing the preceding element.

Pointer arithmetic doesn't work with a list. Pointer arithmetic presumes that the elements are contiguous. By adding the size of one element to the current pointer, we reset the pointer to address the next element. This is the underlying assumption of our implementation of find(). Unfortunately, that assumption doesn't hold when we access the next element of a list.

Our first thought again is to provide an overloaded second instance of find() that accepts a list object. The behaviors of the pointers of a built-in array, a vector, and a list are, we claim, simply too different to achieve a uniform syntax for next element access.

Yes and no. Yes, the behavior of the underlying pointers is too different for a uniform syntax. And no, we don't need to provide a second instance to support the list class. In fact, we don't need to alter the implementation of find() at all, except for its parameter list.

The solution is to provide a layer of abstraction over the behavior of the underlying pointers. Rather than program the underlying pointers directly, we program the layer of abstraction. We place the unique handling of the underlying pointers within that layer, shielding it from our users. This technique allows us to handle any of the standard library container classes with a single instance of find().