Click here to Skip to main content
12,762,098 members (42,681 online)
Click here to Skip to main content
Add your own
alternative version

Tagged as


3 bookmarked
Posted 17 May 2014

Type Lists

, 18 May 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
Type lists

Previously, I had discussed the tuple data type. The tuple is a general purpose container that can be comprised of any sequence of types. Both the types and the values can be accessed by index or traversing similar to a linked list.

The TypeList is a category of types that are very similar to the tuple, except no data is stored within the type list. Whether the final implementation is constructed in the form of a linked list, an array, or even a tree, they are all typically referred to as Typelists. I believe that the Typelist construct is credited to Andrei Alexandrescu. He first published an article in the C/C++ Users Journal, but a more thorough description can be found in his book, Modern C++ Design.

There is No Spoon

What happens when you instantiate a Typelist?


Besides, that's not the point of creating a Typelist container. The overall purpose is to collect, manage, and traverse type information programmatically. Originating with generic programming methods in C++, type lists are implemented with templates. Type lists are extremely simple, and yet can be used to solve a number of problems that would require enormous amounts of hand-written code to solve. I will use the Typelist in my solution for Alchemy.

Let's start by defining a Typelist:

template < typename T, typename U >
struct Typelist
  typedef T        head_t;
  typedef U        tail_t;

There are no data or functions defined in a Typelist, only type definitions. We only need these two elements, because as we saw with the Tuple, more complex sets of types can be created by chaining Typelists together with the tail. Here is an example of more complex Typelist definition:

// Typelist with an 8, 16, 32, and 64 bit integer defined.
  Typelist< char , 
  Typelist< short, 
  Typelist< int, long int > > > integral_t;

When I first saw this, I thought of two things:

  1. How can this be useful, there is no data
  2. The syntax is extremely verbose, I wouldn't want to use that

Remember in The Matrix when Neo goes to meet The Oracle, and he is waiting with the other "potentials"?! While he waits, he watches a young prodigy bending a spoon with his mind. He urges Neo to try, and offers some advice:

Spoon boy: Do not try and bend the spoon. That's impossible. Instead... only try to realize the truth.
Neo: What truth?
Spoon boy: There is no spoon.
Neo: There is no spoon?
Spoon boy: Then you'll see, that it is not the spoon that bends, it is only yourself.

Hmmm, maybe that's a bit too abstract, but, that's pretty much what it's like working with a Typelist. There is no data. Now take your red pill and let's move on.

Simplify the Definition

Let's make the definition simpler to work with. Working with a single Typelist definition of variable length seems much simpler to me than having to enter this repeated nesting of Typelist structures. Something like this:

typedef Typelist< char, short, int, long int > integral_t;
// Or format like a C struct definition:
typedef Typelist
  long int
> integral_t;

This could be usable, and it is easily achieved with template specialization or variadic templates. The solution based on template specialization is much more verbose, however, it is also more portable. I have also seen comments on compiler limits placed on the number of fields supported by variadic templates, but I do not have any personal experience with hitting limits myself. This is something I will probably explore in the future. For now, I will start the implementation with a template specialization solution.


For this type of solution, we must select a maximum number of elements that we want or expect to be used. This is one of the drawbacks of specialization compared to the variadic approach. The forward declaration of the full Typelist would look like this:

template < typename T0, typename T1, ..., typename Tn >
struct Typelist;

We cannot go much further until we resolve the next missing concept.

The Terminator

Similar to a linked-list, we will need some sort of indicator to mark the end of the Typelist. This terminator will also be used in the specialized definitions of Typelist to give us a consistent way to define the large number of definitions that will be created. With meta-programming, we do not have variables, only types and constants. Since a Typelist is constructed entirely from types, we should use a type to define the terminator:

struct empty {};

With a defined terminator, here is what the outer definition for a 10-node Typelist:

template < typename T0,         typename T1 = empty,
           typename T2 = empty, typename T3 = empty,
           typename T4 = empty, typename T5 = empty,
           typename T6 = empty, typename T7 = empty,
           typename T8 = empty, typename T9 = empty >
struct Typelist
  // TBD ...

Here is the outer definition for a specialization with two items:

template < typename T0, typename T1 >
struct Typelist< T0, T1 >
  // TBD ...


Believe it or not, we have already seen the implementation that goes inside of the template definitions shown above. The only exception is we will rename what we previously called a Typelist to a Typenode. Otherwise, the implementation becomes the typedef that we created. By convention, we will name the typedef, type. For reference, constant values are called, value, in template meta-programming. This consistency provides a very generic and compatible way for separate objects that were not designed together, to still inter-operate.

template < typename T, typename U >
struct Typenode
  typedef T        head_t;
  typedef U        tail_t;
// Typelist primary template definition.
template < typename T0,         typename T1 = empty,
           typename T2 = empty, typename T3 = empty,
           typename T4 = empty, typename T5 = empty,
           typename T6 = empty, typename T7 = empty,
           typename T8 = empty, typename T9 = empty >
struct Typelist
  typedef Typenode< T0,
          Typenode< T1,
          Typenode< T2,
          Typenode< T3,
          Typenode< T4,
          Typenode< T5,
          Typenode< T6,
          Typenode< T7,
          Typenode< T8,
          Typenode< T9 > > > > > > > > > >     type;

Here is the implementation for the two node specialization:

template < typename T0, typename T1 >
struct Typelist < T0, T1 >
  typedef Typenode< T0,
          Typenode< T1> >   type;

Simple? Yes. Verbose? Yes. Is it worth it? I believe it will be. Besides, since this definition will be hidden away from users, I would feel comfortable defining some code-generating MACROs to take care of the verbose and repetitive internal definitions. However, I will demonstrate that another time.

Using a Typelist

We have simplified the interface required of the user to define a Typelist, however, interacting with one at this point is still cumbersome. For example, consider the definition of the integral_t Typelist defined above. If we wanted to create a variable using the type in the 3rd slot (index 2, int), this syntax would be required:

integral_t::type::tail_t::tail_t::head_t third_type = 0;

These are the stories that grown-up C programmers tell little C++ programmers growing up to prevent the use of some of the most effective aspects of the language. The next few entries will be focused on extracting data out of the Typelist in a clean and simple way. However, let's tackle one solution right now.

How Many Elements?

Length is a common piece of information that is desired from containers. This is no different for type-containers. How can we determine the number of elements in the integral_t we have been using in this entry? We will write a meta-function. Unfortunately, I have not yet demonstrated many of the techniques in meta-function development. This means we will need to develop a Length function that matches the signature for every specialization that was created for the Typelist definition itself. Otherwise, we could create a meta-function that actively traverses the Typenodes searching for a terminator. We will revisit and solve this problem with a more elegant solution.

The solution will be very simple, and very verbose, but still, very simple. Since we must define a Length implementation for each Typelist specialization that we created, we know in each specialization how many parameters types were defined. We can take advantage of that information to create our simple solution:

template < typename ContainerT >
struct Length;

template <>
struct Length < empty >
  enum { value = 0 };

template < typename T0 >
struct Length < Typelist < T0 > >
  enum { value = 1; }

template < typename T0, typename T1 >
struct Length < Typelist < T0, T1 > >
  enum { value = 2; }

Again, with some preprocessor MACROS, generating all of the variations could be greatly simplified. For now, I would like to get enough infrastructure in place to determine how effective this entire approach will be at solving the goals of Alchemy. Here is a sample that demonstrates querying the number of elements in the integral_t type.

// Calls the meta-function Length
// to get the number of items in integral_t.
size_t count = Length< integral_t >::value;

// count now equals 4


I have now introduced the Typelist meta-programming construct. This is a simple type-only type declaration, which contains quite a bit of untapped potential for us. However, without a basic set of meta-programming constructs to build upon, our only option for implementing the Length meta-function is to resort to one function implementation for the total number of elements that can be held in the Typelist. This is not a very maintainable solution, but it won't be this way for long. I will be introducing a few simple constructs to make decisions based on type at compile-time, in order to create a more elegant and maintainable implementation of Length. From there, I will continue forward and show how to query the type of parameter at a specified index, get the size of that type and many other meta-functions we can use to inspect our new data structure.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Paul M Watt
United States United States
I am a software architect and I have been developing software for nearly two decades. Over the years I have learned to value maintainable solutions first. This has allowed me to adapt my projects to meet the challenges that inevitably appear during development. I use the most beneficial short-term achievements to drive the software I develop towards a long-term vision.

C++ is my strongest language. However, I have also used x86 ASM, ARM ASM, C, C#, JAVA, Python, and JavaScript to solve programming problems. I have worked in a variety of industries throughout my career, which include:
• Manufacturing
• Consumer Products
• Virtualization
• Computer Infrastructure Management
• DoD Contracting

My experience spans these hardware types and operating systems:
• Desktop
o Windows (Full-stack: GUI, Application, Service, Kernel Driver)
o Linux (Application, Daemon)
• Mobile Devices
o Windows CE / Windows Phone
o Linux
• Embedded Devices
o VxWorks (RTOS)
o Greenhills Linux
o Embedded Windows XP

I am a Mentor and frequent contributor to with tutorial articles that teach others about the inner workings of the Windows APIs.

I am the creator of an open source project on GitHub called Alchemy[^], which is an open-source compile-time data serialization library.

I maintain my own repository and blog at[^], because code maintenance does not have to be a living hell.

You may also be interested in...

Comments and Discussions

QuestiontypeList Pin
geoyar19-May-14 16:27
membergeoyar19-May-14 16:27 
AnswerRe: typeList Pin
Paul Watt19-May-14 17:28
mentorPaul Watt19-May-14 17:28 
GeneralRe: typeList Pin
geoyar20-May-14 10:56
membergeoyar20-May-14 10:56 
GeneralRe: typeList Pin
Paul Watt20-May-14 11:41
mentorPaul Watt20-May-14 11:41 

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 | Terms of Use | Mobile
Web02 | 2.8.170217.1 | Last Updated 18 May 2014
Article Copyright 2014 by Paul M Watt
Everything else Copyright © CodeProject, 1999-2017
Layout: fixed | fluid