Overloaded Functions (review)
Recall this problem from our discussion of functions in C++:Output:
int cube(int n) { return n * n * n; } int i = 8; long l = 50L; float f = 2.5F; double d = 3.14;
First attempt, "old skool" fix in C:std::cout << cube(i) << std::endl; // Works fine: 512 std::cout << cube(l) << std::endl; // May or may not work: 125000 std::cout << cube(f) << std::endl; // Not quite what we want: 8 std::cout << cube(d) << std::endl; // Not quite what we want: 27
It will work as expected:
int cube_int(int n) { return n * n * n; } float cube_float(float n) { return n * n * n; } double cube_double(double n) { return n * n * n; } long cube_long(long n) { return n * n * n; }
This quickly becomes tedious and unmanageable as we write other functions to handle other types such as unsigned int, unsigned long, char, as well as user-defined types that might come along.std::cout << cube_int(i) << std::endl; // Works fine: 512 std::cout << cube_long(l) << std::endl; // Works fine: 125000 std::cout << cube_float(f) << std::endl; // Works fine: 15.625 std::cout << cube_double(d) << std::endl; // Works fine: 30.9591
Then we discovered we could "fix" the problem by overloading the function:
Overloaded functions:
int cube(int val) { return val * val * val; } |
long cube(long val) { return val * val * val; } |
float cube(float val) { return val * val * val; } |
double cube(double val) { return val * val * val; } |
Notes:int i = cube(2); // cube(int), i is 8 long l = cube(100L); // cube(long), l is 1000000L float f = cube(2.5f); // cube(float), f is 15.625f double d = cube(2.34e25); // cube(double), d is 1.2812904e+76
Function Templates
Introduction:template <typename T> T cube(T value) { return value * value * value; // This is how you cube any value, // regardless of the type. }
Other notes:template <typename T> T cube(T value) { return value * value * value; }
then code similar to this is generated for us (by the compiler at compile time):int i = cube(2);
int cube(int value) { return value * value * value; }
then code similar to this is generated for us:int i = cube(2); long l = cube(100L); float f = cube(2.5f); double d = cube(2.34e25);
int cube(int value) { return value * value * value; } long cube(long value) { return value * value * value; } |
float cube(float value) { return value * value * value; } double cube(double value) { return value * value * value; } |
Automatic Type Deduction
Note that often the compiler can deduce the types of the arguments (and hence, the type of T) from the parameters. However, sometimes the compiler can't figure it out and generates an error (see below).Let's modify the templated cube function to see what types are actually being passed in:
Operator precedence chart for C++#include <typeinfo> // typeid template <typename T> T cube(T value) { std::cout << "cube<" << typeid(T).name() << ">" << std::endl; return value * value * value; }
Sample code:
As you can see, the actual string that is printed out is dependent on the compiler.void f2() { // Compiler deduction // Microsoft Borland GNU/Clang cube(2); // cube<int> cube<int> cube<i> cube(2.0f); // cube<float> cube<float> cube<f> cube(2.0); // cube<double> cube<double> cube<d> cube('A'); // cube<char> cube<char> cube<c> // Explicit call // Microsoft Borland GNU/Clang cube<int>(2); // cube<int> cube<int> cube<i> cube<double>(2); // cube<double> cube<double> cube<d> cube<int>(2.1); // cube<int> cube<int> cube<i> (warning) }
Of course, you can always cast the parameter to force a particular call:
// Casting will force it as well // Microsoft Borland GNU/Clang cube(static_cast<int>(2)); // cube<int> cube<int> cube<i> cube(static_cast<double>(2)); // cube<double> cube<double> cube<d> cube(static_cast<int>(2.1)); // cube<int> cube<int> cube<i> (no warning)
User-Defined Types in Template Functions
Templates only provide some of the necessary functionality.
Suppose we wanted to cube a StopWatch object:
Will this compile? If so, what will it print out? To understand what's going on, look at what the compiler is generating:StopWatch sw1(4); // Create a StopWatch set to 4 seconds StopWatch sw2; // Create a StopWatch set to 0 seconds sw2 = cube(sw1); // Cube the first StopWatch and assign to second cout << sw2 << endl; // ???
Template Compiler-generated template <typename T> cube(T value) { return value * value * value;----> } StopWatch cube(StopWatch value) { return value * value * value; }
The answer is: it depends.
If there is no overloaded operator*, the compiler will generate an error message in the template function:
Error from g++:template <typename T> T cube(T value) { return value * value * value; // no match for 'operator*' in 'value * value' }
We need to ensure that there is an overloaded * operator that takes a StopWatch on the left and right side of the operator:In instantiation of 'T cube(T) [with T = StopWatch]': required from here error: no match for 'operator*' (operand types are 'StopWatch' and 'StopWatch') return value * value * value; ~~~~~~^~~~~~~
Now, the following will compile:StopWatch StopWatch::operator*(const StopWatch &sw) const { return StopWatch(seconds_ * sw.seconds_); }
Things to realize:StopWatch sw1(4); // Create a StopWatch set to 4 seconds StopWatch sw2; // Create a StopWatch set to 0 seconds sw2 = cube(sw1); // Cube the first StopWatch and assign to second cout << sw2 << endl; // Displays 00:01:04 (4 * 4 * 4 = 64 seconds)
// Microsoft Borland GNU/Clang sw3 = cube(sw1); // cube<class StopWatch> cube<StopWatch> cube<9StopWatch>
Multiple Template Parameters
Suppose we want a generic Max function:we try to use it like this:template <typename T> T Max(T a, T b) { if (a > b) return a; else return b; }
We need to specify the type of both parameters in order to mix types:int i = Max(25, 10); // i = 25 double d = Max(2.5, 3.1); // d = 3.1 double e = Max(2.5, 4); // error: no matching function for call to 'Max(double, int)'
This leads to:template <typename T1, typename T2> T1 Max(T1 a, T2 b) { if (a > b) return a; else return b; }
If we change the return type, it will work for the above problem:double d1 = Max(4.5, 3); // d1 = 4.5 double d2 = Max(3, 4.5); // d2 = 4.0 ??? (warning: converting to 'int' from 'double')
But now this is problematic:template <typename T1, typename T2> T2 Max(T1 a, T2 b) { if (a > b) return a; else return b; }
Finally, add a third type:int i = Max(3, 4.5); // i = 4 ??? (warning: converting to 'int' from 'double')
This leads to:template <typename T1, typename T2, typename T3> T1 Max(T2 a, T3 b) { if (a > b) return a; else return b; }
The errors are slightly different for each compiler:double d1 = Max(3, 4.5); // error: can't deduce template argument for 'T1' Max(3, 4.5); // may be called this way as well (ignore return value)
The simple fact is that the compiler cannot deduce the return type of a function. The user must specify it.GNU: no matching function for call to 'Max(int, double)' Clang: candidate template ignored: couldn't infer template argument 'T1' Borland: Could not find a match for 'Max(int,double)' Microsoft: error 'T1 Max(T2,T3)' : could not deduce template argument for 'T1'
Various solutions:
Suppose I made this subtle change:double d2 = Max<double, int, double>(3, 4.5); // OK, all explicit double d3 = Max<double, double, int>(4.5, 3); // OK, all explicit double d4 = Max<double>(3, 4.5); // Ok, first explicit, compiler deduces others double d5 = Max<double, int, int>(4.5, 3); // OK, all explicit, but truncating (possible warning) double d6 = Max<int, double, int>(4.5, 3); // OK, all explicit, but truncating (possible warning)
How does that affect the code above? Other calls to Max?template <typename T1, typename T2, typename T3> T3 Max(T1 a, T2 b) { if (a > b) return a; else return b; }
So, what's the best solution? There isn't one. The STL (std::max) chose to disallow mixing types so there is no problem!
Finally, in case T is a large object, it may be more desirable to use references:
Since it may be difficult to know exactly what types will be passed to the function, using references helps avoid the cost of passing large objects by value.
template <typename T> T Max(const T& a, const T& b) { if (a > b) return a; else return b; } template <typename T> T cube(const T& value) { return value * value * value; }
Explicit Template Specialization
Up until now, all of our templated functions have been generated from the template. (Which was the whole point.)What if the code generated by the compiler didn't do what we expect? (It can and does happen, e.g. a compiler-generated copy constructor.)
Let's create an example:
template <typename T> bool equal(T a, T b) { std::cout << a << " and " << b << " are "; if (a == b) std::cout << "equal\n"; else std::cout << "not equal\n"; return a == b; } |
void f4() { int a = 5, b = 5, c = 8; double d1 = 3.14, d2 = 5.0; equal(a, b); // 5 and 5 are equal equal(a, c); // 5 and 8 are not equal equal(a, c - 3); // 5 and 5 are equal equal(d1, d2); // 3.14 and 5.0 are not equal } |
Here's a question: What functionality (behavior) must the type T support in order for the code above to work?
This won't work, though:
Error:equal(a, d2);
But, we don't care about that. (How could we make this "work" if we did care?)error: no matching function for call to 'equal(int, double)' equal(a, d2); ^ note: candidate: templateT equal(T, T) T equal(T a, T b) ^ note: template argument deduction/substitution failed: note: deduced conflicting types for parameter 'T' ('int' and 'double') equal(a, d2);
How about these:
Why are we getting "odd" results?const char s1[] = "One"; const char s2[] = "One"; const char s3[] = "Two"; equal(s1, s2); // One and One are not equal equal(s1, s3); // One and Two are not equal equal(s1, "One"); // One and One are not equal equal(s1, s1); // One and One are equal equal("One", "One"); // ???
Template | Expansion (artist's rendering) |
---|---|
template <typename T> bool equal(T a, T b) { // Compare the two if (a == b) // other stuff } |
bool equal(const char * a, const char * b) { // Compare the two if (a == b) // other stuff } |
template <> bool equal<const char *>(const char *a, const char *b) { std::cout << a << " and " << b << " are "; bool same = !strcmp(a, b); if (same) std::cout << "equal\n"; else std::cout << "not equal\n"; return same; }
Note that the type is not strictly required in the second angle brackets, since the compiler can deduce the type from the parameters. This:const char s1[] = "One"; const char s2[] = "One"; const char s3[] = "Two"; // With specialization for equal equal(s1, s2); // One and One are equal equal(s1, s3); // One and Two are not equal equal(s1, "One"); // One and One are equal equal(s1, s1); // One and One are equal
can be changed to this:template <> bool equal<const char *>(const char *a, const char *b)
However, the template and empty angle brackets must remain. If they are not there, then this function is just a regular, non-template function.template <> bool equal(const char *a, const char *b)
More details:
When the compiler must choose a function, the order of choice is: (from best to worst)
// template function
template <typename T>
T cube(T value)
{
std::cout << "Cubing a " << typeid(T).name() << " (template): " << value << std::endl;
return value * value * value;
}
// explicit specialization cube<int>
template <>
int cube<int>(int value)
{
std::cout << "Cubing an int (specialization): " << value << std::endl;
return value * value * value;
}
// regular function (non-template)
int cube(int value)
{
std::cout << "Cubing an int (regular): " << value << std::endl;
return value * value * value;
}
int main()
{
cube(5); // 1. regular
cube<double>(10L); // 2. template, first instantion
cube(2.5F); // 3. template, first instantion
cube<int>(2.5); // 4. specialization
cube<char>(5); // 5. template, first instantion
cube('A'); // 6. template, no instantion (uses previous instantiation from #5)
return 0;
}
Output: (from Microsoft's/Borland's compiler)
Cubing an int (regular): 5 Cubing a double (template): 10 Cubing a float (template): 2.5 Cubing an int (specialization): 2 Cubing a char (template): ??? <--- Why ??? Cubing a char (template): A
Also note that you cannot create an explicit specialization for a function after an implicit instantiation for that same function has been generated. For example, if we had this code before the explicit specialization for the cube function taking an int:
The explicit specialization following this will generate a compiler error along these lines:void foo() { // implicitly instantiates cube for integers int i = cube<int>(25); }
specialization of T cube(T) [with T = int] after instantiation (GNU) Template instance 'int cube(int)' is already instantiated (Borland) explicit specialization; 'T cube (T)' has already been instantiated (Microsoft)
Another example revisited. Given the templated Max function below (only one type specified):
What is printed here?template <typename T> T Max(T a, T b) { if (a > b) return a; else return b; }
Output:int main() { cout << Max(5, 2) << endl; cout << Max(4.5, 3.14) << endl; cout << Max('A', 'a') << endl; cout << Max("banana", "apple") << endl; return 0; }
The fix:5 4.5 a apple
// Explicit specialization for const char * // to sort lexicographically template <> const char* Max<const char *>(const char *a, const char *b) { if (strcmp(a, b) >= 0) return a; else return b; }
Overloaded Template Functions
Suppose we have this "universal" swap function:and a trivial use case:template <typename T> void Swap(T &a, T &b) { T temp = a; a = b; b = temp; }
What is the result of this "Swap"?int i = 10, j = 20; double d = 3.14, e = 2.71; Swap(i, j); // i=20, j=10 Swap(d, e); // d=2.71, e=3.14
int a[] = {1, 3, 5, 7, 9, 11}; int b[] = {2, 4, 6, 8, 10, 12}; Swap(a, b); // ???
To get an idea of what's going on, look at what the instantiated function might look like:
This produces errors because T instantiates to int[6]:void Swap(int a[6], int b[6]) { int temp[6] = a; // error: initializing an array with array a = b; // error: assigning an array b = temp; // error: assigning an array }
g++:
Microsoft:In instantiation of 'void Swap(T&, T&) [with T = int [6]]': required from here error: array must be initialized with a brace-enclosed initializer T temp = a; ^ error: invalid array assignment a = b; ^ error: invalid array assignment b = temp; ^
We need a function that can deal with arrays, so we overload the template:error C2075: 'temp' : array initialization needs curly braces see reference to function template instantiation 'void Swap(T (&),T (&))' being compiled with [ T=int [6] ] error C2106: '=' : left operand must be l-value error C2106: '=' : left operand must be l-value
// original template function template <typename T> void Swap(T &a, T &b) { T temp = a; a = b; b = temp; } |
// overloaded template function template <typename T> void Swap(T &a, T &b, int size) { for (int i = 0; i < size; i++) { T temp = a[i]; a[i] = b[i]; b[i] = temp; } } |
Use:
int a[] = {1, 3, 5, 7, 9, 11}; int b[] = {2, 4, 6, 8, 10, 12}; int size = sizeof(a) / sizeof(*a); Swap(a, b, size); // calls Swap(T &, T &, T) [with T = int] Display(a, size); // 2, 4, 6, 8, 10, 12 Display(b, size); // 1, 3, 5, 7, 9, 11
Of course, we could have leveraged the original Swap function:
Because the two Swap functions have different parameters, the compiler doesn't get confused when one function calls the other.// Using the original Swap function template <typename T> void Swap(T &a, T &b, int size) { for (int i = 0; i < size; i++) Swap(a[i], b[i]); }
Implicit vs. Explicit Instantiations
main1.cpp | foobar1.cpp |
---|---|
int foobar(int a); int main() { int x = foobar(5); return x; } |
int foobar(int a) { return a; } |
g++ -c main1.cpp g++ -c foobar1.cpp g++ main1.o foobar1.o
main2.cpp | foobar2.cpp |
---|---|
template <typename T> T foobar(T a); int main() { int x = foobar(5); return x; } |
template <typename T> T foobar(T a) { return a; } |
Message:g++ -c main2.cpp g++ -c foobar2.cpp g++ main2.o foobar2.o
main2.o:main2.cpp:(.text+0x32): undefined reference to `int foobar(int)' collect2: ld returned 1 exit status
Force the compiler (put this at the end of foobar2.cpp):
The fundamental problem is that the compiler needs to know how to instantiate the foobar function. This means the templated function MUST be in the same compilation unit (i.e. file) as the code that is calling it.// explicit instantiation template int foobar<int>(int);
Pros and Cons of function templates.
Pros:
What are the requirements for T?47 template <typename T> 48 void BadSwap(T &a, T &b, int size) 49 { 50 for (int i = 0; i < size; i++) 51 { 52 T temp(2, "two"); 53 b[i] = temp ^ a; 54 a.foo("hello"); 55 b.bar(1, 2, 3.15); 56 57 if (a % b < a / b) 58 a = "bye" + 7; 59 } 60 }
When the compiler first sees this template, it checks "what ever it can". In this example above, the compiler doesn't say anything. It can't. It has no idea what the type of T is yet.
Later, when some other code calls it, the compiler will know what T is:
This is what happens:// assume a and b are integer arrays as above BadSwap(a, b, size);
Now, look at this equally bad version:main3.cpp: In instantiation of 'void BadSwap(T&, T&, int) [with T = int [6]]': main3.cpp:80:21: required from here main3.cpp:52:7: error: expression list treated as compound expression in initializer [-fpermissive] T temp(2, "two"); ^~~~ main3.cpp:52:7: error: array must be initialized with a brace-enclosed initializer main3.cpp:53:17: error: invalid operands of types 'int [6]' and 'int [6]' to binary 'operator^' b[i] = temp ^ a; ~~~~~^~~ main3.cpp:54:7: error: request for member 'foo' in 'a', which is of non-class type 'int [6]' a.foo("hello"); ~~^~~ main3.cpp:55:7: error: request for member 'bar' in 'b', which is of non-class type 'int [6]' b.bar(1, 2, 3.15); ~~^~~ main3.cpp:57:11: error: invalid operands of types 'int [6]' and 'int [6]' to binary 'operator%' if (a % b < a / b) ~~^~~ main3.cpp:57:19: error: invalid operands of types 'int [6]' and 'int [6]' to binary 'operator/' if (a % b < a / b) ~~^~~ main3.cpp:58:9: error: incompatible types in assignment of 'const char*' to 'int [6]' a = "bye" + 7; ~~^~~~~~~~~~~
This is what the compiler says when it first encounters it (before it has been instantiated):62 template <typename T> 63 void BadSwap2(T &a, T &b, int size) 64 { 65 for (int i = 0; i < siz; i++) // ??? 66 { 67 T temp(2, "two"); 68 b[i] = temp ^ a; 69 a.foo('hello'); // ??? 70 b.bar(1, , 3.15); // ??? 71 72 if (a % b < a / b) 73 a = "bye" * 7; // ??? 74 } 75 retrun; // ??? 76 }
Still, even with all of these cons, function templates abound in the STL, are extremely useful and common, and are used by many C++ programmers every day.main3.cpp:69:11: warning: character constant too long for its type a.foo('hello'); ^~~~~~~ main3.cpp: In function 'void BadSwap2(T&, T&, int)': main3.cpp:65:23: error: 'siz' was not declared in this scope for (int i = 0; i < siz; i++) ^~~ main3.cpp:65:23: note: suggested alternative: 'size' for (int i = 0; i < siz; i++) ^~~ size main3.cpp:70:14: error: expected primary-expression before ',' token b.bar(1, , 3.15); ^ main3.cpp:73:17: error: invalid operands of types 'const char [4]' and 'int' to binary 'operator*' a = "bye" * 7; ~~~~~~^~~ main3.cpp:75:3: error: 'retrun' was not declared in this scope retrun; ^~~~~~ main3.cpp:75:3: note: suggested alternative: 'setbuf' retrun; ^~~~~~ setbuf