computer science goes bonk / all posts / rss / about

a type by any other name

There are only two hard problems in computer science:

  1. naming things,
  2. cache invalidation, and
  3. off-by-one errors.

This is a post about naming things. Consider the following code:

template <typename T>
void foo() {
  T::iterator it;
}

int main() {}

Will this code compile?

No, because the compiler doesn't know that T::iterator refers to a type.

How do I fix it?

You need to use the typename keyword, like so:

template <typename T>
void foo() {
  typename T::iterator it;
}

int main() {}

Why is typename necessary?

T::iterator is called a dependent name, because it depends on what T is. Most of the time, dependent names in templates are not assumed to be types.

Why can't the compiler assume this dependent name is a type?

Because T::iterator might not refer to a type. Here's an example of a potential T where T::iterator isn't a type:

struct Bar {
  static int iterator;
};

Why can't the compiler figure out which names refer to types automatically?

Because the template definition might work either way -- with T::iterator as a type or with T::iterator as a variable:

int b;

template <typename T>
void baz() {
  T::iterator *b;
}

In the above code, does the body of baz:

  • declare a variable named b that is a pointer to the type T::iterator, or
  • multiply the global variable b with the static variable T::iterator, and ignore the result?

If all we've seen is the template, we don't know. It could be either.

Why doesn't the compiler delay processing the template definition until it sees an instantiation?

Good question. Here are some reasons why the compiler parses template definitions when it sees them:

  • It allows the compiler to generate errors sooner.

  • If the compiler waited until it saw an instantiation, it would have to decide if code that appears between definition and instantiation could be used in the template. For example, a better match for an overloaded function call might be introduced -- should it be ignored?

  • Worst of all, different instantiations of the ambiguous template above would mean the same chunk of code could produce totally different parse trees, which seems unlikely to match programmer intent.

My head hurts.

TL;DR: Use the typename keyword with dependent names in templates to indicate those names are types.