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; }
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; // ???
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:
We need to ensure that there is an overloaded * operator that takes a StopWatch on the left and right side of the operator:template <typename T> T cube(T value) { return value * value * value; // no match for 'operator*' in '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:The conditional operator is merely a conditional expression instead of a conditional statement. The above is very similar to this:template <typename T> T Max(T a, T b) { return a > b ? a : b; }
we try to use it like this: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) { return a > b ? a : 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) { return a > b ? a : 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) { return a > b ? a : 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) { return a > b ? a : b; }
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.)
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 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 'Max(double, int)' double d1 = Max(4.5, 3); ^ note: candidate: templateT Max(T, T) T Max(T a, T b) ^ note: template argument deduction/substitution failed: note: deduced conflicting types for parameter 'T' ('double' and 'int') double d1 = Max(4.5, 3);
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)
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 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): ??? 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) { return a > b ? a : 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) { return strcmp(a, b) >= 0 ? a : 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(int *, int *, int) [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:
// explicit instantiation template int foobar<int>(int);