Topical Information

This program should help you understand the use of templates and function objects.

Program Information

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.

The apply Function

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;
      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.

The accumulate Function

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],
   // 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)
        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.)

Putting It All Together

Place these functions in a template library. (Maybe genarr.h -- for generic array processing? *shrug*)

Show your template functions' power by passing arrays of

all in one test application.

Also test (as appropriate) passing functions that

Next test (as appropriate) by passing function objects which

Note: Some tests may not be appropriate for apply and others may not be appropriate for accumulate. You must decide which.

Thought Provoking Questions

  1. How many template functions did you write? How many instantiations of these functions are in your program's compiled binary? How many existed during the compilation of your program?

  2. What are the 'names' of the instantiations of your apply function in this program? Your accumulate function?

  3. Does the size of your .out file change if you comment out one of the calls to the apply? Why/Why not? (Hint: 'ls -l *.out' at the $ prompt will show the size of all the .out files on your account.)

  4. Is it possible for your template functions to fail to instantiate? Why/Why not? (i.e. What things are you requiring of each of your template types? Could the caller send an argument that didn't support all the requirements?)

  5. Is it possible for your template functions, once instantiated, to fail logically? Why/Why not? (i.e. Can the caller pass you something which meets all of your requirements, but does not perform as expected.)

  6. Could you use your template functions on an array of objects of type Point? Why/Why not? (Tell what requirement causes it to fail or the name of the resulting instantiation.)

  7. How long is your typical function object class? Are any of them templated? Could/Should they be?

  8. Could you use default arguments or overloading to have the plain function add an arbitrary n to the element? (See suggested tests.) If so, which would be better and why? If not, why not?

  9. How do you initialize a reference data member? How do you even declare such a beast? Maybe you might check out this example for clarification.

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.)

More Thought Provoking Questions

  1. Could you use static locals combined with default arguments to use a plain function for summing all elements? If so, explain how. If not, why not?

  2. Now, how long is your typical function object class? Are any of them templated? Could/Should they be?