Title: The Tale of a Struggling Template Programmer

Author: 

Date: 01 June 2004 16:51:14 +01:00 or Tue, 01 June 2004 16:51:14 +01:00

Summary: 

Body: 

I'm not exactly a beginner in C++ templates. Hey, I've even got "the book" on it [Vandevoorde-]! But, admittedly, I'm not a guru - if I were, I wouldn't need the book. So I was fairly confident that I could easily come up with a little tool I have wanted to write for a while now. But it wasn't as easy as I thought. For your amusement I'm going to show you what I set out to do and what roadblocks I bumped into.

First, let me describe what I wanted to do. I have repeatedly come across the need to do table lookups in constant tables of key/value pairs. I program for embedded systems, so I am keen on keeping the table itself in nonvolatile memory (ROM, Flash, or whatever). I want to use binary search instead of linear search for efficiency. This requires the table to be stored in sorted order. Sorted according to the key alone, that is. Here's an example of such a table (binary search is not really beneficial with such a small table, but this is only a toy example):

const struct { int key; const char *value; }
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" }
};

The first problem is to ensure the table is sorted. This is a compile-time task, so in theory it could be a job for template (or preprocessor) metaprogramming. If you're good at that, I've got some homework for you. It's too difficult for me. I just resolved to tell the programmer to make sure the table is sorted.

The second problem is simpler: Provide a lookup function that, given a key, returns the associated value, or a default value if the key could not be found in the table. Naturally, I wanted to implement this as a function template that adapts to the actual key and value types. As I want the tables to be put in nonvolatile memory, they will in practice be of POD type (C-style arrays of Cstyle structs). This is a much easier problem to solve, wouldn't you agree? So pour yourself a glass of your favorite beverage, install yourself in your armchair and chuckle while watching me making a fool of myself.

The STL contains binary search algorithms, so it is sensible to use them instead of inventing my own. The first attempt at my function template uses std::equal_range and goes like this:

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

You probably know or guessed that std::equal_range returns the range of entries which compare equal to the value to be searched. If there are no duplicates in the collection, this range will encompass either zero or one element. Also note the declaration of the function parameter tbl, which looks a bit weird at first glance. This declaration specifies that tbl is a reference to an array whose elements are of type const std::pair<Key,Val> and whose size is n elements. Since Key, Val and n are template parameters the compiler deduces all this information at compile time. This version of lookup hence requires the table to be an array of std::pair objects. The example table above thus has to be changed to use std::pair<int,const char*> instead of the anonymous struct. You use it like this:

std::cout << lookup(table,6,"???") << std::endl;

But alas, it doesn't work. As std::pair has constructors, it is not an aggregate, and thus can not be initialized with the curly braces notation. Try it: Your compiler will complain. For the same reason it will most probably not be put into read-only storage. Clearly, std::pair needs to be replaced by something that allows aggregate initialization:

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

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

That didn't work either. Here's what Visual C++ 7.1 had to say:

main.cpp(33) : error C2782: 'const Val
&lookup(const Pair<Key,Val> (&)[n],const Key
&,const Val &)' : template parameter 'Val' is
ambiguous
main.cpp(11) : see declaration of 'lookup'
could be 'const char [4]'
or 'const char *'

Ok, fair enough, I thought, the compiler might have a point here. It can't figure out the proper type for Val, because it occurs twice in lookup's signature (once as part of the Pair, once as the type of the def argument). What can we do about this? Well, I decided to try a separate template parameter for the array element type, like this:

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

I imagined that it would be easier for the compiler to figure out the various type promotions/decays when doing the initialization of the variable entry inside the function template. This stuff would then not get in the way when it tried to deduce the template parameters. The compiler still had something to complain about, however:

main.cpp(13) : error C2440: 'type cast' : cannot
convert from 'int' to 'const char [4]'
  There are no conversions to array types,
although there are conversions to references or
pointers to arrays
  main.cpp(32) : see reference to function
template instantiation 'Val (&lookup<int,const
char[4],const Pair<Key,const char *>,7>(Elem
(&)[7],const Key &,Val (&)))' being compiled
  with
  [
    Val=const char [4],
    Key=int,
    Elem=const Pair<int,const char *>
  ]
main.cpp(16) : error C2440: 'return' : cannot
convert from 'const char *const ' to 'const char
(&)[4]'
  Reason: cannot convert from 'const char *const '
to 'const char [4]'
  There are no conversions to array types,
although there are conversions to references or
pointers to arrays

The first error looked like complete idiocy to me. Why would the compiler want to convert an int to a const char [4] anyway? It had deduced the template arguments correctly, hadn't it? Compiler confusion!

Let's look at the second error then, as it actually made some sense to me. I'm using the Val template parameter for the return type as well as the default value, so it is no surprise that the compiler thinks it should be an array when I'm providing an array in the call to lookup. That can be fixed by forcing the pointer decay in the call to lookup, like this:

std::cout << lookup(table,6,(const char*)"???")
          << std::endl;

Disgusting, isn't it? It could be done with a more "politically correct" type of cast, of course, but it is actually a nuisance to need one in the first place. Let's see what we can do about this:

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

Note that I reordered the template parameters to match the order of occurrence in the function argument list. I thought that was a good idea as the number of template parameters is growing. My stupid compiler still doesn't get it:

main.cpp(14) : error C2440: 'type cast' : cannot
convert from 'int' to 'const char [4]'
  There are no conversions to array types,
although there are conversions to references or
pointers to arrays
main.cpp(33) : see reference to function template
instantiation 'const EVal &lookup<int,const
char*,7,int,const char[4]>(const Pair<Key,Val>
(&)[7],const Key &,const char (&)) ' being compiled
  with
  [
    EVal=const char *,
    Key=int,
    Val=const char *
  ]
main.cpp(18) : warning C4172: returning address of
local variable or temporary

I still can't figure out why the compiler wants to convert an int to a const char [4], but the warning is sensible: Val and EVal aren't necessarily the same, so the compiler is probably compelled to introduce a temporary in the last return statement. This temporary of course goes away too soon. Ok, that's easy to fix:

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 const Pair<EKey,EVal> Elem;
  Elem entry = { key, Val() };
  std::pair<Elem*,Elem*> range
         = std::equal_range(tbl, tbl+n, entry);
  if(range.first != range.second)
    return range.first->val;
  return def;
}

When Val is a const char* the return by value is no more expensive that the return by reference I used before. Alas, the value type could well be something more complicated (a struct full of stuff), so I'm not very happy to have a copy made. But if it must be it shall be...

The weird error remains, however. So how about asking a different compiler? Here's what GCC 3.3 says:

main.cpp: In function 'EVal lookup(const Pair<EKey,
EVal> (&)[n], const Key&, const Val&) [with EKey =
int, EVal = const char*, unsigned int n = 7, Key =
int, Val = char[4]]':
main.cpp:33: instantiated from here
main.cpp:14: error: ISO C++ forbids casting to an
array type 'char[4]'

A number of further errors follow, but they're related to a different problem to which I'm going to turn later. Let's first try to find out what the error above means. Line 14 is where entry gets initialized. So what's wrong with this? When two compilers more or less agree, they might actually be right.

Both compilers seem to believe that I want a conversion from EVal to Val (give or take a const). I would have thought it ought to be the other way round. I construct a temporary of type Val and expect the compiler to convert it to an EVal in order to initialize the second field of the variable entry. In my particular case Val is an array and EVal is a pointer, so the conversion should simply be a decay. But why convert anyway? I've got an idea: Let's construct an EVal directly:

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 const Pair<EKey,EVal> Elem;
  Elem entry = { key, EVal() };
  std::pair<Elem*,Elem*> range
         = std::equal_range(tbl, tbl+n, entry);
  if(range.first != range.second)
    return range.first->val;
  return def;
}

That sorts it out. But it feels as if I had merely dodged the issue. I still don't know why the original attempt failed. If you know, tell me.

That brings us to the next errors I mentioned above. GCC emits a lot of error messages which are too numerous to print here, but most of them contain the text "no match for operator<", which is actually quite right since I obviously forgot to define how to compare a Pair to another. So I guess I have two options here. I could either provide operator< for a Pair or I could provide a custom predicate to std::equal_range to do the comparison. I only want to compare the keys, so I feel that the first option amounts to cheating. If someone else wanted to compare two Pairs and did not know about my ruminations here she would probably expect operator< to take both fields of the Pair into account.

So I think I should rather provide a special predicate with a sensible name like LessKey that makes it clear that only the key is being compared. Here we go:

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

Look Ma! I even made it adaptable by deriving from std::binary_function! I earned extra brownie points for that, didn't I? My lookup function template now looks like this:

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, EVal() };
  std::pair<Elem*,Elem*> range
         = std::equal_range(tbl, tbl+n, entry, Pred());
  if(range.first != range.second)
    return range.first->val;
  return def;
}

Needless to say, GCC still isn't happy. It emits a series of warnings regarding the implicit usage of typename. Here's just one of them:

main.cpp:14: Warning: 'LessKey<Key,
Val>::result_type' is implicitly a typename
main.cpp:14: Warning: implicit typename is
deprecated, please see the documentation for
details

The same happens for first_argument_type and second_argument_type. I could ignore those as they're only warnings, but I want to get it right. Furthermore I think I know what's amiss: I need to use the keyword typename to make clear that they are types. Next try:

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

Now, GCC defecates an even bigger heap of error messages onto me ('scuse my French!). I don't want to spare you the experience:

main.cpp:13: error: Fehler beim Parsen before
'operator'
/usr/include/c++/3.3/bits/stl_algo.h: In function
'std::pair<_ForwardIter, _ForwardIter>
std::equal_range(_ForwardIter, _ForwardIter, const
_Tp&, _Compare) [with _ForwardIter = const
Pair<int, const char*>*, _Tp = Pair<int, const
char*>, _Compare = LessKey<int, const char*>]':
main.cpp:22: instantiated from 'EVal lookup(const
Pair<Key, Val> (&)[n], const Key&, const Val&)
[with EKey = int, EVal = const char*, unsigned int
n = 7, Key = int, Val = char[4]]'
main.cpp:40: instantiated from here
/usr/include/c++/3.3/bits/stl_algo.h:3026: error:
no match for call to '(LessKey<int, const char*>)
(const Pair<int, const char*>&, const Pair<int,
const char*>&)'
/usr/include/c++/3.3/bits/stl_algo.h:3031: error:
no match for call to '(LessKey<int, const char*>)
(const Pair<int, const char*>&, const Pair<int,
const char*>&)'
/usr/include/c++/3.3/bits/stl_algo.h: In function
'_ForwardIter std::lower_bound(_ForwardIter,
_ForwardIter, const _Tp&, _Compare) [with
_ForwardIter = const Pair<int, const char*>*, _Tp =
Pair<int, const char*>, _Compare = LessKey<int,
const char*>]':
/usr/include/c++/3.3/bits/stl_algo.h:3034:
instantiated from 'std::pair<_ForwardIter,
_ForwardIter> std::equal_range(_ForwardIter,
_ForwardIter, const _Tp&, _Compare) [with
_ForwardIter = const Pair<int, const char*>*, _Tp =
Pair<int, const char*>, _Compare = LessKey<int,
const char*>]'
main.cpp:22: instantiated from 'EVal lookup(const
Pair<Key, Val> (&)[n], const Key&, const Val&)
[with EKey = int, EVal = const char*, unsigned int
n = 7, Key = int, Val = char[4]]'
main.cpp:40: instantiated from here
/usr/include/c++/3.3/bits/stl_algo.h:2838: error:
no match for call to '(LessKey<int, const char*>)
(const Pair<int, const char*>&, const Pair<int,
const char*>&)'
/usr/include/c++/3.3/bits/stl_algo.h: In function
'_ForwardIter std::upper_bound(_ForwardIter,
_ForwardIter, const _Tp&, _Compare) [with
_ForwardIter = const Pair<int, const char*>*, _Tp =
Pair<int, const char*>, _Compare = LessKey<int,
const char*>]':
/usr/include/c++/3.3/bits/stl_algo.h:3036:
instantiated from `std::pair<_ForwardIter,
_ForwardIter> std::equal_range(_ForwardIter,
_ForwardIter, const _Tp&, _Compare) [with
_ForwardIter = const Pair<int, const char*>*, _Tp =
Pair<int, const char*>, _Compare = LessKey<int,
const char*>]'
main.cpp:22: instantiated from 'EVal lookup(const
Pair<Key, Val> (&)[n], const Key&, const Val&)
[with EKey = int, EVal = const char*, unsigned int
n = 7, Key = int, Val = char[4]]'
main.cpp:40: instantiated from here
/usr/include/c++/3.3/bits/stl_algo.h:2923: error:
no match for call to '(LessKey<int, const char*>)
(const Pair<int, const char*>&, const Pair<int,
const char*>&)'

I hope the occasional German word in there doesn't irritate you. Having part of the output of tools translated to German with the remainder in English leads to interesting effects. That's a story for another day.

Are you actually able to spot what's wrong from the gobbledygook above? I wasn't. Give me a hint if you are. All it tells me is that GCC ran into a parsing error in a system library because of the code I wrote (!). Is this a GCC bug? Visual C++ 7.1 is happy with it, no matter whether the typename keywords are there or not. So do I need them or not? How do I write this correctly?

Time to consult "the book"[Vandevoorde-]! On page 131 we can find the following description:

Ok, let's see whether I can make any sense of this: Rules 1 and 3 are obviously met. Rule 4 seems to be met indirectly, since result_type is defined by the base class std::binary_function, which in turn is a class template that depends on both template parameters Key and Var. However, rule 2 seems to be violated, as I can not see any qualification. So I conclude that typename shouldn't even be allowed where I put them. So GCC is technically right although it should have generated better error messages. Visual C++ accepted wrong code without complaint. But what is wrong with the original version without typename, why is GCC issuing a warning? Rule 2 pretty much excludes that a typename is missing elsewhere.

I solved the problem by not using return_type and its siblings from std::binary_function. The following is accepted by both GCC and Visual C++:

template<typename Key, typename Val>
struct LessKey : std::binary_function<
                     const Pair<Key,Val>&,
                     const Pair<Key,Val>&,bool> {
  bool operator()(const Pair<Key,Val> &a,
                  const Pair<Key,Val> &b) const
  { return a.key < b.key; }
};

Again, I had chickened out instead of solving the problem. Swallowing my pride, I went on to the next challenge:

const char *result = lookup(table,6,0);

I guess you see what I want to achieve?!? I want lookup to return a null pointer if the key wasn't found in the table. For a table that contains strings as values this is sensible, wouldn't you agree?

It doesn't compile. You already guessed why: The third argument to the lookup function gets interpreted as an integer as opposed to a null pointer, so the compiler comes up with the wrong choices for the template parameters and as a consequence the statement "return def;" fails to compile. I would have to write something like this:

const char *result = lookup(table,6,(char*)0);

But that's ugly; can you really expect that from an innocent user of my templates? What about this:

const char *result = lookup(table,6,NULL);

Nope, the compiler still interprets the NULL as an integer constant. Back to square 1. GCC's error message is actually quite interesting:

main.cpp: In function 'int main()':
main.cpp:40: Warnung: passing NULL used for nonpointer
converting 3 of 'EVal lookup(const
Pair<Key, Val> (&)[n], const Key&, const Val&)
[with EKey = int, EVal = const char*, unsigned int
n = 7, Key = int, Val = int]'
main.cpp: In function 'EVal lookup(const Pair<Key,
Val> (&)[n], const Key&, const Val&) [with EKey =
int, EVal = const char*, unsigned int n = 7, Key =
int, Val = int]':
main.cpp:40: instantiated from here
main.cpp:25: error: invalid conversion from 'const
int' to 'const char*'

The compiler does indeed notice that NULL is being used as a non-pointer, but it still pigheadedly decides to instantiate the template with Val = int.

Despair sets in, creeping slowly from the back of my head towards the front. Is there any hope to get this right? Am I trying to do something frivolous? Illegal? Immoral? Fattening? Time to step back and take a deep breath. What can we learn from this?

It doesn't take much to get into serious trouble with templates. This doesn't mean that templates themselves are to blame. It is rather the interaction between templates and other C++ "features" that cause problems. It is similar to combining drugs: Each one is harmless when taken alone, but taken together they might kill you.

Over the last years we have seen an increasing number of tricks and workarounds attempting to control and contain the unwanted effects of these interactions. Library designers are forced to know and use them to prevent unpleasant surprises for the mere mortal library user. Here's a short list of idiosyncrasies that I just came up with ad-hoc. You're invited to add your favorites to it. Maybe we could create a "C++ derision web page" from it. I hope you don't take this seriously enough to be offended.

To me it seems the more experience I've gained programming in C++ the more I realize how inadequate my skill still is. I have been programming in C++ for a considerable time now, I have read numerous books on the subject, and still I don't seem to have it under control. This bothers me. How can an average programmer be expected to cope with this? Imagine for a moment yourself giving a lecture to a classroom full of the type of programmers you meet in your working life. Your topic is the sort of stuff I came across in my example above. Just imagine the puzzled faces.

I don't know what to do about this. If the other languages weren't even worse in one way or another I would probably switch. But so far I haven't seen anything I like 100%. I had a look at Haskell, and I generally liked what I saw, particularly regarding generic programming, but I couldn't see how to apply this to embedded programming, where you deal extensively with low-level stuff that is rather close to the hardware level. Here I would like to be able to predict what kind of code is being generated. With Haskell I feel I have no control over this. Maybe that's because I'm not experienced enough with it.

My dream language would take Haskell's elegant type inference machinery and built-in list/tuple/array manipulation and combine it with a more "conventional" syntax. It must support object-oriented and imperative programming styles, because I can't see how I could do without them in embedded programming.

My feeling is that languages that have genericity tagged on as an afterthought are not really satisfactory. Backwards compatibility is likely to prevent cleaning up the rough edges. The result is the sort of thing we have now with C++: The language is very complicated and has lots of obscure and surprising special cases. I am asking myself if it would not be possible to deprecate troublesome features in a language more aggressively. I know of course that C++ has become popular precisely because of its backward compatibility and that right now the standard committees for C and C++ are cooperating closely to ensure that this remains so.

Back in now ancient times the ANSI C standard introduced function prototypes, offering a better alternative to K&R style function declarations. I haven't seen any K&R style code for a while now. It still exists, but it is now customary to require a compiler switch to make the compiler accept the old form. Can't something similar be done with C++? Something like a C++ generation 2 that is not backwards compatible with the current generation, but is linkcompatible with it. And the compiler would continue to accept the old version while it is gradually being phased out.

To wind up, let's see where we are with my little problem. Here's the complete code as it stands now:

#include <iostream>
#include <algorithm>
#include <functional>
template<typename Key, typename Val>
struct Pair { Key key; Val val; };
template<typename Key, typename Val>
struct LessKey : std::binary_function<
    const Pair<Key,Val>&, const Pair<Key,Val>&,bool> {
  bool operator()(const Pair<Key,Val> &a,
                  const Pair<Key,Val> &b) const
  { return a.key < b.key; }
};

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, EVal() };
  std::pair<Elem*,Elem*> range
      = std::equal_range(tbl, tbl+n, entry, Pred());
  if(range.first != range.second)
    return range.first->val;
  return def;
}

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

It has the following problems:

So if you want to have a go, you're invited to contribute your solutions. I'd like to know how this is done right!

Developers are people too, and hate to admit that they are confused or that their understanding is incomplete. We should be grateful therefore that Stefan was willing to write this article which illustrates the potential C++ has for causing these symptoms even in experienced developers. It is said that an admission of ignorance is the first step to wisdom and further steps were taken when one of Overload's Readers became interested in solving the problem presented above. If you wish to tackle this exercise yourself then you may want to postpone reading the results of their collaboration (which, in the traditional manner, appears towards the end of this magazine). (AG)