« | (Absolute) Mentality | | Copyrights » |
Recently I have been helping a colleague convert a series of painfully repetitive code segments into function templates and template classes. I respect this colleague very much and he is a very skilled developer, including the use of the C++ Standard Library. However, he has never developed any templates of his own. As I was helping him learn how to develop new templates it occurred to me that there are plenty of fundamental C++ concepts that are given very little attention. This creates an enormous gap in reference material to progress from the competent skill level to proficient and expert levels.
Therefore, I am going to periodically write about fundamental concepts and how to actually apply them to your daily development. This post discusses templates at a very basic level. Entire books have been written about them. I will revisit with more sophisticated applications of templates in the future.
What is a template?
Templates are the basis for generic programming in C++. They are commonly referenced as parameterized-types and they accept parameters. Templates are extremely powerful constructs, but they require practice to benefit from their value.
Templates are also a bit tricky to work with when you first encounter them. They behave as a purely functional sub-language in C++. If you are familiar with function programming techniques, C++ templates may feel a bit more natural to you. Regardless, they open many doors to improve the robustness and quality of your code, and are well worth the time and effort required to use them effectively.
Similar to the usage of a template in the physical world, the final result of a C++ template is not compiled code. An example may be the best way to further explain how template instantiation works:
C++
template <typename T> | |
T sum(const T &lhs, const T &rhs) | |
{ | |
T result(lhs); | |
result += rhs; | |
return result; | |
} |
This example is a simple function that calculates the sum of two input values of the same type, T. This type simply acts as a placeholder for when the actual function is instantiated. With this definition alone, no code is generated. It is the pattern the compiler will use to create the target code when the template is instantiated.
Instantiation
The instantiation of a template is the creation of a template-instance for a specific type. Instantiation only requires the use of the template. In many cases the compiler can deduce the intended type for the template instantiation.
C++
int a = 10; | |
int b = 30; | |
| |
// Instantiates the function template, sum<>(). | |
int c = sum(a,b); |
For the situations where the type may be ambiguous, or you want to be certain of the type instantiated, you can explicitly declare the type during instantiation.
C++
short a = 10; | |
short b = 30; | |
| |
// Explicitly specifies the int type for the instantiation | |
// of the function template, sum<>(). | |
int c = sum<int>(a,b); |
In the previous example, the two values, a
and b
are of type short
. They will be implicitly converted to type int
to match the type of the template instantiation.
Explicit Instantiation
It is possible to force the compiler to generate an instance of a template, even when the instantiation will not be used. This is called explicit instantiation. This is useful for forward declarations and declarations for export from shared libraries. Explicit instantiations are nothing more than declarations with the specified type.
C++
// Explicitly instantiates sum for type short. | |
template short sum<short>(short, short); | |
| |
// Explicitly instantiates and deduces type long. | |
template long sum<>(long, long); | |
| |
// Explicitly instantiates and deduces type double. | |
template double sum(double, double); |
There are many uses for explicit instantiation, and the topic deserves an entire post of its own. I wanted you to be aware of the concept as well as its name. I will revisit this topic another time.
A Compiled Template
We've seen an example of a template, as well as the concept of template instantiation. What actually happens though?
It depends.
Through experience, I believe the simplest way to reason about template substitution is to treat the template type as a placeholder. Then replace each instance of the placeholder with the instantiated type. Our sum
function template instantiated with type int
would look like this:
C++
// template <typename int> | |
int sum(const int &lhs, const int &rhs) | |
{ | |
int result(lhs); | |
result += rhs; | |
return result; | |
} |
In fact, this is how I prefer to get a template working in the first place. I create a working version of the function or class with a specific type, then convert it to a template.
It is important to recognize the different operations that are required by the type used in the template instantiation. Specifically, in the sum
example, support for the operator +=
is required for the function to compile properly. Most of the basic intrinsic types in C++ support this operator. Certainly the int
type supports operator +=
. Consider some of the classes included in the C++ Standard Library, such as std::basic_string
. This class supports operator +=
. Therefore, we could instantiate sum
as follows:
C++
std::basic_string first = "Hello "; | |
std::basic_string second = "World"; | |
| |
std::basic_string result = sum(first, second); | |
std::cout << result ; |
The value assigned to result
is "Hello World".
Unfortunately, this code would not compile if the container classes were used with the template, like list
, map
, or vector
. They do not provide support for this operator.
Header Only
It is not a strict requirement that template definitions are located in a header file. However, it is necessary for the compiler to have access to the entire template definition when a template is to be instantiated. So, if a template definition is only required for a single module, it could be defined entirely in the source file. However, if a template shall be used across modules in your program, it will be necessary to defined the entire implementation within a header file.
Also, take some advice that will make your life simpler: Implement your entire template classes inlined within the class itself. The member function declarations become much simpler to work with, as you don't have to repeatedly define the correct template declaration of the host class.
Parameter Types
Templates are restricted to the types of template parameters that can be processed. Templates can handle:
- Types
- Non-Types
- Template Template-Parameters
Types refer to any type that can be defined, including const/volatile qualifiers.
Non-Types are things like specific values. Rather than declaring a Type-parameter, a variable can be declared instead, such as int
. Non-type values are restricted to constant integral values. This means that floating-point and string literals cannot be used as template arguments. There are tricks to get around the limitations for string literals, which I will save for another time.
Here is a common example that calculates the value of factorial:
C++
template <unsigned int N> | |
struct factorial | |
{ | |
enum | |
{ | |
value = <N * factorial<N-1>:: value; | |
}; | |
}; | |
| |
template <> | |
struct factorial <0> | |
{ | |
enum { value = 1 }; | |
}; |
Notice how a struct is used to contain the value rather than a function. This is because functions are not executed at compile-time. However, the calculation specified in the declaration, value = <* factorial<N-1>:: value
, will be computed by the compiler. This is due to each instantiation is required recursively until the base-case of factorial <0>
is reached. There are two versions of the factorial
. This is called specialization. It allows a template to handle special-cases in a different way than the general implementation. I further discuss specialization in the next section.
Template Template-Parameters are described in a later section.
Template Specialization
Template specialization allows you to define custom implementations of functions or objects for different types. This allows you to create a generic implementation as well as a custom version for types that deviate from the generic behavior. You can think of this as function overloading for template implementations.
There are two types of specialization, full and partial:
- Full-Template Specialization: This is an implementation that specifies a specific template parameter for every parameter of the original template.
- Partial-Template Specialization: This type of specialization only customizes a portion of the template. Only object-templates and member-templates may be partially specialized. Regular function templates can only be fully-specialized.
The Factorial example from the previous section demonstrated specialization. I use partial-template specialization in the Generic Example at the end of this post.
Keyword: class vs typename
One oddity that you may encounter is the usage of two different keywords in template syntax that are roughly equivalent, class
and typename
:
C++
template <typename T> | |
T sum(const T &lhs, const T &rhs) | |
{ | |
// ... | |
} | |
| |
// The class keyword is interchangeable with typename, in most cases. | |
template <class T> | |
T sum(const T &lhs, const T &rhs) | |
{ | |
// ... | |
} |
There are two exceptions where the syntax requires a specific keyword:
- Dependent Types: Require the
typename
keyword to be prepended to the declaration. - Template Template Parameters: Require the
class
keyword to be used in the declaration. However,typename
can be used as well as of C++17.
Let's introduce these two concepts so that you are aware of their existence. I will revisit these topics in detail at another time.
Dependent Types
A dependent type is a type whose definition is dependent upon another type. This could occur in both class and function definitions. There are a few cases in C++, where it becomes necessary to disambiguate the syntax of an expression, dependent types are one of those cases. Suppose we have a function that is passed a std::string
and a global variable, value
:
C++
int value = 0; | |
template <typename T> | |
void example(std::string<T> &str) | |
{ | |
std::string<T>::const_pointer* value; | |
} |
The previous function intended to declare of a new variable, value. However, const_pointer type has not yet been established as a type. Therefore, the compiler interprets this expression as a multiplication of the value 'const_pointer' with the int 'value' defined globally.
This declaration requires a disambiguation for the compiler, to help it identify this new item as a type. The typename
keyword can accomplish this:
C++
int value = 0; | |
template <typename T> | |
void example(std::string<T> &str) | |
{ | |
// Adding 'typename' the declaration will disambiguate | |
// the expression for the compiler. | |
typename std::string<T>::const_pointer* value; | |
} |
Another alternative is to use typedef to declare a new type. This declaration also requires the use of typename
C++
int value = 0; | |
template <typename T> | |
void example(std::string<T> &str) | |
{ | |
typedef typename std::string<T>::const_pointer* ptr_t; | |
| |
// Now, 'ptr_t', has been established as a type to the compiler. | |
// The variable can be declared as: | |
ptr_t value; | |
} |
Template Template-Parameters
Template Template-Parameters is the C++ version of movie Inception. This construct allows you to build a construct that takes both a parameterized-type (template) and a type to complete it's definition. Basically, a template embedded within a template.
Here is an example of template template syntax. Notice the use of the keyword, class
, in the template parameter:
C++
template< size_t index_t, | |
template<size_t> class T | |
> | |
struct accumulate_value | |
{ | |
static const size_t value = T<index_t>::value | |
+ accumulate_value<index_t-1,T>::value; | |
}; | |
| |
template<template<size_t> class T> | |
struct accumulate_value<0,T> | |
{ | |
static const size_t value = T<0>::value; | |
}; |
The previous code is a solution that I created to add the sum for each of the values held in a generic template that contained a set of template-indexed sub-objects. This is actually a meta-template programming solution. I will address that topic at a later time. Template templates are not encountered very often. However, when they are needed, this syntax becomes very useful.
A Generic Example
When working with data that must be portable across different computing platforms, the concept of byte-order or endianess, is important to understand. Some platforms like PowerPC and MIPS use big-endian byte-orders. While architectures like x86 operate on little-endian byte-orders. Big-endian places the largest byte in a word on the left.
Example:
We'll use the number: 287,454,020, which is equivalent to 0x11223344 in hexadecimal:
Broken up into bytes, we have: 0x11, 0x22, 0x33, 0x44. The highest-order byte in 0x11223344 is 0x11. This is how the values will be stored in memory for each endian-type. The orange cells indicate the high-order byte for the specified platform:
Big-endian | | Little-Endian | |||||||||
287,454,020 | |||||||||||
11 | 22 | 33 | 44 | 11 | 22 | 33 | 44 | ||||
1,144,201,745 | |||||||||||
11 | 22 | 33 | 44 | 44 | 33 | 22 | 11 | ||||
287,454,020 |
Network Data Transfer
By convention, network communication protocols usually specify data to be transferred in network byte-order, which is big-endian byte-order. The Berkeley socket implementation (as well as most other socket library implementations) provides a set of functions to help with this conversion process, htons
and htonl
. These functions stand for host-to-network short and host-to-network long, respectively. Some modern implementations provide host-to-network long long, htonll
, for 64-bit integers, but this function is far from standard.
If we had a data structure such as the following:
C++
struct data | |
{ | |
char d1; | |
short d2; | |
long d3; | |
long long d4; | |
unsigned char d5; | |
unsigned short d6; | |
unsigned long d7; | |
unsigned long long d8; | |
}; |
An adequate conversion function to prepare this data for transfer on the network would look like this:
C++
void data_to_network(const data& input, data& output) | |
{ | |
output.d1 = input.d1; | |
output.d2 = htons (input.d2); | |
output.d3 = htonl (input.d3); | |
output.d4 = htonll(input.d4); | |
output.d5 = input.d5; | |
output.d6 = (unsigned short) htons ((short)input.d6); | |
output.d7 = (unsigned long) htonl ((long)input.d7); | |
output.d8 = (unsigned long long) htonll((long long)input.d8); | |
}; |
Code like this is a bit fragile. There is a different function name used to convert each data type. Remember, these are C-library calls. Also, the single-byte values that do not require byte-order conversion, but if the type for these fields is increased in size this code would need to be revisited to add the appropriate conversion function.
We could use function overloading in C++. Simply create a set of functions with the same name for all of the different types, including the single-byte types. That's only 8 functions to implement... Oh, wait! We forgot about the int
variants. Also, how to deal with floating-point types?
This is a perfect fit for a parameterized solution (templates). The only problem is some of the types requires a different conversion implementations. I previously mentioned template specialization. This is the technique we need to employ to solve this problem.
Solution
Let's first start with the base implementation for this template. That would be the conversion function that simply passes the data through to the return value.
C++
template <typename T> | |
T to_network_byte_order(T value) | |
{ | |
return value; | |
} |
Simple.
Now let's create the conversion function for a short
, which is two-bytes in length. We start with a specialized definition for this template:
C++
template <> | |
short to_network_byte_order<short>(short value) | |
{ | |
return htons(value); | |
} |
The only problem is this looks an awfully lot like the implementation if we were to use the overloaded function solution. There are two problems, 1) types are explicitly specified and we wanted to avoid that, 2) we need to address the signed vs. unsigned type specifiers.
So solve this, we can differentiate on the template implementation based on the size of the data type. That is essentially what we did in the first place when we used the htons
function to convert the unsigned short
. This will require a slight modification to the base template.
C++
template <typename T, size_t SizeT> | |
T to_network_byte_order(T value) | |
{ | |
return value; | |
} |
We also want to have something like this for our new version of the short
conversion function:
C++
// This will not compile, why? | |
template <typename T> | |
T to_network_byte_order<T, 2>(T value) | |
{ | |
return htons(value); | |
} |
The problem is, this is called partial specialization and it is not permitted for functions. However, it is allowed for class
and struct
. So we can still achieve our goal with one more adjustment to our strategy. We will now encapsulate our byte-order conversion logic within a member function of a partially-specialized struct
. Then use a top-level template function to construct and call this conversion struct
. Here is the definition of the templated structs.
C++
template <typename T, size_t SizeT> | |
struct Convert | |
{ | |
static T swap(T value) { return value; } | |
}; | |
| |
template <typename T> | |
struct Convert<T, 2> | |
{ | |
static T swap(T value) { return htons(value); } | |
}; | |
| |
template <typename T> | |
struct Convert<T, 4> | |
{ | |
static T swap(T value) { return htonl(value); } | |
}; | |
| |
template <typename T> | |
struct Convert<T, 8> | |
{ | |
static T swap(T value) { return htonll(value); } | |
}; |
Now finally, the top-level function that will access the byte-order conversion logic:
C++
template <typename T, size_t SizeT> | |
T to_network_byte_order(T value) | |
{ | |
return Convert<T, sizeof(T)>::swap(value); | |
} |
What does this solution look like when it is used in our original conversion function:
C++
void data_to_network(const data& input, data& output) | |
{ | |
output.d1 = to_network_byte_order(input.d1); | |
output.d2 = to_network_byte_order(input.d2); | |
output.d3 = to_network_byte_order(input.d3); | |
output.d4 = to_network_byte_order(input.d4); | |
output.d5 = to_network_byte_order(input.d5); | |
output.d6 = to_network_byte_order(input.d6); | |
output.d7 = to_network_byte_order(input.d7); | |
output.d8 = to_network_byte_order(input.d8); | |
}; |
Now, if the data-types are changed during the life of this program, this parameterized implementation will automatically re-compile and adjust to the proper implementation because of this generic implementation.
If only C++ supported reflection, then a function could be written to simply apply the function call, to_network_byte_order
to each member of a class
or struct
. Many efforts are currently under-way to add reflection to C++. I don't know when or if that will happen. Until then, this is the type of problem that my library Alchemy[^] solves.
Summary
Templates are a very powerful tool that is overlooked by many C++ developers. Learning to use the C++ Standard Library is a good start towards increasing your productivity and the reliability of your software. Learning to develop your own robust templates to solve problems for a variety of types will take you to the next level. However, the foreign syntax, functional behavior, and somewhat obscure rules tend to trip up beginners to this aspect of C++ development. This introduction should provide you with the knowledge required to tackle these hurdles. Continue to practice with them and improve your skills. If you have any questions, feel free to post a comment or send me an email.
Recent Comments