Rethinking How to Teach C++ Part 4: Emphasizing the Library

• By Andrew Koenig, Barbara Moo
• February 1, 2001

Our previous three articles^1–3 explored the teaching philosophy embodied in our recent book, Accelerated C++: Practical Programming by Example. We have completely rethought how to teach C++. Our classroom experience has been that students learn much more rapidly with our new approach than they do with more traditional techniques. We are reviewing our philosophy in some detail in the hope that others interested in teaching—or learning—C++ can understand the motivation behind our approach and consider adopting it themselves.

Three principles underlie our approach::

• Explain how to use language or library facilities before explaining how they work.:
• Motivate each facility with a problem that uses that facility as an integral part of its solution. The problem must be interesting in its own right, and not merely constructed to demonstrate the facility.
• Present the most useful ideas first.

Our strategy so far has led us to describe three fundamental standard-library facilities—vector, string, and struct—before even mentioning built-in arrays or pointers. In doing so, we have shown how to write substantial programs. One example, which appeared in our previous article,³ reads a collection of students' names and corresponding grades, and prints an overall grade report in alphabetical order by name.

At this point, we thought about giving in to the temptation of talking about the low-level ideas of pointers, arrays, and dynamic memory allocation. However, in keeping with the idea of presenting the most useful ideas first, we decided to continue by talking about other types of containers and container operations, and the related—and fundamental—idea of iterators. The lower level ideas are important, of course, but we decided not to discuss them until we really needed them.

CONTAINER OPERATIONS AND ITERATORS
An awful lot of programming involves dealing with collections of data, be those collections of strings, files, bitmaps, display lists, URLs, or other collections. Accordingly, one of our aims is to make the reader comfortable working with collections.

So far, we have used only one type of container—a vector—and only a few operations: indexing, push_back, and sorting. Our next pedagogical task, then, was to find problems to motivate additional container operations.

We began by noting that once we have a program to compute grades for a collection of students, we might want to separate the students' grades into two containers based on whether or not the student passed the course. Our first try at solving this problem used only facilities we had already explained:

// separate passing and failing
// student records:first try
vector
  extract_fails(vector& students)
{
  vector pass, fail;
  for (vector::size_type i = 0;
       i != students.size(); ++i)
    if (fgrade(students[i]))
      fail.push_back(students[i]);
    else
      pass.push_back(students[i]);
  students = pass;
  return fail;
}

In this example, fgrade is a function, which we wrote separately, that determines whether a student failed the course.

Solving the problem using only familiar facilities helps in two ways: It reinforces the ideas that the students have already learned, and it provides a basis for improvement.

The improvement we pursued in this case came from the observation that the program copies each student record into one of two local variables, pass or fail, and then copies pass on top of its argument and returns fail. To avoid keeping more copies of data around than necessary, we showed examples of several other ways of solving the same problem.

The first revision appended each failing record to a local variable, and then erased it from the input:

// first revision:
// correct but potentially slow
vector
  extract_fails(vector& students)
{
  vector fail;
  vector::size_type i = 0;
          
  while (i != students.size()) {
    if (fgrade(students[i])) {
      fail.push_back(students[i]);
      students.erase(students.begin() + i);
    } else
      ++i;
  }
  return fail;
}

This is a nice example because it lets us explain several useful ideas, and it also gives us an opportunity to show some bad ideas to avoid.

First, note the statement

students.erase(students.begin() + i);

We have observed that people who are learning C++ often have trouble figuring out how to erase the nth element of a vector, so we made sure we showed an example of how to do it. To ensure that the behavior of this statement was clear, we even drew a picture to explain it (see Fig. 1).

Figure 1. Erasing an element from the middle of a vector.

Figure 1 makes plain both what it means to erase an element from the middle of a vector, and that doing so is a lot of work. If we want a program that uses this strategy to be efficient, we must figure out a way of erasing an element from the middle of a container that does not involve copying all the elements that follow.

ITERATORS AND LISTS
One straightforward way to avoid the work involved in copying the elements after an erasure is to use a different type of container—one that does not require the excess copying. The most common such container is a list, so we decided to recast our grading program in terms of lists.

Before we could do so, however, we needed to make it stop relying on the random-access properties of vectors. For example, when we evaluated fgrade(students[i]), we were relying on the vector class' ability to give us the ith element efficiently when we supplied the value of i. Moreover, to avoid random access, we would need a different way of accessing the container's elements because, until this point, random access was all we had.

These two requirements—the need to stop relying on random access and the related need for some other type of access—led neatly into the notion of an iterator. We described an iterator as a value that:

• Identifies a container and an element in the container;
• Lets us examine the value stored in that element;
• Provides operations for moving between elements in the container; and
• Restricts the available operations in ways that correspond to what the container can handle efficiently.

We also noted that iterators behave analogously to indices; therefore, we can often rewrite programs that use indices to use iterators instead. By way of an example, we rewrote our extract_fails program yet again to use iterators:

// second rewrite: iterators but no indexing;
// still potentially slow
vector
  extract_fails(vector& students)
{
  vector fail;
  vector::iterator
    iter = students.begin();

  while (iter != students.end()) {
    if (fgrade(*iter)) {
      fail.push_back(*iter); 
      iter = students.erase(iter);
    } else
      ++iter;
  }
  return fail;
}

This program is just as slow as the previous version. However, it has the important property of not using the random-access properties of vectors at all. Instead, it uses an iterator, of a type defined as part of the vector class, to traverse the vector sequentially.

The one subtlety about this program is in the statement

iter = students.erase(iter);

This statement solves another problem that often troubles beginning C++ programmers: It erases an element, identified by an iterator, from a container, and positions the iterator on the element after the erasure.

Once we have rewritten the program in this way, it becomes trivial to use lists instead of vectors:

// third revision:
// use list instead of vector
list
  extract_fails(list& students)
{
  list fail;
  list::iterator
    iter = students.begin();

  while (iter != students.end()) {
    if (fgrade(*iter)) {
      fail.push_back(*iter);
      iter = students.erase(iter);
    } else
      ++iter;
  }
   return fail;
}

This example makes an important point: If your program deals with containers by using iterators, it is easy to change the type of container the program uses—as long as the container supports all the operations the program needs. Accordingly, it is wise to write programs that use as small a set of container operations as is reasonably possible, to provide for the possibility of using other container types later.

One reason for choosing one container type over another is efficiency. In Accelerated C++, we reported on informal measurements of the vector and list versions of our program. When we ran both versions on a 735-element input file, the execution time was essentially the same for both versions. However, when the file grew to 73,500 records, the list version took about nine seconds to execute and the vector version took about 10 minutes.

CONCLUSION
The problem of dealing with student grades offers opportunities to use the language and standard library in several different ways. In this column, we showed how we used this example to explain sequential containers and references, and to make several points about program design and its effect on efficiency.

Not mentioned explicitly, but very much in our minds, was the notion that if it is possible to write two programs that solve the same problem for different types of containers, it should be possible to collapse those programs into one by using a template. In other words, by showing how to solve a single problem in the same way using vectors and lists, we have prepared the ground for generic programming—a notion we have not yet discussed.

Notice that even this far into the book—we are at page 87—we still have not mentioned pointers or built-in arrays. Indeed, the chapter that discusses them does not begin until page 169. Before we get there, we will have shown several more programming examples, introduced more algorithms and container operations, shown how to use templates to write generic functions, explained how to write classes with member functions and protection, and covered iterators in more detail. We find it is more effective for C++ programmers to learn about all of these concepts before they tackle pointers.

Of course, it is essential to discuss pointers eventually. Dynamic binding in C++ comes into play only in the context of pointers or references, and it is much harder to write OO programs using only references than it is to do so using pointers, because only by using pointers is it possible to allocate objects dynamically.

However, our experience is that pointers are a slippery subject to master, and beginners have a much easier time dealing with the value-like classes we have been using until now. Moreover, the notion of iterators turns out to provide a nice basis for explaining pointers.

A programmer who has a thorough understanding of the ideas we have described so far typically has no trouble learning how to use pointers. We therefore think it is right to defer explaining them until they are truly necessary.

References

1. Koenig, A., and B. E. Moo. "Rethinking How to Teach C++ Part 1: Goals and Principles," Journal of Object-Oriented Programming, 13(7): 44–47, Nov. 2000.
2. Koenig, A., and B. E. Moo. "Rethinking How to Teach C++ Part 2: Two Interesting Decisions," Journal of Object-Oriented Programming, 13(8): 36–40, Dec. 2000.
3. Koenig, A., and B. E. Moo. "Rethinking How to Teach C++ Part 3: The First Data Structures," Journal of Object-Oriented Programming, 13(9): 35–38, Jan. 2001.