Title: Letters to the Editor

Dear Editor

I was reading Stefan Heinzmann's paper "The Tale of a Struggling Template Programmer" in June 2004 Overload, and I could not help thinking that a 2 page long code listing cannot possibly be a proper solution to such a simple problem!

To make the following discussion clearer, this is Stefan's declaration of the lookup function:

template<class EKey, class EVal, unsigned n,
         class Key, class Val>
EVal lookup(const Pair<EKey, EVal>(&tbl)[n],
            const Key & key, const Val & def)

As it is clearly stated by Phil Bass in his solution, the real problem in this declaration is the fact that we do not really want the types of the key and def function arguments to be automatically deduced by compiler. What instead we want is to force the compiler to deduce the types of the EKey and EVal template arguments by looking at the type of the tbl's Pair elements, and then use these deduced types as the types of the key and def function arguments.

Using pseudo code this is how it would look:

template<class K, class V, int N>
V lookup(const Pair<K, V>(&tbl)[N],
         typeof(K) key,
         typeof(V) const & def)

Now in order to translate this pseudo code into real code the only thing we need is a way to name the types of the Pair's K and V template arguments. And by far the simplest way to create a name for the type of a template argument is by creating a typedef within the definition of the template itself:

template<class K, class V>
struct Pair {
  typedef K key_type;
  typedef V mapped_type;
  key_type key;
  mapped_type value;
};

Once this is done we can rewrite the signature of the lookup function this way:

template<class K, class V, int N>
typename Pair<K, V>::mapped_type
    const & lookup(const Pair<K, V>(&tbl)[N],
           typename Pair<K, V>::key_type key,
           typename Pair<K, V>::mapped_type
                       const & default_value);

Which solves pretty much all of Stefan's problems related to the lookup function (no more ugly casts, function can return the result by reference).

I am attaching the code for the complete solution at the bottom of this mail.

In order to keep the code as simple and as clean as possible, I have decided to provide global definitions of the < and == operators for the Pair type instead of resorting to a custom function object. Given that the Pair type is a very simple type whose usage is entirely under our control I feel this is not at all inappropriate.

Kind Regards

Renato Mancuso

#include <iostream>
      // for std::cout, std::cerr, std::endl
#include <algorithm> // for std::lower_bound
#include <cassert>   // for the assert macro

// This is the definition of the Pair
// template class.
// We do not declare a constructor since
// we want this struct to be a POD type.
template<class K, class V>
struct Pair {
  typedef K key_type;
  typedef V mapped_type;
  key_type key;
  mapped_type value;
};

// These are the global operator < and == for
// the Pair template class. They define a weak
// ordering relationship based on the value of
// the Pair's key data member. NOTE: Comeau
// 4.3.3 STL requires the declaration of the
// complete set of relational operators. This
// is not correct according to the Standard.
template<class K, class V>
inline bool operator<(const Pair<K, V> & lhs,
                    const Pair<K, V> & rhs) {
  return lhs.key < rhs.key;
}
template<class K, class V>
inline bool operator==(const Pair<K, V> & lhs,
                    const Pair<K, V> & rhs) {
  return lhs.key == rhs.key;
}

// This is the lookup function. It assumes
// that tbl's elements are sorted according
// to the // global < and == operators.
template<class K, class V, int N>
typename Pair<K, V>::mapped_type const &
      lookup(const Pair< K, V >( &tbl )[ N ],
          typename Pair<K, V>::key_type key,
          typename Pair<K, V>::mapped_type
                     const & default_value) {
  typedef Pair<K, V> pair_type;
  typedef const pair_type * iterator_type;
  const pair_type target = { key };
  iterator_type first = tbl;
  iterator_type last  = tbl + N;
  iterator_type found =
        std::lower_bound(first, last, target);
  if((found != last) && (*found == target)) {
    return found->value;
  }
  return default_value;
}
// This template function checks that the
// table is sorted and that the key values
// are unique.
// Since this is a template function, it is
// only instantiated if it is called.
template<class T, int N>
bool is_sorted(T(&tbl)[N]) {
  for(int i = 0; i < N - 1; ++i) {
    if((tbl[i+1] < tbl[i])
        || (tbl[i+1] == tbl[i])) {
      std::cerr << "Element at index " << i+1
                << " is not greater than its " 
                << "predecessor.\n";
      return false;
    }
  }
  return true;
}

// This is our test array mapping error codes
// to error messages.
const Pair<int, char const *> table[] = {
  { 0, "OK" },
  { 6, "minor glitch in self-destruction module" },
  { 13, "Error logging printer out of paper" },
  { 101, "Emergency cooling system inoperable" },
  { 2349, "Dangerous substance released" },
  { 32767, "Game over, you lost" }
};

// This is how we check that the array is
// sorted. It is done only in DEBUG builds.
#if !defined(NDEBUG)
namespace {
  struct check_sorted {
    check_sorted() { assert(is_sorted(table)); }
  };
  check_sorted checker;
}
#endif /* !defined(NDEBUG) */

int main() {
  // no need to cast the third argument to a
  // (char const*) since now the type of the
  // default_value argument is deduced from
  // the type of the elements of table[]...
  const char* result = lookup( table, 6, 0 );

  std::cout << (result ? result : "not found")
            << std::endl;
  std::cout << lookup(table, 5, "unknown error")
            << std::endl;
  return 0;
}

Notes: 

More fields may be available via dynamicdata ..