More C++ Idioms/Type Selection

Type Selection

Intent

Select a type at compile-time based on a compile-time boolean value or a predicate.

Motivation

Ability to take decisions based on the information known at compile-time is a powerful meta-programming tool. One of the possible decisions to be made at compile-time is deciding a type i.e., the choice of the type may vary depending upon the result of a predicate.

For example, consider a Queue abstract data-type (ADT) implemented as a class template that holds a static array of Ts and the maximum capacity of the Queue is passed as a template parameter. The Queue class also needs to store the number of elements present in it, starting from zero. A possible optimization for such a queue class could be to use different types to store the size. For instance, when Queue's maximum capacity is less than 256, unsigned char can be used and if the capacity is less than 65,536, unsigned short can be used to store the size. For larger queues, unsigned integer is used. Type selection idiom can be used to implement such compile-time decision making.

Solution and Sample Code

A simple way of implementing the type selection idiom is the IF template. IF template takes three parameters. The first parameter is a compile-time boolean condition. If the boolean condition evaluates to true the 2nd type passed to the IF template is chosen otherwise third. Type selection idiom consists of a primary template and a partial specialization as shown below.

template <bool, class L, class R>
struct IF  // primary template
{
  typedef R type; 
};
 
template <class L, class R>
struct IF<true, L, R> // partial specialization
{
  typedef L type; 
};
 
IF<false, int, long>::type i; // is equivalent to long i;
IF<true,  int, long>::type i; // is equivalent to int i;

We now use the type selection idiom to implement the Queue size optimization mentioned above.

template <class T, unsigned int CAPACITY>
class Queue 
{
  T array[CAPACITY];
  typename IF<(CAPACITY <= 256), 
      unsigned char, 
      typename IF<(CAPACITY <= 65536), 
                  unsigned short, 
                  unsigned int
                 >::type
    >::type size;
  // ...
};

The Queue class template declares an array or Ts. The type of the size data member depends on the result of two comparisons performed using the IF template. Note that these comparisons are not performed at run-time but at compile-time.

Known Uses

• Boost.MPL Library
• std::conditional

Related Idioms

• Tag Dispatching