Advanced Programming II Class Notes

Lecture Notes for Advanced Programming II

30 March 2004 - Template Functions

Outline

Templates
- Template Functions
- Template Instantiation
- Consistent Binding
Gotchas
- Template parameters
- Strict type matching
- Source code
Polymorphism
Advanced function template features
- Explicit parameter bindings
- Actual-parameter conversions
- Template value parameters

x-to-`string` Conversion

Given a value of type x, turn it into a string.

The string-stream idiom works well for this.

#include <sstream>  // Not <strstream>

std::ostringstream oss;
oss << i;
std::string ostr = oss.str();

This is moderately complicated code, and will probably be used many times.
- Encapsulate the idiom in a function.
```
std::string int2str(int i) {
  std::ostringstream oss;
  oss << i;
  return oss.str();
  }

std::string istr = int2str(801);
```
- operator << must be defined for the value.

Avoiding Duplicated Code

One function per value type is a lot.

A lot of work too.

std::string bool2str(bool val) {
  std::ostringstream oss;
  oss << val;
  return oss.str();
  }

std::string char2str(char val) {
  std::ostringstream oss;
  oss << val;
  return oss.str();
  }

std::string int2str(int val) {
  std::ostringstream oss;
  oss << val;
  return oss.str();
  }

std::string float2str(float val) {
  std::ostringstream oss;
  oss << val;
  return oss.str();
  }

and so on

The only real difference is the argument type.

Wouldn't it be nice to treat the argument type as a parameter too?

std::string val2str(VALUE_TYPE val) {
  std::ostringstream oss;
  oss << val;
  return oss.str();
  }

VALUE_TYPE = int
std::string str = val2str(801)

Templates

Template functions treat types as parameters.
Warning: templates were crammed into c++.
- The syntax is disgusting.
  - >> vs. > >.
- Semantics is complicated (but powerful).
  - An infinite thicket of error messages.
- Compile-time behavior can be confusing.
  - Actual vs. formal template parameter matching.
- Determining feature interaction can be difficult.
  - Templates vs. overloading.
There are also template classes (for example, the STL).

Template Functions

Precede a function declaration with a template header.
- template <class T₁, class T₂, ... >.
Each T_i is a formal template parameter.
- A formal template parameter represents a type, not a value.
  - T_i represents the type int not the value 801.
  - This is not completely true.
- T_i can represent any type, not just a class.
  - The alternative keyword typename is less confusing.

Each template parameter T_i is used as a type spec in the associated function.

template <typename valueT>
std::string val2str(valueT v) {
  std::ostringstream oss;
  oss << v;
  return oss.str();
  }

Template Instantiation

Template functions are called just like any other function.
```
std::string istr = val2str(801);
```
- This is not completely true either.
The compiler performs template instantiation to match a template-function call to a template-function definition.
- Instantiation is done at compile time; not at run time.
- This can lead to highly efficient code.
Instantiation matches a template-function call with a defined template function.
- The defined and called function names must match exactly.
- The actual parameter types must be consistently bound to the formal template parameters.
- There must be exactly one matching template-function definition.
- The return value is not used during instantiation.

Consistent Binding

Consistent template parameter binding uses exact type matching. (This is not completely true either.)
- char does not exactly match int.
- const char does not exactly match char.
- T & does not exactly match T.
- A parent class does not exactly match a descendent class.
For example, the template function call
```
f(1.0, 1)
```
does not match the template function definition
```
template < typename t1 >
f(t1 x, t1 y) { . . . }
```
because
1. x = 1.0 binds t1 to type float.
2. y = 1 binds t1 to type int.
3. The binding is inconsistent: float is not int.

A Successful Consistent Binding

To continue the example, the template function call
```
f(1.0, 1)
```
does match the template function definition
```
template < typename t1, template t2>
f(t1 x, t2 y) { . . . }
```
producing the consistent template parameter binding
1. x = 1.0 binds t1 to type float.
2. y = 1 binds t2 to type int.
3. That's a consistent binding.

Gotchas - Template Parameters

The compiler looks only at actual function parameters to determine types.
- Each T_i must appear as an parameter type.
  - Otherwise the compiler can't determine T_i's type.
```
template <class T>
T oops(int i) {
  T tval;
  // whatever
  return tval;
  }

// What is T? 

oops(1);
```
This is not completely true.

Gotchas - Strict Type Matching

Type matching is strict; no conversions are done.

template <typename T>
void oops(T i, T j) {
  // whatever
  }

int i = 3;
unsigned j = 4;
oops(i, j) // An int isn't an unsigned.

struct P { };
struct C : P { };
P p;
C c;
oops(p, c);  // A P isn't a C.

consts and reference types are a great source type-matching problems.
- Particularly with the STL.
This isn't completely true either.

Other Gotchas

Operations performed on template-type values must be defined.
- Horrendous compile-time errors result otherwise.
Interactions with function overloading, function pointers, ...
- Remember KISS: keep is simple and safe.
Template function inclusion.
- Template functions must be defined in the same file in which they're used.
- The compiler has to know the definition to instantiate.
  - There is no separate compilation for template functions.
- This is an exception (a big one) to the rule prohibiting source code in .h files.

Polymorphism

How many elements does a list hold?
- Count them and see.
- Does the type of the elements matter?
  - Not at all.
Template functions abstract away unimportant type aspects.
- Implicit conversions are another example.
  - The difference between an char and an int.
Abstraction with respect to types is polymorphism.
Write code to expose and exploit polymorphism.
- It saves you time and effort.
- You develop general and powerful tools.

The `string`-to-x Problem

Convert a string to a value of type T.
atoi() solves this problem for int values.
- But atoi() isn't standard.
- And what about values other than int?
The string-stream idiom works here too, the other way.
```
std::istringstream iss(valstr);
iss >> val;
```
- operator >> must be defined for the value's type.

But template functions can't handle this idiom.

template <typename valT>
valT val2str(const std::string & vstr) {
  std::istringstream iss(vstr);
  valT v;
  iss >> v;
  return v;
  }

Parameter matching can't determine valT.

Explicit Template Parameter Bindings

A template parameter can be explicitly bound to a type.
- Explicit binding avoids parameter-match binding.
The explicit binding syntax is similar to template-class syntax.
- The type in < > after the function name.
```
int i = val2str<int>(istr);
```
- Compare to std::vector<int> ivec.
Explicit binding works from left to right in the parameter list.
```
template<class FTP₁, class FTP₂, ...> 
FTP₁ f ( FTP₂ a1, ...) { ... }

f<T₁, T₂, ...>(arg1, arg2, ...);
```
- This call binds type T₁ to formal template parameter FTP₁, type T₂ to formal template parameter FTP₂, and so on.
- What about the actual parameter types?

Actual-Parameter Conversions

Explicit bindings support actual-parameter conversions.
- The compiler has enough information to convert properly.
For example,
```
template<class T>
void f(T a1, T a2) { ... }

f(1, 1.0);         // call 1
f<double>(1, 1.0); // call 2
```
- Call 1 doesn't match; no consistent binding.
  - T is both an int and a float.
- Call 2 matches with conversions.
  - int and float convert to double.
Only the default conversions apply.
- Including the parent-child conversion.

Formal Template Value Parameters

Formal template parameters may be given a type.
- These parameters represent constant values, not types.
```
template < type-spec T₁, type-spec T₂, ...>
```

Template value parameters are named constants.

template<int size>
void t(int i) {
  int iarray[size];
  iarray[i] = i;
  }

int main() {
  t<10>(3);
  }

Compile-time evaluation is safer and more efficient than is run-time evaluation.
- Checked for correctness at compile-time.
- Executed once at compile-time.

Bonus! - Vote Counting Revisited

Given a set of ballots, how many votes did candidate c get?
std::count_if() would work, except it wants a unary predicate.
- And we have the binary prediate is_vote_for(v, c).

We can solve this problem with a functor.

struct is_vote_for 
  unsigned c

  is_vote_for(unsigned c) : c(c) { }

  bool operator () (unsigned v) const
    return c == v

We can solve this problem with a function adaptors.

bool is_vote_for(v, c)
  return v == c

unsigned cnt = std::count_if(
  ballots.begin(), ballots.end(),
  std::bind2nd(std::ptr_fun(is_vote_for), c))

Can we solve it any other way?

Vote Counting With Template Functions

We want a family of predicates that vary by candidate.
- Procedural abstraction can do that.
```
bool is_vote_for(c, v) 
  return c == v
```
- Template functions can do that too.

Use a template value parameter to specify a family of predicates.

template < unsigned Candidate >
bool is_vote_for(v)
  return Candidate == v

unsigned cnt = std::count_if(
  ballots.begin(), ballots.end(),
  is_vote_for<1>)

Which is best? It depends.
- You have to write the functor.
- You have to adapt the predicate.
- Template instantiation happens at compile time.

The Compile-Time Gotcha

Template instantiation happens at compile time.
- There is no template resolution at run-time.

I'd like a function that returns candidate c's vote count.

With functors that's easy.

unsigned votes_received(unsigned c)
  return std::count_if(
    ballot.begin(), ballot.end(),
    is_vote_for(c))

And also with adapted functions.

With template functions that's impossible.

unsigned votes_received(unsigned c)
  return std::count_if(
    ballot.begin(), ballot.end(),
    is_vote_for<c>)

c is not a compile-time integral value.

Points to Remember

Sometimes types don't matter.
- How many elements in a list?
Use polymorphism to abstract away unimportant types.
Templates create type-independent functions.
Sometimes type can't completely ignored.
- Make sure all operations are defined.
Templates match actual and formal parameter types.
- Except when type is explicitly specified.
Template parameters are types within a function.
- Except when they're constant values.
Template type matching is exact with no conversions.
- Except for explicit template type.
Templates can get gnarly.
- Remember: little by little and KISS.

This page last modified on 1 April 2004.