More C++ Idioms/Type Generator

Type Generator
edit

Intent edit

  • To simplify creation of complex template-based types
  • To synthesize a new type or types based on template argument(s)
  • To localize default policies when policy-based class design is used

Also Known As edit

Templated Typedef Idiom

Motivation edit

Class templates designed using policy-based class design, often result in very flexible templates with multiple type parameters. One downside of such class templates is that too many type parameters must be provided when instantiating them. Default template parameters can help in such cases. However, when the last template parameter (policy class) differs from the default, all of the intermediate template parameters must be specified.

For example, consider a case in which special purpose allocators are used with standard C++ containers. The GNU C++ compiler provides many special purpose allocators in namespace __gnu_cxx as extensions of the standard C++ library. The following illustrates specializing std::map with GNU's malloc_allocator:

std::map <std::string, int, less<std::string>, __gnu_cxx::malloc_allocator<std::string>>

A variation of the above map using float instead of an int requires all the unrelated type parameters to be mentioned again.

std::map <std::string, float, less<std::string>, __gnu_cxx::malloc_allocator<std::string> >

The type generator idiom is used to reduce code bloat in such cases.

Solution and Sample Code edit

In the type generator idiom, common (invariant) parts of a family of type definitions are collected together in a structure, whose sole purpose is to generate another type. For example, consider the Directory template shown below.

template <class Value>
struct Directory
{
  typedef std::map <std::string, Value, std::less<std::string>, 
                    __gnu_cxx::malloc_allocator<std::string> > type;
};

Directory<int>::type    // gives a map of string to integers.
Directory<float>::type  // gives a map of string to floats.

An extra level of indirection (struct Directory) is used to capture the invariant part and one or two template parameters are left open for customization. A type generator usually consolidates a complicated type expression into a simple one. A type generator can be used to generate more than one type by simply adding more typedefs.

For example, consider how standard STL algorithms are applied to maps.

Directory<int>::type age; // This is a map.
transform(age.begin(), age.end(),
          std::ostream_iterator<string>(std::cout, "\n"),
          _Select1st<std::map<std::string, int>::value_type> ());

An adapter that transforms map's value_type, which is a pair, into the first element of the pair. _Select1st does the job of adapter in the example above. Its type is needlessly complex with ample opportunity of typing it wrong when repeated multiple times. Instead, the type generator idiom simplifies type specification of the adapter considerably.

template <class Value>
struct Directory
{
  typedef map <string, Value, less<string>, __gnu_cxx::malloc_allocator<std::string> > type;
  typedef _Select1st<typename type::value_type> KeySelector;
  typedef _Select2nd<typename type::value_type> ValueSelector;
};
Directory<int>::type age;    // This is a map.
transform(age.begin(), age.end(),
          std::ostream_iterator<string>(std::cout, "\n"),
          Directory<int>::KeySelector());

Finally, the type generator idiom can be used to conveniently change the invariant type parameters, if needed. For example, changing malloc_allocator to debug_allocator throughout the program. The main reason why you might sometimes want to change it is to get more useful information from bounds-checking or leak-detection tools while debugging. Using type generators such a program-wide effect can be achieved by simply changing it at one place.

Known Uses edit

  • Boost.Iterator library

Related Idioms edit

References edit

[1] Type Generator

[2] Policy Adaptors and the Boost Iterator Adaptor Library -- David Abrahams and Jeremy Siek

[3] Template Typedef -- Herb Sutter

[4] The New C++: Typedef Templates -- Herb Sutter