Table of Contents
- Introduction
- Using the Code
- Code Walkthrough
- Static Value List - the Base Implementation
- List Construction through Variadic Templates (C++0x only)
- Retrieving a Value Range for List Item Index
- Retrieving the Value Index for a Value
- Inserting a New Item at a Given Item Index
- Checking Whether a Static List is Ascending
- Sorting a List
- Compacting a List
- Run-Time Capabilities
- Code Samples
- Alternatives
- Points of Interest
- Bibliography
- History
There are plenty of constructs around that allow you to construct lists of all sorts at run-time. That's what everybody needs and uses everyday at work. Examples are:
int my_array[5];
std::vector<int> my_vector;
CString s;
This article is (fortunately) not about them as they are plainly boring. It's about value lists that are constructed but also queried at compile time - hence the name "Static Value Lists". Here, the term static is referring to "fixed at compile time" in the same way as in static assertion.
It's not possible to create such a construct with household aids, even with the following definition:
const static int arr[] = {1, 2, 3};
Sure, arr's contents cannot be modified at run-time and can be seen as fixed at compile-time. But they cannot be queried at compile-time (e.g. it's not possible to write something like my_class_template<arr[2]>).
If you are not already familiar with the concept, you'll probably ask "What do I need that for?"
Chances are you don't. There are however things one could do with static value list:
- Calculate Fibonacci numbers at compile-time and store them in a list: In opposition to 42 here the question is known and I would not know anyone who wouldn't like to have as many algorithms as possible at hand for estimating immortal rabbit proliferation.
- In my article "Enumerator Lists and Enumerated Arrays" I'm using the concept (not the same code but I intend to update it in the future) for constructing enumerator lists. By doing this, value safety is improved.
- Provide an introduction to template meta programming (TMP) using something that is well known at run-time as it is done here.
The source code attached to this article has the following structure:
lobster: A header-only library providing a common namespace. Within the folder, header files are contained that can be externally referenced. E.g. including "static_list.h" will load all files required for working with static lists. Therefore this folder is named as additional include folder in the sample code.
static_list: The namespace providing the templates used is explained here ...: Other namespaces that are not discussed here
static_list_sample
source: Contains code files for comparing the samples
enm_demo.h/.cpp: Example for constructing an enumerator list (a static value list indexing enumerators) in C++ enm_demo_0x.h/.cpp: Example for constructing an enumerator list in C++0x. The use of enum class and variadic class templates is shown. It will only be compiled if the LOBSTER_CPP0X definition is present. Please note that VS2008 does not provide the required functionality (VS2010 may work) so I have tested this only using GCC. int_demo.h/.cpp: Example for constructing a static integer list and performing transformations on it. fib_demo.h/.cpp: Example for calculating Fibonacci numbers and storing them in a static value list.
gcc: Batch files for compiling the sample with gcc. The output will be an executable in the same folder. msvc: Workspace and project files for VS2010
When executing the code sample, demonstrations for static value lists named above will be shown. The source code contains BAD_IDEA_X definitions that can be enabled for testing code lines that will (or should not) compile.
The samples will become more clear after the following code walkthrough.
The underlying concept is to create minimal base templates for defining static lists and provide additional functionality in additional templates (see KISS rule). In early versions of this code, I tried to hug functionality together but this tended to get too complicated at the point where I was concerned with class templates embedded in other class templates and deciding who should be whose friends (and template friend declarations will get long).
The only option for creating a metadata (Abrahams2005) list is to doing it by recursion as C++ TMP is purely functional in nature. Basically, all list items have to be stacked on top of each other. At the end of the list, some sort of a list tail is needed. The term "stacked" can be understood in the truest sense of the word here, every operation on it has to start on the top.
Each list item has to provide the following information:
- A reference to its parent list (the stack element it has been constructed on). This is also known as tail (Alexandrescu2001) in type list publications - in opposition to head which then is the list element currently looked at. Please note that this is not the way the word tail is used here.
- An value for the content of this list item. In this solution, I'm actually using two values;
value_first and value_last. This allows to store a range of values inside each list item - and also allow to have only one value in the list item as special case.
Still, we are not complete - e.g. the static list's value type is still missing. As I don't want to define this information for each list item, it is stored in the list tail:
- The
value_type for the stored values is the same for all list items. - The type
comparable_type is presented that can be used as cast target for comparing list item values. Some value types cannot be compared directly (e.g. the C++0x enum class) so its necessary to convert it into something allowing for comparison operators. This type defaults to int which will probably be sufficient for realistic purposes.
An optical representation is given in the following figure:
When seen from the TMP perspective, class templates take over the role of classes and instantiated class templates take the role of objects. The entities shown in the figure are instantiated class templates, but are presented like objects as that is their role here.
Let's have a look at the code for the list item:
template<
typename _parent_type,
typename _parent_type::value_type _value_first,
typename _parent_type::value_type _value_last = _value_first
>
class list_item
{
public:
typedef _parent_type parent_type;
typedef typename _parent_type::value_type value_type;
typedef typename _parent_type::comparable_type comparable_type;
static const value_type value_first = _value_first;
static const value_type value_last = _value_last;
static const int size = parent_type::size + 1;
static const int value_count =
parent_type::value_count
+ (comparable_type) (value_last)
- (comparable_type) (value_first)
+ (comparable_type) (1);
inline static int index_of(value_type e) {
...
}
inline static value_type at(int index) {
...
}
...
private:
list_item() {};
};
As you may have noted, I've already broken the KISS rule mentioned at the begin of the code walkthrough. Besides the mandatory part, this class template contains methods for use at run-time (which are quite convenient on the other hand) but also constructs like size, value_count, value_type and comparable_type. Latter ones could in fact be externalized without any drawback.
The size value stores the number of list items in the list when this list item is seen as head. The value_count contains the number of values in total. Therefore there are two indexes to the list:
- The list item index provides access to a
list_item which represents a range of values. - The value index provides access to a certain value.
The following table demonstrates the difference:
list_item<list_item<list_item<list_tail<int>, 1>, 3, 7>, -11> my_complex_list;
| List Item | List Item | List Item |
| Item Indexes | 0 | 1 | 2 |
|---|
| Value Indexes | 0 | 1, 2, 3, 4, 5 | 6 |
|---|
Values
| 1 | 3, 4, 5, 6, 7 | -11 |
|---|
The tail is simpler and defined in "sl_list_tail.h":
template<typename _value_type, typename _comparable_type = int>
class list_tail {
public:
typedef _value_type value_type;
typedef _comparable_type comparable_type;
static const int size = 0;
static const int value_count = 0;
inline static int index_of(value_type) {
...
}
inline static value_type at(int) {
...
}
};
Static lists are built by embedding list items in each other with a list tail as bottom element:
typedef list_item<list_item<list_item<list_tail<int>, 1>, 2>, 3> my_list;
As typing this is a nuisance, "sl_shortcut.h" and "sl_shortcut_0x.h" (only for C++0x) provide typedefs for simplifying the type creation. Using them the same type can be created more easily by:
typedef list_3<list_tail<int>, 1, 2, 3>::type my_second_list;
typedef var_list<list_tail<int>, 1, 2, 3>::type my_third_list;
The variadic template is discussed in the following section. You might wonder why I left the user to type list_tail into the type definition. This is in order to allow the extension of the list by further wrapping:
typedef list_1<my_list, 4>::type my_extended_list;
By using this approach, static value lists with more than ten values can be constructed even though shortcuts are defined only from list_1 to list_10.
Variadic templates stand out because of the "..." syntax. If you are new to them, an introduction is given by Gregor2006.
The code from "sl_shortcut_0x.h" looks like follows:
template<
typename tail,
typename tail::value_type... args
> struct var_list;
First, the template is only declared (Normally, at this point, the non-specialized behavior could already be defined). This is a best practice when constructing regular templates, but for variadic templates, it is a must-have as GCC 4.5.2 is not able to parse the variadic template code otherwise.
The next step is the template specialization for 2 and more values. This is already a specialization as the variadic template parameter is split into head "v" and tail "args...":
template<
typename tail,
typename tail::value_type v,
typename tail::value_type... args
> struct var_list<
tail,
v,
args...
>
{
typedef typename var_list<list_item<tail, v>, args...>::type type;
};
Another partial specialization for last enumerator (args... is now empty) is needed to stop the recursion:
template<
typename tail,
typename tail::value_type v>
struct var_list<
tail,
v
> {
typedef list_item<tail, v> type;
};
One highlight of this approach is that the items are added to the list in the exact same order as in the basic approach. This is done through the sorting of class templates in this line in the 2+ parameters specialization:
typedef typename var_list<list_item<tail, v>, args...>::type type;
The static value list would have been created in reverse if this line was:
typedef typename list_item<var_list<tail, args...>, v>::type type;
The first value extracted from the variadic template parameters would be the most outward and therefore the last in the result. This actually gives a glance about algorithms in TMP. Given information in form of a type is always final, but it is possible to construct new types on its base.
Still, we cannot do anything with the static value list. So it is time to extend the functionality by providing additional templates. This functionality is usually given by template classes that take the static value list as parameter and contain a public typedef or static const value that contains the result.
Such constructs are known as metafunctions (Abrahams2005).
Before showing the code, I would like to go through a planning stage. Before starting to type, it is necessary to switch from imperative to functional thinking. This is done in a way similar to Alexandrescu2001, chapter 3.6 and following.
Imperatively, we would simply say:
Give me the n-th list item of the list!
Expressing this recursively is not as easy:
Choose depending on the list_item<...>::size
If the current item is the one I want,
return its values
Otherwise go to the parent list item, try again and return
the values delivered from there
Also, we need to define clearly what goes in and what out:
In: Static value list item and the index to this list
Out: The value range at that index represented by list<...>::value_first and list::<...>::value_last.
The input information leads to the template declaration:
template<
typename list,
int index>
struct value_at;
The output information is then used to define the result. This will be a static const list::value_type value_first = ... definition in the template (specialization) body.
Next, for non-trivial decisions at compile-time, helper class templates with different specializations can be used. It is possible to calculate a value within a class template (e.g. using the ? operator which may be used at compile-time), but it is not possible to switch compilations paths inside a template. In order to do this, we let the compiler choose a helper template specialization on base of the ? operator:
template<typename list, int index>
struct value_at
{
static_assert((0 <= index) && (index < list::size),
"index not found in static list");
typedef value_at_helper<list, index, index == list::size - 1> helper;
const static typename list::value_type value_first =
helper::value_first;
const static typename list::value_type value_last =
helper::value_last;
};
As it can be seen, the decision is done by the comparison index == list::size - 1. It decides about which specialization of the helper template class is called. The result is then queried from that specialization.
Helper templates typically take the same parameters as the main template plus the decision parameter. For binary decisions, a Boolean value is sufficient. (For more complex decisions, I prefer enumerations.) Therefore, the helper template has the following declaration:
template<
typename list,
int index,
bool index_found
> struct value_at_helper;
The declaration is followed by the two specializations, one for each case:
template<
typename parent,
typename parent::value_type v1,
typename parent::value_type v2,
int index
> struct value_at_helper<
list_item<parent, v1, v2>,
index,
false
> {
const static typename parent::value_type value_first =
value_at<parent, index>::value_first;
const static typename parent::value_type value_last =
value_at<parent, index>::value_last;
};
This specialization is used for propagating the index comparison to the parent. Therefore, it extracts the parent type from the given static list in the specialization definition and calls value_at<...> for that.
template<typename list, int index>
struct value_at_helper<
list,
index,
true
> {
const static typename list::value_type value_first =
list::value_first;
const static typename list::value_type value_last =
list::value_last;
};
This specialization is used when the index searched for is found. It returns the values associated with the list template parameter. The result is propagated while the recursion unwinds.
The whole construct can be seen as one metafunction. It is e.g. called through:
const static int i1 = value_at<my_list, 3>::value_first;
const static int i2 = value_at<my_list, 3>::value_last;
As it can be seen here, it is permissible for metafunctions to have multiple return values.
The combination of main template class and helper template class is a pattern that is found in some functions this library. It is not the only option and in many cases only one template class with different specializations is required. In the source file, a disabled section (LOBSTER_INDEX_OF_BAD_ALTERNATIVE) is found that tries to handle the recursion in one base template. If you try to make it work, you will note that there will be serious obstacles.
For the new operation, we repeat the process of defining input and outputs - and then define the functional algorithm:
In: The list and a value
Out: The value index of the given value
The algorithm can be formulated as follows:
Choose depending of value range of current list item
If the one containing the given value,
return its value index
Otherwise acquire its parent type and return the
value index delivered by it
The template class declaration is almost the same as for value_at:
template<
typename this_type,
typename this_type::value_type test_value
> struct value_index_of;
In the implementation, the helper template is replaced by a bottom plug returning -1 if a value is not found in the list:
template<
typename value_type,
value_type test_value
>
struct value_index_of<
list_tail<value_type>,
test_value>
{
enum {
value = -1
};
};
This specialization aborts the search if the list tail is found and returns -1. Also, the return type is different here. While above, I have used static const qualifiers to create a compile-time value, here the same is done using an enumeration providing only one value. From the outside, both methods look almost the same. Though the enumeration approach is often seen in examples and also a bit briefer, I tend to prefer the qualifier way. E.g. for value_at, it is necessary to have the correct type for the return values, otherwise the user would have to cast it back.
As long as the correct index is not found, the search is continued by recursively calling this specialization:
template<
typename _parent_type,
typename _parent_type::value_type value_first,
typename _parent_type::value_type value_last,
typename _parent_type::value_type value_test
>
struct value_index_of<
list_item<_parent_type, value_first, value_last>,
value_test>
{
typedef typename _parent_type::comparable_type comparable_type;
enum {
value = ((comparable_type) (value_first) <= (comparable_type) (value_test))
&& ((comparable_type) (value_test) <= (comparable_type) (value_last))
?
_parent_type::size + (comparable_type) (value_test) -
(comparable_type) (value_first)
:
index_of<_parent_type, value_test>::value
};
};
Now the comparable_type is placed into action in order to allow the comparison of types otherwise not comparable by <=. Again, the specialization deducts the parent list item, but also the value range for this list item. As it can be seen, the return value is not the list item index, but the value index. As a result, all value indexes of a list are indexed through 0 <= index_of<list, value>::type <= list::value_count.
As it also can be seen, in the context of this section (and also the previous one where it is used), the helper template is not necessary. Decision and return value calculation can be done in one step when the metafunction recursion always stops at a fixed item index (here 0 - indicated through reaching the tail).
Inserting items is a typical run-time list operation which I also want to have in my static list. The full imperative description of the operation is as follows:
An item is inserted into a static list at a given item index. If the index is 0, the new list item will be the first item in the list. If the index is not present in the list, the new item will be appended at the end of the list.
In: The original list, the insertion item index and the value range that the new item should carry
Out: The updated list (The old list will have to stay as compile-time objects are immutable by nature).
Inputs and output define the following main template declaration:
template<
typename list_item,
int idx,
typename list_item::value_type new_value_first,
typename list_item::value_type new_value_last = new_value_first
> struct list_insert_at;
Translated into functional speech, the code will resemble this:
Choose depending on the presence of the insertion position in the static list:
If the insertion position is reached, create the new list
item on top of it
If the insertion position is not yet reached, traverse
further into the list
If the insertion position is not inside the list, simply
append the new item at the end of the list
As it can be seen, 2 decision options will not be sufficient here. Therefore, I will use an enumeration to visualize the different options:
enum index_pos {
index_equals,
index_in_range,
index_out_of_range
};
This will make the main template which analyzes the position a bit more complex, but the helper template approach stays the same as in 3.3:
template<
typename list_item,
typename list_item::value_type new_value_first,
typename list_item::value_type new_value_last,
int idx,
index_pos index_tag
> struct list_insert_at_switch;
...
template<
typename list,
int idx,
typename list::value_type new_value_first,
typename list::value_type new_value_last
> struct list_insert_at
{
const static index_pos ip =
idx == list::size - 1 ? index_equals :
idx >= list::size ? index_out_of_range :
idx < 0 ? index_out_of_range :
index_in_range;
typedef typename list_insert_at_switch<
list,
new_value_first,
new_value_last,
idx,
ip
>::type type;
};
Again, the implementation of the helper template specialization remains:
#pragma region "list_insert_at_switch<..., index_in_range>"
template<
typename parent_list,
typename parent_list::value_type parent_value_first,
typename parent_list::value_type parent_value_last,
typename parent_list::value_type new_value_first,
typename parent_list::value_type new_value_last,
int idx
> struct list_insert_at_switch<
list_item<parent_list, parent_value_first, parent_value_last>,
new_value_first,
new_value_last,
idx,
index_in_range
> {
typedef list_item<
typename list_insert_at<parent_list, idx, new_value_first, new_value_last>::type,
parent_value_first,
parent_value_last
> type;
};
#pragma endregion
#pragma region "list_insert_at_switch<..., index_equals>"
template<
typename parent_list,
typename parent_list::value_type parent_value_first,
typename parent_list::value_type parent_value_last,
typename parent_list::value_type new_value_first,
typename parent_list::value_type new_value_last,
int idx
> struct list_insert_at_switch<
list_item<parent_list, parent_value_first, parent_value_last>,
new_value_first,
new_value_last,
idx,
index_equals
> {
typedef list_item<
list_item<parent_list, new_value_first, new_value_last>,
parent_value_first,
parent_value_last
> type;
};
#pragma endregion
#pragma region "list_insert_at_switch<..., index_out_of_range>"
template<
typename list,
typename list::value_type new_value_first,
typename list::value_type new_value_last,
int idx
> struct list_insert_at_switch<
list,
new_value_first,
new_value_last,
idx,
index_out_of_range
> {
typedef list_item<
list,
new_value_first,
new_value_last
> type;
};
#pragma endregion
There are many algorithms that may be performed on lists, I'm picking this simple one in "sl_is_ascending.h" as exemplatory one.
In: The list to test
Out: A boolean containing true if the list is ascending, and false otherwise
This results in the following declaration:
template<typename list> struct is_ascending;
The algorithm can be written recursively as:
Choose depending on if the first list item is reached
If it is,
return true only if its last value is higher
than its first one
Otherwise return true only if the parent list
is ascending, the last value in this item
is higher equal than the first and the first
value in this list higher than the last of
the parent list item
This can be implemented straight-forward without using a helper class template:
template<
typename list,
typename list::value_type parent_value_first,
typename list::value_type parent_value_last,
typename list::value_type value_first,
typename list::value_type value_last
> struct is_ascending<
list_item<
list_item<
list,
parent_value_first,
parent_value_last
>,
value_first,
value_last
>
> {
typedef list_item<
list,
parent_value_first,
parent_value_last
> parent_type;
typedef typename parent_type::comparable_type comparable_type;
const static bool value =
is_ascending<parent_type>::value
&& ((comparable_type) (value_first) > (comparable_type) (parent_value_last))
&& ((comparable_type) (value_last) >= (comparable_type) (value_first));
};
template<
typename value_type,
value_type value_first,
value_type value_last,
typename comparable_type
> struct is_ascending<
list_item<
list_tail<
value_type,
comparable_type
>,
value_first,
value_last
>
> {
const static bool value = ((comparable_type) (value_last) >=
(comparable_type) (value_first));
};
In this code sample, the importance and complexity of the template specialization headers become very clear - they are not only used to define types and values they are applied to but also the only way to access those in the body of the specialization. It takes time to familiarize with the way information is presented here and it even takes time to locate the template class name in such a header.
Due to the extent of parameters, their mandatory declaration before the class naming and the specialization definition afterwards, I have decided to separate each parameter on its own line of code and use indentation to visualize the level of template wrapping.
When it is possible to test whether a static value list is ascending, it is also possible to sort it in that way. The code in "sl_sort_ascending.h" is way simpler than the previous code samples because it uses the other templates list_insert_at (see 3.5) and list_find_insert_pos ("sl_find_insert_pos.h"). Latter one works similar to 3.5.
At this point, I will not dive into the implementation - as though being complex it will not add anything new to explain. For the template user, sorting a list is as simple as writing this (example taken from "enm_demo.cpp"):
typedef sort_ascending<weekdays>::type sorted_weekdays;
When a static list is constructed using the list_N or var_list templates, each list item carries only one value. This is good for safety reasons (as each list item has to be explicitly named and therefore no other values may slip in) but may result in performance drags in run-time as the value access time there has the order of N. Therefore, it would be nice to be able to compact a list - which is done by the following line of code (example taken from "enm_demo.cpp"):
typedef compact<weekdays>::type compacted_weekdays;
This will create a new static list joining all adjacent values as long as the increment direction stays the same.
The following code samples make use of the "sl_to_string.h" functionality in order to output the contents of a static list to the console. This is mainly a debugging and demonstration feature. E.g. the following line is used in "enm_demo.cpp" calls the COUT_INFO macro to first output the to_string function template itself as headline and then output its result.
COUT_INFO(to_string<workdays>().c_str());
This call will output the following:
to_string<workdays>().c_str()
-----------------------------
List Item Start End
0: 1 -> 1
1: 2 -> 2
2: 3 -> 3
3: 4 -> 4
4: 5 -> 5
Another run-time capability is the ability to iterate through a static list using a close resemblance of STL iterators provided by "sl_list_iterator.h". In the samples, this functionality is not used at all, even to_string uses compile-time recursion to iterate through the list items of a list.
If run-time iteration was to be used, it would look like follows (compressed_weekdays is found in "enm_demo.cpp"):
for (compressed_weekdays::const_iterator it = compressed_weekdays::begin();
it != compressed_weekdays::end();
it++)
{
std::cout << *it << std::endl;
}
enm_demo.h/.cpp
Creating a static list containing enumerators using the list_N template, inserting further items to that list, sorting and compacting is shown.
enm_demo_0x.h/.cpp
Creating a static list containing enumerators from a C++0x enum class enumeration is shown. Also, the variadic template var_list (see 3.2) is used instead of list list_N. This sample can only be compiled using GCC as VC++ 2010 does not support variadic templates.
int_demo.h/.cpp
A demonstration using int as base type instead of an enumeration.
fib_demo.h/.cpp
A list of Fibonacci numbers is generated and stored in a static list. Don't think that it will bring any benefit in compilation time to a plain recursive solution not using a static list. Each new value is stored by the compiler in a new type that will only be generated once, anyway.
That is clearly a difference to run-time Fibonacci calculation, where avoiding pre-storing results in almost infinite calculation time for N of about value 40.
As a result, using a static list to cache Fibonacci temporary results does not bring any benefit.
Static value lists do not have to be designed from scratch. E.g. static value lists can be implemented on the base of type lists that are provided by the C++ TR1 extension, C++0x, Loki or the Boost libraries. The idea is to provide a type list with types that represent values. For that, an int2type template can be used as described in Alexandrescu2001.
The Boost Meta-Programming Library (MPL) already provides templates for creating static value lists on the base of Boost type lists, there the feature is called integral sequence wrappers. An introduction can be found in Abrahams2005, chapter 3. Chapter 4 then deals with integral type wrappers.
There's one thing I found out: When it comes to TMP, some basic rules of programming are more important than ever:
KISS (Keep It Simple + Self-Insult of your choice beginning on "S"): When template programming, keep it as simple as possible. Never use constructs more complicated than necessary. In regular programming, one usually gets away with that but here it will cost substantial development time and may provide no gain at all.
Divide et Impera: Separate functionality as far as possible. As done in 3.7, using sub-functions creates code units that can be individually tested (even if they are used only in one context) - which is a big advantage if you only have poor debugging options.
- David Abrahams, Aleksey Gurtovoy. 2005. C++ template metaprogramming: concepts, tools, and techniques from boost and beyond
- Douglas Gregor, Jaakko Jarvi, Gary Powell. 2005. Variadic Templates (Revision 3) (Document n2080 on open-std.org)
- Andrei Alexandrescu. 2001. Modern C++ Design: Generic Programming and Design Patterns Applied
