CS计算机代考程序代写 compiler c++ COMP6771 Advanced C++ Programming

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 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 2
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 a) -> T {
}
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 x{3, 1, 2};
}
std::array y{3.3, 1.1, 2.2, 4.4};
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 a) -> int {
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 a) -> double {
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 stack_;
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 stack_;
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 stack_;
};
#include “./demo705-classtemp.tpp”
#endif // STACK_H
1 #include “./demo705-classtemp.h” 2
3 template
4 auto stack::push(T const& item) -> void {
5 6} 7
8 template
9 auto stack::pop() -> void {
10 stack_.pop_back();
11 }
12
13 template
14 auto stack::top() -> T& {
15 return stack_.back();
16 }
17
18 template
19 auto stack::top() const -> T const& {
20 return stack_.back();
21 }
22
23 template
24 auto stack::empty() const -> bool {
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 s1; // int: template argument
8 s1.push(1);
9 s1.push(2);
10 stack s2 = s1;
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 string_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::stack() { }
3
4 template
5 stack::stack(const stack &s) : stack_{s.stack_} { }
6
7 template
8 stack::stack(Stack &&s) : stack_(std::move(s.stack_)); { }
9
10 template
11 stack& stack::operator=(const stack &s) {
12 stack_ = s.stack_;
13 }
14
15 template
16 stack& stack::operator=(stack &&s) {
17 stack_ = std::move(s.stack_);
18 }
19
20 template
21 stack::~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 2 Tmin(Ta,Tb);
1 template
2 automin(Ta,Tb)->T{
3 return a < b ? a : b; 4} 5 6 template int min(int, int);
7 template double min(double, double);
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 was instantiated
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 items_;
}
template
auto stack::pop() -> void {
items_.pop_back();
}
template
auto stack::push(const T& i) -> void {
1 auto main() -> int {
2 stack s;
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 2
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 stack_;
16 };
17
18 template
19 int stack::num_stacks_ = 0;
20
21 template
22 stack::stack() {
23 num_stacks_++;
24 }
25
26 template
27 stack::~stack() {
28 num_stacks_–;
29 }
1 2 3 4 5 6 7 8 9
10
#include
#include “./demo706-static.h”
auto main() -> int {
stack fs;
}
stack is1, is2, is3;
std::cout << stack::num_stacks_ << "\n"; std::cout << stack::num_stacks_ << "\n"; demo706-static.h demo706-static.cpp 8 Friends Each stack instantiation has one unique instantiation of the friend 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include
#include
template
class stack {
public:
auto push(T const&) -> void;
auto pop() -> void;
friend auto operator<<(std::ostream& os, stack const& s) -> std::ostream& {
return os << "My top item is " << s.stack_.back() << "\n"; } private: std::vector stack_;
};
template
auto stack::push(T const& t) -> void {
}
stack_.push_back(t);
1 #include
2 #include
3
4 #include “./stack.h” 5
6 auto main() -> int {
7 stack ss;
8 ss.push(“Hello”);
9 std::cout << ss << "\n": 10 11 stack is;
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