SELECTIVE IGNORANCE

Finding the Signal in the Noise

March 2007

When should your class have a default constructor? Most C++ programmers know you need one if you want to create an array of your type, but are there other circumstances?

It occurred to me recently that you don't need a default constructor if objects of your class can never change their value once constructed. After all, if your objects are immutable, having a default constructor doesn't do you much good unless you happen to want an object that always has its default value.

The contrapositive of a true statement is also true--which means that a class that does need a default constructor must offer a way of changing the value of its objects. And if a class offers any way of changing its objects' value, it should probably have an assignment operator as well.

These two facts lead to the following somewhat surprising rule of thumb, which I have not seen before:

    If your class needs a default constructor, it should probably also have an assignment operator.

If you follow this rule, it means that whenever you can write

    T x = y;

you will be able to replace it by

    T x; x = y;

Indeed, the usefulness of this idiom suggests that the inverse of the rule may well make sense also, so that perhaps we should say

    Assignment operators and default constructors go together: If your class has one, it should have both.

Notice that it is possible for the assignment operator in this case to be generated by default. So, for example, the rule suggests that if you define a class such as

struct Point {
    Point(x0, y0): x(x0), y(y0) { }
    int x, y;
};

you should really define a default constructor as well, becuase otherwise the class will have a (compiler-generated) assignment operator but no default constructor.

I have not seen this rule of thumb discussed elsewhere; if you have seen it before now, I'd appreciate hearing about it.

Posted by Andrew Koenig at 12:13 PM  Permalink |

I've been teaching C++ in an industrial setting recently, and happened to notice a particularly subtle pitfall.

Suppose we write

vector<int> v(10);

Then we've defined a vector named v with 10 elements. But old habits die hard, and sometimes we might be tempted to write

vector<int> v[10];

Note the square brackets in place of the parentheses.

What we've done here is to say that we want an array with 10 elements, each of which is an empty vector! And of course, v[i] is still meaningful--it's just that its meanine is now completely different.

Needless to say, the diagnostic messages that result from this particular mistake are likely to be hard to interpret, as they will probably point to a place far away from the actual source of the problem.

One more reason to avoid stating vector sizes explicitly. Let's hear it for push_back!

Posted by Andrew Koenig at 02:40 PM  Permalink |

We want to write a function with the following declaration:

Seq<unsigned> dealstamps(cents c, const Seq<cents>& denoms);

Here, cents is an unsigned type that is appropriate to represent a number of cents. This function should return a sequence with one element for each element in denoms, representing how many stamps of each denomination there are.

If the problem can't be solved, we'll return an empty Seq. Our caller can check whether the result is empty to see whether the function worked.

If we were to pass an empty denomination sequence, of course, the result would be empty regardless; we'll consider that the caller's problem.

We begin by defining a variable to hold the result:

Seq<size_t> result;

If denoms is empty, either the problem has no solution or c is zero; either way the result is an empty sequence.

if (denoms.empty())
    return result;

Now we pick off the first denomination; if it's zero, we have no work to do.

const cents firstdenom = denoms.head();
if (firstdenom == 0)
    return result;

Now we have a first denomination and a number of cents. The maximum number of stamps will therefore be c/firstdenom. We'll also keep track in bestsum of the smallest total count of stamps we've seen so far, and in result of the corresponding number of each stamp. Until we see the first solution, bestsum will be infinity:

const size_t maxcount = c / firstdenom;
size_t bestsum = 0; bestsum = ~bestsum;

We will now proceed to work through every possible number of stamps for that first denomination.

for (size_t n = 0; n <= maxcount; ++n) {
    const cents remainder = c - n * firstdenom;

Here, remainder is the number of cents not accounted for by the stamps of the first denomination. We now call ourselves recursively to see if we can allocate the remainder among the rest of the denominations.

    const Seq<unsigned> s = dealstamps(remainder, denoms.tail());

If remainder was zero, this call might return an empty sequence; but we must treat it as success anyway. Otherwise, it is successful if it returns a nonempty sequence. Either way, we check whether this solution was better than the one we had so far. If so, we remember the new solution:

    if ((remainder == 0 || !s.empty()) && n + sum(s) < bestsum) {
        result = cons(n, s);
        bestsum = n + sum(s);
    }
}

return result;

And that's basically it.

Of course, we still need to write the Seq template. We'll leave that as an exercise.

Posted by Andrew Koenig at 12:09 PM  Permalink |

In order to try to solve this problem elegantly, or at least concisely, I imagined what kind of data structure I would really like to have available. What I came up with was something like Lisp lists.

Lisp is one of the oldest programming languages, and its fundamental data structure is based on five operations. If s is one of these data structures (Lispers call them S-expressions), then:

empty(s) is true if s is empty and false otherwise.

If s is not empty, car(s) is the first element of s.

If s is not empty, cdr(s) is a list that contains all but the first element of s.

If x is an element and s is a list, then cons(x, s) is a list such that car(cons(x, s)) is x and cdr(cons(x, s)) is s

nil is a list with no elements.

How might such a data structure look in C++?

Suppose that T is a type that can stand as an element of a vector. Then I imagined a template type Seq<T> such that if we defined

Seq<T> s;

then

s.empty() is true if s has no elements and false otherwise.

s.head() is the first element of s, provided that s is not empty.

s.tail() is a Seq containing all but the first element of s, provided that s is not empty.

cons(x, s) is a Seq that contains x followed by the elements of s.

Finally, Seq<T>() is an empty list.

With that data structure available, the problem becomes a good deal easier to solve.

Posted by Andrew Koenig at 11:59 AM  Permalink |

A number of problems involve trying a value for the first element in a sequence and then recursively figuring out the rest of the sequence. Such problems are often trickier to code in C++ than they look.

One reason for the difficulty is the impulse to be efficient--by not copying data structures around unless needed. For example, suppose we use a vector to represent the denominations of stamps that we have available. It should be easy enough to try all of the possibilities for the first denomination. But how do we then manage the recursive call?

The problem devolves to passing all but the first element of a vector to a function. It happens to be our own function, but the problem is still there. When put that way, it would seem that the obvious solution is to pass a pair of iterators rather than a vector, which means yet another argument to the function.

Then there is the problem of producing output. Ideally, we would like the output for such a program to be a sequence of values for each denomination--but in order to do that, the values have to be stored in a way that can be built up one element at a time. If we're not careful, we'll wind up copying a vector each time we return from one of the recursive calls.

The first solution I sketched out was embarrassingly complicated for this reason. In particular, the function took no fewer than four arguments: (1) The number of cents to express as stamps; (2-3) two iterators representing the denominations available, and (4) an output iterator representing a place to put the counts of available stamps.

Indeed, this program was so ungainly that I am reluctant to post it here, preferring instead to look for a more elegant solution.

(To be continued...)

Posted by Andrew Koenig at 11:04 AM  Permalink |

How many 2-, 7-, and 9-cent stamps are the minimum to make up a given amount? We've seen that a greedy strategy won't solve this problem, so what can we do?

One useful way of solving problems such as this one is to do so recursively, one denomination at a time. For example, although we don't know how many 2-cent stamps are optimum, we do know the range of possible values: We can't possibly have a negative number of stamps, and if we're trying to make up n cents, we can't have more than floor(n/2) stamps.

So here's a way of solving the problem: For each value in the range [0, n/2], assume that we have that number of 2-cent stamps and ask--recursively--what is the best way of solving the remaining problem. In other words, if we're assuming k 2-cent stamps, we find the best way of making up n-k cents with only 7- and 9-cent stamps, then add k to the number of stamps in the best solution. The value of k that minimizes the sum is the key to the puzzle.

It is true that this solution might be slow in practice; but we won't know until we try it whether it's too slow to be practical. So let's think about how to write such a program and see what it does for us.

Posted by Andrew Koenig at 09:10 AM  Permalink |

When the postage-stamp puzzle appeared on Usenet, my first thought was that a solution that contains three nested loops can't be right. Of course, that thought says little about what strategy is right. So let's think a little about how to approach the problem.

Our input is an amount of money and a collection of stamp denominations. The object of the game is to minimize the total number of stamps that we use to make up that amount of money.

Of course, there may be no solution at all. For example, if our smallest stamp is 2 cents, we have no way of making up a 1-cent sum. So whatever we do, we must take that possibility into account.

Some of the Usenet solutions I saw used a greedy algorithm: They tried to use as many 2-cent stamps as would fit, then as many 7-cent stamps, then as many 9-cent stamps. As stated, this algorithm doesn't work.

Consider, for example, what happens if you're trying to make up 11 cents. You'll take five 2-cent stamps, with one cent left over, and then you're stuck. Whereas if you had taken only one 2-cent stamp, you'd have 9 cents left over.

An obvious solution to that problem is to go the other way: Take as many 9-cent stamps as possible, then as many 7-cent, and finally as many 2-cent stamps. As it turns out, that doesn't work either. Consider, for example, what happens if you have 23 cents. You can take two 9-cent stamps, after which you have 5 cents left and you're stuck. If you had taken as many 7-cent stamps as possible first, you'd have wound up with three 7-cent stamps and one 2-cent stamp.

This line of reasoning suggests that being greedy isn't going to solve this problem. Instead, we need a systematic way of considering all possibilities. My next article will discuss one way of doing so.

Posted by Andrew Koenig at 12:00 PM  Permalink |

I encountered a cute programming problem recently on the comp.lang.c++ newsgroup: You have a supply of 2-cent, 7-cent, and 9-cent stamps, and you wish to figure out how to produce a given amount of postage using the smallest number of stamps.

This problem is interesting because it is hard enough that most programmers can't immediately dash off a solution, and easy enough that a solution will fit on one page. Even more interesting is how much trouble people seem to have with it, and how badly the sample programs are written.

I'm going to have more to say about this problem and its solution in coming articles. For now, I want to observe that several of the solutions I've seen have three nested loops: one for 2-cent stamps, one for 7-cent stamps, and one for 9-cent stamps.

My immediate impulse is that such a strategy is wrong--even without knowing what the right strategy might be. The reason is that the inventory of stamps that we have available is part of our data, whereas the number of loops in the program is part of its structure. The strategy is wrong, therefore, because it violates a fundamental principle:

The structure of a program should be independent of the values of its input data.

Of course, this general statement is a negative: It tells us what not to do, not what to do. So we still need to figure out how to solve the problem. We'll begin doing that in the next article.

Posted by Andrew Koenig at 11:23 AM  Permalink |

What have we learned from this algorithm story?

In the early days of C++, I wanted to show prospective users what C++ might be able to do for them. To that end, I wanted to write a program that would show off some recently available libraries that handled variable-length strings, lists, and associative arrays.

I chose topological sorting as my problem, because it had a practical application (although a slightly obscure one), and because it was small enough that I could explain it without boring the audience. The sorting program was much smaller than its C counterpart. Would it be faster too?

The answer was "it depends." Each of the C++ libraries had an abstraction penalty. For example, inserting an element in an associative array takes longer than appending an element to a built-in array. Moreover, in the case of this early version of the I/O library, the abstraction penalty could be described only as horrendous.

To counterbalance this overhead, the C topological-sorting program had quadratic execution time, which meant that in theory, the C++ version would be faster when the input was large enough.

In practice, "large enough" was still small enough to be encountered in practice. Which meant that I could find real data on which the C++ version of the program ran four times as quickly as the C version.

This let me claim, legitimately, that even at this early stage of development, there was an existing C program that, when rewritten in C++, was not only dramatically shorter but also faster on large data.

This example shows that there is often no easy answer to the question: "How much slower is C++ than C?" If the higher level of abstraction available in C++ gives a programmer the time to use a fast algorithm instead of a slow one, a C++ program can sometimes be much faster than its C counterpart.

Are such comparisons fair? After all, the programs being compared aren't really the same--although they solve the same program, they do so in different ways. Your answer to that question will depend on whether you care about theory or practice.

In theory, you should be able to translate any C program into an equivalent C++ program that runs just as fast. In practice, there is a tension that is caused by the difference in abstraction ability between C and C++. This difference encourages C++ programmers to write different programs from their C counterparts. Often, there is no theoretically meaningful way to compare such programs.

Posted by Andrew Koenig at 09:42 AM  Permalink |