Click here to Skip to main content
13,864,522 members
Click here to Skip to main content
Add your own
alternative version


37 bookmarked
Posted 10 Dec 2003

Tiny Template Library: implementing typelist

, 10 Dec 2003
Rate this:
Please Sign up or sign in to vote.
An article on how to implement compile time lists of types, typelist. Typelists are useful for generic and meta programming.


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.


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;

  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:



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 {};


  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 {};


  typename T1=empty, 

  typename T2=empty, 

  typename T3=empty, 

  typename T4=empty,

  typename T5=empty 

> struct typelist;


  typename T1, 

  typename T2, 

  typename T3, 

  typename T4,

  typename T5 

struct typelist
  typedef T1 head;
  typedef typelist< T2, T3, T4, T5 > tail;
    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.

struct typelist< empty, empty, empty, empty >
    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.


  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

  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

  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


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.


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


About the Author

Software Developer (Senior)
United States United States
No Biography provided

You may also be interested in...


Comments and Discussions

GeneralMy vote of 5 Pin
paladin_t16-Jan-12 18:08
memberpaladin_t16-Jan-12 18:08 
GeneralGreat stuff!! Pin
faraz0828-Dec-04 4:37
memberfaraz0828-Dec-04 4:37 
GeneralRe: Great stuff!! Pin
kig28-Dec-04 21:48
memberkig28-Dec-04 21:48 
GeneralRe: Great stuff!! Pin
_faraz29-Dec-04 2:14
member_faraz29-Dec-04 2:14 
GeneralRe: Great stuff!! Pin
kig29-Dec-04 9:48
memberkig29-Dec-04 9:48 
GeneralRe: Great stuff!! Pin
_faraz1-Jan-05 22:55
member_faraz1-Jan-05 22:55 
GeneralCompiling with Borland C++ Builder 6 Pin
23-Dec-04 9:24
suss23-Dec-04 9:24 
GeneralRe: Compiling with Borland C++ Builder 6 Pin
kig23-Dec-04 17:02
memberkig23-Dec-04 17:02 
Generalthere's a way to kill the empty tail Pin
Anonymous21-Sep-04 23:09
memberAnonymous21-Sep-04 23:09 
GeneralMy problem (cont.) Pin
Chit Zone23-Mar-04 5:35
sussChit Zone23-Mar-04 5:35 
GeneralMy Problem Pin
Chit Zone23-Mar-04 5:30
sussChit Zone23-Mar-04 5:30 
GeneralFacinating stuff Pin
fin27-Jan-04 12:00
memberfin27-Jan-04 12:00 
GeneralRe: Facinating stuff Pin
kig27-Jan-04 12:57
memberkig27-Jan-04 12:57 
GeneralAbout samples Pin
fin27-Jan-04 14:03
memberfin27-Jan-04 14:03 
GeneralRe: About samples Pin
kig27-Jan-04 14:34
memberkig27-Jan-04 14:34 
GeneralGot sucked in... Pin
fin28-Jan-04 14:41
memberfin28-Jan-04 14:41 
Generalboost::any Pin
Stephen Quattlebaum17-Dec-03 5:13
memberStephen Quattlebaum17-Dec-03 5:13 
GeneralRe: boost::any Pin
kig17-Dec-03 8:13
memberkig17-Dec-03 8:13 
GeneralRe: boost::any Pin
kig17-Dec-03 8:57
memberkig17-Dec-03 8:57 
GeneralJust love it Pin
Andreas S. Franci Gonçalves11-Dec-03 4:24
professionalAndreas S. Franci Gonçalves11-Dec-03 4:24 
GeneralRe: Just love it Pin
kig11-Dec-03 7:32
memberkig11-Dec-03 7:32 
GeneralRe: Just love it Pin
Andreas S. Franci Gonçalves11-Dec-03 7:36
professionalAndreas S. Franci Gonçalves11-Dec-03 7:36 
GeneralAll I can say, is, "WOW!!" This is so cool. Pin
WREY11-Dec-03 1:30
memberWREY11-Dec-03 1:30 
GeneralRe: All I can say, is, &quot;WOW!!&quot; This is so cool. Pin
kig11-Dec-03 7:37
memberkig11-Dec-03 7:37 
GeneralRe: All I can say, is, &quot;WOW!!&quot; This is so cool. Pin
kig11-Dec-03 7:43
memberkig11-Dec-03 7: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.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web04 | 2.8.190214.1 | Last Updated 11 Dec 2003
Article Copyright 2003 by kig
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid