Compile Time Data Structure Using Template Meta Programming

1. Introduction

You have seen different applications of template meta-programming such as static data structures [5], algorithms [2][6], design patterns [1][3], reflection [4], expression templates [7], and number theory [8][9]. The Compile Time Data Structure is, in fact, not a new concept in C++. Further information about it can be found [1][5]. Here, you are going to study the link list as an example of a compile-time data structure and try to implement it with template meta-programming.

Template meta-programming is usually difficult to understand at first for those who are not familiar with it; therefore, you will learn about the run-time counterpart at the same time. You used a naming convention, “List,” for all the runtime programs to distinguish with the compile-time version. Although you can implement the run-time programs in more than one way, in the compile-time world you have only recursion to do everything, including looping; therefore, you are going to use recursion in the run-time version too.

2. Compile Time Link List

If you are going to make a single link list, the structure of your link list would be something like this.

///////////////////////////////////////////////////////////
// Node of Runtime Link List
///////////////////////////////////////////////////////////
struct ListNode
{
   int value;
   ListNode* next;
};

Here is the compile-time version of this structure:

///////////////////////////////////////////////////////////
// Termination of Link List
///////////////////////////////////////////////////////////
struct End
{
};

///////////////////////////////////////////////////////////
// Node of Static Link List
///////////////////////////////////////////////////////////
template <int iData, typename Type>
struct Node
{
   enum { value = iData };
   typedef Type Next;
};

Here, you need one more structure to indicate the termination condition of the link list. You also can say it is an end marker. In the run-time version, you don’t need any such concept because, in that case, you simply check the value of next field in the node. If its value is NULL, it means that it is the last node of the link list.

However, in the case of template meta-programming you have to do template specialization (or partial template specialization) to stop the recursion. You can do template specialization for any specific type or for any specific value. Here, you can’t do template specialization on the value because the second template parameter is type. Therefore, you have to create one new type to stop the recursive instantiation of the template. The name of the end marker can be anything and it can be stored whatever you like. In the example, it would be sufficient to make one empty structure to create a new type as an end marker.

Now, try to implement a few auxiliary functions that work on lists. Here is the first function to insert data in the link list. You explicitly made its name look familiar to the member function of STL list class because you are going to implement a few more STL algorithms.

Here is the simplest implementation of how to insert items in a run-time single link list.

///////////////////////////////////////////////////////////
// Insert item into Runtime Link List
///////////////////////////////////////////////////////////
void ListPushBack(ListNode** pHead, int value)
{
   if (*pHead == NULL)
   {
      *pHead = new ListNode();
      (*pHead)->value = value;
   }
   else
   {
      ListPushBack(&(*pHead)->next, value);
   }
}

The name of the link list is prefixed by the “List” word to distinguish it from the compile-time version. Interestingly, the compile-time version of the same function doesn’t use recursion and its implementation is very easy.

///////////////////////////////////////////////////////////
// Insert item into Static Link List
///////////////////////////////////////////////////////////
template <int iData, typename Type>




struct PushBack
{
   typedef Node<iData, Type> staticList;
};

And here is the usage of this function at compile time.

typedef PushBack<2,  End>::staticList   node1;
typedef PushBack<4,  node1>::staticList node2;
typedef PushBack<6,  node2>::staticList node3;
typedef PushBack<8,  node3>::staticList node4;
typedef PushBack<10, node4>::staticList node5;
typedef PushBack<12, node5>::staticList myList;

You can create a static link list in this way:

typedef Node<-15, Node<15, Node<18, Node<13, End> > > > myList;

But the above method to create a static link list has few advantages. You will see these when you implement a few STL algorithms at compile time.

Now, implement another STL list algorithm at compile time, but first, take a look at its run-time version to better understand template meta-programming.

///////////////////////////////////////////////////////////
// Structure to calculate the length of Run-time Link List
///////////////////////////////////////////////////////////
int ListSize(ListNode* pHead)
{
   if (pHead == NULL)
      return 0;
   else
      return 1 + ListSize(pHead->next);
}

This function is quite simple and uses tail recursion for optimization. The compiler can optimize tail recursion with looping to avoid any run-time stack overhead. Here is the compile-time version of the same function.

///////////////////////////////////////////////////////////
// Structure to calculate the length of Static Link List
///////////////////////////////////////////////////////////
template <typename T>
struct Size;

template <int iData, typename Type>
struct Size<Node<iData, Type> >
{
   enum { value = 1 + Size<Type>::value };
};

template <>
struct Size<End>
{
   enum { value = 0 };
};

Although the STL list class doesn’t have an at() function because list doesn’t have a random access iterator, you are trying to implement this function for a link list. Because you can’t access any item of the link list randomly, it is a linear time function, not a constant time, just like the at() function of a vector.

Here is the simple run-time implementation of an at() function on a single link list with linear complexity.

///////////////////////////////////////////////////////////
// Structure to find item from specific location from
// Runtime Link List
///////////////////////////////////////////////////////////
int ListAt(ListNode* pHead, int iPos)
{
   static int iIndex = 0;
   ++iIndex;

   if (iIndex == iPos)
      return pHead->value;
   else if (pHead->next == NULL)
      return -1;
   else
      return ListAt(pHead->next, iPos);
}

The code presented here is just a proof of concept, not production-quality code. One major problem with this function is the return code. If the input position is greater than the length of link list, such as the length of the link list is 4 but you are trying to access the 6th element, this function returns -1. This code is misleading because -1 can be a datum in the link list at a given position so it would be impossible to differentiate whether it is an error code or the actual data at a given position.

This one is a much better implementation than the previous one.

///////////////////////////////////////////////////////////
// Structure to find item from specific location from
// Runtime Link List
///////////////////////////////////////////////////////////
bool ListAt(ListNode* pHead, int iPos, int* iVal)
{
   static int iIndex = 0;
   ++iIndex;

   if (iIndex == iPos)
   {
      *iVal = pHead->value;
      return true;
   }
   else if (pHead->next == NULL)
   {
      return false;
   }
   else
   {
      return ListAt(pHead->next, iPos, iVal);
   }
}

This function returns the value at a specific location by parameter. If the user passes a position that is greater than the length of the link list, it will return false; otherwise, it stores the value at the parameter and returns true.

Here is the usage of this function.

if (pHead != NULL)
{
   int val;

   if (ListAt(pHead, 3, ∓val))
   {
      std::cout << val << std::endl;
   }
}

Here is the compile-time version of the same function.

///////////////////////////////////////////////////////////
// Structure to find item from specific location from
// Static Link List
///////////////////////////////////////////////////////////
template <int iIndex, typename T, int iStart = 0>
struct At;

template <int iIndex, int iData, typename Type, int iStart>
struct At<iIndex, Node<iData, Type>, iStart>
{
   enum { value = iIndex == iStart ? iData : At<iIndex, Type,
      (iStart + 1)>::value };
};

template <int iIndex, int iData, int iStart>
struct At<iIndex, Node<iData, End>, iStart>
{
   enum { value = iIndex == iStart ? iData : -1 };
};

This program has the same problem; it returns -1 when an item is not found. In template meta-programming, you can’t return a value by parameter, just like its run-time equivalent. The solution is to introduce one more enum variable inside the structure to store whether or not the item was found. Here is the next version of the same program.

///////////////////////////////////////////////////////////
// Structure to find item from specific location from
// Static Link List
///////////////////////////////////////////////////////////
template <int iIndex, typename T, int iStart = 0>
struct At;

template <int iIndex, int iData, typename Type, int iStart>
struct At<iIndex, Node<iData, Type>, iStart>
{
   enum { value = iIndex == iStart ? iData : At<iIndex, Type,
      (iStart + 1)>::value };
   enum { found = iIndex == iStart ? 1 : At<iIndex, Type,
      (iStart + 1)>::found };
};

template <int iIndex, int iData, int iStart>
struct At<iIndex, Node<iData, End>, iStart>
{
   enum { value = iIndex == iStart ? iData : -1 };
   enum { found = iIndex == iStart ? 1 : 0 };
};

Although the value variable still stores -1 when an item is not found in the link list, if you use the other variable—the “found” variable—you can ignore this value. Here is the usage of this algorithm.

if (At<8, myList>::found == 1)
{
   std::cout << At<8, myList>::value << std::endl;
}

More by Author

Must Read