Title: A Template Programmer’s Struggles Resolved

Thaddaeus Frogley suggested that rather than sorting the table at compile time, which may be impossible, the debug build could check the sorting when the program starts up. You would need to write a function that checks the table sorting and call it in an assert macro that is run at program startup. As an additional service, the checking code could generate a sorted version of the table in a format that can be cut and pasted into the source code, so that the burden of keeping the table sorted is not on the struggling programmer. We'll not actually show any code for this here, as we believe that it is fairly straightforward. Furthermore, this issue was not the main point in [Heinzmann] anyway.

Here, we owe you an explanation why the typedefs in the binary_function base class could not be used in the definition of LessKey::operator(). It turns out that this is because of the name lookup rules, namely two-phase lookup. If you want to know the full story you need to turn to The Book [Vandevoorde-] chapter 9.4.2, but here's the bottom line:

As std::binary_function is a base class for LessKey that depends on LessKey's template parameters, it is called a dependent base class. The C++ standard says that nondependent names are not looked up in dependent base classes. Hence a standard conforming compiler will not find result_type and its siblings and emit an error message. The error messages that were actually emitted by GCC weren't particularly helpful, in particular the mentioning of typename was misleading, but the code was definitely wrong. So what can we do about it? There are a number of possibilities here, though none are particularly appealing:

That's disappointing, isn't it? It means that deriving from std::binary_function in order to make the predicate adaptable according to the rules of the STL is only half as useful as you'd wish it to be. It makes you wonder whether you want to derive from std::binary_function at all. After all, you can make your predicate adaptable by providing the required typedefs yourself, like this:

template<typename Key, typename Val>
struct LessKey {
  typedef bool result_type;
  typedef const Pair<Key,Val> &first_argument_type;
  typedef first_argument_type second_argument_type;
  result_type operator()(first_argument_type a,
                         second_argument_type b) const
  { return a.key < b.key; }
};

If you don't want the predicate to be adaptable, you can apply a clever trick that appeared in [Sposato]: You make the predicate work on the key type directly. This removes the need to construct an element with all its associated problems mentioned in [Heinzmann]. If we needn't construct an element, we need no default constructor for the Val type either, which is an additional advantage. Here's the code:

template<typename Key, typename Val>
struct CleverLessKey {
  typedef const Pair<Key,Val> Elem;
  bool operator()(Elem &elem, const Key &key) const
  { return elem.key < key; }
  bool operator()(const Key &key, Elem &elem) const
  { return key < elem.key; }
};

Note the overloading of operator() to allow passing the arguments in any order. Inside the lookup function template the key can now be passed directly to equal_range:

template<typename EKey, typename EVal,
         unsigned n, typename Key, typename Val>
         EVal lookup(const Pair<EKey,EVal>(&tbl)[n],
         const Key &key, const Val &def) {
  typedef CleverLessKey<EKey,EVal> Pred;
  typedef const Pair<EKey,EVal> Elem;
  std::pair<Elem*,Elem*> range
        = std::equal_range(tbl, tbl+n, key, Pred());
  if(range.first != range.second)
    return range.first->val;
  return def;
}

This bends the intuitive rule of what a good predicate is; ordinarily you would think both argument types had to be the same, but as far as we know there's nothing in the C++ standard that would make this illegal. It certainly works with VC++ 7.1 and GCC 3.3.

The Comeau compiler [comeau] disagrees, however. Apparently, the library implementation used by Comeau contains compile-time concept checks that verify whether the two argument types of the predicate are the same. As ours are not, those checks fail and the compiler rejects the code. We feel that this is overly restrictive.

That leads us to the weird error mentioned in [Heinzmann] where the compiler apparently wanted to convert an int to a const char [4]. We owe you an explanation here, too. Let us repeat the relevant code where the error occurs:

template<typename EKey, typename EVal,
         unsigned n, typename Key, typename Val>
         EVal lookup(const Pair<EKey,EVal>(&tbl)[n],
         const Key &key, const Val &def) {
  typedef LessKey<EKey,EVal> Pred;
  typedef const Pair<EKey,EVal> Elem;
  Elem entry = { key, Val() }; // error here
  std::pair<Elem*,Elem*> range
        = std::equal_range(tbl, tbl+n, entry, Pred());
  if(range.first != range.second)
    return range.first->val;
  return def;
}

The error message was strange, but there's indeed an error. The compiler correctly deduces the following type for Val, namely const char [4]. That means that Val() tries to default construct a temporary of type const char [4], which is impossible. No conversion from int to const char [4] is involved, the error displayed by the compiler is again rather misleading here.

The fix employed in [Heinzmann] was correct, but there is another, more elegant possibility:

template<typename EKey, typename EVal,
         unsigned n, typename Key, typename Val>
EVal lookup(const Pair<EKey,EVal>(&tbl)[n],
         const Key &key, const Val &def) {
  typedef LessKey<EKey,EVal> Pred;
  typedef const Pair<EKey,EVal> Elem;
  Elem entry = { key }; // second part of Pair
                        // omitted
  std::pair<Elem*,Elem*> range
        = std::equal_range(tbl, tbl+n, entry, Pred());
  if(range.first != range.second)
    return range.first->val;
  return def;
}

As you may have noted, it is not actually necessary to explicitly initialize the val member of the variable entry, as we don't use it anyway. Omitting the initializer for val causes it to be value-initialized, which in practice does the same as calling EVal() explicitly.

Anyway, we will use our clever predicate henceforth, despite the problems with the Comeau compiler.

Now that we've got those niggles out of the way, we can turn to the remaining problems. Remember what the question was: Given the following program fragment, how can we implement the lookup() function as a function template that works for arbitrary instantiations of Pair<Key,Val>?

template<typename Key, typename Val>
struct Pair {
  Key key;
  Val val;
};

const Pair<int, const char*> 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" }
};

int main() {
  const char *result = lookup(table,6,(char*)0);
  std::cout << (result ? result : "not found")
            << std::endl;
}

The implementation we arrived at in the last chapter still has those two problems:

First, note that the lookup() function given above is based on std::equal_range(), but actually behaves more like std::lower_bound(). It returns the mapped value of the first element matching the key, if any. Since lower_bound() is a simpler and slightly more efficient algorithm we will use it in the subsequent code samples. However, it is a bit trickier to use, as you'll see shortly.

While equal_range returns a pair of iterators, lower_bound returns just one. If there are suitable elements (according to the predicate) in the collection, the returned iterator points to the first one found. Otherwise it points to the place where such an element could be inserted without breaking the sorting order. This makes it more complicated to test for success. Here's what lookup would look like using lower_bound instead of equal_range:

template<typename EKey, typename EVal,
         unsigned n, typename Key, typename Val>
EVal lookup(const Pair<EKey,EVal>(&tbl)[n],
         const Key &key, const Val &def) {
  CleverLessKey<EKey,EVal> pred;
  const Pair<EKey,EVal> *pos
        = std::lower_bound(tbl, tbl+n, key, pred);
  if(pos == tbl+n || pred(key,*pos))
    return def;
  return pos->val;
}

Lets take a step back and look at the problem from a generic angle: Why restrict ourselves to arrays? Surely, it should be possible to write lookup() so that it works with any map-like container. In particular, we would expect to be able to write:

// ... table definition, etc. as before ...
using namespace std;
int main() {
  map<int, const char*> message_map;
  message_map[6]
        = "Minor glitch in self-destruction module";
  cout << lookup(message_map, 6, "not found”)
       << endl;
  cout << lookup(message_map, 6, 0) << endl;
  cout << lookup(table, 6, "not found") << endl;
  cout << lookup(table, 6, 0) << endl;
}

Although this is a slightly different problem, it points the way towards a solution to the original problem that removes the remaining blemishes in Stefan's code.

The lookup function needs to be implemented in quite different ways for maps and arrays. For a map, lookup should call std::map<>::find(); for an array, it should call std::lower_bound(). These two functions have different interfaces. The former is a member function taking a single parameter; the latter is a non-member function taking four parameters (for the overload we need). Somehow, the lookup function template must deduce these differences from the type of the container passed to it.

In principle, we could just provide separate overloads for maps and arrays:

template<typename Key, typename Val>
const Val& lookup(const std::map<Key,Val>&,
                  const Key&, const Val&);

template<typename Key, typename Val, unsigned n>
const Val& lookup(const Pair<Key,Val>(&)[n],
                  const Key&, const Val&);

But that gets us back to where we came in. Stefan's article was all about the difficulties of implementing the second of those lookup() function overloads.

An alternative approach treats lookup as an algorithm that can be applied to any map-like container. There is a single lookup() function, but there can be several types of “map”. Or, more precisely, we define a generic Map concept, write the lookup() function template in terms of the Map interface and provide as many implementations of the Map concept as we need (including std::map<>s and arrays of Pair<>s).

// pseudo-code
template<typename Map>
const MapVal& lookup(const Map&, const MapKey&,
                     const MapVal&);

Here, we have used MapKey and MapVal to stand for the Map's key and mapped value types. In real C++ code these types would be deduced from the Map type. In the case of std::map<> the MapKey and MapVal types are immediately available: MapKey is std::map<>::key_type and MapVal is std::map<>::mapped_type. In the case of arrays things are less straightforward. Arrays are not classes, so we can't add nested typedefs. Instead we can use the traits class technique.

template<typename Map>
const typename map_traits<Map>::mapped_type&
lookup(const Map& map,
       const typename map_traits<Map>::key_type&
                   target_key,
       const typename map_traits<Map>::mapped_type&
                   default_value);

Now we can put information about the differences between maps and arrays in the traits class and use that information in our implementation of lookup().

Note that now there's only one template parameter for the compiler to deduce: The type of the map itself. Only the first argument to the lookup function participates in this deduction, as the types of the other arguments are dependent on the result of this deduction. This greatly reduces the chance for deduction problems such as ambiguities.

As noted above, lookup() will need to call either std::map<>::find() or std::lower_bound(). A map_traits<>::find() function is introduced to hide this from the lookup() function itself. Then lookup() needs to check whether the key was found and return either the default value or the value part of the element matching the key. Here, we use a map_traits<>::end() function to get the appropriate past-the-end iterator for the ‘key found' test. Retrieving the mapped value via an iterator depends on the element type (not the map type), so an element traits template with a mapped_value() member is used for that.

The traits functions represent operations that might be useful in other contexts. In those cases writing

map_element_traits<Map>::mapped_value(element)

for example, is both tedious and verbose. So, we provide nonmember wrapper functions to simplify the code in these situations and take advantage of them in the lookup() function itself.

// The mapped_value() convenience function
template<typename Elem>
inline
const typename map_element_traits<Elem>::mapped_type&
mapped_value(const Elem& element) {
  return map_element_traits<Elem>::mapped_value(element);
}

// The find() convenience function
template<typename Map>
inline
typename map_traits<Map>::const_iterator
find(const Map& map,
     const typename map_traits<Map>::key_type& key) {
  return map_traits<Map>::find(map, key);
}

// The lookup() function
template<typename Map>
const typename map_traits<Map>::mapped_type&
lookup(const Map& map,
       const typename map_traits<Map>::key_type& target_key,
       const typename map_traits<Map>::mapped_type& default_value) {
  typename map_traits<Map>::const_iterator i
        = find(map, target_key);
  return (i == end(map))
        ? default_value : mapped_value(*i);
}

The traits templates are declared (but not defined) and then specializations are defined for each of the map-like containers we wish to support. This prevents the instantiation of the traits templates with unexpected template arguments (e.g. via template argument deduction), which should help to minimize the number of incomprehensible error messages if the programmer makes a mistake.

template<typename Elem> struct map_element_traits;
template<typename Map> struct map_traits;

The traits templates for std::map<> are straightforward. A partial specialisation of the map element traits template is provided for any std::pair<>.

template<typename Key, typename Val>
struct map_element_traits< std::pair<Key,Val> > {
  typedef std::pair<Key,Val> value_type;
  typedef typename value_type:: first_type key_type;
  typedef typename value_type::second_type mapped_type;

  static const key_type& key(
        const value_type& element) {
    return element.first;
  }

  static const mapped_type& mapped_value(
        const value_type& element) {
    return element.second;
  }
};

Similarly, a partial specialization of the map traits template is provided for any std::map<>.

template<typename Key, typename T, typename Cmp,
         typename A>
struct map_traits< std::map<Key,T,Cmp,A> > {
  typedef std::map<Key,T,Cmp,A> map_type;
  typedef typename map_type::key_type key_type;
  typedef typename map_type::mapped_type mapped_type;
  typedef typename map_type::value_type value_type;
  typedef typename map_type::const_iterator const_iterator;

  static const_iterator begin(const map_type& map)
  { return map.begin(); }

  static const_iterator end(const map_type& map)
  { return map.end(); }

  static const_iterator find(const map_type& map,
                             const key_type& key)
  { return map.find(key); }
};

These traits classes adapt std::map for use with our lookup() function.

The traits for arrays of Pair<Key,Val> are similar to those for std::map<>. There is a partial specialisation of map_element_traits<> for Pair<Key,Val>.

template<typename Key, typename Val>
struct map_element_traits< Pair<Key,Val> > {
  typedef Pair<Key,Val> value_type;
  typedef Key key_type;
  typedef Val mapped_type;

  static const key_type& key(
        const value_type& element)
  { return element.key; }

  static const mapped_type& mapped_value(
        const value_type& element)
  { return element.val; }
};

And there is a partial specialisation of map_traits<> for arrays of Pair<Key,Val>.

template<typename Key, typename Val, unsigned n>
struct map_traits< Pair<Key,Val>[n] > {
  typedef Key key_type;
  typedef Val mapped_type;
  typedef Pair<Key,Val> value_type;
  typedef const value_type* const_iterator;

  static const_iterator begin(
        const value_type (&map)[n])
  { return &map[0]; }

  static const_iterator end(
        const value_type (&map)[n])
  { return &map[n]; }

  static const_iterator find(
        const value_type (&map)[n],
        const key_type& target_key) {
    const_iterator i = std::lower_bound(begin(map),
          end(map), target_key,
          key_value_compare<value_type>());
    return (i == end(map) || key(*i) != target_key)
          ? end(map) : i;
  }
};

The find() function uses lower_bound() passing a key comparison predicate with two asymmetric function call operators. The predicate class is generated from the following template:

template<typename Elem>
struct key_value_compare {
  typedef typename
    map_element_traits<Elem>::key_type key_type;
  typedef typename
    map_element_traits<Elem>::value_type value_type;

  bool operator()(const value_type& x,
                  const value_type& y) const {
    return map_element_traits<Elem>::key(x) <
           map_element_traits<Elem>::key(y);
  }

  bool operator()(const value_type& elem,
                  const key_type& key) const {
    return map_element_traits<Elem>::key(elem) <
           key;
  }

  bool operator()(const key_type& key,
                  const value_type& elem) const {
    return key <
           map_element_traits<Elem>::key(elem);
  }
};

This is a generalisation of the CleverLessKey class shown above. It uses the key() function from the map element traits to ensure that the predicate class can be generated for any element of a map-like class and only those elements. A third operator() overload is provided so that two elements can be compared to each other. We omitted the additional typedefs needed for adaptability.

The code presented in the previous sections does fix all the imperfections in Stefan's version. At least, it does if you are using the GCC compiler (Code tested on gcc 3.2 and 3.3.). But VC++ 7.1 produces an error. It turns out that it fails to find the map_traits specialization for Pair<Key,Val>. The reason is related to const qualification. VC++ is happy if the map_traits template is specialized for const Pair<Key,Val> instead of just Pair<Key,Val>, but that creates an error when compiled with GCC. We don't know yet whether this is because of a compiler error or because of an imprecision in the C++ standard. In practice, you will therefore have to provide both (otherwise identical) specializations.

So here is the entire code in all its glory:

#include <iostream>
#include <algorithm>
#include <map>
#include <functional>

// Generic map element declarations.
template<typename Elem> struct map_element_traits;

template<typename Elem> inline
const typename map_element_traits<Elem>::mapped_type&
mapped_value(const Elem& element) {
  return map_element_traits<Elem>::mapped_value(element);
}

template<typename Elem> inline
const typename map_element_traits<Elem>::key_type&
key(const Elem& element) {
  return map_element_traits<Elem>::key(element);
}

template<typename Elem>
struct key_value_compare {
  typedef typename
              map_element_traits<Elem>::key_type
              key_type;
  typedef typename
              map_element_traits<Elem>::value_type
              value_type;
  bool operator()(const value_type& x,
                  const value_type& y) const {
    return map_element_traits<Elem>::key(x) <
           map_element_traits<Elem>::key(y);
  }

  bool operator()(const value_type& elem,
                  const key_type& key) const {
    return map_element_traits<Elem>::key(elem) <
           key;
  }

  bool operator()(const key_type& key,
                  const value_type& elem) const {
    return key <
           map_element_traits<Elem>::key(elem);
  }
};

// Generic map declarations.
template<typename Map> struct map_traits;
template<typename Map> inline
typename map_traits<Map>::const_iterator
find(const Map& map,
     const typename map_traits<Map>::key_type& key) {
  return map_traits<Map>::find(map, key);
}

template<typename Map> inline
typename map_traits<Map>::const_iterator
end(Map const& map) {
  return map_traits<Map>::end(map);
}

// The lookup() function
template<typename Map>
const typename map_traits<Map>::mapped_type&
lookup(const Map& map,
       const typename map_traits<Map>::key_type& target_key,
       const typename map_traits<Map>::mapped_type& default_value) {
  typename map_traits<Map>::const_iterator pos
           = find(map, target_key);
  return (pos == end(map))
          ? default_value
          : mapped_value(*pos);
}

// specializations for std::map
template<typename Key, typename Val>
struct map_element_traits< std::pair<Key,Val> > {
  typedef std::pair<Key,Val> value_type;

  typedef typename value_type:: first_type key_type;
  typedef typename value_type::second_type mapped_type;

  static const key_type& key(const value_type& element) {
    return element.first;
  }

  static const mapped_type& mapped_value(
                     const value_type& element) {
    return element.second;
  }
};

template<typename Key, typename T, typename Cmp, typename A>
struct map_traits< std::map<Key,T,Cmp,A> > {
  typedef std::map<Key,T,Cmp,A> map_type;
  typedef typename map_type::key_type key_type;
  typedef typename map_type::mapped_type mapped_type;
  typedef typename map_type::value_type value_type;
  typedef typename map_type::const_iterator const_iterator;

  static const_iterator begin(const map_type& map)
  { return map.begin(); }
  static const_iterator end(const map_type& map)
  { return map.end(); }

  static const_iterator find(const map_type& map,
                             const key_type& key)
  { return map.find(key); }
};

// Our own Pair type suitable for aggregate
// initialization
template<typename Key, typename Val>
struct Pair {
  Key key;
  Val val;
};

// Specializations for Pair
template<typename Key, typename Val>
struct map_element_traits< Pair<Key,Val> > {
  typedef Pair<Key,Val> value_type;
  typedef Key key_type;
  typedef Val mapped_type;
  static const key_type& key(
                    const value_type& element)
  { return element.key; }

  static const mapped_type& mapped_value(
                    const value_type& element)
  { return element.val; }
};

template<typename Key, typename Val, unsigned n>
struct map_traits< Pair<Key,Val>[n] > { // for GCC
  typedef Key key_type;
  typedef Val mapped_type;
  typedef Pair<Key,Val> value_type;
  typedef const value_type* const_iterator;

  static const_iterator begin(
                 const value_type (&map)[n])
  { return &map[0]; }
  static const_iterator end(
                 const value_type (&map)[n])
  { return &map[n]; }
  static const_iterator find(
                 const value_type (&map)[n],
                 const key_type& target_key) {
    const_iterator i = std::lower_bound(
                 begin(map), end(map), target_key,
                 key_value_compare<value_type>());
    return (i == end(map) || key(*i) != target_key)
            ? end(map) : i;
  }
};

template<typename Key, typename Val, unsigned n>
struct map_traits< const Pair<Key,Val>[n] > {
// for VC++
  typedef Key key_type;
  typedef Val mapped_type;
  typedef Pair<Key,Val> value_type;
  typedef const value_type* const_iterator;
  static const_iterator begin(
               const value_type (&map)[n])
  { return &map[0]; }
  static const_iterator end(
               const value_type (&map)[n])
  { return &map[n]; }
  static const_iterator find(
               const value_type (&map)[n],
               const key_type& target_key) {
    const_iterator i
          = std::lower_bound(
                 begin(map), end(map), target_key,
                 key_value_compare<value_type>());
    return (i == end(map) || key(*i) != target_key)
            ? end(map) : i;
  }
};

// Test code
typedef const Pair<int, const char*> Elem;

Elem 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" }
};

using namespace std;

int main() {
  map<int, const char*> message_map;
  message_map[6]
       = "Minor glitch in self-destruction module";
  const char *result
       = lookup(message_map, 6, "not found");
  cout << "lookup(map, 6, \"not found\") = "
       << result << endl;
  result = lookup(message_map, 6, 0);
  cout << "lookup(map, 6, 0) = " << result
       << endl;
  result = lookup(table, 5, "not found");
  cout << "lookup(table, 5, \"not found\") = "
       << result << endl;
  result = lookup(table, 6, 0);
  cout << "lookup(table, 6, 0) = "
       << result
       << endl;
}