[Contents]

Copyright © 2011 jsd

Modern Programming
John Denker

1  Introduction

This is an answer to some questions I received, namely:

Executive summary: Program objects, also called classes, have advantages at the conceptual level and at the implementation level. The central idea is that often you want to think about and deal with the object as a whole, without having to fuss with the internal details. Engineers call this the “black box” approach. By way of example: You are happy to drive a car without spending every moment thinking about the details of how the engine works internally.

The C++ system has a huge number of features that plain C does not, most notably the Standard Template Library (STL). There are two remarkable things here: firstly, that the C++ language is powerful enough to permit a template library to be written, and secondly, that the STL was in fact written and standardized.

Programming in the modern style makes the code easier to write and easier to read. It makes the code more reliable, more maintainable, more usable, and more extensible.

For small, simple, unimportant programs, C++ has no advantages over Tiny Basic or Fortran anything else; the choice of language doesn’t matter. On the other hand, if the task is in any way large, tricky, or important, programming in the modern style makes things much, much easier.

Note that there are some general good programming practices that apply in all situations, whether or not modern language features are being used. See reference 1.

*   Contents

1  Introduction
2  Some Examples
2.1  A First Example : Strings
2.2  Interfaces versus Internals
2.3  The Standard Template Library and Boost Library
2.4  Levels of Proficiency
2.5  How To Read This Document; Usability
2.6  Structures, Narrowly Speaking
2.7  Incrementer : Introductory Example of Classes and Functors
2.8  Managed Storage; STL Container Classes
2.9  brent::zero : Real-World Example of Derived Classes etc.
2.10  Namespaces
2.11  References
2.11.1  Call by Reference
2.11.2  Other References
2.12  Exceptions
2.13  Guaranteed Pairing of Constructors and Destructors
2.14  Max of Two or Three Integers : Overloading
2.15  Templates
2.16  Max of an Arbitrarily-Long List
2.17  Assembling a List from Disparate Sources
3  Discussion
3.1  Why Bother with C++?
3.2  Derived Classes
4  References

2  Some Examples

2.1  A First Example : Strings

Let’s start with a basic yet spectacular difference between C and C++: the strings. The strings!

Here is a sample of code. This is a complete, working C++ program that concatenates two strings and prints the results.

// Example program : concatenation of strings
using namespace std;

#include <string>       // the standard string library
#include <iostream>     // for cout

int main(){
  string a = "apple";
  string b = "sauce";
  string c = a + b;     // concatenate the two strings
  cout << c << endl;    // print the compound word
}

strings-example.c

This code stands in contrast to the plain C code that would accomplish the same task using functions such as strcpy and strcat. The C++ version has several advantages, including:

2.2  Interfaces versus Internals

Another interesting thing is that the internal representation of the strings is not public, so that code outside of the string class cannot see it, let alone mess with it. This supports a style of programming that emphasizes the importance of good interfaces. As long as the declared interface methods do what they are supposed to do, users do not need to know anything about the internals of the class. The class maintainer (as distinct from ordinary users) is then free to re-implement the internals if the need arises, and the users don’t need to know about it.

The fact that user code is insensitive to the internals of the class makes the overall project vastly easier to debug, to maintain, and to extend.

2.3  The Standard Template Library and Boost Library

The C++ programming system is immensely more useful than the C++ language itself, because the system includes not just the language but also the Standard Template Library (STL). The same international groups that standardize the language features also standardize the STL features. Every C++ implementation must include the full STL ... which means that code that relies on the STL is portable.

The STL includes the aforementioned strings. It also includes arrays, linked lists, fifos, maps (i.e. associative memory), I/O formatting, and lots of other stuff.

To become a C++ programmer, you do not need to become an expert on everything in the Standard Template Library. Instead, you should skim the STL documentation, to get a feel for the sort of thing that is there. Then, when you are actually ready to do something, you can read up on the details of whatever feature you need.

The Boost library provides yet more capabilities. It is constantly growing (unlike the STL, which is internationally standardized, and therefore changes slowly if at all).

All this stands in contrast to plain C, which does not guarantee anywhere near the same level of library support.

2.4  Levels of Proficiency

There are several levels of C++ proficiency:

2.5  How To Read This Document; Usability

Important: If you are presently operating at level zero or level one, when you read the examples below, don’t worry too much about how the structures and classes are constructed, but instead focus on how they are used. That is, start by looking at the main programs. Later you can look at the class declarations to see how things work internally.

In my experience, people learn more about programming from looking at samples of code than they do from reading the formal specification of the language.

One of the big ideas here concerns the reusability of code. If the hope is that your code is going to be reused dozens or thousands or millions of times, it is worth expending some effort in order to make sure that desire is fulfilled. Often handing the general case no harder than handling one or two special cases. Even if handling the general case is 2X or 3X harder, it’s well worth it, if it makes the code more more reliable, more usable, more reusable, and more extensible.

Specifically: Some of the class declarations shown below are trickier and more complicated than you might have expected, but I found it worthwhile to write them this way, because it made them easier to use.

It’s something of a self-fulfilling prophecy either way:

2.6  Structures, Narrowly Speaking

Narrowly speaking, objects existed in C decades before C++ came along. C uses the keyword “struct” (as in structure) when talking about objects. The term “structured programming” originally referred to structuring the control-flow of the program using subroutines and well-designed { ... } blocks, but nowadays it also refers to structuring the data.

A familiar example of this type of object is a complex number, which has a real part (first member) and an imaginary part (second member). Another oft-cited example is the HR record of a person, which has various members including first name, last name, social security number, et cetera.

Along the same lines, one could define a three-dimensional vector, with members x, y, and z.

Another example that I have used a gazillion times is a struct representing a particle, for a physics application or a game application or whatever. It has various members including position, velocity, et cetera.

The members of a struct can be built-in data types (int, double, char, etc.) ... or they can be other structs. Engineers love to build black boxes out of smaller black boxes, hierarchically. For example, in the aforementioned particle structure, the members themselves were vector structures.

2.7  Incrementer : Introductory Example of Classes and Functors

Now let’s talk about classes. In C++, the terms class and struct are almost1 synonymous.2 I will use the term class from now on, mainly to emphasize that I am talking about C++ as opposed to C. A class can have members that are functions in addition to members that are data items. The function members of a class are also called the methods of the class.

As a particularly simple example, suppose you wanted to have a function that returns the successor to an integer.

        step(1) is 2
        step(2) is 3
        step(64) is 65

That’s an easy function to write. Now suppose on some days you want to count by twos, so you conceive of another function

        hop(1) is 3
        hop(2) is 4
        hop(64) is 66

That’s also easy, but now suppose you want to handle the general case, and you don’t want to write a separate copy of the code for every possible case, considering that there are infinitely many possibilities. Wouldn’t it be nice to write a function that had a data member inside it somewhere, so that you could tell it what addend is desired today?

Here is a sample program that uses these ideas:

// Example program : parameterized family of functions
using namespace std;

#include <iostream>     // for cout
#include "incrementer.h"

int main(){
  incrementer step;                 // constructor without args; addend=1
  incrementer hop(2);
  incrementer skip = hop;                   // instances can be copied
  incrementer jump(5);
  cout << step(64) << endl;                     // prints 65
  cout << skip(64) << endl;                     // prints 66
  cout << jump(64) << endl;                     // prints 69
  cout << jump.backwards(64) << endl;           // prints 59
  cout << incrementer(3)(64) << endl;       // emphemeral instance : prints 67
}

incrementer.c

Here “incrementer” is the class (as defined below), and step, hop, skip, and jump are instances of the class. In the last line of the program, we create an anonymous ephemeral instance of the class (with addend 3), and immediate apply that instance to the argument (64).

Note that the incrementer class defines a method called operator(). That allows us to treat each instance of the class as a function. That is, we can use the name of the instance (such as “hop”) followed by an argument in parentheses, which looks just like a function call, and the operator() method will be called. Any class that defines an operator() method is called a functor.

Remark: It is important to keep in mind the distinction between the class itself and instances of the class.

In particular: Beware that the word “struct” sometimes refers to the struct-class and sometimes to a struct-instance, and similarly the word “object” sometimes refers to the object-class and sometimes to an object-instance. This ambiguous terminology leads to needless confusion.

There are a few cases where the ambiguity is harmless (for instance if we say that a certain object has five member variables), but even so, ambiguity is never a good thing. It is best to avoid using the words “struct” and “object” altogether.

Stick to using the well-behaved terms “class” and “instance”.

A major advantage of classes is that you can write the incrementer class-definition just once, and then use it again and again. Here is the definition of the incrementer class:

class incrementer{
public:
  int addend;
  incrementer(const int _addend = 1){
    addend = _addend;
  }
// special method for using this class as a function
// i.e. functor:
  int operator()(const int arg) {
    return arg + addend;
  }
// non-special method i.e. member function:
  int backwards(const int arg){
    return arg - addend;
  }
};

incrementer.h

The incrementer class is somewhat contrived, in the sense that there are easier ways to increment numbers. Its purpose is to provide an easy-to-understand illustration of language features.

If you would like a completely non-contrived real-world example that uses several modern language features yet is simple enough to be understood in detail, see section 2.9.

Additional examples that do even more powerful things include the STL strings (section 2.1) and the STL container classes (section 2.8).

2.8  Managed Storage; STL Container Classes

As a more complicated and very important example, consider managed storage. When you first create an instance of the class, it allocates a bunch of memory and returns a pointer that you can use to access the memory. If you copy the pointer, methods within the class keep track of how many copies you have made. This is tricky, but it can be done ... and the ordinary user does not need to worry about – or even know about – how it is done. Then, when the last of these pointers goes out of scope, there is a method that notices that and automatically frees the allocated storage.

C++ strings do this. Lots of other things do it, too.

This is incredibly important for reliability and security, because long and painful experience proves that programmers cannot be trusted to count these things by hand, and dangling pointers are a recipe for disaster. (Look at the CERT archives if you don’t believe me.)

Again, for anything that requires security or reliability, modern languages such as C++ and Java are the only game worth playing.

Here’s an example that uses the STL container classes:

// Example program : concordance, using STL container classes
// i.e. for each word, print a list of all pages where it appears
using namespace std;

#include <string>       // the standard string library
#include <iostream>     // for cout
#include <map>
#include <list>

int main(){
  int foo(3);
  {// beginning of block
// create empty concordance:
    map<string, list<int> > concordance;
// add some entries to it:
    concordance["apple"].push_back(foo++);
    concordance["lemon"].push_back(foo++);
    concordance["apple"].push_back(foo++);
    concordance["apple"].push_back(foo++);
    concordance["lemon"].push_back(foo++);
// dump the contents of the concordance:
    for (map<string, list<int> >::const_iterator wordlist = concordance.begin();
                 wordlist != concordance.end(); wordlist++){
// print the word:
      cout << wordlist->first << " : ";
// print the list of all pages where it appears
      for (list<int>::const_iterator page = wordlist->second.begin();
                page != wordlist->second.end(); page++) {
        cout << *page << " ";
      }
      cout << endl;
    }
  }// end of block; all memory used by the concordance has been freed

  // more processing ...
  // and more .....
}

container-example.c

and here is the output:

apple : 3 5 6 
lemon : 4 7 

container-example.out

Note that the concordance object is declared within an inner block, and goes out of scope before the end of the program. At the point where it goes out of scope, all the storage used by the concordance is automatically freed. See section 2.13 for more on this.

Writing the concordance example in C++ requires knowing a few things, such as what a list is and what a map is, and what list::push_back does and what map::const_iterator does. However, the advantage is that once you’ve got it written, it is very likely to just work. There is not much to debug.

This stands in contrast to plain C. It could be argued that writing a rough draft of the concordance program in plain C would not be much harder than writing it in C++. However, a rough draft doesn’t solve the problem. We need something that works reliably, and getting the C version to be reliable would require a lot of care and a lot of effort.

The point is that although it takes some time to learn C++, the investment breaks even by the time you’ve written one or two programs ... and the investment becomes more and more profitable as you become more and more familiar with the language.

To say the same thing another way: Writing bad code is easier in C. Writing good code is easier in C++.

2.9  brent::zero : Real-World Example of Derived Classes etc.

In this section we consider a real-world situation that leads on a tour of interesting programming techniques and language features, including functors, derived classes, namespaces, et cetera.

Once upon a time, I wanted to calculate the pH of an acid solution. This involved finding the root of a cubic polynomial. There are standard “textbook” formulas for solving a cubic, but in practice they fail miserably, because they are numerically unstable. That is, they are unduly sensitive to roundoff errors. We are much better off using an algorithm that searches for the zeros of an arbitrary function. The so-called “Brent algorithm” is a good way to do this. We are in luck, because John Burkardt has already written some code to implement this, along with several related algorithms; see reference 2. We are particularly interested in the routine zero(a, b, t, f) which searches the interval from a to b looking for a zero of the function f with tolerance t. Here is a program that demonstrates the use of this function:

// Progrem to demonstrate calling Brent zero-finder

#include <iostream>
#include <iomanip>
#include "brent.h"

using namespace std;
using namespace brent;

int main(){
  monicPoly Hbalance(3);                     // a cubic polynomial
  Hbalance.coeff[1] = -1;
  Hbalance.coeff[2] = 2;
  for (int ii = 0; ii <=6; ii++) {
    double prod = 2. + ii/1e5;
// the polynomial is something like:  -2.000001 - x + 2x^2 + x^3
    Hbalance.coeff[0] = -prod;
    double root = zero(0.5, 1.5, 1e-13, Hbalance);
    cout << "Prod of roots: " << setprecision(6) << setw(7) << prod
        << "  Pos root: "    << setprecision(12) << setw(13) << root
        << "  Y val: "        << setprecision(2) << Hbalance(root)
        << endl;
  }
}

brent-poly.c

The example in brent-poly.c is very, very similar to the real-world pH-finding program, just slightly simplified so that you can understand it without knowing any chemistry. You just need to know what a polynomial is. The output of the program is:

Prod of roots:       2  Pos root:             1  Y val: 4.7e-14
Prod of roots: 2.00001  Pos root: 1.00000166666  Y val: 4.5e-14
Prod of roots: 2.00002  Pos root: 1.00000333332  Y val: 4.5e-14
Prod of roots: 2.00003  Pos root: 1.00000499998  Y val: 4.6e-14
Prod of roots: 2.00004  Pos root: 1.00000666663  Y val: 4.6e-14
Prod of roots: 2.00005  Pos root: 1.00000833328  Y val: 4.6e-14
Prod of roots: 2.00006  Pos root: 1.00000999992  Y val: 4.5e-14

brent-poly.out

You can see that we pass the Hbalance object to the zero-finding routine. Conceptually, Hbalance is a polynomial. We could have defined a simple function

         double Hbal(double x){...}

and passed that to the zero-finding routine, but that would have been awkward, since we have a loop that iterates N times. It would not make sense to write N different functions. We would prefer to have just one function that depends on x but also depends on some parameters, namely the coefficients of the polynomial.

The question then arises, when we pass a function to the zero-finding routine, how do we pass the necessary parameters? Well, the best way to do it is to pass a functor. (There are at least two other ways of doing it, but the functor approach is by far the nicest.)

Hbalance is in fact a functor. It is an instance of the poly class. Note the distinction:

To get a clearer idea how this works, let’s take a look at the file brent.h, which defines the interface to this set of routines.

#include <vector>
namespace brent {

class func_base{
public:
  virtual double operator() (double) = 0;
};

class monicPoly : public func_base {
public:
  std::vector<double> coeff;
  virtual double operator() (double x);
// constructors:
  monicPoly(const size_t degree)
   : coeff(degree) {}
  monicPoly(const std::vector<double>& v)
   : coeff(v) {}
  monicPoly(const double* c, size_t degree)
   : coeff(std::vector<double>(c, c+degree)) {}
};

class Poly : public func_base {
public:
  std::vector<double> coeff;    // a vector of size nterms i.e. 1+degree
  virtual double operator() (double x);
// constructors:
  Poly(const size_t degree)
   : coeff(1+degree) {}
  Poly(const std::vector<double>& v)
   : coeff(v) {}
  Poly(const double* c, size_t degree)
   : coeff(std::vector<double>(c, 1+c+degree)) {}
};

double glomin ( double a, double b, double c, double m, double e, double t,
  func_base& f, double &x );
double local_min ( double a, double b, double t, func_base& f,
  double &x );
double local_min_rc ( double &a, double &b, int &status, double value );
double r8_abs ( double x );
double r8_epsilon ( );
double r8_max ( double x, double y );
double r8_sign ( double x );
void timestamp ( );
double zero ( double a, double b, double t, func_base& f );
void zero_rc ( double a, double b, double t, double &arg, int &status,
  double value );

// === simple wrapper functions
// === for convenience and/or compatibility
double glomin ( double a, double b, double c, double m, double e, double t,
  double f ( double x ), double &x );
double local_min ( double a, double b, double t, double f ( double x ),
  double &x );
double zero ( double a, double b, double t, double f ( double x ) );

}

brent.h

You can see that the zero(⋯) function is expecting an object of type func_base), but we are passing it an object of type poly. That is allowed, because poly is a derived class, derived from func_base (which is called the base class). We know that by looking at the statement

        class poly : public func_base {...}

where the base class is mentioned after the colon.a

The derived class inherits all the member variables and methods of the base class, and then adds zero or more variables and methods of its own. In this case, the poly class adds a member variable, namely the coeff vector.

If the base class declares a method to be virtual, the derived class is allowed to override the method, replacing it with a different method of the same name. Indeed, if the base class declares a method to be pure virtual then the derived class is obliged to override it. In fact the func_base class does declare the operator() method to be pure virtual; that’s what the “= 0” in the declaration means. We could have specified a trivial default method instead, but in this case it is better to make it pure virtual, since the whole exercise doesn’t make any sense unless the derived class provides a method to evaluate the function. By making it pure virtual, the compiler can check at compile-time that what we are doing makes sense.

The poly class is predefined for us in brent.h, but we are allowed to define our own derived classes, as you see in brent-sine.c, which uses a discrete Fourier sine series instead of a polynomial. This is the sort of thing that might arise in connection with a standing wave in a box.

// Progrem to demonstrate calling Brent zero-finder

#include <iostream>
#include <cmath>
#include "brent.h"

using namespace std;

class sine_series : public brent::func_base{
public:
  std::vector<double> coeff;
  virtual double operator() (double x);
// constructor:
  sine_series(const std::vector<double>& v)
   : coeff(v) {}
};

double sine_series::operator()(double x){
  double rslt(0);
  for (size_t ii = 1; ii <  coeff.size(); ii++){
    rslt += coeff[ii] * sin(ii * x);
  }
  return rslt;
}

int main(){
// Beware:  The initializer-list on the following line
// uses a c++11 language feature.
// If it doesn't compile chez vous, consider upgrading your compiler
// ... or rewrite this to use c++03 features.
  sine_series foo({0, 0.3, 0.4, 0.15});
  double rslt = brent::zero(1, 2, 1e-10, foo);
  cout << "Root: " << rslt
       << "  Y val: " << foo(rslt)
       << endl;
}

brent-sine.c

2.10  Namespaces

At this point you may be asking, why does brent-sine.c refer to brent::zero(⋯) when the previous example referred to simply zero(⋯)? The answer has two parts:

2.11  References

2.11.1  Call by Reference

Here’s another way in which C++ differs from plain C:

// Example program : call by reference
using namespace std;

#include <iostream>     // for cout

void seventeen(int& foo){
  foo = 17;
  return;
}

int main(){
  int bar;
  bar = 3;
  seventeen(bar);
  cout << bar << endl;          // prints 17
}

call-by-ref.c

The subroutine modifies the value of the main program’s variable bar. Note the ampersand in the declaration of the subroutine argument. This indicates call by reference.

You can achieve more-or-less the same effect in plain C by passing a pointer, but then you would need to use asterisks all over the place to dereference the pointer. Call by reference means you don’t need those asterisks, so the code in the subroutine looks the same and works the same as the code in the main program.

This does have anywhere near the degree of security and reliability implications as the other language features we have been discussing. It is just a convenience. However, it does make the code easier to write and easier to read.

2.11.2  Other References

The notion of reference is not restricted to the arguments of functions. The same notion of reference appears in menu-list.c, where menu_head is defined as a reference, making it a synonym for menu_root->next. This makes the subsequent code slightly clearer and cleaner. (This makes use of the fact that menu_root does not change. If it did change, menu_head would no longer be a synonym for menu_root->next. This would not be the only thing that got broken if menu_root changed.)

2.12  Exceptions

C++ provides for exceptions. Here is an example where an exception is thrown at the fourth level and caught at the top level:

// Example program : exceptions with constructors and destructors
using namespace std;

#include <string>       // the standard string library
#include <iostream>     // for cout

class light {
  string description;
public:
// constructor:
  light(const string d = "whatever") : description(d) {
    cout << "Light turned on: " << description << endl;
  }
// destructor:
  ~light(){
    cout << "Light turned off: " << description << endl;
  }
};

int fourth_level(){
  light xxx("red");
  throw string("something unusual");
  // complicated stuff
  return 4;
}

int third_level(){
  light xxx("green");
  cout << "+++ third-level manual setup" << endl;
  int rslt = 3*fourth_level();
  cout << "+++ third-level manual cleanup" << endl;
  return rslt;
}

int second_level(){
  light xxx("blue");
  // complicated stuff
  return 2*third_level();
}

int main(){
  try {
    // will print 24, unless there is an exception:
    cout << second_level() << endl;
  } catch (int foo) {
    cout << "Caught int exception: " << foo << endl;
  } catch (string foo) {
    cout << "Caught string exception: " << foo << endl;
  }
}

exception-example.c

One thing to notice is that the intermediate levels (second level and third level) don’t need to know anything about the exception. They don’t even need to know that the exception is possible. This means that in a big complicated program, you can modify it by throwing an exception in one place and catching it in another place, without having to rewrite the entire program.

Here is the output from the program:

Light turned on: blue
Light turned on: green
+++ third-level manual setup
Light turned on: red
Light turned off: red
Light turned off: green
Light turned off: blue
Caught string exception: something unusual

exception-example.out

It is of course possible to emulate exception-handling in a language that does not support it, by writing code at every level to detect and deal with exceptions coming from lower levels. However, this is laborious and error-prone.

C++ allows you to throw any type of object. At one extreme, you can define your own class that has the sole purpose of being something to throw. At the other extreme, you can throw some prosaic pre-existing object such as an int or a string. Another option is to throw something derived from std::exception, as discussed in section 2.16.

It is possible to abuse exceptions. You should probably use them only sparingly. On the other hand, it seems safe to say there are more programs that would benefit from more exception handling than programs that would benefit from less.

2.13  Guaranteed Pairing of Constructors and Destructors

Another thing to notice in container-example.c is that C++ will automatically call the destructors for the relevant “light” objects, so that by the time the exception is caught, all the lights have been turned off.

More generally: We are guaranteed that every call to a constructor will eventually be paired with a call to the corresponding destructor. This is important, because for all the reasons you might want to turn on lights, you want to make sure they get turned off before you leave.

This is true for exceptions, as in the example in section 2.12, but it is equally true for any other way of leaving a block of code, such as a goto statement or an early return statement.

This is very different from the manual setup and manual cleanup we see in the third_level code. In this example, whenever there is an exception (or an early return or whatever), the manual cleanup code never gets called. If you depended on such code to turn the lights off (rather than using constructors and destructors), it would be tricky to do it correctly. The code would be hard to write, hard to read, hard to test, and hard to modify.

For what it’s worth, the automatic memory management discussed in section 2.8 is implemented by means of constructors and destructors. However, you are mostly free to use the container classes without worrying about how they are implemented internally. Also, as illustrated by the example in this section, there are lots of things other than memory management that can be done using constructors and destructors.

2.14  Max of Two or Three Integers : Overloading

Let’s write a function that computes the maximum of two numbers. We start with an ultra-simple version, and then gradually make it more sophisticated. (This is an example of iterative refinement which is often a good engineering practice.)

We start by writing the usual form of the function, with two arguments. Soon afterwards, we discover that we sometimes want to find the maximum of three numbers. So we implement that also. Here is the code:

// Example program : maximum

#include <iostream>     // for cout

const int & max(const int& a, const int& b){
  return (b<a)?a:b;
}

const int & max(const int& a, const int& b, const int& c){
  return ::max(a, ::max(b, c));
}

int main(){
  using namespace std;
  cout << max(1, 3, 5) << endl;        // prints 5
}

max3-example.c

Note that that 3-argument max and the 2-argument max have the same name! It turns out the C++ compiler is smart enough to count the number of arguments, and thereby figure out which version of the function should be called.

It is also smart enough to look at the type of arguments (int, double, string, etc.) and to pick versions accordingly.

This is called overloading. We have overloaded the name of the function “max”. It is also possible to overload operators; for instance if you define a class of complex numbers, you get to overload the “+” and “*” operators so they do something useful when applied to complex numbers. As another familiar example, in the STL, the iostream class heavily overloads the << and >> operators.

Experts note: It is possible to write a max function that takes arbitrarily many arguments – a so-called variadic function – but we don’t need to get into that at the moment. Variadic functions in C (and C++) are a bit ugly. A cleaner way to take the max of arbitrarily many numbers is presented in section 2.16.

Also note that writing a two-argument max function is a somewhat contrived exercise, because std::max(,) already exists in the library. In contrast, the three-argument max function is genuinely useful, and also serves as a good example of overloading.

In this example, we wrote ::max instead of plain max, to make sure the compiler knows we want our own version of the two-argument max function (not std::max). Writing ::max is not technically necessary here, but it is a good practice, if only because some folks reflexively put "using namespace std" at the top of every file, and we want our code to keep working even if somebody does that.

2.15  Templates

In section 2.14, the max functions worked for integers. Now suppose we want to work with other things, such as long integers, doubles, et cetera.

// Example program : maximum, using templates

#include <iostream>     // for cout

// Two-argument version:
template <class Tp>
const Tp& max(const Tp& a, const Tp& b){
  return (b<a)?a:b;
}

// Three-argument version:
template <class Tp>
const Tp& max(const Tp& a, const Tp& b, const Tp& c){
  return ::max(a, ::max(b, c));
}

int main(){
  using namespace std;
  cout << max(1, 3, 5) << endl;                 // the integer 5
  cout << max(1.11, 3.33, 5.55) << endl;        // the double 5.55
}

max3-template.c

The max function as written makes reference to some indefinite type Tp. The C++ compiler is smart enough to look at how you are using the max function, pick the type Tp that matches what you are doing, and compile the appropriate version(s) of the max function accordingly.

Note that there are other situations where the compiler cannot guess what version of the template to use, so you need to tell it. In particular, when an entire class (not just a function) is templated, you generally have to specify which version you want. As an example, we need to say std::list<int> rather than simply std::list, as in container-example.c and max-list.c.

As a good rule of thumb, you should avoid writing any code twice. If you find yourself starting to write the same chunk code a second time (let alone a third!) you should stop and ask whether it would be possible to write a single chunk that handles the general case. Sometimes this is not possible, but sometimes it is. Commonly, handling the general case is harder than handling a single case ... but not twice as hard, so the generalization pays for itself immediately. Templates are particularly useful in this regard, because they make it easy to take existing code and make it more general.

Now you know what the T stands for in STL.

2.16  Max of an Arbitrarily-Long List

The main program (max-list.c) sets up a list of numbers, and then finds the maximum by calling a function (list-max.h) that can deal with a list of arbitrary length. This is a tremendous generalization over the two-argument and three-argument max functions in max3-example.c and max3-template.c.

This is a somewhat-contrived pedagogical exercise, because std::valarray already provides max() and min() functions. The point is to demonstrate some techniques that may come in handy in other situations.

// Example program : maximum of a std::list

#include <iostream>     // for cout
#include "max-list.h"

using namespace std;
int main(){
  static double foo_set[] = {1.11, 5.55, 2.22, 4.44};
  list<double> foo(foo_set, foo_set + sizeof(foo_set) / sizeof(foo_set[0]));
  foo.push_back(3.33);          // tack on another element
  cout << "The max of foo is: " << max(foo) << endl;
  list<int> bar;
  cout << "The max of bar is: " << max(bar) << endl;
// Nothing from here on will get executed,
// because we don't catch the exception.
  cout << "won't get here" << endl;
}

max-list.c

The first two lines of the main program are a somewhat idiomatic way of initializing a list from a bunch of constants. First we construct a static array. We use the sizeof() function to figure out the number of elements in the array. Then we use the array to initialize the list. There is not, so far as I know, any simpler or more direct way of stuffing multiple constants into a std::list.

Note that we tack on another element (3.33). We could also remove elements if we wanted to. All this is easy to do using the STL list class. The list class is somewhat complex internally, but you don’t need to worry about that. You don’t need to write it or even read it. If you want to use it, all you need to do is read is the documentation ... or find some example code and modify it to do what you want.

Now let’s look at the class definition. Note that we have to deal with a special case, namely the empty list. Throwing an exception is exactly the right thing to do in this case. You could imagine other solutions, such as returning a special value (perhaps -Inf, if we are dealing with doubles ... or the most-negative integer, if we are dealing with integers). On the other hand, the caller would have to check for the special value after calling max, and that would not be one iota easier than checking for a zero-size list before calling! Therefore we just make it a documented requirement to have one or more elements in the list, and we throw an exception if this requirement is violated.

#include <string>
#include <list>

class bad_thing: public std::exception{
  const char* msg;
  virtual const char* what() const throw() {
    return msg;
  }
public:
  bad_thing(const char* _msg)
  : msg(_msg) {}
};

// Function to find the maximum element of a list.
// The list may contain one or more elements.
// We throw an exception if there are zero elements.
//
template <class Tp>
Tp max(const std::list<Tp>& arg) {
  using namespace std;
  if (!arg.size()) throw bad_thing("max of empty list");
  typename list<Tp>::const_iterator ii(arg.begin());
// Initialize the result to the first element.
// This is well known to be the only valid way of doing it:
  Tp rslt(*ii++);
  while(ii != arg.end()) {
    rslt = max(rslt, *ii++);
  }
  return rslt;
}

max-list.h

Note the keyword “typename” in this example. I have no idea why it is required in this situation ... but not required in hundreds of seemingly-similar situations.

Note the somewhat idiomatic use of std::exception in this example. A programmer who is not clever enough to check for zero-sized lists is unlikely to be clever enough to catch the exception, so it is useful to throw some kind of exception that the standard library knows about. It will print a semi-useful message, while terminating the program, as you can see in the following output:

The max of foo is: 5.55
terminate called after throwing an instance of 'bad_thing'
  what():  max of empty list
Aborted

max-list.out

In contrast, if we had thrown an object that did not have a what() method, the message would have been less informative.

Note yet again that we have made the .h file relatively complex internally, so that it is as easy to use as possible. The idea is that you write the .h file once and then use it again and again. You pay the somewhat-high cost of implementing it well only once, and you reap the benefit of using it again and again. This makes sense if the .h file implements a function that is generally useful. (Conversely, if the function is not generally useful, it may not be worth implementing it well.)

2.17  Assembling a List from Disparate Sources

Here is another serious example. The implementation in list-item.h is general-purpose code, used in multiple serious applications. The main program in menu-list.c was written primarily as a test driver, for testing the implementation.

Yet again, I’m not trying to impress you by how complicated the .h file is, but rather how simple the .c files are.

The purpose of list-item.h is to facilitate building one or more lists. The list rooted at menu_root is interesting, because it gets built before the main() program begins. It gets built by the constructors of list_items that are declared outside of any function. It is especially noteworthy that the code in the main program doesn’t have any compiled-in information about these list_items. It doesn’t even know how many of them there are, if any. You can add new list_items without recompiling the main program, indeed without recompiling anything except the file containing the new list_items. You can remove list_items without recompiling anything. (You do need to re-link.)

//////////////////////////////////////
// program to demonstrate use of class list_item
//
using namespace std;
#include <iostream>
#include "list-item.h"

list_item* menu_root(0);
static list_guard whatever(menu_root, "guard");

int main() {
  cout << "* first part of main()" << endl;
  list_item*& menu_head(menu_root->next);
  menu_head->dump();              // show initial state

  { // begining of temporary scope
    list_item kumquat(menu_root, "kumquat");  // add temporary item
    menu_head->dump();             // show new state including temporary item
  } // temporary item goes out of scope now

  menu_head->dump();               // show original state again
  cout << "* second part of main()" << endl;

// Slightly simpler procedures are also available
// when the root itself is a dynamic (local) variable:
  {
    list_item myroot("dynamic");  // create dummy root-item directly
    list_item*& myhead(myroot.next);
    list_item cat(myroot, "cat");
    list_item dog(myroot, "dog");
    list_item bird(&myroot, "bird");
    myhead->dump();          // dump the local list
  }  // myroot, cat, dog, and bird all go out of scope now

  cout << "* third part of main()" << endl;

// Yet another set of procedures is available:
  {
    list_root myptr("game");
    list_item*& myhead(myptr.root->next);
    list_item rock(myptr.root, "rock");
    list_item paper(myptr.root, "paper");
    list_item scissors(myptr.root, "scissors");
    myhead->dump();          // dump the local list
  }  // myptr, rock, paper, and scissors all go out of scope now

  cout << "* end of main()" << endl;
}

menu-list.c

#include "list-item.h"
extern list_item* menu_root;
list_item apple(menu_root, "apple");

menu-list-apple.c

#include "list-item.h"
extern list_item* menu_root;
list_item orange(menu_root, "orange");

list_item banana(menu_root, "banana");

menu-list-orange.c

* first part of main()
===========
kumquat
===========
===========
* second part of main()
bird
dog
cat
===========
* third part of main()
scissors
paper
rock
===========
* end of main()

menu-list.out

You may think that writing code that executes before main() begins is something only a mad scientist would do, and maybe that’s true. The code in list-item.h had to be written very carefully. There’s a lot of stuff you would like to do that you can’t do in this environment. For starters, almost none of the STL is available. But still, that’s not the main point. The point is that the code in e.g. menu-list-orange.c could hardly be simpler. The effort per menu_item to add another item to the menu is about as small as it possibly could be. Being able to build lists like this is seriously useful.

This example illustrates the advantage of modular code. We can add a module (such as menu-list-apple.c) without worrying about how it interacts with other modules. The principle of modularity is neither entirely different nor entirely the same as the black-box principle mentioned in section 2.6.

FWIW, note that the actual code in list-item.h is only about 30% of the file; the other 70% is comments.

To make this truly useful, you would probably want to use inheritance aka derived classes to attach some useful methods to each menu_item ... but that is a topic for another day. For now, suffice it to say that this can be done without changing a single line in list-item.h.

#include <string>
#include <iostream>

// Class to construct a list ... even if the list-items
// are spread across multiple source files, and even if
// the list needs to be constructed before main() begins.
// See menu-list.c and menu-list-orange.c for examples
// of usage.

// Principles of operation:  For list_item instances
// that are declared outside of any function, the
// rootptr should be declared as
//      list_item* my_root_ptr(0);
// where we rely on the fact that scalar types (including
// pointers) are initialized _before_ things that require
// constructors are initialized.  That is, we need the
// rootptr to be initialized very early.
//
// To say the same thing another way, we cannot use an
// instance of std::list, because the list has to be
// initialized before it can be used, and we have no
// control over the order in which constructors will be
// called, for things declared outside of any function.
//
// In this scenario, an instance of class list_guard
// should also be declared, outside of any function,
// preferably right after the rootptr is declared.
// This guarantees that rootptr will always be a valid
// pointer, and rootptr->next will safely evaluate to
// zero (when the list is empty) or to a pointer to the
// first element of the list (when that exists).
//
// Also: the list_guard destructor will clean up the dummy
// root-item if necessary.  This upholds the rule that a
// "new" in a constructor should be matched by a "delete"
// in the corresponding destructor ... and indeed compensates
// for the fact that this rule is /not/ upheld by the
// list_item constructor.
//
// Initialization of the rootptr cannot be built into
// the constructor for the ordinary list item.  The whole
// point of the list_guard class is to cope with the case
// where there /aren't/ any list_item constructors, i.e.
// the empty list.
//
// After initialization, rootptr does not point to the
// first "real" item of the list.  Instead it points to
// a dummy root-item, which is an instance of list_item,
// and that in turn has a pointer to the first real
// (non-dummy) item in the list, if any.  The rationale
// is simple:  We want every non-dummy item to have a
// parent (of type list_item) that can be cleanly updated
// when the item is destructed.  Updating the rootptr
// itself would not be nearly so clean.
//
// In contrast, for instances of list_item that are declared
// within some function, the order of initialization is
// under control, so the dummy root-item can be declared
// directly and then used as the root of the list, with
// no need for a root-pointer.

class list_item{
public:
  list_item* prev;      // conventional double-linked list
  list_item* next;      // ditto
  std::string name;

  void attach(list_item& root){
    prev = &root;       // we always add ourself at the head
    next = prev->next;

    prev->next = this;          // tell our parent about us
    if(next) next->prev = this; // tell our kid about us
  }

// Normal constructor #1, for attaching via a root-pointer
// that may need initializing:
  list_item(list_item*& rootptr, const std::string& _name)
  : name(_name)
  {
    if (!rootptr) {
      rootptr = new list_item(_name);
    }                   // rootptr is now guaranteed valid
    attach(*rootptr);
  }

// Normal constructor #2, for attaching to an existing dummy root-item:
  list_item(list_item& root, const std::string& _name)
  : name(_name)
  {
    attach(root);
  }

// Similar to the above:
// Rarely-used constructor, for attaching via a root-pointer
// that has already been initialized, perhaps by taking the
// address of an existing dummy root-item:
  list_item(list_item* const& rootptr, const std::string& _name)
  : name(_name)
  {
    attach(*rootptr);
  }

// Special constructor for creating a dummy root-item.
// Must not be used outside of a function;  use
//   list_item* rootptr(0) and list_guard ....
// for lists declared outside of any function.
  list_item(const std::string _name)
  : prev(0),
    next(0),
    name("dummy: root of list: " + _name) {}

  void dump (const int skip = 0) const {
    const list_item* item(this);
    for (int ii = 0; ii < skip; ii++) {
      if (item) item = item->next;
    }
    while (item) {
      std::cout << item->name << std::endl;
      item = (list_item*)item->next;
    }
    std::cout << "===========" << std::endl;
  }

// Destructor:
  ~list_item(){
#ifdef DEBUG_LIST_ITEM
    using namespace std;
    cout << "   Destructor: " << name << endl;
#endif
    if (next) next->prev = prev;
    if (prev) prev->next = next;
  }
};


// Special class used mainly for the side effects of
// its constructor and destructor, namely to initialize
// rootptr (if necessary) to make sure it points to a
// valid dummy root-item ... and conversely to delete
// the dummy root-item when the time comes.
//
// Normally every time you declare a rootptr you declare
// a list_guard to watch over it.
//
class list_guard{
  list_item** ptrptr;
public:
  list_guard(list_item*& rootptr, const std::string _name)
    : ptrptr(&rootptr)
  {
    if (!rootptr) {
      rootptr = new list_item(_name);
    }
  }

  ~list_guard() {
    if (*ptrptr) {
      delete *ptrptr;
      *ptrptr = 0;
    }
  }
};

// Use this within a function to create a root-pointer
// with a built-in guard.
// That is, we automagically delete the dummy root-item
// when we go out of scope.
//
// You must *not* use this for any lists that get constructed
// before main() begins.  Use plain list_item* and list_guard
// instead.  See the Principles of Operation above.
//
// I don't know whether this is more elegant or less elegant
// than just creating your own dummy root-item and using it
// directly.  (Outside of any function you can't do that,
// either.)  The advantage is that the list_root::root can
// be used in exactly the same ways as a guarded list_item*.
// The disadvantage is that it creates a pointer variable
// that wouldn't otherwise be needed.

class list_root {
public:
  list_item* root;

  list_root(const std::string& _name = "whatever")
  : root(new list_item(_name))
  {}

  ~list_root() {
    if (root) delete root;
  }
};

list-item.h

3  Discussion

3.1  Why Bother with C++?

You may be thinking that all the examples in section 2 are too complicated. You may be wishing for an ultra-simple example that shows why using C++ is useful. In fact, though, in ultra-simple cases C++ is not better. It’s not worse, but it’s not better.

There is absolutely nothing that you can do in C++ that you could not also do in plain C, if you are willing to put enough effort into the plain C. This should be obvious from the fact that you can write a C++ compiler that just translates C++ into C (and then compiles the C). The world’s first C++ compiler (called cfront) did exactly this.

For example, in C++ you could write a function that takes a single argument, namely a class with 17 methods and 21 member variables. In plain C, you could use a struct containing all the member variables plus pointers to the appropriate functions. So far, we have not seen much difference. The difference becomes apparent when you realize that the C++ compiler can do a tremendous amount of type-checking. This makes the code far more reliable, because all sorts of common errors can be detected at compile-time.

For example, if you have many, many classes such as cat, dog, squirrel, et cetera, you don’t want to accidentally call a dog-specific method on squirrel-specific data.

Similarly, if you want to concatenate two strings, and they will always be the same two strings, you can perfectly well do that using plain C and the strlib functions. However, if there are many strings and they will be different each time the program is run, experience shows that ordinary programmers cannot be trusted to write all the code necessary to keep track of the details, such as the string storage requirements. In nontrivial cases, it is much easier and much safer to let the C++ compiler keep track of the details.

3.2  Derived Classes

Note the distinction:

4  References

1.
John Denker,
“Suggestions for Writing Good Software”
www.av8n.com/computer/htm/good-software.htm

2.
John Burkardt,
“BRENT – Algorithms for Minimization Without Derivatives”
http://people.sc.fsu.edu/~jburkardt/cpp_src/brent/brent.html

1
In C++, the only difference between struct and class is that struct declares a class where all the members are public (unless the private keyword is used at some point), whereas the class keyword makes all the members private (unless the public keyword is used at some point).
2
In C++, if you happen to have a class where there are no methods, and all the data-members are public, that is informally called a POD-struct (plain old data structure). In plain C, the class keyword is not implemented, there are no private members, and there are no methods, so every struct is perforce a POD-struct.
[Contents]

Copyright © 2011 jsd