Interesting example from homework and the wonder of valgrind The previous homework has 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, due to how short-circuit evaluation of && works, 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.

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:

Note: the new syntax new int[3]{42,13,88} that that both 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
==6671== Memcheck, a memory error detector
==6671== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==6671== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==6671== Command: ./bad
==6671== 
==6671== Invalid read of size 4
==6671==    at 0x108969: main (in /home/wcbrown/courses/S20SI204/S20SI204/lec/l22/bad)
==6671==  Address 0x5b7dc8c is 0 bytes after a block of size 12 alloc'd
==6671==    at 0x4C3089F: operator new[](unsigned long) (in ...)
==6671==    by 0x108922: main (in /home/wcbrown/courses/S20SI204/S20SI204/lec/l22/bad)
==6671== 
Not found!
==6671== 
==6671== HEAP SUMMARY:
==6671==     in use at exit: 12 bytes in 1 blocks
==6671==   total heap usage: 3 allocs, 2 frees, 73,740 bytes allocated
==6671== 
==6671== LEAK SUMMARY:
==6671==    definitely lost: 12 bytes in 1 blocks
==6671==    indirectly lost: 0 bytes in 0 blocks
==6671==      possibly lost: 0 bytes in 0 blocks
==6671==    still reachable: 0 bytes in 0 blocks
==6671==         suppressed: 0 bytes in 0 blocks
==6671== Rerun with --leak-check=full to see details of leaked memory
==6671== 
==6671== For counts of detected and suppressed errors, rerun with: -v
==6671== 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 tp 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 did a delete[] on our array to free that memory. So the end of main needs the line: 
delete [] A;

Functions and Arrays

There are many situations in which it's natural to ask for functions that have arrays as arguments or that return arrays ... or both! This class is just going to look at functions that operate on arrays, and the few new concepts that arise with them. In reality, there's nothing new at all ... it's just that the consequences of the fact that it is the pointers to the arrays that get manipulated in our programs, not the arrays themselves may not be so obvious.

We'll look at this stuff first from the prespective of our simple program from last class for computing averages. Here's that program. We're going to try and break it up into separate componants using functions. Essentially we'd like the bulk of the program to consist of these two function calls: 

  // Create array A and read N int's from input
  int *A = readints(N,fin);

  // Compute average
  double average = sum(A,N) / double(N);
In defining these two functions, we'll see how arrays get passed in and out of functions.

Returning Arrays from Functions

The first of our two functions is int* readints(int N, istream &IN);. This function should return an array of N ints, populated with values read in from IN. 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, istream &IN)
{
  // Create the array
  int* B = new int[N];
  
  // Read values into the array
  for(int i = 0; i < N; i++)
    IN >> B[i];

  // Return pointer to array
  return B;
}
And here's a pictorial depiction of what goes on. Notice that what gets returned from the function is a point, not an actual array. The array of ints does not disappear when the function call returns, because memory allocated with new has no scope or lifetime ... it just sticks around until the end of the program, or until it's explicitly destroyed with a call to delete, which we'll discuss later.
So, to sum up, functions can create arrays with new and return them by returning a pointer to the block of memory allocated by the call to new.

Passing Arrays to Functions

Arrays can be passed into functions by passing a pointer to the block of memory that comprises the array. Notice what this means as far as pass-by-value is concerned: the pointer is what gets passed, so your function gets a copy of the pointer, but the copy points to the same array in memory, so when you modify the array in the function you modify the same array you have back in the calling function. Thus, some people will say that arrays are always passed by reference in C++. Well ... really what happens is that arrays themselves are not passed, rather pointers to the arrays are what we pass, and receiving a copy of the pointer still allows us to modify the actual array.

So, getting back to our example, we need to implement the function int sum(int* A, int 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. 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;
}
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.

Modifying Arrays Passed to Functions

Hopefully the above functions make it pretty clear that 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.

Here's a good example of where we might want to do this. Continuing with the example program we've been adding functions to, what if these numbers were grades, and I wanted to add a curve to these grades? I might imagine having a function "bump" that would take an array and an integer "delta", and modify the array by increasing every value in the array by delta. So at the end of main() I might make the call 

bump(A,N,int(80 - average + 0.5));
... and then print out the contents of the array after the bump. Can you define the "bump" function?

Problems

  1. A contains predicate. Write function bool contains(string *A, int N, string s); that tells you whether or not the string s is contained in the array A.
  2. A getarray function. Write a function int* getarray(int N, int x); that allocates and returns a pointer to an array of N ints, each initialized to the value x.
  3. A shiftleft function. Write a function double shiftleft(double *A, int N, double x); that shifts all the elements in array A to the left by 1 position, puts the value x in the rightmost position in the array, and returns the value that had previously been in the leftmost position.
  4. An average function for arrays of doubles.
  5. Use the average function and the shiftleft function to do the smoothing problem from the last lab. Here's my solution.