C++ Templates: The Complete Guide The Basics

C++ Templates: The Complete Guide The Basics This part introduces the general concept and language features of C++ templates. It starts with a discussion of the general goals and concepts by showing examples of function templates and class templates. It continues with some additional fundamental template techniques such as nontype template parameters, the keyword typename, and member templates. It ends with some general hints regarding the use and application of templates in practice. This introduction to templates is also partially used in Nicolai M. Josuttis's book Object-Oriented Programming in C++, published by John Wiley and Sons Ltd, ISBN 0-470-84399-3. This book teaches all language features of C++ and the C++ standard library and explains their practical usage in a step-by-step tutorial. Why Templates? C++ requires us to declare variables, functions, and most other kinds of entities using specific types. However, a lot of code looks the same for different types. Especially if you implement algorithms, such as quicksort, or if you implement the behavior of data structures, such as a linked list or a binary tree for different types, the code looks the same despite the type used. If your programming language doesn't support a special language feature for this, you only have bad alternatives: You can implement the same behavior again and again for each type that needs this behavior. You can write general code for a common base type such as Object or void*. You can use special preprocessors. If you come from C, Java, or similar languages, you probably have done some or all of this before. However, each of these approaches has its drawbacks: If you implement a behavior again and again, you reinvent the wheel. You make the same mistakes and you tend to avoid complicated but better algorithms because they lead to even more mistakes. If you write general code for a common base class you lose the benefit of type checking. In addition, classes may be required to be derived from special base classes, which makes it more difficult to maintain your code. If you use a special preprocessor such as the C/C++ preprocessor, you lose the advantage of formatted source code. Code is replaced by some "stupid text replacement mechanism" that has no idea of scope and types. Templates are a solution to this problem without these drawbacks. They are functions or classes that are written for one or more types not yet specified. When you use a template, you pass the types as arguments, explicitly or implicitly. Because templates are language features, you have full support of type checking and scope. In today's programs, templates are used a lot. For example, inside the C++ standard library almost all code is template code. The library provides sort algorithms to sort objects and values of a specified type, data structures (so-called container classes) to manage elements of a specified type, strings for which the type of a character is parameterized, and so on. However, this is only the beginning. Templates also allow us to parameterize behavior, to optimize code, and to parameterize information. This is covered in later chapters. Let's first start with some simple templates. Function Templates This chapter introduces function templates. Function templates are functions that are parameterized so that they represent a family of functions. A First Look at Function Templates Function templates provide a functional behavior that can be called for different types. In other words, a function template represents a family of functions. The representation looks a lot like an ordinary function, except that some elements of the function are left undetermined: These elements are parameterized. To illustrate, let's look at a simple example. 2.1.1 Defining the Template The following is a function template that returns the maximum of two values: // basics/max.hpp template <typename T> inline T const& max (T const& a, T const& b) { // if a < b then use b else use a return a<b?b:a; } This template definition specifies a family of functions that returns the maximum of two values, which are passed as function parameters a and b. The type of these parameters is left open as template parameter T. As seen in this example, template parameters must be announced with syntax of the following form: template < comma-separated-list-of-parameters > In our example, the list of parameters is typename T. Note how the less-than and the greater-than symbols are used as brackets; we refer to these as angle brackets. The keyword typename introduces a so-called type parameter. This is by far the most common kind of template parameter in C++ programs, but other parameters are possible, and we discuss them later (see Chapter 4). Here, the type parameter is T. You can use any identifier as a parameter name, but using T is the convention. The type parameter represents an arbitrary type that is specified by the caller when the caller calls the function. You can use any type (fundamental type, class, and so on) as long as it provides the operations that the template uses. In this case, type T has to support operator < because a and b are compared using this operator. For historical reasons, you can also use class instead of typename to define a type parameter. The keyword typename came relatively late in the evolution of the C++ language. Prior to that, the keyword class was the only way to introduce a type parameter, and this remains a valid way to do so. Hence, the template max() could be defined equivalently as follows: template <class T> inline T const& max (T const& a, T const& b) { // if a < b then use b else use a return a<b?b:a; } Semantically there is no difference in this context. So, even if you use class here, any type may be used for template arguments. However, because this use of class can be misleading (not only class types can be substituted for T), you should prefer the use of typename in this context. Note also that unlike class type declarations, the keyword struct cannot be used in place of typename when declaring type parameters. 2.1.2 Using the Template The following program shows how to use the max() function template: // basics/max.cpp #include <iostream> #include <string> #include "max.hpp" int main() { int i = 42; std::cout << "max(7,i): " << ::max(7,i) << std::endl; double f1 = 3.4; double f2 = -6.7; std::cout << "max(f1,f2): " << ::max(f1,f2) << std::endl; std::string s1 = "mathematics"; std::string s2 = "math"; std::cout << "max(s1,s2): " << ::max(s1,s2) << std::endl; } Inside the program, max() is called three times: once for two ints, once for two doubles, and once for two std::strings. Each time, the maximum is computed. As a result, the program has the following output: max(7,i): 42 max(f1,f2): 3.4 max(s1,s2): mathematics Note that each call of the max() template is qualified with ::. This is to make sure that our max() template is found in the global namespace. There is also an std::max() template in the standard library, which under some circumstances may be called or may lead to ambiguity. [1] [1] For example, if one argument type is defined in namespace std (such as strings), according to the lookup rules of C++, both the global and the std max() template are found. Normally, templates aren't compiled into single entities that can handle any type. Instead, different entities are generated from the template for every type for which the template is used. [2] Thus, max() is compiled for each of these three types. For example, the first call of max() [2] The "one-entity-fits-all" alternative is conceivable but rare in practice. All language rules are based on the concept that different entities are generated. int i = 42; … max(7,i) … uses the function template with int as template parameter T. Thus, it has the semantics of calling the following code: inline int const& max (int const& a, int const& b) { // if a < b then use b else use a return a<b?b:a; } The process of replacing template parameters by concrete types is called instantiation. It results in an instance of a template. Unfortunately, the terms instance and instantiate are used in a different context in object-oriented programming—namely, for a concrete object of a class. However, because this book is about templates, we use this term for the "use" of templates unless otherwise specified. Note that the mere use of a function template can trigger such an instantiation process. There is no need for the programmer to request the instantiation separately. Similarly, the other calls of max() instantiate the max template for double and std::string as if they were declared and implemented individually: const double& max (double const&, double const&); const std::string& max (std::string const&, std::string const&); An attempt to instantiate a template for a type that doesn't support all the operations used within it will result in a compile-time error. For example: std::complex<float> c1, c2; // doesn't provide operator < … max(c1,c2); // ERROR at compile time Thus, templates are compiled twice: Without instantiation, the template code itself is checked for correct syntax. Syntax errors are discovered, such as missing semicolons. At the time of instantiation, the template code is checked to ensure that all calls are valid. Invalid calls are discovered, such as unsupported function calls. This leads to an important problem in the handling of templates in practice: When a function template is used in a way that triggers its instantiation, a compiler will (at some point) need to see that template's definition. This breaks the usual compile and link distinction for ordinary functions, when the declaration of a function is sufficient to compile its use. Methods of handling this problem are discussed in Chapter 6. For the moment, let's take the simplest approach: Each template is implemented inside a header file by using inline functions. Argument Deduction When we call a function template such as max() for some arguments, the template parameters are determined by the arguments we pass. If we pass two ints to the parameter types T const&, the C++ compiler must conclude that T must be int. Note that no automatic type conversion is allowed here. Each T must match exactly. For example: template <typename T> inline T const& max (T const& a, T const& b); … max(4,7) // OK: T is int for both arguments max(4,4.2) // ERROR: first T is int, second T is double There are three ways to handle such an error: Cast the arguments so that they both match: max(static_cast<double>(4),4.2) // OK Specify (or qualify) explicitly the type of T: max<double>(4,4.2) // OK Specify that the parameters may have different types. For a detailed discussion of these topics, see the next section. Template Parameters Function templates have two kinds of parameters: Template parameters, which are declared in angle brackets before the function template name: template <typename T> // T is template parameter Call parameters, which are declared in parentheses after the function template name: … max (T const& a, T const& b) // a and b are call parameters You may have as many template parameters as you like. However, in function templates (unlike class templates) no default template arguments can be specified. [3] For example, you could define the max() template for call parameters of two different types: [3] This restriction is mainly the result of a historical glitch in the development of function templates. There are probably no technical hindrances to implementing such a feature in modern C++ compilers, and in the future it will probably be available (see Section 13.3 on page 207). template <typename T1, typename T2> inline T1 max (T1 const& a, T2 const& b) { return a < b ? b : a; } … max(4,4.2) // OK, but type of first argument defines return type This may appear to be a good method to enable passing two call parameters of different types to the max() template, but in this example it has drawbacks. The problem is that the return type must be declared. If you use one of the parameter types, the argument for the other parameter might get converted to this type, regardless of the caller's intention. C++ does not provide a means to specify choosing "the more powerful type" (however, you can provide this feature by some tricky template programming, see Section 15.2.4 on page 271). Thus, depending on the call argument order the maximum of 42 and 66.66 might be the double 66.66 or the int 66. Another drawback is that converting the type of the second parameter into the return type creates a new, local temporary object. As a consequence, you cannot return the result by reference. [4] In our example, therefore, the return type has to be T1 instead of T1 const&. [4] You are not allowed to return values by reference if they are local to a function because you'd return something that doesn't exist when the program leaves the scope of this function. Because the types of the call parameters are constructed from the template parameters, template and call parameters are usually related. We call this concept function template argument deduction. It allows you to call a function template as you would an ordinary function. However, as mentioned earlier, you can instantiate a template explicitly for certain types: template <typename T> inline T const& max (T const& a, T const& b); … max<double>(4,4.2) // instantiate T as double In cases when there is no connection between template and call parameters and when template parameters cannot be determined, you must specify the template argument explicitly with the call. For example, you can introduce a third template argument type to define the return type of a function template: template <typename T1, typename T2, typename RT> inline RT max (T1 const& a, T2 const& b); However, template argument deduction does not match up return types, [5] and RT does not appear in the types of the function call parameters. Therefore, RT cannot be deduced. As a consequence, you have to specify the template argument list explicitly. For example: [5] Deduction can be seen as part of overload resolution—a process that is not based on selection of return types either. The sole exception is the return type of conversion operator members. template <typename T1, typename T2, typename RT> inline RT max (T1 const& a, T2 const& b); … max<int,double,double>(4,4.2) // OK, but tedious So far, we have looked at cases in which either all or none of the function template arguments were mentioned explicitly. Another approach is to specify only the first arguments explicitly and to allow the deduction process to derive the rest. In general, you must specify all the argument types up to the last argument type that cannot be determined implicitly. Thus, if you change the order of the template parameters in our example, the caller needs to specify only the return type: template <typename RT, typename T1, typename T2> inline RT max (T1 const& a, T2 const& b); … max<double>(4,4.2) // OK: return type is double In this example, the call to max<double> explicitly sets RT to double, but the parameters T1 and T2 are deduced to be int and double from the arguments. Note that all of these modified versions of max() don't lead to significant advantages. For the one-parameter version you can already specify the parameter (and return) type if two arguments of a different type are passed. Thus, it's a good idea to keep it simple and use the one-parameter version of max() (as we do in the following sections when discussing other template issues). Overloading Function Templates Like ordinary functions, function templates can be overloaded. That is, you can have different function definitions with the same function name so that when that name is used in a function call, a C++ compiler must decide which one of the various candidates to call. The rules for this decision may become rather complicated, even without templates. In this section we discuss overloading when templates are involved. If you are not familiar with the basic rules of overloading without templates, please look at Appendix B, where we provide a reasonably detailed survey of the overload resolution rules. The following short program illustrates overloading a function template: // basics/max2.cpp // maximum of two int values inline int const& max (int const& a, int const& b) { return a<b?b:a; } // maximum of two values of any type template <typename T> inline T const& max (T const& a, T const& b) { return a<b?b:a; } // maximum of three values of any type template <typename T> inline T const& max (T const& a, T const& b, T const& c) { return max (max(a,b), c); } int main() { ::max(7, 42, 68); // calls the template for three arguments ::max(7.0, 42.0); // calls max<double> (by argument deduction) ::max('a', 'b'); // calls max<char> (by argument deduction) ::max(7, 42); // calls the nontemplate for two ints ::max<>(7, 42); // calls max<int> (by argument deduction) ::max<double>(7, 42); // calls max<double> (no argument deduction) ::max('a', 42.7); // calls the nontemplate for two ints } As this example shows, a nontemplate function can coexist with a function template that has the same name and can be instantiated with the same type. All other factors being equal, the overload resolution process normally prefers this nontemplate over one generated from the template. The fourth call falls under this rule: max(7, 42) // both int values match the nontemplate function perfectly If the template can generate a function with a better match, however, then the template is selected. This is demonstrated by the second and third call of max(): max(7.0, 42.0) // calls the max<double> (by argument deduction) max('a', 'b'); // calls the max<char> (by argument deduction) It is also possible to specify explicitly an empty template argument list. This syntax indicates that only templates may resolve a call, but all the template parameters should be deduced from the call arguments: max<>(7, 42) // calls max<int> (by argument deduction) Because automatic type conversion is not considered for templates but is considered for ordinary functions, the last call uses the nontemplate function (while 'a' and 42.7 both are converted to int): max('a', 42.7) // only the nontemplate function allows different argument types A more useful example would be to overload the maximum template for pointers and ordinary C-strings: // basics/max3.cpp #include <iostream> #include <cstring> #include <string> // maximum of two values of any type template <typename T> inline T const& max (T const& a, T const& b) { return a < b ? b : a; } // maximum of two pointers template <typename T> inline T* const& max (T* const& a, T* const& b) { return *a < *b ? b : a; } // maximum of two C-strings inline char const* const& max (char const* const& a, char const* const& b) { return std::strcmp(a,b) < 0 ? b : a; } int main () { int a=7; int b=42; ::max(a,b); // max() for two values of type int std::string s="hey"; std::string t="you"; ::max(s,t); // max() for two values of type std::string int* p1 = &b; int* p2 = &a; ::max(p1,p2); // max() for two pointers char const* s1 = "David"; char const* s2 = "Nico"; ::max(s1,s2); // max() for two C-strings } Note that in all overloaded implementations, we pass all arguments by reference. In general, it is a good idea not to change more than necessary when overloading function templates. You should limit your changes to the number of parameters or to specifying template parameters explicitly. Otherwise, unexpected effects may happen. For example, if you overload the max() template, which passes the arguments by reference, for two C-strings passed by value, you can't use the three-argument version to compute the maximum of three C-strings: // basics/max3a.cpp #include <iostream> #include <cstring> #include <string> // maximum of two values of any type (call-by-reference) template <typename T> inline T const& max (T const& a, T const& b) { return a < b ? b : a; } // maximum of two C-strings (call-by-value) inline char const* max (char const* a, char const* b) { return std::strcmp(a,b) < 0 ? b : a; } // maximum of three values of any type (call-by-reference) template <typename T> inline T const& max (T const& a, T const& b, T const& c) { return max (max(a,b), c); // error, if max(a,b) uses call-by-value } int main () { ::max(7, 42, 68); // OK const char* s1 = "frederic"; const char* s2 = "anica"; const char* s3 = "lucas"; ::max(s1, s2, s3); // ERROR } The problem is that if you call max() for three C-strings, the statement return max (max(a,b), c); becomes an error. This is because for C-strings, max(a,b) creates a new, temporary local value that may be returned by the function by reference. This is only one example of code that might behave differently than expected as a result of detailed overload resolution rules. For example, the fact that not all overloaded functions are visible when a corresponding function call is made may or may not matter. In fact, defining a three-argument version of max() without having seen the declaration of a special two-argument version of max() for ints causes the two-argument template to be used by the three-argument version: // basics/max4.cpp // maximum of two values of any type template <typename T> inline T const& max (T const& a, T const& b) { return a<b?b:a; } // maximum of three values of any type template <typename T> inline T const& max (T const& a, T const& b, T const& c) { return max (max(a,b), c); // uses the template version even for ints } // because the following declaration comes // too late: // maximum of two int values inline int const& max (int const& a, int const& b) { return a<b?b:a; } We discuss details in Section 9.2 on page 121, but for the moment, as a rule of thumb you should always have all overloaded versions of a function declared before the function is called. Summary Template functions define a family of functions for different template arguments. When you pass template arguments, function templates are instantiated for these argument types. You can explicitly qualify the template parameters. You can overload function templates. When you overload function templates, limit your changes to specifying template parameters explicitly. Make sure you see all overloaded versions of function templates before you call them.