Click here to Skip to main content
15,867,308 members
Articles / Programming Languages / C++
Article

Tiny Template Library: implementing typelist

Rate me:
Please Sign up or sign in to vote.
4.86/5 (53 votes)
10 Dec 20034 min read 120.4K   678   37   25
An article on how to implement compile time lists of types, typelist. Typelists are useful for generic and meta programming.

Introduction

My standard warning. Don't try to compile this project with MSVC v6.0/v7.0. This project requires a conforming compiler. MSVC v7.1 or GCC v3.2.3 will work just fine.

In my previous article, I described how the Tiny Template Library (TTL) implements generic functors.

Details

In this article, I originally wanted to talk about variant. variant is a very powerful template that allows you to create union-like data types that can contain C++ classes. As you all know in C++, it is not legal to have non-POD data types in union. For example the following code won't compile.

struct my_type
{
   int x;
   my_type() : x(0) {}
   virtual ~my_type();
};

union my_union
{
   my_type a;
   double b;
};

The variant template solves this problem and adds a lot of other cool features. One application of variant is heterogenous containers.

typedef variant< my_type, double > mv;

main()
{
  my_type a;
  
  std::vector<mv> v;
  v.push_back(2.3); //add double 
  v.push_back(a); //add my_type
}

Cool! Is not it.

As I was writing about variant, I realized that it won't be complete without a description of typelists. So I decided to talk about typelists first. A great introduction to typelists could be found in the excellent book by A. Alexandrescu "Modern C++ Design". However our implementation of typelist is quite different from that described in the book. I believe that the suggested implementation is more efficient and easier to understand and debug.

Also please note that the code extracts in this article are to demonstrate the basic ideas only. The complete implementation could be found in TTL

What is typelist? Typelists are a compile time structures that are extremely important for generic and meta programming. Typelists provide a COMPILE TIME management of data types. They don't hold any user data nor do they have any run-time methods. ttl::meta::typelist in TTL is a foundation for ttl::var::variant.

The simplest typelist allows you to list your data types and have a compile-time access to its elements and other typelist properties such as the list length.

struct my_type {}; 

typedef typelist<int, doulble, my_type> my_types;  

get<my_types, 0>::type n = 1;  //instantiate int variable
get<my_types, 1>::type x = 2.3; //instantiate double variable 
get<my_types, 2>::type s = {0}; //instantiate my_struct variable 
get<my_types, 3>::type  //compile time error
int l = length<my_types>::value; //get the typelist length 

As follows from this example, our objective is to
implement following templates:

typelist<>
get<>
length<>

Implementation

The typelist implementation suggested in "Modern C++ Design" uses nested templates. Our implementation uses recursive types. According to "C++ Templates: Complete Guide" by David Vandevoorde and Nicolai Josuttis, recursive types put less stress on the compiler and from my experience, are easier for debugging.

typelist can contain a variable number of data types. Unfortunately C++ standard doesn't allow us to define a variable number of template parameters. We'll have to find a way to work around it. It is obvious that we'll need to put a hard limit on the maximal number of types in typelist. In TTL, the limit is defined in the config.h file the macro name is TTL_MAX_TEMPLATE_PARAMS. For the simplicity sake, we put the limit to 5. So the basic typelist definition will be as follows.

struct empty {};

template
< 
  typename T1=empty, 
  typename T2=empty, 
  typename T3=empty, 
  typename T4=empty,
  typename T5=empty 
> struct typelist;

Note: by using the the default template parameter type empty, we can actually use typelist as a template with a variable number of template parameters up to 5.

typelist< int >, 
typelist< int, double > 
...

It is convenient to process lists recursively. A well known method is to use the head/tail idiom. First we want to find the length of the list. To do that we insert the length value in the typelist itself and define the first parameters as head and the rest as another typelist that is tail. In this case the typelist length is the tail length plus 1.

struct empty {};

template
< 
  typename T1=empty, 
  typename T2=empty, 
  typename T3=empty, 
  typename T4=empty,
  typename T5=empty 
> struct typelist;

template
< 
  typename T1, 
  typename T2, 
  typename T3, 
  typename T4,
  typename T5 
> 
struct typelist
{
  typedef T1 head;
  typedef typelist< T2, T3, T4, T5 > tail;
  enum
  {
    length = tail::length+1
  };
};

Now all we have to do is to stop the recursion. It is obvious that the recursion has to stop when all template parameters are 'empty'. So we just need to specialize this particular case.

template<> 
struct typelist< empty, empty, empty, empty >
{
  enum
  {
    length = 0;
  };
};

The length<> implementation is straightforwad.

template< typename Typelist >
struct length
{
  enum { value = Typelist::length };
};

get<> is more interesting. It is obvious that it will have to be recursive. The recursion should stop when the index of the requested element is equal to the recursion step. If the index is bigger than the typelist's length, get<> should generate a compile-time error. First, let's make the basic definition.

template<
  typename Typelist, 
  int Index, //requested element index
  int Step = 0, //current recusion step
  bool Stop=(Index==Step), //stop recusion flag
  bool OutOfRange = length<Typelist>::value==0 //out of range flag
>
struct get
{
  typedef typename get<typename Typelist::tail, Index, Step+1>::type type;
};

We recursively instantiating get<> while increasing the Step value. Now we specialize the above definition to stop the recursion and to handle out of range condition.

//"out of range" specialization
template<
  typename Typelist, 
  int Index,
  int Step,
  bool Stop
>
struct get< Typelist, Index, Step, Stop, true >
{
  //if OutOfRange is 'true' the 'type' is undefined
  //so we'll get a compile-time error
};

//"element found" specialization
template<
  typename Typelist, 
  int Index,
  int Step,
  bool OutOfRange
>
struct get<Typelist, Index, Step, true, OutOfRange >
{
  //the index is equal to the recursion step
  //so the result type is the head of the Typlist and stop!
  typedef typename Typelist::head type;
};

The access time during compilation is O(N). TTL suggests an implementation that has a constant access time independent of the number of elements in the list. However it is not as elegant as this one.

Using the Code

The whole library resides in header files only. There is nothing to be built or installed, just copy the TTL files into one of you folders and and make sure that this folder is in the list of include folders in your compiler. You can then include TTL headers as in the following example.

#include "ttl/meta/typelist.hpp" 

The source contains a simple sample in the samples/test folder. The code has been tested with MSVC v7.1 and GCC v3.2.3

Conclusion

C++ templates is a powerful mechanism for compile-time calculations and meta programming. The recursive instantiation and partial specialization are the corner stones of such methods. What I especially like about compile-time programming is that if the code compiles it usually runs right away. Well, almost...:)

If there is enough interest, in my next article, I'll describe how to implement and use variant. If you are interested, please vote.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
kig
Software Developer (Senior)
United States United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
GeneralMy vote of 5 Pin
paladin_t16-Jan-12 17:08
paladin_t16-Jan-12 17:08 
GeneralGreat stuff!! Pin
faraz0828-Dec-04 3:37
faraz0828-Dec-04 3:37 
GeneralRe: Great stuff!! Pin
kig28-Dec-04 20:48
kig28-Dec-04 20:48 
GeneralRe: Great stuff!! Pin
_faraz29-Dec-04 1:14
_faraz29-Dec-04 1:14 
GeneralRe: Great stuff!! Pin
kig29-Dec-04 8:48
kig29-Dec-04 8:48 
GeneralRe: Great stuff!! Pin
_faraz1-Jan-05 21:55
_faraz1-Jan-05 21:55 
GeneralCompiling with Borland C++ Builder 6 Pin
23-Dec-04 8:24
suss23-Dec-04 8:24 
GeneralRe: Compiling with Borland C++ Builder 6 Pin
kig23-Dec-04 16:02
kig23-Dec-04 16:02 
Generalthere's a way to kill the empty tail Pin
Anonymous21-Sep-04 22:09
Anonymous21-Sep-04 22:09 
GeneralMy problem (cont.) Pin
Chit Zone23-Mar-04 4:35
sussChit Zone23-Mar-04 4:35 
GeneralMy Problem Pin
Chit Zone23-Mar-04 4:30
sussChit Zone23-Mar-04 4:30 
Please help me to slove this.

Problem 1
Array manipulations, Class, Exception, handling, Generic Class.

Design, implement and test a set class in C++ that provides the operations; set membership, set intersection, set union and set difference. An array is to be used to represent a set within a class.

Problem 2
Class, Sorting, Data Structures, Exception handling

Assume that a lecturer teahces on tow modules CO101 and CO102. Use the set class developed in Problem 1 to determine:
a) A list of studends who are taking CO101 but not taking CO102.
b) A list of students who are taking both CO101 and CO102.
c) A list of students who are taking CO101 or CO102 or both. A student's name can only appear once in a list.

Additionally, a user wishes to display each of the above lists in alphabetical order. You are required to use the Quicksort method to sort any of the above lists.

Please Help me before 27th Mar 2004..
GeneralFacinating stuff Pin
fin27-Jan-04 11:00
fin27-Jan-04 11:00 
GeneralRe: Facinating stuff Pin
kig27-Jan-04 11:57
kig27-Jan-04 11:57 
GeneralAbout samples Pin
fin27-Jan-04 13:03
fin27-Jan-04 13:03 
GeneralRe: About samples Pin
kig27-Jan-04 13:34
kig27-Jan-04 13:34 
GeneralGot sucked in... Pin
fin28-Jan-04 13:41
fin28-Jan-04 13:41 
Generalboost::any Pin
Stephen Quattlebaum17-Dec-03 4:13
Stephen Quattlebaum17-Dec-03 4:13 
GeneralRe: boost::any Pin
kig17-Dec-03 7:13
kig17-Dec-03 7:13 
GeneralRe: boost::any Pin
kig17-Dec-03 7:57
kig17-Dec-03 7:57 
GeneralJust love it Pin
Andreas Saurwein11-Dec-03 3:24
Andreas Saurwein11-Dec-03 3:24 
GeneralRe: Just love it Pin
kig11-Dec-03 6:32
kig11-Dec-03 6:32 
GeneralRe: Just love it Pin
Andreas Saurwein11-Dec-03 6:36
Andreas Saurwein11-Dec-03 6:36 
GeneralAll I can say, is, "WOW!!" This is so cool. Pin
WREY11-Dec-03 0:30
WREY11-Dec-03 0:30 
GeneralRe: All I can say, is, &quot;WOW!!&quot; This is so cool. Pin
kig11-Dec-03 6:37
kig11-Dec-03 6:37 
GeneralRe: All I can say, is, &quot;WOW!!&quot; This is so cool. Pin
kig11-Dec-03 6:43
kig11-Dec-03 6:43 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.