A Template Programmer's Struggles Revisited

Overload 61 included a couple of lengthy articles (Heinzmann] and [Heinzmann-]) which demonstrated how difficult it is to undertake a small, realistic and well defined programming task using function templates and C++. The afterwords of the authors and of the editor of Overload suggested that C++ is too difficult to use.

The solution in the second article does indeed look verbose. Surely, I said to myself, there must be a better way. I wondered what I would have done if I had been faced with the same task.

A lookup table.

My initial reaction is to just use std::map unless there is a good reason not to.

Is there a good reason not to? In this case, yes, because it is also required to hold the table in non-volatile memory, which requires the table to be POD (a C-style array of a C-style struct). std::map does not fulfil this requirement.

We need something that behaves like std::map but is implemented with POD.

Let's borrow the bits of the interface we need from std::map:

namespace rom {
  template<typename T1, typename T2>
  struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
  };

  template<typename Key, typename T,
          typename Cmp = std::less<Key> >
  class map {
  public:
    typedef Key key_type;
    typedef T mapped_type;
    typedef pair<const Key, T> value_type;
    typedef Cmp key_compare;
  };
}

I'm sure if I had been doing this from scratch I would have tried to use std::pair, then realised like Stefan that this wouldn't work because it is not an aggregate. However I've used the hindsight I gained from reading his article to go straight to using a pair that supports aggregate initialisation.

Our new rom::map does not need a template parameter for allocation, since the whole point of it is that it uses a statically initialised array, so we discard that parameter of std::map.

The constructor of rom::map seems to be the obvious way to associate it with an array. The constructor would also be an ideal place to check that the array is sorted. Stefan used template argument deduction to obtain the size of the array but, as this fails on some compilers, I pass the size as a separate argument. The arguments of the constructor suggest the member variables the class requires:

template<typename Key, typename T,
         typename Cmp = std::less<Key> >
class map {
public:
  typedef pair<const Key, T> value_type;
  map(const value_type array[],
      unsigned int array_size)
        : values(array), size(array_size) {}
private:
  const value_type * const values;
  unsigned int size;
};

The only member function we need is find(). For std::map this returns an iterator, but we can simply return a value because we are supplying a default value to use if none can be found. At this stage I want to verify that the interface is sound, so to get something that I can try out as early as possible I implement find() with a linear search rather than a more efficient binary search:

template<typename Key, typename T,
         typename Cmp = std::less<Key> >
class map {
public:
  const T &find(const Key &k, const T &def) const {
    for(unsigned int n = 0; n != size; ++n) {
      if(!Cmp()(k, values[n].first)
         && !Cmp()(values[n].first, k)) {
        return values[n].second;
      }
    }
    return def;
  }
};

Let's try it out. We know that the rom::map should behave like a std::map, so we write a utility to populate a std::map with the same table as a rom::map and check that every entry in the std::map can be found in the rom::map. Additionally we check that if an entry cannot be found in the rom::map the supplied default value is returned. (For brevity, I have implemented my tests with plain C asserts rather than use a unit test framework.)

namespace {
typedef rom::map<unsigned int,
                 const char *> RomLookup;

RomLookup::value_type table[] = {
  {0,"Ok"},
  {6,"Minor glitch in self-destruction module"},
  {13,"Error logging printer out of paper"},
  {101,"Emergency cooling system inoperable"},
  {2349,"Dangerous substances released"},
  {32767,"Game over, you lost"}
};
typedef std::map<RomLookup::key_type,
           RomLookup::mapped_type> StdLookup;
void PopulateStdLookup(
         const RomLookup::value_type table[],
         unsigned int table_size,
         StdLookup &stdLookup) {
  for(unsigned int n=0; n != table_size; ++n) {
    stdLookup[table[n].first] = table[n].second;
  }
}

class CheckFind {
public:
  CheckFind(const RomLookup &romLookup,
            const RomLookup::mapped_type
                               &def_value)
       : lookup(romLookup), def(def_value) {}
  void operator()(const StdLookup::value_type
                              &value) const {
    assert(lookup.find(value.first, def)
          == value.second);
  }
private:
  const RomLookup &lookup;
  const RomLookup::mapped_type &def;
};
}
 
int main(int, char**) {
  const unsigned int table_size
            = sizeof(table)/sizeof(table[0]);
  RomLookup romLookup(table, table_size);
  StdLookup stdLookup;
  PopulateStdLookup(table, table_size,
                    stdLookup);
  std::for_each(stdLookup.begin(),
                stdLookup.end(),
                CheckFind(romLookup, 0));
  assert(romLookup.find(1, 0) == 0);
  return 0;
}

This is all fine. We have a usable interface and set of test cases. Note that I didn't need to do any type casting to pass 0 as the default argument to romLookup.find(), it just compiled straight away with no problems.

Now we need to refine find() to use a binary search, which requires std::lower_bound. My first attempt is:

template<typename Key, typename T,
         typename Cmp = std::less<Key> >
class map {
public:
  const T &find(const Key &k, const T &def) const {
    const value_type *value = std::lower_bound(
             values, values+size, k, Cmp());
    if(value == values+size
       || Cmp()(k, value->first)) {
      return def;
    }
    else {
      return value->second;
    }
  }
};

This gives me a compiler error saying it can't pass value_types to less<unsigned int>. It isn't too hard to work out that this is because I am passing a key_type comparison function to std::lower_bound which attempts to use it to compare value_types. So in the private part of the map I write a function object that adapts the key comparison function to work with value_types. Normally I do not bother to derive private function objects from std::unary_function or std::binary_function, but as this raised problems in the original article I did so on this occasion:

template<typename Key, typename T,
         typename Cmp = std::less<Key> >
class map {
public:
  const T &find(const Key &k,
                const T &def) const {
    const value_type *value =
         std::lower_bound(values, values+size,
                           k, value_compare());
    // rest of member function as before
  }
private:
  struct value_compare
    : public std::binary_function<value_type,
                           value_type, bool> {
    bool operator()(const value_type &v1,
                 const value_type &v2) const {
      return Cmp()(v1.first, v2.first);
    }
  };
};

Still a compiler error, this time that I am trying to pass an unsigned int as an argument to value_compare::operator(). Again, it is not too difficult to spot that I am passing a key_type as the third argument of std::lower_bound where a value_type is required. We use the elegant fix employed in [Heinzmann-]:

template<typename Key, typename T,
         typename Cmp = std::less<Key> >
class map {
public:
  const T &find(const Key &k,
                const T &def) const {
    const value_type key = { k };
    const value_type *value =
       std::lower_bound(values, values+size,
                        key, value_compare());
    // rest of member function as before
  }
};

Now everything compiles cleanly (including the use of std::binary_function) and the test code also executes successfully.

We have reached a solution that works. We reached it by a less painful route, with less code and with simpler code. But does this solution have some disadvantages the original did not have?

Most obviously, it does not provide a mechanism that can be used equally well for any map-like container: it is a less general solution. I'm not convinced this is a disadvantage. "Why restrict ourselves to arrays?" asks [Heinzmann-]. I'm tempted to reply "Why not?"

Another difference is that our rom::maps have two member variables that take up memory which the original solution did not. This may be insignificant, but since the context of the task is an embedded system it is conceivable that we may be required to conserve memory. If this is the case there is a simple refactoring that can be applied to the rom::map. The array can be passed directly to the find() member function, which can be made static, and the constructor and member variables removed. (If we had implemented a check that the array is sorted in the constructor, that code could also be refactored into a static member function).

At this stage, if I had a smart enough compiler, I could try to use template argument deduction to determine the array size rather than pass it as an explicit parameter. Personally, I don't think I would go to that trouble.

If we find it necessary to eliminate the constructor and member variables, leaving only a static member function, the next obvious refactoring is to turn it into a standalone function. But if we do that, we run into the problems experienced in [Heinzmann]. So we are faced with a choice: proceed with the refactoring and introduce the necessary traits class as in [Heinzmann-], or abandon the refactoring and stick with what we have. I'd go for the latter. The syntax is a little less elegant, but overall it's simpler.

Why did things run more smoothly with the approach I took? It is because my solution uses a class template rather than a function template. It therefore does much less template argument deduction, which avoids a whole host of problems.

This suggests a design guideline: if you are struggling to implement a function template, consider re-implementing it as a class template (as an alternative to introducing traits).

Chris Main

Is C++ too difficult? I'm not so sure. I think I've demonstrated that the code which provoked comments to that effect was unnecessarily complicated. I think I did so not because I am a C++ expert but because I followed strategies that are generally useful when programming: follow the pattern of a known working solution to a similar problem (in this case std::map), work incrementally towards the solution, try to keep things as simple as possible.

How would the problem be solved in other programming languages? In C you could use the standard library bsearch(). I have used it, but it is quite fiddly to get the casting to and from void * right, so in my experience it is not significantly easier to use than C++. What other languages could be used?