It's amazing what you can do with templates, once you learn a few basic techniques.
Motivation
C/C++ provides support for arrays but requires that array dimensions be known at compile time. Often it is convenient to have support for arrays whose dimensions are run-time parameters. The straightforward solution (solution 1) for dynamic-array support is to create an array class which uses allocated memory to hold the elements. To access the elements, you create an indexing function that takes a value for each dimension of the array and calculates an offset from the start of the allocated memory, thereby determining where the array element of interest resides.
For example, consider a two-dimensional array class A2D and an instance theArray. Obtaining element theArray[1][2] might be accomplished using syntax such as theArray(1,2). This approach becomes burdensome if you are replacing static arrays with dynamic ones, since the indexing syntax has to be altered throughout the code. In addition, such an ad hoc solution is hard to reuse.
A more general solution (solution 2) implements the two-dimensional array in the above example as an array of one-dimensional arrays (see [1]). This technique significantly reduces the changes required in your code because it uses operator[] to access the array elements just as with static arrays. Continuing with the above example, an element of theArray would be accessed as theArray[1][2].
This works as follows. If theArray has dimensions 4 and 5, then theArray is really an array of four elements, each of which is an array of five elements. The expression theArray[1] returns the second five-element array, which is then indexed by [2] to return the third element. A set of class declarations for one-, two-, and three-dimensional arrays is shown in Listing 1.
Note that in Listing 1, Array1D, Array2D, and Array3D are very similar. Their most significant difference is in the number of parameters that their respective constructors each take. If the constructor of each ArrayXD takes a pointer to X elements, the differences would be eliminated and each array of dimension X would be implemented in terms of an array of dimension X - 1. This article refers to the lower dimension (X - 1) arrays as subarrays. The repetition of code required for this technique lacks esthetic appeal. It can also be quite tedious and error prone if arrays of higher dimensions are required. The solution to this repetition is template metaprogramming.
Template Metaprogramming
The technique of template metaprogramming uses the compiler as a C++ interpreter and code generator. Metaprogramming can be used to unroll loops and calculate constants [2]. It has even been used to improve the performance of linear-algebra class libraries [3]. A metaprogram is a pattern which the compiler follows to generate code. As an example, consider the metaprogram to generate factorials shown in Listing 2.
In Listing 2, the value of 5! is calculated at compile time. The class Factorial<5> is generated first using:
template<int N> class FactorialTo complete class Factorial<5>, the compiler needs class Factorial<4> which it generates next. This process continues until the compiler needs class Factorial<1>, which you supply as an explicit specialization. This is the general method for metaprogramming - a general case involving a recursive definition, and a terminating case are supplied by the programmer. The compiler generates the intermediate code.
The application of this technique to defining multidimensional arrays is shown in Listing 3. As suggested earlier, the data for the constructor is passed in via the array pdimensions, which is passed to all subarrays so that they may initialize themselves. As in Listing 1, each operator[] returns a reference to an array of the next lower dimensionality SPACE. A three-dimensional array is an array in three space.
This solution creates another problem, however. To create an Array<T, SPACE>, the number of dimension should match SPACE. But this cannot be checked at compile time. It is easy to make a mistake and not provide enough dimension information, especially if code is being modified by someone other than the initial developer. To solve this problem, you can replace the pointer to size_t with an expression template [4].
Expression Templates
Expression templates provide a means for passing expressions to functions. The expression itself is a template class with the template parameter indicating the expression type. The expression type is generated by the compiler - it is the type which gives the expression its functional properties. A basic expression template is shown in Listing 4 as:
template <class E> class ExprTemplate class Expr is a wrapper for more interesting expressions. They can be variables, numbers, binary expressions, etc. The parameter E indicates the expression type. Wrapping other expressions in this way allows you to pass them to a template function such as function foo shown in the listing. Because foo is a template function, the compiler generates a version of foo compatible with the expression being passed into it. Class Expr<E> overloads operator(), which is used to evaluate the expression.
As presented in Listing 4, the evaluation of the expression does not produce anything useful. However it is instructive to see how a call to foo is compiled. In the case of foo(IntExpr(10)), the compiler needs an Expr object to satisfy the foo parameter, and infers that it can make an Expr object from an IntExpr object because the Expr constructor takes a single parameter which can be anything that is a valid template parameter.
Listing 4 also introduces a touple expression (ToupleExpr) and overloads operator<< to create a ToupleExpr object given two IntExpr arguments. (operator<< was chosen as the one to be overloaded because it did not imply any mathematical semantics. You can overload practically any other operator just as well, except for the comma operator. ) The ToupleExpr object is wrapped in an Expr object and returned from the call to operator<<. The call occurs in the argument expression foo(IntExpr(10) << 20). Although there is no operator<<(IntExpr, int), the compiler can make an IntExpr object from 20 and use the available operator<<.
The result of operator<< is an Expr object specifically of type ToupleExpr, which in this case is an aggregate of the two IntExpr objects. The types of the aggregates are template parameters, so the types could be anything, including the types of other ToupleExpr expressions. Evaluation of the expression via operator() involves evaluation of the aggregates, which, at the lowest level, are of type IntExpr. Evaluation of the IntExpr objects prints out the integer values.
Implementation
Listing 5 shows the merging of the three ideas (subarrays, template metaprogramming, and expression templates) into a full implementation of the Array class. The Dim class is a wrapper for a size_t element which represents one dimension of an array. It is analogous to the IntExpr of the previous section. From Listing 4 to Listing 5, the expression templates are enhanced in two ways. The class Expr has an additional template parameter called SPACE which is a count of the number of Dim classes nested in the Expr. It equals the dimensionality of the array.
An operator<<(Expr, Dim) is also added and used to create a touple of Expr and Dim so that constructs like:
Dim(d1) << d2 << d3can be handled. As discussed in the previous section, Dim(d1) << d2 creates an Expr of type ToupleExpr. This is then combined with d3 to create another ToupleExpr. The resulting expression is shown in Figure 1.
Here, the SPACE template parameter of the Expr class is shown as the numbers 2 and 3. In the function operator()<<(const Dim&, const Dim&), SPACE is set to 2. When a Dim is combined with an expression via operator<<(const Expr<>&, const Dim& ), SPACE is incremented, as shown by the return type of that operator. Once the dimension expression is created, it can be passed to the Array constructor.
The Array constructor is a template, parameterized on the type of expression holding the array dimensions, in this case the type is shown in Figure 1. The Array class is parameterized on SPACE, and the constructor is designed to accept only expressions with matching SPACE parameters. This ensures that compilation will pass only if you have provided the correct number of dimensions to the array you are trying to make.
In the Array constructor, the expression must be evaluated at runtime. The evaluation populates an array, called dims, of size_t elements representing the dimensions. Evaluation is done through operator(size_t**) of each of the expression types - Expr, ToupleExpr, and Dim. In the example shown in Figure 1, the outer Expr is evaluated first. This immediately passes evaluation to ToupleExpr, which evaluates its two aggregates. The first aggregate is Expr<ToupleExpr<Dim, Dim>> and the second is Dim. The process is repeated again. Eventually, ToupleExpr<Dim, Dim> evaluates its two aggregates, which are both Dim. In Dim::operator()(size_t** x), the values of the dimension are placed in **x. Next the stack is unwound, and the third Dim::operator() places its value in **x.
Once the dims array is populated, construction of the Array proceeds with allocation of subarrays. This is done with new and the default constructor in the Array class. The subarrays are then initialized via Array::init. Dimension information for the subarrays is passed in via the dims array. The dims array is passed to subarrays as &dims[1] so that each subarray will find its dimension at dims[0].
The default constructor and the function Array::init are private, to protect users from invoking them. Furthermore, they are in an entirely different class from the executing constructor; the constructor of Array<T, SPACE> calls Array<T, SPACE-1>::init. To allow this call, Array<T, SPACE> declares Array<T, SPACE + 1> as its friend.
A sample array is created as shown in the function main of Listing 5:
Array<int, 3> A1(Dim(a)<< b << c);It is used the same as any static array:
A1[a][b][c] = 0;Conclusion
The odd syntax of the array definition, especially the unconventional usage of operator<<(), is compensated for by the ease with which static arrays can be replaced by dynamic arrays. It also ensures that your compiler, and not your client, will find any problems in your dimension data. Some of the concepts described here are somewhat esoteric. However, once you reach the initial "ah-ha," they are not so daunting. Furthermore, the user does not have to know about them. Also, because much of the work is done at compile time, they do not pose any runtime overhead above that of the original solution 2.
A few caveats. There are compiler-imposed limits on generating templates. The compiler I used is the HP aC++ version A.01.06 . It has a template generation nesting limit of 255. For the curious, arrays of SPACE greater than 20 became impractical.
Not all compilers support template member functions or partial template specialization, such as the specialization of:
template<class T, int S> class MyClassto:
template <class T> class MyClass<T, 1>However, with the completion of the ANSI C++ Standard, such features should quickly become commonplace.
Acknowledgments
Thanks to Raj Persaud, Technical Writer, Oasis Technology, for his comments and suggestions.
References
[1] Scott Meyers. More Effective C++ (Addison-Wesley, 1996). Item 30.
[2] Todd Veldhuizen. "Template Metaprograms," C++ Report Vol.7 No.4 (May 1995). Also available through http://monet.uwaterloo.ca/blitz.
[3] Todd Veldhuizen. "Linear Algebra with C++ Template Metaprograms," Dr. Dobb's Journal, August 1996. Also available at http://www.ddj.com/ddj/1996/1996_08/veld.htm.
[4] "Expression Templates," Todd Veldhuizen, C++ Report Vol.7 No.5 (June 1995). Also available through http://monet.uwaterloo.ca/blitz.
Zlatko Marcok has a BASc in Computer Engineering from the University of Waterloo, Canada. He has been developing software for seven years and using object-oriented technology for the last two. His interests are in object-oriented software development and in teaching object technology. He can be reached at zlatko.marcok@bell.ca.