Standard C++

I have vague recollections of trying to track down a copy of the C++ standard several years ago. I went to the ISO's web site, went into sticker shock at the several hundred dollars they wanted for a CD or PDF, and soon forgot about it.

Until I came across this discussion on Stack Overflow, I didn't realize that the C++ standard was so easy to acquire. PDF versions are available for $30 from ANSI's web site and from Techstreet. If even $30 is too much, or if you want to read about cutting-edge C++ stuff, then you can download the C++0x draft standard from the ISO committee's web site for free, with the caveat that it is "incomplet and incorrekt." Copies of the C++98 and/or C++03 draft standards are also archived in various places around the web.

With the wealth of C++ information available on the web and in print, there are often more convenient resources than the standard, but topics such as the order in which integral types are promoted seem difficult to come by on the web, and for particularly arcane issues of C++ style, it's nice to have a more disciplined approach than "munging syntax until it works" and a more authoritative source than "whatever my compiler accepts." The C++ standard acts as a grammar textbook for the C++ language, and although the standard isn't exactly thrilling reading, its dialect of standardese isn't nearly as difficult to read as you might think.

Linguists will tell you that a natural language's grammar is descriptive, not prescriptive. In other words, English grammar isn't the list of rules that you find in a high school textbook, it's a description of how people actually talk and write, complete with colloquialisms, various "ungrammatical" speech, and, in the 21st century, emoticons and online acronyms. There's some merit to taking a similar approach with programming languages. Using a programming language effectively requires more than just knowing the language's formal constructs; it involves using the language's community's idioms (using and combining constructs to get things done, as in C++'s RAII) and taboos (aspects of the language that are too obscure or problematic to rely upon, like C++'s exception specifications or the relative precedence of || and &&). Moreover, what ultimately matters is how a language can be used in the field rather than how the standard says a language can be used; it's a small comfort to read that your template metaprogramming technique or C99 construct is permitted by the standard if your target platform rejects it.

The rules of grammar (in the prescriptive high school sense rather than the descriptive linguistic sense) are generally worth following, to promote clarity of communication, but skilled writers know that it's sometimes effective to break these rules, whether to create a particular effect (such as a conversational, informal tone) or because the rules are outdated or never made much sense in the first place (such as the prohibition against split infinitives). Similarly, there are times where it may be beneficial to break the C++ standard. Imperfect C++ gives two examples of this (with caveats as to their use): the "friendly template" technique (declaring a template parameter to be a friend of the template class; technically illegal but very widely supported) and nested or local functors (potentially very useful but rejected by almost all compilers). C99 features such as variable length arrays (supported by GCC) and variadic macros also fall in this category. Obviously, breaking the standard should only be done with full awareness of the consequences (primarily damage to future portability) and is usually a bad idea, but not always. For example, code using variadic macros completely violates the C++ standard, but it's likely much more portable than some of the more advanced uses of templates.

C++ might deserve mention for even having a (well-discussed, reasonably well-implemented) standard. Perl, for example, lacks any official standard; instead, its implementation and test suite serve as the de facto standard, and the need to remedy this may be part of the reason for Perl 6's delays. JavaScript has an international standard and yet continues to suffer from browser compatibility issues, not just in the DOM and event models, but in the language core:

var cmd, valve;
// Perl- or Python-style assignment to an array: legal in Firefox, but 
// rejected by Chrome
[ , cmd, valve ] = /(\w+)_valve_(\d+)/.exec(this.id);

// A C-style trailing comma in an initializer list: creates an array 
// of length 3 in Firefox, but IE creates an array of length 4 with 
// undefined as its last element
var fields = [ 'street', 'city', 'zip', ]

Fred Brooks has more to say about the risks of using an implementation as a standard in chapter 6 of The Mythical Man-Month, but by this point we're pretty far afield of the C++ standard. So, if you're a C++ developer, go download or buy yourself a copy and give it a look.

Comparing Version Numbers

Comparing version numbers is one of those operations that seems like it ought to be simple but can have a fair bit of complexity under the surface. How would you write an algorithm that gives the correct result for all of the following?

• 2.10 comes after 2.9
• 2.11-beta comes after 2.11-alpha
• 2.11 comes after 2.11-beta
• 7 comes after 2003
• the revision that was checked in on 1/30/2009 and never given a version number comes after the revision that was checked in on 8/1/2008 and never given a version number

The Debian Project deals with more version numbers than anyone - over 30,000 packages over more than fifteen years, each of which must be separately versioned and tracked for upgrade and depedency purposes - so it's no surprise that they've developed a policy and algorithm that can handle all of the above cases. Debian's algorithm neatly handles cases like 2.9 versus 2.10, and it has two main additions over other version comparison algorithms: it states that ~ is sorted before anything, even the empty string, so 2.11~beta comes before 2.11, and it permits the addition of an epoch to "reset" version numbers, so 2003, which has the default epoch of 0, comes before 1:7, which has an epoch of 1. All of this makes Debian's algorithm a good approach for comparing version numbers even if you're not a Debian package maintainer.

I recently needed to compare some Debian version numbers, but the only C or C++ implementations of this algorithm that I could find were GPL'ed, and my target environment wouldn't permit me to simply shell out to dpkg --compare-versions, so I wrote my own implementation. Here it is, under the public domain. Note that, although it's written as a C++ class, the method bodies are in C style to make it easier to reuse them in a non-C++ project.

DebVersion.h:

#ifndef DEBVERSIONH
#define DEBVERSIONH

#include <stdlib.h>
#include <iostream>
#include <boost/operators.hpp>

class DebVersion : public boost::totally_ordered<DebVersion> {
public:
  DebVersion() : mEpoch(0), mUpstream(NULL), mRevision(NULL) {}
  DebVersion(const DebVersion& other) { *this = other; }
  explicit DebVersion(const char *version);
  ~DebVersion();

  int Epoch() const { return mEpoch; }
  const char *Upstream() const { return mUpstream; }
  const char *Revision() const { return mRevision; }

  void Epoch(int new_epoch) { mEpoch = new_epoch; }
  void Upstream(const char *new_upstream) { free(mUpstream); mUpstream = strdup(new_upstream); }
  void Revision(const char *new_revision) { free(mRevision); mRevision = strdup(new_revision); }
  void ClearRevision() { Revision("0"); }

  DebVersion& operator=(const DebVersion& other);
  bool operator<(const DebVersion& other) const;
  bool operator==(const DebVersion& other) const;

protected:
  int mEpoch;
  char *mUpstream;
  char *mRevision;

  static int CompareComponent(const char *a, const char *b);
};

inline DebVersion::~DebVersion()
{
  free(mUpstream);
  free(mRevision);
}

inline bool DebVersion::operator==(const DebVersion& other) const
{
  return Epoch() == other.Epoch()
    && strcmp(Upstream(), other.Upstream()) == 0
    && strcmp(Revision(), other.Revision()) == 0;
}

inline DebVersion& DebVersion::operator=(const DebVersion& other)
{
  mEpoch = other.Epoch();
  mUpstream = strdup(other.Upstream());
  mRevision = strdup(other.Revision());
  return *this;
}

void operator<<(std::ostream& o, const DebVersion& ver);

#endif

DebVersion.cpp:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>

#include "DebVersion.h"

void operator<<(std::ostream& o, const DebVersion& ver)
{
  if (ver.Epoch() != 0) {
    o << ver.Epoch() << ":";
  }
  o << ver.Upstream();
  if (0 != strcmp(ver.Revision(), "0")) {
    o << "-" << ver.Revision();
  }
}

DebVersion::DebVersion(const char *version)
{
  // Extract epoch.  The Debian Policy Manual says that epoch must be
  // numeric, so atoi is safe.
  const char *epoch_end = strchr(version, ':');
  if (epoch_end != NULL) {
    mEpoch = atoi(version);
  } else {
    mEpoch = 0;
  }

  const char *upstream_start;
  if (epoch_end) {
    upstream_start = epoch_end + 1;
  } else {
    upstream_start = version;
  }

  const char *upstream_end = strrchr(upstream_start, '-');
  size_t upstream_size;
  if (upstream_end == NULL) {
    upstream_size = strlen(upstream_start);
  } else {
    upstream_size = upstream_end - upstream_start;
  }

  mUpstream = (char*) malloc(upstream_size + 1);
  strncpy(mUpstream, upstream_start, upstream_size);
  mUpstream[upstream_size] = '\0';

  if (upstream_end == NULL) {
    mRevision = strdup("0");
  } else {
    mRevision = strdup(upstream_end + 1);
  }
}

/**Compare two components of a Debian-style version.  Return -1, 0, or 1
 * if a is less than, equal to, or greater than b, respectively.
 */
int DebVersion::CompareComponent(const char *a, const char *b)
{
  while (*a && *b) {

    while (*a && *b && !isdigit(*a) && !isdigit(*b)) {
      if (*a != *b) {
        if (*a == '~') return -1;
        if (*b == '~') return 1;
        return *a < *b ? -1 : 1;
      }
      a++;
      b++;
    }
    if (*a && *b && (!isdigit(*a) || !isdigit(*b))) {
      if (*a == '~') return -1;
      if (*b == '~') return 1;
      return isdigit(*a) ? -1 : 1;
    }

    char *next_a, *next_b;
    long int num_a = strtol(a, &next_a, 10);
    long int num_b = strtol(b, &next_b, 10);
    if (num_a != num_b) {
      return num_a < num_b ? -1 : 1;
    }
    a = next_a;
    b = next_b;

  }
  if (!*a && !*b) {
    return 0;
  } else if (*a) {
    return *a == '~' ? -1 : 1;
  } else {
    return *b == '~' ? 1 : -1;
  }
}

bool DebVersion::operator<(const DebVersion& other) const
{
  if (Epoch() != other.Epoch()) {
    return Epoch() < other.Epoch();
  }

  int result = CompareComponent(Upstream(), other.Upstream());
  if (result) {
    return -1 == result;
  }

  return -1 == CompareComponent(Revision(), other.Revision());
}

And, because no code is complete without some good unit tests, here's DebVersionTest.cpp, using the excellent Google Test framework:

#include <gtest/gtest.h>

#include "DebVersion.h"

TEST(DebVersionTest, ParsesUpstreamOnly)
{
  DebVersion v("1");
  EXPECT_EQ(0, v.Epoch());
  EXPECT_STREQ("1", v.Upstream());
  EXPECT_STREQ("0", v.Revision());
}

TEST(DebVersionTest, ParsesEpochs)
{
  DebVersion v("1:2.0.1");
  EXPECT_EQ(1, v.Epoch());
  EXPECT_STREQ("2.0.1", v.Upstream());
  EXPECT_STREQ("0", v.Revision());
}

TEST(DebVersionTest, ParsesRevisions)
{
  DebVersion v("10:4.0.1~alpha-4-5");
  EXPECT_EQ(10, v.Epoch());
  EXPECT_STREQ("4.0.1~alpha-4", v.Upstream());
  EXPECT_STREQ("5", v.Revision());
}

TEST(DebVersionTest, ComparesNumbers)
{
  EXPECT_LT(DebVersion("1"), DebVersion("2"));
  EXPECT_EQ(DebVersion("10"), DebVersion("10"));
  EXPECT_LT(DebVersion("9"), DebVersion("10"));
  EXPECT_GT(DebVersion("10"), DebVersion("9"));
}

TEST(DebVersionTest, ComparesEpochs)
{
  EXPECT_GT(DebVersion("2:1"), DebVersion("1:2"));
  EXPECT_LT(DebVersion("10"), DebVersion("1:2"));
}

TEST(DebVersionTest, ComparesAlphas)
{
  EXPECT_LT(DebVersion("alpha"), DebVersion("beta"));
  EXPECT_LT(DebVersion("alpha1"), DebVersion("alpha2"));
  EXPECT_GT(DebVersion("alpha10"), DebVersion("alpha2"));
}

TEST(DebVersionTest, ComparesTildes)
{
  EXPECT_LT(DebVersion("3.0~beta1"), DebVersion("3.0"));
  EXPECT_GT(DebVersion("3.0~beta"), DebVersion("3.0~~prebeta"));
  EXPECT_LT(DebVersion("3.0~beta4"), DebVersion("3.0~rc1"));
}

TEST(DebVersionTest, ComparesRevisions)
{
  EXPECT_LT(DebVersion("3.0-2"), DebVersion("3.0-10"));
}

Minding Your Manners

I recently went to a book sale where shoppers could browse countless bins of completely disorganized books and buy as many as could fit in a box for $30. I quickly learned that the only way to navigate a sale like this was to disregard my traditional short list of topics and authors that I follow, grab anything remotely interesting, and sort it out later. One of my finds was New Rules @ Work, by Barbara Pachter and Ellen Coleman.

The book's subtitle sums up its contents: "79 Etiquette Tips, Tools, and Techniques to Get Ahead and Stay Ahead." It covers topics such as greeting people, navigating social gatherings, corporate attire, and communications skills (whether face-to-face or by phone or email). For me, at least, the tips presented are an odd mix of the very obvious (stand up when shaking a guest's hand), the rather irrelevant (how to sample wine at restaurants fancier than my humble software developer's expense account would cover), and the desperately needed (how to mingle at a social gathering). Even though many of the suggestions fell in the first category for me, the book is a quick read and is interspersed with plenty of amusing anecdotes about various etiquette blunders to keep it interesting.

All of this has little to do with coding, but there's a lot more to software development than just coding:

• gathering requirements
• managing the infrastructure (version control, build system, continuous integration)
• documentation (developer docs if not end-user docs)
• testing
• release management and deployment
• customer support (possibly indirectly, depending on the size of your organization)

And there's a lot more to a career in software development than just software development:

• teamwork
• networking (the social kind, not the TCP/IP kind)
• time management (Getting Things Done if you like an overarching system, Time Management for System Administrators or Johanna Rothman's articles if you prefer individual pieces of advice)
• stress management (avoid burnout; remember that your job is just a job; take a vacation and don't check your email)
• continuing education
• business acumen

And, of course, workplace etiquette. New Rules @ Work emphasizes the effects that etiquette (or the lack thereof) can have on your career, and it seems to present etiquette primarily as a tool for advancing your career. Considering the book's focus, this is probably okay, but it seems a bit utilitarian to me. I've always preferred Brendan Frasier's character's explanation in the movie Blast from the Past:

Good manners are just a way of showing other people we have respect for them... A lady or a gentleman is someone who always tries to make sure the people around him or her are as comfortable as possible.

Etiquette is a way to serve others.

As software developers, it can be our tendency to focus too much on the technology. We want to try out the latest development tools or techniques even if they're not best for the job; we pursue certain standards or ideals even if they don't make business sense; we see a technical challenge and try to solve it even if it's not the right problem to solve. As a remedy to this, we're told to focus on delivering business value. This is good advice, but it raises the question, why pursue business value? The standard answer is "profits," but as Max De Pree says, "Profits are like breathing. Breathing is not the goal of life, but it is pretty good evidence of whether or not you are alive." The goal of business - the reason that business can exist, the way that business makes profits - is service: meeting people's needs by offering goods or services.

There's a story that, during the initial development of the Apple Macintosh, Steve Jobs complained that it booted too slowly. He argued that shaving ten seconds off of the boot time, multiplied by millions of users, would save several lifetimes. My software may never save a lifetime, but every feature that I add, every bug that I fix, every UI interaction that I streamline means that users can do their jobs a bit faster, a bit easier, with a bit less stress.

Software development is about serving users. Etiquette is just a way to do in the small what our businesses and our careers do in the large.

Memberwise Visitation

This code was the original impetus for my postings on template template parameters and multi-paradigm programming, but those didactic digressions grew into articles of their own. I don't know how helpful such digressions are - I'm learning that truly effective teaching requires the patience to develop good examples and an awareness of where your target audience is, and I'm not sure that I possess either, at least in this format - but at least they're out of the way...

C++'s object-oriented and generic programming each offer a lot of capability, but they can be combined for even more power. Consider, for example, the following code:

#include <iostream>
#include <boost/ptr_container/ptr_vector.hpp>
#include <boost/shared_ptr.hpp>

template <typename Class>
class ClassVisitor {
public:

  class MemberVisitor {
  public:
    virtual ~MemberVisitor() {}
    virtual void Visit(Class& instance) = 0;
  };

  template <typename T>
  class MemberVisitorImpl : public MemberVisitor {
  public:
    MemberVisitorImpl(T Class::*ptr) : mMember(ptr) {}
    void Visit(Class& instance) {
      // Sample visitor method.  You can define whatever member-specific
      // behavior you want.
      std::cout << instance.*mMember << ' ';
    }
  private:
    T Class::*mMember;
  };

  template <typename T>
  ClassVisitor& Declare(T Class::*ptr);

  void Visit(Class& instance);

private:
  typedef boost::ptr_vector<MemberVisitor> MemberVisitorList;
  MemberVisitorList mMemberVisitors;
};

template <typename Class>
template <typename T>
ClassVisitor<Class>& ClassVisitor<Class>::Declare(T Class::*ptr)
{
  mMemberVisitors.push_back(new MemberVisitorImpl<T>(ptr));
  return *this; // supports a fluent interface
}

template <typename Class>
void ClassVisitor<Class>::Visit(Class& instance)
{
  for (typename MemberVisitorList::iterator i = mMemberVisitors.begin();
       i != mMemberVisitors.end();
       i++) {
    i->Visit(instance);
  }
}

struct Annotation {
  const char *mMessage;
  int mX;
  int mY;
};

int main(int argc, char *argv[])
{
  ClassVisitor<Annotation> def;
  def.Declare(&Annotation::Message)
    .Declare(&Annotation::X)
 .Declare(&Annotation::Y);

  Annotation annotation;
  annotation.Message = "Note this";
  annotation.X = 10;
  annotation.Y = 20;
  def.Visit(annotation);
  return 0;
}

This code offers one approach to visiting each member of a class with a client-specified operation. Generic programming is used MemberVisitor subclasses handle members of any type, while OOP's polymorphism is used to let different types be handled at runtime. (Normally templates can only be applied at compile-time.) The example code simply dumps member variables' contents to screen and ends up being merely an overcomplicated operator<<(std::ostream&, const Annotation&), but MemberVisitor instances can contain additional information about their member variables and can define more than one Visit operation. In my current code's memberwise visitor implementation:

• MemberVisitor instances contain member variables' descriptions, defaults, and constraints (minimum, maximum, etc.).
• Copy constructors, operator=, and default constructors can be implemented by iterating over the list of member variables and default values that the MemberVisitor list provides.
• MemberVisitors' information is shared by visit operations: per-member serialization and unserialization use members' types and formats, constraints are used during unserialization to check for corrupt archives and at runtime to check design by contract-style invariants, member descriptions and defaults can be used to report errors and reset to a known good state if a corrupt archive is encountered during deserialization, and the class can easily be dumped one member at a time to a human-readable format for inspection and debugging.
• A second set of visitors handles binding members to a form's fields: loading form fields from a class instance, checking whether a form is dirty, validating a form, and saving form fields to a class instance are each implemented as Visit operations, and information such as MemberVisitor constraints can be used when a form is loaded to configure the UI widgets and before a form is saved to check for validity.

The result is that the MemberVisitors offer some introspection/reflection capability for C++ as well as something like a database schema for each class, similar to what would be provided by most frameworks' database support, but not tied in to a database backend. This multiparadigm (OO-and-generic) combination is only one approach to implementing this functionality; other implementations could use more of a pure template metaprogramming approach or could rely on preprocessor macros, code generation via an external tool, or reflection (via vendor extensions or a third-party library). Each implementation offers its own tradeoffs for complexity, portability (template metaprogramming often runs into compiler bugs; reflection is often vendor-specific), and build system support (in the case of code generation and reflection).

I'm still playing around with different approaches trying to find the best balance of tradeoffs and trying to figure out the best way to take advantage of C++'s multiparadigm support without overcomplicating my code. Are there other examples of code that directly leverages C++'s multiparadigm support? Are there preexisting implementations of this kind of member schema functionality for C++? Would there be any interest in a (cleaned up and open-sourced) member schema library, or is that functionality adequately covered by database libraries? Comments welcome.

A Plethora of Paradigms

paradigm - a pretentious and overused term for a way of thinking (Bjarne Stroustrup, "C++ Glossary")

C++ is frequently described (by Stroustrup and others) as a multi-paradigm programming language, which simply means that it lets you use more than one programming paradigm (such as procedural or object-oriented) and freely switch between or combine paradigms. When I was first introduced to this concept of multi-paradigm programming languages, I thought that it was an incredibly cool trait of C++. Then I read on Wikipedia that the multi-paradigm label can be applied to many more languages than I'd realized and that C++ is a relative lightweight at only three paradigms. (The current record holder, supporting eight Wikipedian-recognized paradigms, is a language I've never heard of called Oz.) However, C++ is probably still the best known example of this sort - there are even ">books about it - and has some of the most practical multi-paradigm applications. A quick overview of C++'s paradigms:

First, of course, is the structural or procedural programming paradigm. Procedural programming's pretty passé, so there's not much to be said here, except to note that C++'s multi-paradigm nature lets you incrementally migrate a procedural app to an OO design.

Second is object-oriented programming. When OO first went mainstream, it was billed as a way of achieving reuse in software development. This doesn't seem to have quite worked out as advertised; creating truly reusable software is hard regardless of the technology you're using, and while OO design is critical to frameworks from MFC to RoR, framework development isn't where most programmers live. Even if its ability to grant reuse per se is limited, modern OO design is quite good at permitting software to be flexible, extensible, and stable in the face of change. "Modern OO design" means taking full advantage of guidelines like the SOLID principles and the Law of Demeter rather than just applying the basic OO techniques of encapsulation, inheritance, and polymorphism. It also includes knowing when to bend those guidelines if circumstances call for it.

C++'s third paradigm is generic programming. I find this to be harder to get a handle on... It's much less commonly taught than object-oriented programming, and although I've worked in C++ for years, it's only been in the last year or two that I've really started to "get" generic programming. (A good test to see how well you understand generic programming is to browse the Boost libraries and see how many of them you think you could, in theory, implement.) Generic programming makes the STL possible; it makes it possible to add features like dimensional analysis, lambda expressions, and callbacks to C++; it's a major component in adding user-defined types of all sorts. It also creates some rather heinous error messages...

However, generic programming isn't just for STL containers and the metaprogramming wizards at Boost; it overlaps with and can partially replace OO techniques. OO programming is known for permitting software components to be loosely coupled (such that they can be freely combined and freely changed, within limits, without the effects of those changes rippling out to other components), through polymorphism and interfaces. Generic programming also permits loose coupling, except that it's handled entirely at compile time, with no runtime overhead, and it doesn't require that objects be related through an inheritance hierarchy. The Curiously Recurring Template Pattern is probably the simplest and best known example of this (and is even referred to as compile-time or static polymorphism), but it's far from the only example. Most of part four, for example, of Imperfect C++ contains different applications of generic programming techniques to simulate what might require inheritance, interfaces, or (C#) extension methods in the OO world.

For even more power, the generic and OO paradigms can be combined. And because C++ is such a flexible language, you're not limited to the "officially supported" paradigms. I've already touched on Boost's support for functional programming; as another example, reflection (which is available through vendor extensions, like C++Builder's or the .NET Framework's and through third party libraries like CERN's Reflex) can also promote flexible, extensible software. Having three different techniques from three different paradigms that can be used individually or in various combinations offers incredible power: power to shoot yourself in the foot by creating an overcomplicated, obtuse rat's nest of code, or power to write robust, extensible software. Now if I could only figure out which category my code falls in...

Things I Didn't Know about C++: Template Template Parameters

Continuing my series on things I didn't know about C++...

I knew about templates, and I knew about parameters to templates, but I did not know about template template parameters, which are useful when dealing with containers and policies and, if nothing else, are worth learning about for having such a "pleasingly repetitious name" (in C++ author Stephen Dewhurst's words).

A template template parameter is simply a template parameter that is itself a template. Dewhurst gives the example of a Stack template that can be customized to use a particular underlying storage container:

template <typename T, template <typename> class Cont>
class Stack;

Stack<int, List> stack_of_ints;

Without template template parameters, the base type (int in this case), which hampers readability at best and could be a source of errors at worst:

template <typename T, typename Cont>
class Stack;

Stack<int, List<int> > stack_of_ints;
Stack<double, List<int> > stack_of_doubles_badly_truncated_to_ints;

Template template parameters can be used anywhere you need to let the caller customize an algorithm or class for a particular container, policy, or similar:

• A stack or other higher-level container can be instantiated using any lower-level container, as in Dewhurst's example.
• A class or function can be customized with a policy template. Andrei Alexandrescu gives an example of this in section 1.5 of Modern C++ Design. (His example is also summarized in this Stack Overflow post.)
• Template template parameters can be used when you need to know both the type of a template and how that template was instantiated, although this comes up less often than you might initially think, because there are often better ways to find the types involved. For example, there's no need to declare template <typename T, template <typename> class Cont> void ProcessContainedObjects(Cont<T>& cont) to let ProcessContainedObjects know what T is when any well-written container will define the Cont::value_type typedef.

Template template parameters are a useful addition to the C++ template programming toolbox, alongside techniques such as partial template specialization, type traits, concepts (also in C++0x), and C++0x's variadic templates (which can be simulated in C++03 to some extent by using default template arguments or by using Boost Preprocessor to create overloads of every arity from 1 through a #define'd limit).

Floating Point Exceptions

As further evidence that floating point math is stranger than you think, consider the following code:

#include <stdio.h>
#include <math.h>
#ifdef __unix__
#define _GNU_SOURCE   // gives us feenableexcept on older gcc's
#define __USE_GNU     // gives us feenableexcept on newer gcc's
#include <fenv.h>
#else
#include <float.h>
#ifndef _EM_OVERFLOW
#define _EM_OVERFLOW EM_OVERFLOW
#endif
#endif

int main(int argc, char **argv)
{
    float a, b;

#ifdef __unix__
    feenableexcept(FE_OVERFLOW);
#else
    _controlfp(0, _EM_OVERFLOW);
#endif

    // gcc will compute these expressions at compile-time (which is
    // actually kinda cool, but it ruins the example) if we just do
    // pow(10.0, 50) and fabs(-13).
    int exponent = 50;
    a = pow(10.0, exponent);

    puts("1e50 is too big for a float, but we got this far,\n"
         "so we must be okay, right?\n");

    b = -13;
    b = fabs(b);

    puts("You'll never see this, because we just got an overflow trying\n"
         "to process a really small number!  How can this be!?!?\n"
         "The world is coming to an end!\n");

    printf("%f %f\n", a, b);

    return 0;
}

By default, at least on x86 systems, floating point exceptions are usually masked ¹, but I've been enabling them as part of my attempt at hairshirt programming or fail fast programming; exceptions such as overflow or division by 0 probably indicate logic errors or algorithmic limitations within the software, and I'd like to know about such problems as soon as possible. That led me to this problem: the pow call generates the exception, but it's not raised until the fabs call, completely confusing the poor programmer. Section 8.6 of the Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 1 (hereafter IASDM) explains how this behavior comes to be:

Because the integer unit and x87 FPU are separate execution units, it is possible for the processor to execute floating-point, integer, and system instructions concurrently. No special programming techniques are required to gain the advantages of concurrent execution. (Floating-point instructions are placed in the instruction stream along with the integer and system instructions.) However, concurrent execution can cause problems for floating-point exception handlers.

Intel's manual provides more details; to summarize, exceptions generated within the FPU are flagged within the FPU's status register but not raised until the CPU executes the next floating point operation. In practice, this should rarely be a problem: if the exception is generated during an operation, it will be raised when the results of the operation are written back to memory, and if the exception is generated when the results are written to memory (due to truncating to a smaller precision), it will be immediately raised as long as you immediately use the result that you just stored. So as long as you're not storing a low-precision value for later use and immediately going on to something else, you ought to avoid the confusing behavior described here.

If you do suspect that something like this is happening, then using C99's fetestexcept functions can help pinpoint the culprit:

    int exponent = 50;
    a = pow(10.0, exponent);

    if (fetestexcept(FE_OVERFLOW)) {
        puts("Warning; doom is impending.");
    }

    b = -13;
    b = fabs(b);

Or you can use C99's fegetenv and the undocumented internals of its fenv_t parameter to examine the entire x87 FPU state - its status word (including pending exceptions), its control word (including the current exception mask), and so on. If your environment doesn't provide an implementation of these fenv.h functions, you can borrow the MinGW runtime's (after adjusting the syntax for your compiler); the implementation is extremely simple (a few lines of assembly per function), and the MinGW runtime is in the public domain.

As an aside, this particular problem would not have happened if the code used doubles throughout instead of floats. Using floats at all is probably a mistake, but I've had some difficulty finding detailed information on the tradeoffs of floats versus doubles. Here's what I've been able to find so far:

• Doubles take up twice as much memory as floats, although the extra memory usage is rarely an issue.
• The x87 FPU always operates on 80-bit long doubles internally, as described in the IASDM (volume 1, section 8.2). For this reason, doubles are usually no slower than floats.
• As a small exception to the previous statement, some builtin functions like pow that offer both float and double versions seem to run faster in their lower-precision versions.
• As a larger exception to the previous statement, the performance SSE is entirely dependent on the size of the data it's operating on, so floats are twice as fast as doubles. On the other hand, if you're doing the kind of graphics, scientific, or gaming development that would most benefit from SSE, you probably already know more than I could tell you about the kinds of performance issues you'll face.
• Floating point precision has a few historical oddities in C and C++; particularly old compilers promoted floats to doubles while doing calculations, and floats are promoted to doubles when given as arguments to variadic functions. (Since pointers can't be promoted, printf and scanf are asymmetrical: printf("%f", f); will work whether f is a float or a double, but scanf("%f", &f); requires that f be a float.)
• The IASDM says (volume 1, section 8.2) that doubles should be used "as a general rule" but notes that "the single-precision format is useful for debugging algorithms, because rounding problems will manifest themselves more quickly in this format" and that 80-bit long doubles can be used "when an application requires the maximum range and precision of the x86 FPU."
• If you're using Microsoft Visual C++ (as of MSVC++ 2008), you can't use 80-bit long doubles. Sorry.

If there are other pros and cons involved in selecting a precision, please let me know. Of course, if you or your predecessor designed your C/C++ code right, all of this is controlled by a single typedef, so it would be very easy to test for yourself. (If you do have the pleasure of working on such well-designed code, feel free to post a comment and gloat over those of us stuck maintaining legacy apps.)

1. Specifically, the x87 FPU disables all floating point exceptions by default, as described in section 8.1.5 of the Intel 64 and IA-32 Software Developer's Manual Volume 1. Microsoft follows suit (unless you set a compiler option), and apparently Linux does too, but CodeGear C++Builder only masks underflow, denormal operand, and inexact result exceptions as part of its startup code.