Click here to Skip to main content
Click here to Skip to main content

Tiny Template Library: implementing typelist

By , 10 Dec 2003
Rate this:
Please Sign up or sign in to vote.

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...Smile | :)

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

About the Author

kig
Web Developer
United States United States
No Biography provided

Comments and Discussions

 
GeneralMy vote of 5 Pinmemberpaladin_t16-Jan-12 17:08 
GeneralGreat stuff!! Pinsuss_faraz28-Dec-04 3:37 
GeneralRe: Great stuff!! Pinmemberkig28-Dec-04 20:48 
GeneralRe: Great stuff!! Pinmember_faraz29-Dec-04 1:14 
GeneralRe: Great stuff!! Pinmemberkig29-Dec-04 8:48 
GeneralRe: Great stuff!! Pinmember_faraz1-Jan-05 21:55 
GeneralCompiling with Borland C++ Builder 6 PinmemberT11723-Dec-04 8:24 
GeneralRe: Compiling with Borland C++ Builder 6 Pinmemberkig23-Dec-04 16:02 
Generalthere's a way to kill the empty tail PinsussAnonymous21-Sep-04 22:09 
GeneralMy problem (cont.) PinsussChit Zone23-Mar-04 4:35 
GeneralMy Problem PinsussChit Zone23-Mar-04 4:30 
GeneralFacinating stuff Pinmemberfin27-Jan-04 11:00 
GeneralRe: Facinating stuff Pinmemberkig27-Jan-04 11:57 
GeneralAbout samples Pinmemberfin27-Jan-04 13:03 
GeneralRe: About samples Pinmemberkig27-Jan-04 13:34 
GeneralGot sucked in... Pinmemberfin28-Jan-04 13:41 
Generalboost::any PinmemberStephen Quattlebaum17-Dec-03 4:13 
GeneralRe: boost::any Pinmemberkig17-Dec-03 7:13 
Glad you like it!
 
Well, boost::any is quite different from variant.
Just to list a few differences:
boost::any can hold *any* type, so it doesn't provide
the level of type safety that variant does.
Obviously boost::any cannot support visitors.
 
Actually AFAICT, the next release of boost will
include boost::variant that has almost the same
interface as ttl::variant.
If you download the boost sources from CVS
you can take a look at it.
In fact I used the boost::variant semantic
in my variant.
You can see the description of ttl::variant vs. boost::variant (to be released)at
http://tinytl.sourceforge.net/#variant

GeneralRe: boost::any Pinmemberkig17-Dec-03 7:57 
GeneralJust love it PinmemberSaurweinAndreas11-Dec-03 3:24 
GeneralRe: Just love it Pinmemberkig11-Dec-03 6:32 
GeneralRe: Just love it PinmemberSaurweinAndreas11-Dec-03 6:36 
GeneralAll I can say, is, "WOW!!" This is so cool. PinmemberWREY11-Dec-03 0:30 
GeneralRe: All I can say, is, &quot;WOW!!&quot; This is so cool. Pinmemberkig11-Dec-03 6:37 
GeneralRe: All I can say, is, &quot;WOW!!&quot; This is so cool. Pinmemberkig11-Dec-03 6:43 

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

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

| Advertise | Privacy | Mobile
Web01 | 2.8.140415.2 | Last Updated 11 Dec 2003
Article Copyright 2003 by kig
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid