This program should help you understand the use of templates and function objects.
Two functions made popular by mathematical theorists and functional programmers (programmers using Lisp or Scheme or such languages) are the apply function and the accumulate function. We'll be building these facilities for our C++ programs! (I know you can't wait/can't contain your excitement...*grin*) Let's look at each in turn.
We did a function similar to the apply function in lecture (I think we called it 'foreach').
The apply function will call a specified function (sent as an argument to the apply function) for each member of the array (the array also being sent as an argument to the apply function). Each array element is sent as the single argument of the specified function. It is the specified function's business if it chooses to alter that array element or not. (In other words, the apply function may or may not end up changing the elements of the array.)
Here's a new apply example to help you recall:
class Add_N
{
double addend;
public:
Add_N(double add = 0.0) { addend = add; }
Add_N(const Add_N & add) { addend = add.addend; }
double operator() (double add_to) { return addend + add_to; }
};
double x[MAX_X];
Array<long> y;
// fill x and y arrays
apply(x, actual_x, Add_N(4.2));
apply(y, y.size(), Add_N(-3));
Here all of the elements of x will have 4.2 added to them. All of y's elements will be 3 less than they once were.
Note how we construct an (function) object during the call to the apply function. This is common practice if you don't plan to re-use the object.
Both accept an array argument and a function argument. The first will potentially alter its array, while the second never does. Let's look at each in turn.
The accumulate function also takes a function as an argument. It again passes each element of the array to the function (specified by the argument). But this time, the function argument is not allowed to alter the proffered array element. Instead, it returns its result so that the accumulate function can 'add' it on to a result variable.
The accumulate was done in a group activity. Recall that its basic structure is similar to apply, but any desired accumulation is no longer required to be provided by the function (object) argument -- the accumulate function does the accumulation itself (truly shocking, I know).
To help you understand this, here are some more examples of using accumulate:
String append(const String & x, const String & y)
{
return x + ' ' + y;
}
// ...
String words[MAX_W],
sentence;
// fill words
sentence = accumulate(words, actual_words, append, String()) + '.';
Here we store the user's words into an array. Then, passing these words to the accumulate function, we concatenate them together inserting spaces along the way. The first argument is the array, the second argument is the length of the array (this could also be the start and end positions you wished to accumulate across), the third is the function to use for the accumulation (note it takes two arguments -- the first is the accumulator, the second is the new portion), then there is the fourth argument. That one is simply there to allow you to specify the type of the accumulator variable (the type that should be returned from accumulate). We could pass the accumulator variable by reference, but this negates the natural syntax of our call (adding the period onto the end of the accumulation and then storing that in our sentence). Also it helps illustrate a common trick in template programming: the template type must be used in the argument list. The array's template type is used. So is the function argument's. But the accumulator type isn't present (since we chose to use a return value). So, a dummy argument is instituted to accept the type -- its value is completely ignored. (See the template'd set driver for another example of this idea.)
Here's another example (which assumes we have a template'd dynamic array class):
typedef Array<short> Day_Counter;
Day_Counter which_day(Day_Counter & x, const Date & y)
{
x[y.day_of_week()]++;
return x;
}
Set<Date> meeting_times;
Day_Counter day_counts;
// fill meeting_times with dates for meetings
day_counts = accumulate(meeting_times, meeting_times.size(),
which_day, Day_Counter());
// day_counts will hold the number of meetings on each
// day of the week
Note that we still don't change the array element in accumulate's function argument. We are, however, changing the accumulator argument to the function argument. This is more efficient than creating a whole new array and then incrementing the one element. (Note the ++ applies to the return value of the [] so it must be the [] which returns a reference.)
Another example:
double add_em(double x, double y)
{
return x + y;
}
Array<double> nums;
double total;
// fill nums with user's numbers
total = accumulate(nums, nums.size(), add_em, 0.0);
Here the only change is that our dummy isn't a constructed object, but a simple literal. It has to be 0.0, however, or it will instantiate as integer. (Again, see the template'd set driver for other examples of these dummy arguments.)
Place these functions in a template library. (Maybe genarr.h -- for generic array processing? *shrug*)
Show your template functions' power by passing arrays of
short integers
doubles
chararacters
String class objects
all in one test application.
Also test (as appropriate) passing functions that
Next test (as appropriate) by passing function objects which
n to an element (show that this works for
different values of n using the same function
object!!)
Note: Some tests may not be appropriate for apply and others may not be appropriate for accumulate. You must decide which.
This assignment is (Level 3).
Add (Level 1) to also hand in
a version which has only the apply function -- no accumulate.
Here, you'll have to employ some sort of function object class
which can accumulate values. You'll have to be able to both add
something to the sum inside the object as well as retrieve that
value. All methods besides constructors should be operators.
See your notes for an example. (Note: mutable
class members may prove useful here...)
(Just to make sure: you'll be handing in two versions of this lab to
do this option. The original and the one which uses accumulating
function objects instead of an accumulate template.)