Arrays and Functions

Topics Covered

Using Valgrind
Functions taking an array as input.
Functions returning an array as output.
Using those functions in main()
exit() function, and #include <cstdlib>

Interesting example and the wonder of valgrind

Consider this problem: "Suppose we want to search for int x in array A of size n." ... and proposed the following code as a possiblity:

int i = 0;
while(A[i] != x && i < n)
  i++;
if (i == n)
  cout << "Not found!";
else
  cout << "Found!";
cout << endl;

You were supposed to recognize that you would be testing A[i] before recognizing that i was actually too big to use as an index for the array A.

However, if you compile and run this code, we may not see any problem. In fact, it's pretty likely the program will function exactly the way you want.

So how can I say there's and "error"?

Well, accessing an array at indices outside of its range is an error ... it's just kind of hard to predict when or whether that error will manifest itself in bad behavior that the user sees.

In fact, we've seen this same kind of thing with unitialized variable errors. We get programs that sometimes do run OK, and sometimes don't.

Valgrind

There's an amazing tool called valgrind that we can use to monitor the execution of our program to detect whether there are array out of bound accesses, as well as other bad things like memory leaks. Here's an example:

badexample.cpp Running with valgrind: don't be intimidated by the amount of output!

#include <iostream>
using namespace std;

int main()
{
  // Create array A = [32,13,88]
  int n = 3;
  int* A = new int[3]{42,13,88};

  // Value we're looking for
  int x = 15;

  // Code with an error!
  int i = 0;
  while(A[i] != x && i < n)
    i++;
  if (i == n)
    cout << "Not found!";
  else
    cout << "Found!";
  cout << endl;
  
  return 0;
}

/*******************************************
About new int[3]{42,13,88}:

It allocates an array of 3 ints
and initializes them to 42, 13 and 88.  I'm
just showing it here because it's so darn
useful!
******************************************/

$ g++ -o bad badexample.cpp
$ valgrind ./bad
...
==418== Invalid read of size 4
==418==    at 0x10922C: main (badexample.cpp:15)
==418==  Address 0x4dafc8c is 0 bytes after a block of size 12 alloc'd
==418==    at 0x483C583: operator new[](unsigned long) (in ...)
==418==    by 0x1091E5: main (badexample.cpp:8)
==418==
Not found!
==418==
==418== HEAP SUMMARY:
==418==     in use at exit: 12 bytes in 1 blocks
==418==   total heap usage: 3 allocs, 2 frees, 76,812 bytes allocated
==418==
==418== LEAK SUMMARY:
==418==    definitely lost: 12 bytes in 1 blocks
==418==    indirectly lost: 0 bytes in 0 blocks
==418==      possibly lost: 0 bytes in 0 blocks
==418==    still reachable: 0 bytes in 0 blocks
==418==         suppressed: 0 bytes in 0 blocks
==418== Rerun with --leak-check=full to see details of leaked memory
==418==
==418== For lists of detected and suppressed errors, rerun with: -s
==418== ERROR SUMMARY: 1 errors from 1 contexts (suppressed: 0 from 0)

See how valgrind is telling us that "Invalid read of size 4"?

That's because we are reading one int (4 byte) past the end of our array.
Valgrind can give you more information if you compile with the -g option to g++, which puts "debugging" information into the executable.

Specifically, it inserts information that connects the machine code in the executable with the line of source code that produced it.

g++ -g -o bad badexample.cpp

In this case valgrind's error message includes

==7204== Invalid read of size 4
==7204==    at 0x108969: main (badexample.cpp:15)

which shows us that line 15 of badexample.cpp is where the invalid read occurred.

Also notice that valgrind is reporting that we have a "memory leak". That's because we didn't do a delete[] on our array to free that memory. So the end of main needs the line:

delete [] A;

Important: Valgrind is an incredibly useful tool (especially if you remember to compile with the -g option) that checks for otherwise hard to find bugs related to using pointers. Take advantage of it.

Function sum()

Computing an average

Suppose that we want to compute the average of the elements contained in an array A with its size N. Then, we would like to have a function sum so that the following code works:

int s = sum(A,N);
double avg = s / double(N);

Prototype

Arrays can be passed into functions by passing a pointer to the block of memory that comprises the array. So, the prototype of the function sum() is as follows:

int sum(int* A, int N);

Note about the pointer A:

As far as pass-by-value is concerned, the pointer is what gets passed, so your function gets a copy of the pointer.
However, remeber that if the two pointers are equal, they both point to the same object.

Note about N:

Notice that when we pass an array to a function we always have to pass the length of the array along with it, otherwise we have no idea how many elements are in the array pointed to by A.

Definition

So, getting back to our example, we need to implement the function

int
  sum(int* A, int N);

. Hopefully the definition of this function looks straightforward.

int sum(int* A, int N)
{
  int total = 0;
  for(int i = 0; i < N; i++)
    total = total + A[i];
  return total;
}

Pictorial depiction

The question is this: What really goes on when we run it? Hopefully the pictures below, which illustrate what goes on in a sample run of the above function, will make clear to you what really goes on when arrays are passed to functions.

In summary,

If you modify any element within an array passed to a function, you're actually modifying the same array that the caller of the function is looking at.

Function readints(): How to return arrays

Likewise, you can write a function that works as follows:

Create an array of size N.
Read integers into the array.
Return the array.

Prototype

The prototype of the function is as follows:

int* readints(int N);

This function should return an array of N elements.

Definition

The basics of the function should be fairly straightforward. The important thing is to understand what happens! So, here's the function definition:

int* readints(int N) {
  // Create the array
  int* B = new int[N];
  
  // Read values into the array
  for( int i = 0; i < N; i++ )
    cin >> B[i];
      
  // Return pointer to array
  return B;
}

In summary:

A function can create arrays with new.
Then then it can return the arrays by returning a pointer to the block of memory allocated by the call to new.

The final program

Note that the main() function contains

delete[] A;

in the end.

Someone has to take care of deleting the array, when it becomes no more useful.

In our case, that's when the final average is computed. So, the main function should take the role.

#include <iostream>
using namespace std;

int* readints(int);
int sum(int* , int);

int main()
{
  int N;
  cout << "How many numbers? ";
  cin >> N;

  int* A = readints(N);
  int s = sum(A, N);
  double avg = s/double(N);

  cout << "Average is " << avg << endl;

  delete [] A;
  return 0;
}

int* readints(int N) {
  // Create the array
  int* B = new int[N];

  // Read values into the array
  for( int i = 0; i < N; i++ )
    cin >> B[i];

  // Return pointer to array
  return B;
}


int sum(int* A, int N)
{
  int total = 0;
  for(int i = 0; i < N; i++)
    total = total + A[i];
  return total;
}

exit(1)

Q: If you want to exit the program, and you're not in main(), you can't just do "return 0;". Why?

A: Because it would only return from the current function.

So there is a function "exit" that you can call to exit from anywhere. In particular, consider the following statement:

exit(0);    // requires #include <cstdlib>

It will exit the program, no matter where you are.

Note

You must #include <cstdlib> to use it.
The function exit() takes an int argument which is the value the program will return to the operating system.

Mandatory Practice Problems

A contains predicate. Write function contains that tells you whether or not the string s is contained in the array A.
A getarray function. Write a function getarray that allocates and returns a pointer to an array of N ints, each initialized to the value x.

Topics Covered

Interesting example and the wonder of valgrind

Valgrind

Function sum()

Computing an average

Prototype

Definition

Pictorial depiction

Function readints(): How to return arrays

Prototype

Definition

The final program

exit(1)

Note

Mandatory Practice Problems

Other Practice Problems