9. More structures¶

9.1. Time¶

As a second example of a user-defined structure, we will define a type called Time, which is used to record the time of day. The various pieces of information that form a time are the hour, minute and second, so these will be the instance variables of the structure.

The first step is to decide what type each instance variable should be. It seems clear that hour and minute should be integers. Just to keep things interesting, let’s make second a double, so we can record fractions of a second.

Here’s what the structure definition looks like:

struct Time {
    int hour, minute;
    double second;
};

We can create a Time object in the usual way:

Time time = {11, 59, 3.14159};

The state diagram for this object looks like this:

The word “instance” is sometimes used when we talk about objects, because every object is an instance (or example) of some type. The reason that instance variables are so-named is that every instance of a type has a copy of the instance variables for that type.

9.2. `print_time`¶

When we define a new type it is a good idea to write a function that displays the instance variables in a human-readable form. For example:

void print_time(Time& t) {
    cout << t.hour << ":" << t.minute << ":" << t.second << endl;
}

The output of this function, if we pass time as an argument, is 11:59:3.14159.

9.3. Functions for objects¶

In the next few sections, we will demonstrate several possible interfaces for functions that operate on objects. For some operations, you will have a choice of several possible interfaces, so you should consider the pros and cons of each of these:

pure function: Takes objects and/or basic types as arguments but does not modify the objects. The return value is either a basic type or a new object created inside the function.
modifier: Takes objects as parameters and modifies some or all of them. Often returns void.
fill-in function: One of the parameters is an “empty” object that gets filled in by the function. Technically, this is a type of modifier.

9.4. Pure functions¶

A function is considered a pure function if the result depends only on the arguments, and it has no side effects like modifying and argument or outputting something. The only result of calling a pure function is the return value.

One example is after, which compares two Times and returns a bool that indicates whether the first operand comes after the second:

bool after(Time& time1, Time& time2)
{
    if (time1.hour > time2.hour) return true;
    if (time1.hour < time2.hour) return false;

    if (time1.minute > time2.minute) return true;
    if (time1.minute > time2.minute) return false;

    if (time1.second > time2.second) return true;
    return false;
}

What is the result of this function if the two times are equal? Does this seem like the appropriate result for this function? If you were writing documentation for this function, would you mention that case specifically?

A second exampel is add_time, which calculates the sum of two times. For example, if it is 9:14:30, and your breadmaker takes 3 hours and 35 minutes, you could use add_time to figure out when the bread will be done.

Here is a rough draft of this function that is not quite right:

Time add_time(Time& t1, Time& t2)
{
    Time sum;
    sum.hour = t1.hour + t2.hour;
    sum.minute = t1.minute + t2.minute;
    sum.second = t1.second + t2.second;
    return sum;
}

Here is an example of how to use this function. If current_time contains the current time and bread_time it takes for your breadmaker to make bread, then you could use add_time to figure out when the bread will be done.

Time current_time = {9, 14, 30.0};
Time bread_time = {3, 35, 0.0};
Time done_time = add_time(current_time, bread_time);
print_time(done_time);

The output of this program is 12:49:30, which is correct. On the other hand, there are cases where the result is not correct. Can you think of one?

The problem is that this function does not deal with cases where the number of seconds or minutes adds up to more than 60. When that happens we have to carry the extra seconds into the minutes column, or extra minutes into the hours column.

Here’s a second, corrected version of this function.

Time add_time(Time& t1, Time& t2)
{
    Time sum;
    sum.hour = t1.hour + t2.hour;
    sum.minute = t1.minute + t2.minute;
    sum.second = t1.second + t2.second;

    if (sum.second >= 60) {
        sum.second -= 60;
        sum.minute += 1;
    }
    if (sum.minute >= 60) {
        sum.minute -= 60;
        sum.hour += 1;
    }
    return sum;
}

Although it’s correct, it’s starting to get big. Later, we will suggest an alternate approach to this problem that will be much shorter.

This code demonstrates two operators we have not seen before, += and -=. These operators provide a consise way to increment and decrement variables. For example, the statement sum.second -= 60; is equivalent to sum.second = sum.second - 60;

9.5. `const` parameters¶

You might have noticed that the parameters for after and add_time are being passed by reference. Since these are pure functions, they do not modify the parameters they receive, so we could just as well have passed them by value.

The advantage of passing by value is that the calling function and the callee are appropriately encapsulated - it is not possible for a change in one to affect the other, except by affecting the return value.

On the other hand, passing by reference usually is more efficient, because it avoids copying the argument. Furthermore, there is a nice feature in C++, called const, that can make reference parameters just as safe as value parameters.

If you are writing a function and you do not intend to modify a parameter, you can declare that it is a constant reference parameter. The syntax looks like this:

void print_time (const Time& time) ...
Time add_time(const Time& t1, const Time& t2) ...

We’ve included only the first line of the functions. If you tell the compiler that you don’t intend to change a parameter, it can help remind you. If you try to change one, you should get a compiler error, or at least a warning.

9.6. Modifiers¶

Of course, sometimes you want to modify one of the arguments. Functions that do are called modifiers.

As an example of a modifier, consider increment, which adds a given number of seconds to a Time object. Again, a rough draft of this function looks like:

void increment(Time& time, double secs)
{
    time.second += secs;

    while (time.second >= 60.0) {
        time.second -= 60.0;
        time.minute += 1;
    }
    while (time.minute >= 60) {
        time.minute -= 60;
        time.hour += 1;
    }
}

This solution is correct, but not very efficient. We’ll leave it as an exercise to write a better one.

9.7. Fill-in functions¶

Occasionally you will see functions like add_time written with a different interface (different arguments and return values). Instead of creating a new object every time add_time is called, we could require the caller to provide an “empty” object where add_time can store the result. Compare the following with the previous version:

void add_time_fill(const Time& t1, const Time& t2, Time& sum)
{
    sum.hour = t1.hour + t2.hour;
    sum.minute = t1.minute + t2.minute;
    sum.second = t1.second + t2.second;

    if (sum.second >= 60) {
        sum.second -= 60;
        sum.minute += 1;
    }
    if (sum.minute >= 60) {
        sum.minute -= 60;
        sum.hour += 1;
    }
}

One advantage of this approach is that the caller has the option of reusing the same object repeatedly to perform a series of additions. This can be slightly more effecient, although it can be confusing enough to cause subtle errors. For the vast majority of programming, it is worth spending a little run time to avoid a lot of debugging time.

Notice that the first two parameters can be declared const, but the third cannot.

9.8. Which is best?¶

Anything that be done with modifiers and fill-in functions can also be done with pure functions. In fact, there are programming languages, called functional programming languages, that only allow pure functions. Some programmers believe that programs that use pure functions are faster to develop and less error-prone than programs that use modifiers. Nevertheless, there are times when modifiers are convenient, and cases where functional programs are less efficient.

In general, we recommend that you write pure functions whenever it is reasonable to do so, and resort to modifiers only if there is a compelling advantage. This approach might be called a functional programming style., that only allow pure functions. Some programmers believe that programs that use pure functions are faster to develop and less error-prone than programs that use modifiers. Nevertheless, there are times when modifiers are convenient, and cases where functional programs are less efficient.

9.9. Incremental development versus planning¶

In this chapter we have demonstrated an approach to program development we refer to as rapid prototyping with iterative improvement. In each case, we wrote a rough draft (or prototype) that performed the basic calculation, and then tested it on a few cases, correcting flaws as we found them.

Although this approach can be effective, it can lead to code that is unnecessarily complicated - since it deals with many special cases - and unreliable - since it is hard to know if you have found all the errors.

An alternative is high-level planning, in which a little insight into the problem can make the programming much easier. In this case the insight is that a Time is really a three-digit number in base 60! The second is the “ones column,” the minute is the “60s column,” and the hour is the “3600’s column.”

When we wrote add_time and increment, we were effectively doing addition in base 60, which is why we had to “carry” from one column to the next.

Thus an alternative approach to the whole problem is to convert Times into doubles and take advantage of the fact that the computer already knows how to do arithmetic with doubles. Here is a function that converts a Time into a double:

double convert_to_seconds(const Time& t)
{
    int minutes = t.hour * 60 + t.minute;
    double seconds = minutes * 60 + t.second;

    return seconds;
}

Now all we need is a way to convert from a double to a Time object:

Time make_time(double secs)
{
    Time time;
    time.hour = int(secs / 3600.0);
    secs -= time.hour * 3600.0;
    time.minute = int(secs / 60.0);
    secs -= time.minute * 60;
    time.second = secs;

    return time;
}

You might have to think a bit to convince yourself that the technique we are using to convert from one base to another is correct. Assuming you are convinced, we can use these functions to rewrite add_time:

Time add_time(const Time& t1, const Time& t2)
{
    return make_time(convert_to_seconds(t1) + convert_to_seconds(t2));
}

This is much shorter than the original version, and it is much easier to demonstrate that is is correct (assuming, as usual, that the functions it calls are correct).

9.10. Generalization¶

In some ways converting from base 60 to base 10 and back is harder than just dealing with times. Base conversion is more abstract; our intuition for dealing with times is better.

But if we have the insight to treat times as base 60 numbers, and make the investment of writing the conversion functions (convert_to_seconds and make_time), we get a program that is shorter, easier to read and debug, and more reliable.

It is also easier to add more features later. For example, imagine subtracting two Times to find the duration between them. The naive approach would be to implement substraction with borrowing. Using the conversion functions would be much easier and more likely to be correct.

Ironically, sometimes making a problem harder (more general) makes it easier (fewer special cases, fewer opportunities for error).

9.11. Algorithms¶

When you write a general solution for a class of problems, as opposed to a specific solution to a single problem, you have written an algorithm. We mentioned this word in The way of the program chapter, but we did not define it carefully. It is not easy to define, so we will try a couple of approaches.

First, consider something that is not an algorithm. When you learned to multiply single-digit numbers, you probably memorized the multiplication table. In effect, you memorized 100 specific solutions. That kind of knowledge is not really algorithmic.

But if you were “lazy”, you probably cheated by learning a few tricks. For example, to find the product of \(n\) and 9, you can write \(n - 1\) as the first digit and \(10 - n\) as the second digit. This trick is a general solution for multiplying any single-digit number by 9. That’s an algorithm!

Similarly, the techniques you learned for addition with carrying, subtraction with borrowing, and long division are all algorithms. One of the characteristics of algorithms is that they do not require any intelligence to carry out. They are mechanical processes in which each step follows from the last according to a simple set of rules.

In our opinion, it is embarrassing that humans spend so much time in school learning to execute algorithms that, quite literally, require no intelligence.

On the other hand, the process of designing algorithms is interesting, intellectually challenging, and a central part of what we call programming.

Some of the things that people do naturally, without difficulty or concious thought, are the most difficult to express algorithmically. Understanding natural language is a good example. We all do it, but it is only recently that the interdisciplinary field of natural language processing has reached the point where programs like ChatGPT have become possible for computers.

Later in this book, you will have the opportunity to design algorithms for a variety of problems, including some of the more interesting, clever, and useful algorithms computer science has produced.

9.12. Glossary¶

constant reference parameter¶: A parameter that is passed by reference but that cannot be modified.
fill-in function¶: A function that takes an “empty” object as a parameter and fills in its instance variables instead of generating a return value.
functional programming style¶: A style of program design in which the majority of functions are pure.
instance¶: An example from a category. Your cat is an instance of the category “feline things”. Every object is the instance of some type.
modifier¶: A function that changes one or more of the objects it recieves as parameters, and usually returns void.
pure function¶: A function whose result depends only on its parameters, and that has no other effects other than returning a value.

9.13. Exercises¶

Chapter 9 Exercise Set 1