| I l@ve RuBoard |
|
2.2 Invoking a FunctionIn this section we implement a function to sort a vector of integer values so that we can explore the behavior of passing parameters both by reference and by value. The sorting algorithm is a simple bubble sort implemented by two nested for loops. The outer for loop walks through the vector elements from ix, which begins at 0 and ends at size-1. The idea is that upon completion of each iteration of the outer loop, the element indexed by ix is in its proper place. When ix is 0, the smallest element is found and placed at position 0, and when ix is 1, the second smallest element is in place, and so on. The placement is executed by the inner for loop. jx begins at ix+1 and ends at size-1. It compares the element value at ix with the element value at jx. If the element value at jx is smaller, the two element values are swapped. Our first implementation fails. The purpose of this section is to explain why. Here we go.
void display( vector<int> vec )
{
for ( int ix = 0; ix < vec.size(); ++ix )
cout << vec[ix] << ' ';
cout << endl;
}
void swap( int val1, int val2 )
{
int temp = val1;
val1 = val2;
val2 = temp;
}
void bubble_sort( vector<int> vec )
{
for ( int ix = 0; ix < vec.size(); ++ix )
for ( int jx = ix+1; jx < vec.size(); ++jx )
if ( vec[ ix ] > vec[ jx ] )
swap( vec[ix], vec[jx] );
}
int main()
{
int ia[ 8 ] = { 8, 34, 3, 13, 1, 21, 5, 2 };
vector<int> vec( ia, ia+8 );
cout << "vector before sort: ";
display( vec );
bubble_sort( vec );
cout << "vector after sort: ";
display( vec );
}
When this program is compiled and executed, the following output is generated, showing that the vector defined within main() is not sorted: vector before sort: 8 34 3 13 1 21 5 2 vector after sort: 8 34 3 13 1 21 5 2 It's not unusual to have a program not work the first time we run it. The question is, what do we do now? If we have a debugger available, a good next step is to step through the program's execution, examining the run-time values of the various objects in our program and watching the actual control flow of the for loops and if statement. A more practical approach in the context of this text is to add print statements to trace the control logic and display the state of the objects. So where do we begin? The nested for loops represent the critical area of our program ?in particular, the test of the two elements and call of swap(). If the sorting algorithm isn't working, this portion of the program is likely to be failing. I've instrumented it as follows:
ofstream ofil( "text_out1" );
void bubble_sort( vector<int> vec )
{
for ( int ix = 0; ix < vec.size(); ++ix )
for ( int jx = ix+1; jx < vec.size(); ++jx )
if ( vec[ ix ] > vec[ jx ] ){
// debugging output
ofil << "about to call swap!"
<< " ix: " << ix << " jx: " << jx << '\t'
<< " swapping: " << vec[ix]
<< " with " << vec[ jx ] << endl;
// ok: actual swap code ...
swap( vec[ix], vec[jx] );
}
}
After we compile and execute the program, the following debugging output is generated. Two things are surprising: swap() is called exactly as it should be, and the vector is nevertheless unchanged from its original order. Who said programming is fun? vector before sort: 8 34 3 13 1 21 5 2 about to call swap! ix: 0 jx: 2 swapping: 8 with 3 about to call swap! ix: 0 jx: 4 swapping: 8 with 1 about to call swap! ix: 0 jx: 6 swapping: 8 with 5 about to call swap! ix: 0 jx: 7 swapping: 8 with 2 about to call swap! ix: 1 jx: 2 swapping: 34 with 3 about to call swap! ix: 1 jx: 3 swapping: 34 with 13 about to call swap! ix: 1 jx: 4 swapping: 34 with 1 about to call swap! ix: 1 jx: 5 swapping: 34 with 21 about to call swap! ix: 1 jx: 6 swapping: 34 with 5 about to call swap! ix: 1 jx: 7 swapping: 34 with 2 about to call swap! ix: 2 jx: 4 swapping: 3 with 1 about to call swap! ix: 2 jx: 7 swapping: 3 with 2 about to call swap! ix: 3 jx: 4 swapping: 13 with 1 about to call swap! ix: 3 jx: 6 swapping: 13 with 5 about to call swap! ix: 3 jx: 7 swapping: 13 with 2 about to call swap! ix: 5 jx: 6 swapping: 21 with 5 about to call swap! ix: 5 jx: 7 swapping: 21 with 2 about to call swap! ix: 6 jx: 7 swapping: 5 with 2 vector after sort: 8 34 3 13 1 21 5 2 An examination of swap() should convince us that it is implemented correctly. If we've started to doubt our judgment, however, we can instrument swap() to confirm that it is correctly swapping values:
void swap( int val1, int val2 )
{
ofil << "swap( " << val1
<< ", " << val2 << " )\n";
int temp = val1;
val1 = val2;
val2 = temp;
ofil << "after swap(): val1 " << val1
<< " val2: " << val2 << "\n";
}
In addition, after calling swap(), I added a call of display() to see the state of the vector. The output shows us that (1) everything is working correctly, and (2) nothing is coming out right: vector before sort: 8 34 3 13 1 21 5 2 about to call swap! ix: 0 jx: 2swapping: 8 with 3 swap( 8, 3 ) after swap(): val1 3 val2: 8 vector after swap(): 8 34 3 13 1 21 5 2 The trace output shows that bubble_sort() correctly recognizes that the first and third elements, values 8 and 3, must be swapped. swap() is correctly invoked, and, within swap(), the values are correctly swapped. The vector, however, is not changed. Unfortunately, this is not something we're just going to figure out on our own. If you're like me, you tend to be dogged about problems, hunkering down and thinking you can bull your way through. Sometimes, what we need more than a stubborn streak is someone to show us the missing bit of the puzzle. The problem has to do with how we are passing the arguments to swap(). A way to approach this issue is to ask this question: What is the relationship between, on the one hand, the two elements of the vector passed to swap() from within bubble_sort() and, on the other hand, the two parameters manipulated within swap()?
void bubble_sort( vector<int> vec )
{
// ...
if ( vec[ ix ] > vec[ jx ] )
swap( vec[ix], vec[jx] );
// ...
}
void swap( int val1, int val2 )
{
// what is the relationship between
// the formal parameters val1, val2
// and the actual arguments vec[ix] and vec[jx]?
}
What is the relationship between vec[ix] and vec[jx], passed to the call of swap(), and the two parameters of swap(), val1 and val2? If both pairs represent the same two objects, then changing val1 and val2 within swap() should change the values within vec[ix] and vec[jx]. But this is not what is happening. It is as if we were manipulating two different pairs of objects that have no relationship to each other except that both pairs hold the same values. This, in fact, is exactly what is happening. It explains why even though we swap the values, the change is not reflected in the vector. In effect, the objects passed to swap() are copied, and there is no relationship between the two pairs of objects. When we invoke a function, a special area of memory is set up on what is called the program stack. Within this special area of memory there is space to hold the value of each function parameter. (It also holds the memory associated with each object defined within the function ?we call these local objects.) When the function completes, this area of memory is discarded. (We say that it is popped from the program stack.) By default, when we pass an object to a function, such as vec[ix], its value is copied to the local definition of the parameter. (This is called pass by value semantics.) There is no connection between the objects manipulated within swap() and the objects passed to it within bubble_sort(). That is why our program fails. For our program to work, we must somehow bind the swap() parameters to the actual objects being passed in. (This is called pass by reference semantics.) The simplest way of doing this is to declare the parameters as references:
/*
* OK: by declaring val1 and val2 as references
* changes to the two parameters within swap()
* are reflected in the objects passed to swap()
*/
void swap( int & val1, int & val2 )
{
/*
* note that our code within swap()
* does not change -- only the relationship
* between the parameters of swap() and the
* objects passed to swap() changes
*/
int temp = val1;
val1 = val2;
val2 = temp;
}
Before I explain references, let's confirm that in fact this small change corrects our program. Here is a partial trace of a recompilation and execution of our program: vector before sort: 8 34 3 13 1 21 5 2 about to call swap! ix: 0 jx: 2 swapping: 8 with 3 3 34 8 13 1 21 5 2 about to call swap! ix: 0 jx: 4 swapping: 3 with 1 1 34 8 13 3 21 5 2 about to call swap! ix: 1 jx: 2 swapping: 34 with 8 1 8 34 13 3 21 5 2 about to call swap! ix: 1 jx: 4 swapping: 8 with 3 // ... about to call swap! ix: 5 jx: 7 swapping: 21 with 13 1 2 3 5 8 13 34 21 about to call swap! ix: 6 jx: 7 swapping: 34 with 21 1 2 3 5 8 13 21 34 vector after sort: 8 34 3 13 1 21 5 2 Oops. Everything is working great now except that the vector within main() that we pass to bubble_sort() is not being changed. Now that we're experienced, the first thing we look for is a parameter passed by value rather than by reference:
void bubble_sort( vector<int> vec ){ /* ... */ }
Changing vec to be a reference is the final correction to our program:
void bubble_sort( vector<int> &vec ){ /* ... */ }
To confirm that, let's recompile and execute: vector before sort: 8 34 3 13 1 21 5 2 vector after sort: 1 2 3 5 8 13 21 34 Whew! That was hard. A lot of programming is like that. Often, the solution is pretty simple, but only after you understand what the problem is. Pass by Reference SemanticsA reference serves as an indirect handle to an object. We declare a reference by sandwiching an ampersand (&) between the type's name and the name of the reference: int ival = 1024; // an object of type int int *pi = &ival; // a pointer to an object of type int int &rval = ival; // a reference to an object of type int When we write int jval = 4096; rval = ival; we assign ival, the object rval refers to, the value stored by jval. We do not cause rval to now refer to jval. A reference cannot be reassigned to refer to another object. When we write pi = &rval; we assign pi the address of ival, the object rval refers to. We do not cause pi to point to rval. All manipulation of a reference acts on the object the reference refers to. This is also true when the reference is a function parameter. When we assign val1 with val2 within swap(),
void swap( int &val1, int &val2 )
{
// the actual arguments are modified ...
int temp = val1;
val1 = val2;
val2 = temp;
}
we are really assigning vec[ix] with vec[jx], which are the two objects val1 and val2 refer to in the call of swap() within bubble_sort(): swap( vec[ix], vec[jx] ); Similarly, when val2 is assigned with temp within swap(), we are really assigning vec[jx] with the original value of vec[ix]. When an object is passed to a reference parameter, the object's value is not copied. Rather, the address of the object being passed is copied. Each access of the reference parameter within the function is an indirect manipulation of the object passed in. One reason to declare a parameter as a reference is to allow us to modify directly the actual object being passed to the function. This is important because, as we've seen, our program otherwise may behave incorrectly. A second reason to declare a parameter as a reference is to eliminate the overhead of copying a large object. This is a less important reason. Our program is correct; it is simply less efficient. For example, we currently pass our vector to display() by value. This means that we copy the entire vector object each time we wish to display it. This is not wrong. The output generated is exactly what we want. It is simply faster to pass the address of the vector. Again, one way to do that is to declare the vector parameter to be a reference:
void display( const vector<int> &vec )
{
for ( int ix = 0; ix < vec.size(); ++ix )
cout << vec[ix] << ' ';
cout << endl;
}
We declare it to be a reference to const vector because we do not modify it within the body of the function. It is not an error to omit the const. Having the const there informs readers of the program that we are passing the vector by reference to prevent copying it rather than to modify it within the function. If we wish, we can pass our vector as a pointer parameter. The effect is the same: We pass the address of the object into the function rather than make a copy of the entire object. One difference, of course, is the syntax between a reference and a pointer. For example,
void display( const vector<int> *vec )
{
if ( ! vec ){
cout << "display(): the vector pointer is 0\n";
return;
}
for ( int ix = 0; ix < vec->size(); ++ix )
cout << (*vec)[ix] << ' ';
cout << endl;
}
int main()
{
int ia[ 8 ] = { 8, 34, 3, 13, 1, 21, 5, 2 };
vector<int> vec( ia, ia+8 );
cout << "vector before sort: ";
display( &vec ); // pass the address now
// ...
}
A more important difference between a pointer and a reference parameter is that a pointer may or may not actually address an object. Before we dereference a pointer, we must always make sure that it is not set to 0. A reference, however, always refers to some object, so the check for 0 is unnecessary. In general, unless you wish to modify the parameter within the function, as we did with fibon_elem() in the preceding section, bool fibon_elem( int pos, int &elem ); I recommend not passing built-in types by reference. The reference mechanism is primarily intended to support the passing of class objects as parameters to functions. Scope and ExtentObjects defined within a function, with the requisite one exception, exist only while the function is executing. Returning the address of one of these local objects results in serious run-time program errors. Recall that a function is temporarily placed on the program stack in a special area of memory for the extent of its execution. Local objects are stored in this area of memory. When the function completes, this area of memory is discarded. The local objects no longer exist. Addressing a nonexisting object in general is a bad programming idiom. For example, fibon_seq() returns a vector of Fibonacci elements of some user-specified size:
vector<int> fibon_seq( int size )
{
if ( size <= 0 || size > 1024 )
{
cerr << "Warning: fibon_seq(): "
<< size << " not supported -- resetting to 8\n";
size = 8;
}
vector<int> elems( size );
for ( int ix = 0; ix < size; ++ix )
if ( ix == 0 || ix == 1 )
elems[ ix ] = 1;
else elems[ ix ] = elems[ix-1] + elems[ix-2];
return elems;
}
It would be incorrect to return elems by either reference or pointer because elems ceases to exist with the completion of fibon_seq(). Returning elems by value is OK: The copy of the object returned exists outside the function. [2]
The period of time for which memory is allocated for an object is called its storage duration or extent. The memory for elems is allocated each time fibon_seq() is executed. It is deallocated each time fibon_seq() terminates. We say that it has local extent. (Function parameters, such as size, also have local extent.) The region of the program over which an object is active is called its scope. We say that size and elems have local scope within the function fibon_seq(). The name of an object that has local scope is not visible outside its local scope. An object declared outside a function has file scope. An object that has file scope is visible from the point of its declaration to the end of the file within which it is named. An object at file scope has static extent. This means that its memory is allocated before the beginning of main() and remains allocated until the program is terminated. An object of a built-in type defined at file scope is always initialized to 0. An object of a built-in type defined at local scope, however, is left uninitialized unless explicitly provided with an initial value by the programmer. Dynamic Memory ManagementBoth local and file extent are managed for us automatically. There is a third form of storage duration called dynamic extent. This memory comes from the program's free store and is sometimes called heap memory. This memory must be managed explicitly by the programmer. Memory allocation is done using the new expression, whereas memory deallocation is done using the delete expression. The new expression is written this way: new Type; Here, Type can be any built-in or class type known to the program, or the new expression can be written as new Type( initial_value ); For example, int *pi; pi = new int; assigns pi the address of an object of type int allocated in heap memory. By default, an object allocated on the heap is uninitialized. The second form of the new expression allows us to specify an initial value. For example, pi = new int( 1024 ); also assigns pi the address of an object of type int allocated in heap memory. This object, however, is initialized to a value of 1,024. To allocate an array of heap elements, we write int *pia = new int[ 24 ]; This code allocates an array of 24 integer objects on the heap. pia is initialized to address the first element of this array. The array elements themselves are uninitialized. There is no syntax for initializing an array of elements allocated on the heap. A heap object is said to have dynamic extent because it is allocated at run-time through use of the new expression and continues to exist until explicitly deallocated through use of the delete expression. For example, the following delete expression causes the object addressed by pi to be deallocated: delete pi; To delete an array of objects, we add an empty subscript operator between the pointer addressing the array and the delete expression: delete [] pia; We do not need to check that pi is nonzero:
if ( pi != 0 ) // unnecessary -- compiler checks for us
delete pi;
The compiler does this check automatically. If for some reason the programmer does not apply the delete expression, the heap object is never deallocated. This is called a memory leak. In Chapter 6, we look at why we might choose to use dynamic memory allocation in the design of our programs. We look at ways to prevent memory leaks in our discussion of exception handling in Chapter 7. |
| I l@ve RuBoard |
|