Compile Time Data Structure Using Template Meta Programming Zeeshan Amjad
[email protected] 1. Introduction We have seen different applications of template meta-programming such as static data structure [5], algorithms [2][6], design pattern [1][3], reflection [4], expression template [7], number theory [8][9]. Compile Time Data Structure is in fact not a new concept in C++. Further information about it can be found in [1][5]. Here we are going to study the link list as an example of compile time data structure and try to implement it with template meta-programming.
Because template meta-programming is usually difficult to understand at first, for those who are not familiar with it; therefore we will discuss the run-time counterpart at the same time. We used a naming convention “List” for all the runtime programs to distinguish is with compile-time version. Although we can implement the run-time programs with more than one ways, but in compile-time world we have only recursion to do everything including looping, therefore we are going to use recursion in run time version too. 2. Compile Time Link List If we are going to make a single link list then our structure of 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 { };
1
/////////////////////////////////////////////////////////// // Node of Static Link List /////////////////////////////////////////////////////////// template struct Node { enum { value = iData }; typedef Type Next; };
Here we need one more structure to indicate the termination condition of the link list. You can also say it is an end marker. In run time version we don’t need any such concept because in that case we simply check the value of next filed in the node. If its value is NULL then it means that it is the last node of the link list. However in case of template meta-programming we have to do template specialization (or partial template specialization) to stop the recursion. We can do template specialization for any specific type or for any specific value. Here we can’t do template specialization on value, because the second template parameter is type. Therefore we have to create one new type to stop the recursive instantiation of template. The name of the end marker can be anything and it can store whatever you like. In our example it would be sufficient to make one empty structure to create a new type as an end marker. Now let’s try to implement few auxiliary functions that work on lists. Here is out first function to insert data in the link list. We explicitly made its name looks familiar to the member function of STL list class, because we are going to implement few more STL algorithm. Here is the simplest implementation of insert items in runtime 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); } }
2
The name of the link list is prefixed by “List” word to distinguish it from compile time version. Interestingly compile time version of the same function doesn’t use recursion and its implementation is very easy. /////////////////////////////////////////////////////////// // Insert item into Static Link List /////////////////////////////////////////////////////////// template struct PushBack { typedef Node staticList; };
And here is the usage of this function at compile time. typedef typedef typedef typedef typedef typedef
PushBack::staticList node1; PushBack::staticList node2; PushBack::staticList node3; PushBack::staticList node4; PushBack::staticList node5; PushBack::staticList myList;
Although we can create static link list from this way typedef Node myList;
But the above method to create static link list has few advantages, which we will see when we are going to implement few STL algorithm in compile-time world. Now let’s implement few more STL list algorithm at compile time, but first take a look at its runtime version to better understand the template meta-programming. /////////////////////////////////////////////////////////// // Structure to calculate the length of Runtime Link List /////////////////////////////////////////////////////////// int ListSize(ListNode* pHead) { if (pHead == NULL) return 0; else return 1 + ListSize(pHead->next); }
3
This function is quite simple and using tail recursion for optimization. Compiler can optimize tail recursion with looping to avoid any runtime stack overhead. Here is the compiletime version of the same function. /////////////////////////////////////////////////////////// // Structure to calculate the length of Static Link List /////////////////////////////////////////////////////////// template struct Size; template struct Size { enum { value = 1 + Size::value }; }; template struct Size { enum { value = 0 }; };
Although STL list class doesn’t have at() function, because list doesn’t have random access iterator, but we are trying to implement this function for link list. Because we can’t access any item of the link list randomly therefore it is a linear time function not a constant time just like the at() function of vector. Here is the simple run-time implementation of at() function on 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); }
4
The code presented here is just a proof of concept not a 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 length of link list is 4 but we are trying to access 6th element then this function returns -1. This code is misleading, because -1 can be a data in the link list at given position so it would be impossible to differentiate weather it is an error code or the actual data at given position. This one is much better implementation than 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 specific location by parameter. If user passes the position that is greater than the length of the link list then it will return false, otherwise it stores the value at the parameter and return true. Here is the usage of this function. if (pHead != NULL) { int val; if (ListAt(pHead, 3, &val)) { std::cout
