GotW #79

Home Blog Talks Books & Articles Training & Consulting

On the
blog
RSS feed November 4: Other Concurrency Sessions at PDC
November 3
: PDC'09: Tutorial & Panel
October 26: Hoare on Testing
October 23
: Deprecating export Considered for ISO C++0x

This is the original GotW problem and solution substantially as posted to Usenet. See the book Exceptional C++ Style (Addison-Wesley, 2004) for the most current solution to this GotW issue. The solutions in the book have been revised and expanded since their initial appearance in GotW. The book versions also incorporate corrections, new material, and conformance to the final ANSI/ISO C++ standard (1998) and its Technical Corrigendum (2003).

Template Typedef
Difficulty: 3 / 10

This GotW exists to answer a recurring question about C++ syntax: When, and how, could you make use of a template typedef?

Problem

JG Question

1. The following code is not legal C++. Why not?

  // Example 1
  //
  template<class T>
  typedef std::map<std::string, T> Registry;

  Registry<Employee> employeeRoster;
  Registry<void (*)(int)> callbacks;
  Registry<ClassFactory*> factories;

Guru Question

2. Demonstrate a C++ technique that lets you get the same effect.

Solution

1. The following code is not legal C++. Why not?

  // Example 1
  //
  template<class T>
  typedef std::map<std::string, T> Registry;

  Registry<Employee> employeeRoster;
  Registry<void (*)(int)> callbacks;
  Registry<ClassFactory*> factories;

Plain old typedefs are useful beasts; see also GotW #46 for a broader discussion of what typedef is good for. Alas, the code in question above isn't legal for a simple reason: Today's C++ doesn't support template typedefs.

The good news is that it's not hard to simulate this feature:

2. Demonstrate a C++ technique that lets you get the same effect.

According to today's C++ language, typedefs can't be templated directly. What saves the day is that: a) classes can be templated; and b) classes can contain typedefs. Putting this together, we get the following solution, which is the usual technique for working around the absence of template typedefs:

  // Example 2
  //
  template<class T>
  struct Registry
  {
    typedef std::map<std::string, T> Type;
  };

This solution isn't quite the same as having a template typedef, but it's close. The main difference is that we had to give up some of the syntactic niceness, because we now have to mention the name of the helper typedef Type:

  Registry<Employee>::Type employeeRoster;
  Registry<void (*)(int)>::Type callbacks;
  Registry<ClassFactory*>::Type factories;

It's Deja Vu All Over Again

As noted above, Example 2 is "the usual workaround." In fact, it's so usual that it's even  used in the standard library itself. All STL-compliant allocators have to provide a template class member called rebind whose entire purpose in life is to simulate a template typedef:

  // Example 3
  //

  // The type of af is SomeAllocator<float>
  SomeAllocator<float> af;

  // The type of ad is SomeAllocator<double>
  SomeAllocator<float>::rebind<double>::other ad;

One way to think of rebind is as a way to get "an allocator kind of sort of just like this one that I've already got, except different" -- specifically, an allocator that allocates objects of a different type but behaves the same way in other respects. For an allocator A<T>, it's guaranteed that A<T>::rebind<U>::other is the same type as A<U>.

The reason why allocators have to be able to jump through these hoops is mildly arcane. Consider a vector<int, SomeAllocator<int> > called vec_of_ints. This vec_of_ints will use the provided allocator directly to get memory for its internal buffer of ints, because the standard requires that it must store a real array of ints internally. Fair enough, and simple enough.

But now consider a list<int, SomeAllocator<int> > called list_of_ints. Unlike vector, list is a node-based container. This means that, unlike vec_of_ints, list_of_ints doesn't allocate ints directly; rather, it allocates nodes containing an int plus forward and back pointers for navigation to other nodes in the list. But that means that SomeAllocator<int>, which allocates ints, isn't at all what list_of_ints needs; what list_of_ints needs is something that will allocate its own ListNode<int>s. Enter rebind: To solve the problem, list_of_ints will internally use rebind to get a related allocator of the type it needs that does what it wants. Assuming its second template parameter is called Allocator, it just asks for an object of type Allocator::rebind<ListNode<int> >::other.

Copyright 2009 Herb Sutter