C++ templates are a powerful tool that allows you to write generic code that can be used with different data types. One of the less commonly known features of C++ templates is the ability to perform compile-time calculations. This can be very useful in situations where you need to perform calculations that can be determined at compile-time, such as computing the size of an array or a constant value. In this article, we'll explore how to use C++ templates to do compile-time calculations.
What are Compile-Time Calculations?
Compile-time calculations are calculations that can be evaluated at compile-time, rather than at run-time. This means that the value of the calculation is known before the program runs. This can have several advantages, such as avoiding the overhead of performing the calculation at run-time and enabling the compiler to perform optimizations that may not be possible with run-time calculations.
Using C++ Templates for Compile-Time Calculations
To use C++ templates for compile-time calculations, we can define a template class or function that takes one or more arguments and performs the calculation. The result of the calculation is then used as a template parameter, which can be used in other parts of the program.
One commonly used example is to write a function that calculates the power of a number. The following implementation is frequently found in many sources:
template <signed B, unsigned N>
struct pow {
static const int value = B * pow<B, N - 1>::value;
};
template <signed B>
struct pow<B, 0> {
static const int value = 1;
};
int main() {
constexpr auto res = pow<-3, 5>::value;
std::cout << res << std::endl; // output: -243
return 0;
}
In the above implementation, we can see that the base case for the recursion is when N is 0, in which case is handled by the specialization pow<B, 0>.
As we can see, it is tedious and non-intuitive to write a "duplicated" base case. With the help of constexpr keyword and if constexpr support from C++17, we can implement the power function in a more intuitive and concise way, just like writing a normal function.
template <signed B, unsigned N>
constexpr auto pow() {
if constexpr (N == 0) {
return 1;
} else {
return B * pow<B, N - 1>();
}
}
int main() {
constexpr auto res = pow<-3, 5>();
std::cout << res << std::endl; // output: -243
return 0;
}
Furthermore, we can easily evolve the above implementation to make it support the positive/negative power calculation of an integer or a float number. In addition, we can also optimize the algorithm to improve the time complexity from O(N) to O(log N).
template <typename T, signed N>
constexpr T pow(const T base) {
if constexpr (N < 0) {
return 1 / pow<T, -N>(base);
}
if constexpr (N == 0) {
return 1;
}
if constexpr ((N & 1) == 0) {
return pow<T, N / 2>(base * base);
}
return base * pow<T, N / 2>(base * base);
}
int main() {
constexpr auto m = pow<int, 3>(-3);
std::cout << m << std::endl; // output: -27
constexpr auto n = pow<int, -3>(-3);
std::cout << n << std::endl; // output: 0
constexpr auto p = pow<double, 3>(2.5);
std::cout << p << std::endl; // output: 15.625
constexpr auto q = pow<double, -3>(2.0);
std::cout << q << std::endl; // output: 0.125
return 0;
}
Once again, all the calculations mentioned above will be done during the compile-time, which means that in the run-time the program just directly prints the final result.
Now, let's discuss a more complex problem to enhance our understanding of compile-time calculations using templates.
Using constexpr and templates to solve FizzBuzz problem at compile-time
FizzBuzz Problem
It is an easy problem that is commonly used in some tech interviews. The requirement is: write a program that can accept a positive integer N as input, then print out a series of numbers from 1 to N. More specifically, if the number is divisible by 3, then print fizz; if the number is divisible by 5, then print buzz; if the number is divisible by both 3 and 5, then print fizzbuzz.
Solution at run-time
It is trivial to write a solution to solve it at run-time. Below is an example:
std::string nFizzBuzz(const unsigned N) {
if (N % 15 == 0) {
return "fizzbuzz";
} else if (N % 3 == 0) {
return "fizz";
} else if (N % 5 == 0) {
return "buzz";
}
return std::to_string(N);
}
std::string fizzBuzz(const unsigned N) {
if (N == 0) {
return "";
}
std::string str = nFizzBuzzT(1);
for (auto i = 2; i <= N; ++i) {
str += ", " + nFizzBuzz(i);
}
return str;
}
When you call fizzBuzz(16), it will print out:
1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, 11, fizz, 13, 14, fizzbuzz, 16
Solution at compile-time
Implement auxiliary functions for compile-time use
In above solution, we use std::string and std::to_string which involves dynamic memory allocations under the hood. However, in C++17, heap allocations are not allowed in constexpr functions (Sidenote: in C++20, dynamic memory allocations are allowed, that means we can use std::vector and std::string in constexpr context). To solve this issue in C++17, we can manually implement the same functionality using char array.
First thing first, we can use a std::array<char, Size> to represent a string.
template <std::size_t Size>
using chars = std::array<char, Size>;
As we can see, in the naive solution, we use += for string cancatenation. So we also need to implement a concat for our chars. Since the underlying storage of chars is a fixed length array, we need to handle the array copy during the concatenation.
constexpr auto copy(const char* start, const char* end, char* dst) {
while (start < end) {
*dst++ = *start++;
}
}
template <std::size_t N1, std::size_t N2>
constexpr auto concat(const chars<N1>& arr1, const chars<N2>& arr2) {
chars<N1 + N2> res{};
copy(arr1.begin(), arr1.end(), res.begin());
copy(arr2.begin(), arr2.end(), res.begin() + N1);
return res;
}
Then, we need to handle the std::to_string which can convert an integer into a string.
template <unsigned N>
constexpr auto to_chars() {
constexpr char last_digit = '0' + N % 10;
if constexpr (N >= 10) {
return concat(to_chars<N / 10>(), chars<1>{last_digit});
} else {
return chars<1>{last_digit};
}
}
Tackle the FizzBuzz problem at compile-time
Now with all the tools we have on hand, it is straightforward to translate the naive solution into a compile-time one:
template <unsigned N>
constexpr auto nFizzBuzz() {
constexpr chars<4> FIZZ{'f', 'i', 'z', 'z'};
constexpr chars<4> BUZZ{'b', 'u', 'z', 'z'};
if constexpr (N % 15 == 0) {
return concat(FIZZ, BUZZ);
} else if constexpr (N % 3 == 0) {
return FIZZ;
} else if constexpr (N % 5 == 0) {
return BUZZ;
} else {
return to_chars<N>();
}
}
template <unsigned N>
constexpr auto fizzBuzz() {
static_assert(N > 0);
constexpr chars<2> SEPERATOR{',', ' '};
if constexpr (N > 1) {
return concat(fizzBuzz<N - 1>(), concat(SEPERATOR, nFizzBuzz<N>()));
} else {
return nFizzBuzz<N>();
}
}
Conclusion
C++ templates can be used to perform compile-time calculations, which can be very useful in situations where you need to perform calculations that can be determined at compile-time. By defining a template class or function that takes one or more arguments and performs the calculation, you can compute the result at compile-time and use it as a template parameter in other parts of the program. With the help of constexpr keyword and if constexpr support, it is easier for us to write more intuitive and concise code in template metaprogramming. This can lead to more efficient and optimized code, as well as enabling new programming techniques that may not be possible with run-time calculations.
Top comments (0)