COMP6771 Advanced C++ Programming
Week 7.1 Templates Intro
1
Why?
In this lecture
Understanding compile time polymorphism in the form of templates helps understand the workings of C++ on generic types
What?
Templates
Non-type parameters Inclusion exclusion principle Classes, statics, friends
2
Polymorphism & Generic Programming
Polymorphism: Provision of a single interface to entities of different types Two types – :
Static (our focus):
Function overloading
Templates (i.e. generic programming)
std::vector
Dynamic:
Related to virtual functions and inheritance – see week 9
Genering Programming: Generalising software components to be independent of a particular type
STL is a great example of generic programming
3
Function Templates
Without generic programming, to create two logically identical functions that behave in a way that is independent to the type, we have to rely on function overloading.
#include
auto min(int a, int b) -> int {
return a < b ? a : b;
7 auto min(double a, double b) -> double{ 8 return a < b ? a : b;
9}
1
2
3
4 5} 6
10 11 12 13 14
auto main() -> int {
std::cout << min(1, 2) << "\n"; // calls line 1
std::cout << min(1.0, 2.0) << "\n"; // calls line 4
}
demo701-functemp1.cpp
Explore how this looks in Compiler Explorer
4.1
Function Templates
Function template: Prescription (i.e. instruction) for the compiler to generate particular instances of a function varying by type
The generation of a templated function for a particular type T only happens when a call to that function is seen during compile time
1 #include
3 template
4 automin(Ta,Tb)->T{
5 6} 7
8
9
10 11
return a < b ? a : b;
auto main() -> int {
std::cout << min(1, 2) << "\n"; // calls int min(int, int)
std::cout << min(1.0, 2.0) << "\n"; // calls double min(double, double)
}
demo702-functemp2.cpp
Explore how this looks in Compiler Explorer
4.2
Some Terminology
template type parameter
template parameter list
1 template
2 min a, b){
3 returna
#include
template
auto findmin(const std::array
}
T min = a[0];
for (std::size_t i = 1; i < size; ++i) {
if (a[i] < min)
min = a[i];
}
return min;
auto main() -> int {
std::array
}
std::array
std::cout << "min of x = " << findmin(x) << "\n";
std::cout << "min of x = " << findmin(y) << "\n";
demo703-nontype1.cpp
Compiler deduces T and size from a
5.1
Type and Nontype Parameters
The above example generates the following functions at compile time What is "code explosion"? Why do we have to be weary of it?
1
2
3
4
5
6}
7 return min; 8}
auto findmin(const std::array
int min = a[0];
for (int i = 1; i < 3; ++i) {
if (a[i] < min)
min = a[i];
9
10 auto findmin(const std::array
11 double min = a[0];
12 for (int i = 1; i < 4; ++i) {
13 if (a[i] < min)
14 min = a[i];
15 }
16 return min;
17 }
demo704-nontype2.cpp
5.2
Class Templates
How we would currently make a Stack type Issues?
Administrative nightmare
Lexical complexity (need to learn all type names)
1 class int_stack {
2 public:
3 auto push(int&) -> void;
4 auto pop() -> void;
5 auto top() -> int&;
6 auto top() const -> const int&;
7 private:
8 std::vector
9 };
1 class double_stack {
2 public:
3 auto push(double&) -> void;
4 auto pop() -> void;
5 auto top() -> double&;
6 auto top() const -> const double&;
7 private:
8 std::vector
9 };
6.1
Class Templates
Creating our first class template
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// stack.h
#ifndef STACK_H
#define STACK_H
#include
#include
template
class stack {
public:
friend auto operator<<(std::ostream& os, const stack& s) -> std::ostream& {
for (const auto& i : s.stack_)
os << i << " ";
return os;
}
auto push(T const& item) -> void;
auto pop() -> void;
auto top() -> T&;
auto top() const -> const T&;
auto empty() const -> bool;
private:
std::vector
};
#include “./demo705-classtemp.tpp”
#endif // STACK_H
1 #include “./demo705-classtemp.h” 2
3 template
4 auto stack
5 6} 7
8 template
9 auto stack
10 stack_.pop_back();
11 }
12
13 template
14 auto stack
15 return stack_.back();
16 }
17
18 template
19 auto stack
20 return stack_.back();
21 }
22
23 template
24 auto stack
25 return stack_.empty();
26 }
stack_.push_back(item);
demo705-classtemp-main.h
demo705-classtemp-main.tpp
https://en.cppreference.com/w/cpp/language/friend#Template_friends
6.2
Class Templates
1 #include
2 #include
3
4 #include “./demo705-classtemp.h” 5
6 int main() {
7 stack
8 s1.push(1);
9 s1.push(2);
10 stack
11 std::cout << s1 << s2 << '\n';
12 s1.pop();
13 s1.push(3);
14 std::cout << s1 << s2 << '\n';
15 // s1.push("hello"); // Fails to compile.
16
17 stack
18 string_stack.push(“hello”);
19 // string_stack.push(1); // Fails to compile.
20 }
demo705-classtemp-main.cpp
6.3
Class Templates
Default rule-of-five (you don’t have to implement these in this case)
1 template
2 stack
3
4 template
5 stack
6
7 template
8 stack
9
10 template
11 stack
12 stack_ = s.stack_;
13 }
14
15 template
16 stack
17 stack_ = std::move(s.stack_);
18 }
19
20 template
21 stack
6.4
Inclusion compilation model
What is wrong with this?
g++ min.cpp main.cpp -o main
min.h
min.cpp
main.cpp
1 template
2 auto min(T a, T b) -> T;
1 #include
2
3 auto main() -> int {
4 std::cout << min(1, 2) << "\n"; 5}
1 template
2 auto min(T a, T b) -> int {
3 4}
return a < b ? a : b;
7.1
Inclusion compilation model
When it comes to templates, we include definitions (i.e. implementation) in the .h file
This is because template definitions need to be known at compile time (template definitions can't be instantiated at link time because that would require an instantiation for all types)
Will expose implementation details in the .h file
Can cause slowdown in compilation as every file using min.h will have to instantiate the template, then it's up the linker to ensure there is only 1 instantiation.
min.h
main.cpp
1 #include
2
3 auto main() -> int {
4 std::cout << min(1, 2) << "\n"; 5}
1 template
2 auto min(T a, T b) -> T {
3 4}
return a < b ? a : b;
7.2
Inclusion compilation model
Alternative: Explicit instantiations
Generally a bad idea
min.h
min.cpp
main.cpp
1 template
1 template
2 automin(Ta,Tb)->T{
3 return a < b ? a : b;
4}
5
6 template int min
7 template double min
1
2
3
4
5 6}
#include
auto main() -> int {
std::cout << min(1, 2) << "\n";
std::cout << min(1.0, 2.0) << "\n";
7.3
Inclusion compilation model
Lazy instantiation: Only members functions that are called are instantiated
In this case, pop() will not be instantiated
Exact same principles will apply for classes
Implementations must be in header file, and compiler should only behave as if one Stack
main.cpp
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
stack.h
#include
template
class stack {
public:
stack() {}
auto pop() -> void;
auto push(const T& i) -> void;
private:
std::vector
}
template
auto stack
items_.pop_back();
}
template
auto stack
1 auto main() -> int {
2 stack
3 s.push(5);
4}
}
items_.push_back(i);
7.4
Static Members
Each template instantiation has it’s own set of static members
1 #include
3 template
4 class stack {
5 public:
6 stack();
7 ~stack();
8 auto push(T&) -> void;
9 auto pop() -> void;
10 auto top() -> T&;
11 auto top() const -> const T&;
12 static int num_stacks_;
13
14 private:
15 std::vector
16 };
17
18 template
19 int stack
20
21 template
22 stack
23 num_stacks_++;
24 }
25
26 template
27 stack
28 num_stacks_–;
29 }
1 2 3 4 5 6 7 8 9
10
#include
#include “./demo706-static.h”
auto main() -> int {
stack
}
stack
std::cout << stack
#include
template
class stack {
public:
auto push(T const&) -> void;
auto pop() -> void;
friend auto operator<<(std::ostream& os, stack
return os << "My top item is " << s.stack_.back() << "\n";
} private:
std::vector
};
template
auto stack
}
stack_.push_back(t);
1 #include
2 #include
3
4 #include “./stack.h” 5
6 auto main() -> int {
7 stack
8 ss.push(“Hello”);
9 std::cout << ss << "\n":
10
11 stack
12 is.push(5);
13 std::cout << is << "\n":
14 }
demo707-friend.h
demo707-friend.cpp
9
(Unrelated) Constexpr
We can provide default arguments to template types (where the defaults themselves are types)
It means we have to update all of our template parameter lists
10 . 1
Either:
Constexpr
A variable that can be calculated at compile time
A function that, if its inputs are known at compile time, can be run at compile time
#include
constexpr int constexpr_factorial(int n) {
return n <= 1 ? 1 : n * constexpr_factorial(n - 1);
7 int factorial(int n) {
8 return n <= 1 ? 1 : n * factorial(n - 1); 9}
10
11 auto main() -> int {
12 // Beats a #define any day.
13 constexpr int max_n = 10;
14 constexpr int tenfactorial = constexpr_factorial(10);
15
16 // This will fail to compile
17 int ninefactorial = factorial(9);
18
19 std::cout << max_n << "\n";
20 std::cout << tenfactorial << "\n";
21 std::cout << ninefactorial << "\n";
22 }
1
2
3
4 5} 6
demo708-constexpr.cpp
10 . 2
Constexpr (Benefits)
Benefits:
Values that can be determined at compile time mean less processing is needed at runtime, resulting in an overall faster program execution
Shifts potential sources of errors to compile time instead of runtime (easier to debug)
10 . 3
Feedback
11