程序代写代做代考 C data structure compiler go c++ COMP2012 Object-Oriented Programming and Data Structures

COMP2012 Object-Oriented Programming and Data Structures
Topic 4: Generic Programming
Dr. Desmond Tsoi
Department of Computer Science & Engineering The Hong Kong University of Science and Technology Hong Kong SAR, China
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 1 / 83

Part I
Function and Class Template
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 2 / 83

How Many larger() Functions Do You Need?
inline const int& larger(const int& a, const int& b)
{ return (a > b) ? a : b; }
inline const char& larger(const char& a, const char& b)
{ return (a > b) ? a : b; }
inline const double& larger(const double& a, const double& b)
{ return (a > b) ? a : b; }
#include
inline const string& larger(const string& a, const string& b)
{ return (a > b) ? a : b; }
#include “teacher.h”
inline const Teacher& larger(const Teacher& a, const Teacher& b)
{ return (a > b) ? a : b; }
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 3 / 83

How Many (Linked List) Node Classes Do You Need?
class ll_int_node {
private: int data; ll_int_node* next;
public: ll_int_node(const int&); ̃ll_int_node();
void ll_print() const; void ll_insert(const int&);
};
class ll_char_node {
private: char data; ll_char_node* next;
public: ll_char_node(const char&); ̃ll_char_node();
void ll_print() const; void ll_insert(const char&);
};
#include “student.h”
class ll_student_node {
private: Student data; ll_student_node* next;
public: ll_student_node(const Student&); ̃ll_student_node();
void ll_print() const; void ll_insert(const Student&);
};
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 4 / 83

Generic Programming using Templates
A lot of times, we find functions and data structures that look alike: they differ only in the types of objects they manipulate.
Since C++ allows function overloading, one may define many
my max() functions, one for each type of values/objects T, but they all have the following general form:
inline const T& larger(const T& a, const T& b) { . . . }
For nodes of different types of objects, one has to make up different class names for them (ll int node, ll char node, etc.).
Again, we don’t like the solution of creating the various larger() or nodes by “copy-and-paste-and-modify”.
The solution is generic programming using function templates and class templates.
They are similar to function definitions and class definitions but the types of objects they manipulate are parameterized with type variables.
Generic programming allows programmers to write just one version of code that works for different types of objects.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 5 / 83

Function Template of larger( )
It starts with the keyword template.
template /* File: larger-template.cpp */
inline const T& larger(const T& a, const T& b)
{
return (a > b) ? a : b;
}
The typename keyword may be replaced by class.
template /* File: larger-template2.cpp */
inline const T& larger(const T& a, const T& b)
{
return (a > b) ? a : b;
}
This is just a function template definition; it itself is not an actual function and no codes will be generated on its own.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 6 / 83

Use of the larger( ) Function Template
You may make use of the template to call larger() for any types, as long as the function code makes sense for the types.
In the case of larger(), it is required that the types can be compared by the operator <. #include /* File: larger-calls.cpp */
using namespace std;
template inline const T&
larger(const T& a, const T& b) { return (a < b) ? b : a; } int main() { int x = 4, y = 8; cout << larger(x, y) << " is a bigger number!" << endl; string a("cheetah"), b("gorilla"); cout << larger(a, b) << " is stronger!" << endl; return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 7 / 83 Function Template Instantiation Based on the function template definition, the compiler will create the codes of the functions that are actually used (called) in your program. This is called template instantiation. The parameter T in the template definition is called the formal parameter or formal argument of the template. For the program “larger-calls.cpp”, the compiler will instantiate 2 larger() functions by substituting T with the actual arguments int and string respectively into the larger function template. template inline const T&
larger(const T& a, const T& b) { return (a < b) ? b : a; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 8 / 83 Template: Formal Argument Matching #include /* File: larger-match-arg.cpp */
using namespace std;
template inline const T&
larger(const T& a, const T& b) { return (a < b) ? b : a; } int main() { cout << larger(3, 5) << endl; // T is int; cout << larger(4.3, 5.6) << endl; // T is double } When the compiler instantiates a template, it tries to determine the actual type of the template parameter by looking at the types of the actual arguments in a function call. If you call a template with different types, the compiler will generate separate instantiated function code for each type, and the size of the final executable increases accordingly. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 9 / 83 Explicit Template Instantiation For regular functions including overloaded functions, compilers try to match function arguments in function calls by type conversion. However, there is no automatic type conversion for template arguments. The following code gives a compile-time error: cout << larger(4, 5.5); // Error: no matching function for call to 'larger(int, double)' If what you really want is: const double& larger(const double& a, const double& b) { ... } you may do this by explicitly instantiating the function template by adding the actual type you want after the function name using the < > syntax:
cout << larger(4, 5.5);
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 10 / 83

What If < Is Not Properly Defined for Objects of T? #include /* File: template-problem.cpp */
using namespace std;
template const T&
larger(const T& a, const T& b) { return (a < b) ? b : a; } int main() { const char* m = "microsoft"; const char* a = "apple"; cout << larger(a, m) << " is better!" << endl; cout << larger(m, a) << " is better!" << endl; return 0; } Question: Isn’t “microsoft” bigger than “apple” in the alphabetical order? Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 11 / 83 Template Specialization Example 1 #include
#include
#include
using namespace std;
/* General case */
/* File: template-specialization-cstring.cpp */
template
const T& larger(const T& a, const T& b)
{ cout << "general case: "; return (a < b) ? b : a; } /* Exceptional case */ template <>
const char* const& larger(const char* const& a, const char* const& b)
{ cout << "special case: "; return (strcmp(a, b) < 0) ? b : a; } int main() { const char* m = "microsoft"; // Smaller address const char* a = "apple"; // Bigger address cout << larger(a, m) << " is better!" << endl; cout << larger(m, a) << " is better!" << endl; cout << larger(22, 88) << " is greater!" << endl; return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 12 / 83 Template Specialization Example 2 #include /* File: template-specialization-student.cpp */
using namespace std;
#include “student.h”
/* General case */
template
const T& larger(const T& a, const T& b)
{ cout << "general case: "; return (a < b) ? b : a; } /* Exceptional case */ template <>
const Student& larger(const Student& a, const Student& b)
{ cout << "special case: "; return (a.get_GPA() < b.get_GPA()) ? b : a; } int main() { Student a("Amy", ECE, 3.2); Student b("Bob", CSE, 4.2); cout << larger(a, b).get_name() << " is better!" << endl; cout << larger(b, a).get_name() << " is better!" << endl; cout << larger(22, 88) << " is greater!" << endl; return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 13 / 83 Function Template w/ More Than One Formal Argument 1 #include /* File: fcn-template-2arg.cpp */
2 using namespace std;
3
4 template inline const T1&
5 larger(const T1& a, const T2& b) { return (a < b) ? b : a; } 6 7 int main() 8{ 9 cout << larger(4, 5.5) << endl; // T1 is int, T2 is double 10 cout << larger(5.5, 4) << endl; // T1 is double, T2 is int 11 } A template may take more than one type arguments, each using a different typename. However, there is a subtle problem in this case: the return type is const T1&, but if (a < b), the return value is of type T2. Question: Can we return a T2 value to a return type of T1&? Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 14 / 83 Problem with fcn-template-2arg.cpp fcn-template-2arg.cpp:5:47: warning: returning reference to local temporary object [-Wreturn-stack-address] larger(const T1& a, const T2& b) { return (a < b) ? b : a; } ^~~~~~~~~~~~~~~ fcn-template-2arg.cpp:9:13: note: in instantiation of function template specialization ’larger’ requested here
cout << larger(4, 5.5) << endl; // T1 is int, T2 is double ^ fcn-template-2arg.cpp:5:47: warning: returning reference to local temporary object [-Wreturn-stack-address] larger(const T1& a, const T2& b) { return (a < b) ? b : a; } ^~~~~~~~~~~~~~~ fcn-template-2arg.cpp:10:13: note: in instantiation of function template specialization ’larger’ requested here
cout << larger(5.5, 4) << endl; // T1 is double, T2 is int ^ 2 warnings generated. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 15 / 83 Solution 1: Return by Value #include /* File: fcn-template-2arg-rbv.cpp */
using namespace std;
template inline T1
larger(const T1& a, const T2& b) { return (a < b) ? b : a; } int main() { cout << larger(4, 5.5) << endl; // T1 is int, T2 is double cout << larger(5.5, 4) << endl; // T1 is double, T2 is int return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 16 / 83 Solution 2: Don’t Return Any Value #include /* File: fcn-template-2arg-print.cpp */
using namespace std;
template
void print_larger(const T1& a, const T2& b)
{
if (a > b)
cout << a << endl; else } cout << b << endl; int main() { print_larger(4, 5.5); print_larger(5.5, 4); return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 17 / 83 Template Arguments: Too Many Combinations /* File: many-combinations.cpp */ short s = 1; char c = 'A'; int i = 1023; double d = 3.1415; print_max(s, s); print_max(s, c); print_max(c, s); print_max(s, i); // ... And all other combinations; 16 in total. With the above code, the compiler will instantiate a print larger() for each of the 16 different combinations of arguments. With the current compiler technology, this means that we get 16 (almost identical) fragments of code in the executable program. There is no sharing of code. So a simple program may have a surprisingly large binary size, if we are not careful. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 18 / 83 Function Template: Common Errors 1 #include /* File: f-template-err.cpp */
2 using namespace std;
3 template T* create() { return new T; };
4 template void f() { T a; cout << a << endl; } 5 int main() { create(); f(); } f-template-err.cpp:5:21: error: no matching function for call to 'create()' int main() { create(); f(); } ^ f-template-err.cpp:3:23: note: template argument deduction/substitution failed f-template-err.cpp:5:21: note: couldn't deduce template parameter 'T' int main() { create(); f(); } ^ f-template-err.cpp:5:26: error: no matching function for call to 'f()' int main() { create(); f(); } ^ f-template-err.cpp:4:25: note: template argument deduction/substitution failed f-template-err.cpp:5:26: note: couldn't deduce template parameter 'T' int main() { create(); f(); } The compiler can’t deduce the actual object types from such calls. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 19 / 83 Class Template for Nodes of a List The template mechanism works for classes as well. This is particularly useful for defining container classes — classes that contains objects of the same kind such as arrays, lists, and sets. #ifndef LISTNODE_H #define LISTNODE_H template
class List_Node
{
/* File: listnode.h */
public:
List_Node(const T& x) : data(x) { }
List_Node* next {nullptr};
List_Node* prev {nullptr};
T data;
};
#endif
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 20 / 83

Class Template for a List
#ifndef LIST_H /* File: list.h */
#define LIST_H
#include “listnode.h”
template class List
{
public:
List() = default;
void append(const T& item) {
List_Node* new_node = new List_Node(item);
if (!tail)
head = tail = new_node;
else
{ /* incomplete */ }
}
void print() const {
for (const List_Node* p = head; p; p = p->next)
cout << p->data << endl; } // ... Other member functions private: List_Node* head {nullptr};
List_Node* tail {nullptr};
};
#endif
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 21 / 83

Class Template: List Example
Now we can use the parameterized class template list to create lists to store any types of elements that we want, without having to resort to “code re-use by copying”.
#include
using namespace std;
#include “list.h”
#include “student.h”
int main() {
/* File: list-example.cpp */
}
List letters; letters.append(‘a’);
cout << "*** print char list *** \n"; letters.print(); List primes; primes.append(2);
cout << "### print int list ###\n"; primes.print(); List students;
students.append(Student(“James”, CSE, 4.0));
// Why don’t we call students.print() ?
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 22 / 83

Nontype Parameters for Templates
Template may also have nontype parameters, which are not type variables.
#ifndef NONTYPE_LIST_H /* File: nontype-list.h */
#define NONTYPE_LIST_H
#include “listnode.h”
template
class List {
public:
bool append(const T& item) {
if (num_items == max_num_items)
{ cerr << "List is full\n"; return false; } else { /* incomplete */ return true; } } // ... Other member functions private: int num_items {0}; List_Node* head {nullptr};
List_Node* tail {nullptr};
};
#endif
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 23 / 83

Find the Size of Any Array Using Nontype Parameter
#include /* File: array-size-by-template.cpp */
using namespace std;
// Here, x is a reference to an array of N objects of type T
template
int f(T (&x) [N]) { return N; }
int main() {
int a[] = {10, 11, 12, 13};
double b[] = {0.0, 0.1, 0.2};
bool c[] = {true, false};
cout << f(a) << endl; cout << f(b) << endl; cout << f(c) << endl; return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 24 / 83 Difference Between Class and Function Templates For function templates, the compiler may deduce the template arguments from the function call. int i = larger(4, 5); // Rely on compilers to deduce larger
int j = larger(7, 2); // Explicit instantiation
For class templates, you always have to specify the actual template arguments when creating the class objects; the compiler does not deduce the template arguments.
List primes; // Error: how can compilers deduce the type?
primes.append(2); // Error: too late; compilers can’t lookahead!
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 25 / 83

Separate Compilation For Templates??
For regular non-template functions, we usually put their declarations in a header file, and their definitions in the corresponding .cpp file.
Should we do the same for templates? /* File: larger.h */
template inline const T&
larger(const T& a, const T& b);
/* File: larger.cpp */
template inline const T&
larger(const T& a, const T& b) { return (a < b) ? b : a; } But a function/class template is instantiated only when it is used, and its definition must be in the same file which calls it. No, we put the template function/class definitions in the header file as well and include the template header file in every files which use the template. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 26 / 83 Part II +*-/ Operator Overloading <&% >
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 27 / 83

From Math Notation to Language Operators
To program the mathematical equation:
c = 2(a – 3) + 5b
one may have to write
c = add(multiply(2, subtract(a,3)), multiply(5,b));
Most programming languages have operators which allow us to mimic the mathematical notation by writing
c = 2*(a – 3) + 5*b;
However, many languages only have operators defined for the built-in types.
C++ is an exception: it allows you to re-use most, but not all, of its operators and re-define them for new user-defined types.
You may re-define “+”, “-” etc. for types such as Vector, Matrix, Student, Word, etc. defined by you.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 28 / 83

Add 2 Vectors by a Global Add( ) Function
using namespace std; /* File: vector0.h */
class Vector
{
public:
Vector(double a = 0, double b = 0) : x(a), y(b) { }
double getx() const { return x; }
double gety() const { return y; }
void print() const { cout << "(" << x << ", " << y << ")\n"; } private: double x, y; }; #include /* File: vector0-add.cpp */
#include “vector0.h”
Vector add(const Vector& a, const Vector& b)
{ return Vector(a.getx() + b.getx(), a.gety() + b.gety()); }
int main()
{
Vector a(1, 3), b(-5, 7), c(22), d;
d = add(add(a, b), c); d.print(); // d = a + b + c
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 29 / 83

Global Non-member Operator+ Function
Wouldn’t it be nicer if we could write the last addition expression as: d = a + b + c instead of
d = add(add(a, b), c));
C++ allows you to do that by simply replacing the name of the function add by operator+.
Also notice that our global non-member operator+ function will work for adding
􏰢 a vector to a vector
􏰢 a vector to a scalar
􏰢 a scalar to a vector
Question: Why do they work?
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 30 / 83

Global Non-member Operator+ Function ..
#include /* File: vector0-op-add.cpp */
#include “vector0.h”
Vector operator+(const Vector& a, const Vector& b)
{ return Vector(a.getx() + b.getx(), a.gety() + b.gety()); }
int main() {
Vector a(1, 3), b(-5, 7), c(22), d;
d = a + b + c; cout << "vector + vector: a + b + c = "; d.print(); d = b + 1.0; cout << "vector + scalar: b + 1.0 = "; d.print(); d = 8.2 + a; cout << "scalar + vector: 8.2 + a = "; d.print(); return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 31 / 83 Operator Function Syntax operator+ is a formal function name that can be used like any other function name. We could have called the operator+ function in the formal way as d = operator+(operator+(a, b), c); But who would want to write code like that? Operator functions in C++ are just like ordinary functions, except that they also can be called with a nicer syntax similar to the usual mathematical notations. The operator + has a formal name, namely operator+ (consisting of 2 keywords), and a “nickname,” namely +. The formal name requires you to call it as operator+(a, b) while the simple nickname let you call it as a+b Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 32 / 83 Operator Syntax . . . The nickname can only be used when calling the function. The formal name can be used in any context, when declaring the function, defining it, calling it, or taking its address. There is nothing that you can do with operators that cannot be done with ordinary functions. In other words, operators are just syntactic sugar. Be careful when defining operators. There is nothing that inhibits you from coding operator+ to do, e.g., subtraction. Similarly, nothing inhibits you from defining operator+ and operator+= so that the following 2 expressions: a = a + b and a += b, have 2 different meanings. However, your code will become unreadable. Don’t shock the user! Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 33 / 83 C++ Operators Almost all operators in C++ can be overloaded except: . :: ?: .* (reason) The C++ parser is fixed. That means that you can only re-define existing operators, and you cannot define new operators (using new symbols). Nor can you change the following properties of an operator: 1. Arity: the number of arguments an operator takes. e.g., !x x+y a%b s[j] (So you are not allowed to re-define the + operator to take 3 arguments instead of 2.) 2. Associativity: e.g. a+b+c is always identical to (a+b)+c. 3. Precedence: which operator is done first? e.g., a+b*c is treated as a+(b*c). Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 34 / 83 C++ Operators: Member or Non-member Functions All C++ operators already have predefined meaning for the built-in types. It is impossible to change their meaning. You can only overload operators for your own (user-defined) classes (such as Vector in the example above) with new meanings. Therefore, every operator function you define must implicitly have at least one argument of a user-defined class type. You may define a (new) operator function as a member function of a new class, or as a global non-member function. As a global function, operator+ has 2 arguments. When it is called in an expression such as a + b, it is equivalent to writing operator+(a, b). More about defining operator function as a member function of a class later. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 35 / 83 Global Non-member Operator<< Function void print() const { cout << "(" << x << ", " << y << ")\n"; } Until now, one prints out a Vector object by calling its print function. Let’s write a non-member operator<< function to print Vector objects more naturally by using cout or cerr. The syntax should be similar to the one we use to print values of the basic types (such as int). E.g., cout << x; But cout and cerr are objects of the ostream class. So let’s generalize the operator<< function to print Vectors to any ostream objects. ostream is the base class for all possible output streams. To allow the usual output syntax with cout on the left, the ostream object must be the first argument in the function. Question: Why does it return ostream&? Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 36 / 83 Global Non-member Operator<< Function .. #include /* File: vector0-op-add-os.cpp */
#include “vector0.h”
using namespace std;
ostream& operator<<(ostream& os, const Vector& a) { return (os << '(' << a.getx() << ", " << a.gety() << ')'); } Vector operator+(const Vector& a, const Vector& b) { return Vector(a.getx() + b.getx(), a.gety() + b.gety()); } int main() { Vector a(1.1, 2.2); Vector b(3.3, 4.4); cout << "vector + vector: a + b = " << a + b << endl; cout << "vector + scalar: b + 1.0 = " << b + 1.0 << endl; cout << "scalar + vector: 8.2 + a = " << 8.2 + a << endl; return 0; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 37 / 83 Global Non-member Operator<< Function ... The operator<< returns an ostream object because we like to cascade outputs in one statement such as: Vector a(1, 0); cout << " a = " << a << "\n"; The second line is equivalent to: operator<<(operator<<(operator<<(cout," a = "),a),"\n"); This can only work if operator<< returns the ostream object itself. Question: Could we define operator<< as a member function? Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 38 / 83 Operator+ Member Function Member operator functions are called using the same “dot syntax” by specifying an object of, for example, type Vector. If a is a Vector object, then the expression a+b is equivalent to a.operator+(b). To call the operator+ as a member function, the class object must be the left operand. (Here a.) Thus, when we define operator+ as a member function of Vector, it has only one argument — the first argument is implicitly the object on which the member function is invoked. Recall the implicit this pointer in all member functions. Thus, Vector operator+(const Vector& b) const; of the class Vector will be compiled into the following global function: Vector Vector::operator+(const Vector* this, const Vector& b); Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 39 / 83 Operator+ and Operator+= Member Functions #include /* File: vector-op-add.h */
class Vector
{
public:
Vector(double a = 0, double b = 0) : x(a), y(b) { }
double getx() const { return x; }
double gety() const { return y; }
Vector operator+(const Vector& b) const;
const Vector& operator+=(const Vector& b);
private:
double x, y;
};
Vector Vector::operator+(const Vector& b) const
{ // Return by value; any copy constructor?
return Vector(x + b.x, y + b.y);
}
const Vector& Vector::operator+=(const Vector& b)
{
x += b.x; y += b.y;
return *this; // Return by const reference. Why?
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 40 / 83

Operator+ and Operator+= Member Functions ..
#include “vector-op-add.h” /* File: vector-op-add-test.cpp */
using namespace std;
ostream& operator<<(ostream& os, const Vector& a) { return (os << '(' << a.getx() << ", " << a.gety() << ')'); } int main() { Vector a(1.1, 2.2); Vector b(3.3, 4.4); cout << "vector + vector: a + b = " << a + b << endl; cout << "vector + scalar: b + 1.0 = " << b + 1.0 << endl; cout << "scalar + vector: 8.2 + a = " << 8.2 + a << endl; // Error a += b; cout<<"After+=:a="< /* File: word-test.cpp */
using namespace std;
#include “word.h”
int main() {
Word ship(“Titanic”);
Word movie(ship);
Word song(“My heart will go on”); // Which constructor?
}
song = song;
song = movie;
// Call assignment operator
// Call assignment operator
// Which constructor?
// Which constructor?
Rm 3553, desmond@ust.hk
COMP2012 (Fall 2020)
49 / 83

Member Operator= with Owned Data Members …
If a class contains pointer data members and dynamic memory allocation is required, the default memberwise assignment — shallow copy — is not adequate.
The copy constructor and operator= should be implemented using deep copy so that each object has its own copy of the owned data.
Since the copy constructor and operator= usually do the same thing, they may be defined by making use of the other.
Here, the copy constructor is defined by calling operator=.
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 50 / 83

Member Operator[ ] To Access Vector Component
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19 20 21
#include /* File: vector-op-index.h */
using namespace std;
class Vector {
public:
Vector(double a = 0, double b = 0) : x(a), y(b) { }
double operator[](int) const; // Read-only; c.f. getx() and gety()
double& operator[](int); // Allow read and write
private:
double x, y;
};
double Vector::operator[](int j) const {
switch (j) {
case 0: return x;
case 1: return y;
default: cerr << "op[] const: invalid dimension!\n"; } } double& Vector::operator[](int j) { switch (j) { case 0: return x; case 1: return y; default: cerr << "op[]: invalid dimension!\n"; } } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 51 / 83 Member Operator[ ] To Access Vector Component .. 1 #include "vector-op-index.h" /* File: vector-op-index-test.cpp */ 2 3 // Replace getx(), gety() by op[] 4 ostream& operator<<(ostream& os, const Vector& a) // Which op[]? 5{ 6 7} 8 9 int 10 { 11 12 13 14 15 16 17 18 19 } return(os<<'(' < /* File: vector-op-incr-test.cpp */
#include “vector-op-incr.h”
using namespace std;
ostream& operator<<(ostream& os, const Vector& a) {return(os<<'(' < const int days_in_month[] /* File: date.h */
= { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
class Date // Only for non-leap years
{
private:
int days; // Days in a non-leap year; must be within [1, 365]
public:
Date(int n): days((n < 1 || n > 365) ? 1 : n) { }
bool operator<(const Date& x) const { return (days < x.days); } int month() const { for (int remain_days = days, m = 0; m < 12; ++m) if (remain_days <= days_in_month[m]) return m+1; else remain_days -= days_in_month[m]; } int day() const { for (int remain_days = days, m = 0; m < 12; ++m) if (remain_days <= days_in_month[m]) return remain_days; else remain_days -= days_in_month[m]; } }; Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 58 / 83 A Student Class That Overloads Operator>
class Student /* File: student.h */
{
friend ostream& operator<<(ostream& os, const Student& s) { os << "(" << s.name << " , " << s.dept << " , " << s.GPA << ")"; return os; } private: string name; string dept; float GPA; public: Student(string n, string d, float x) : name(n), dept(d), GPA(x) { } bool operator<(const Student& s) const { return GPA < s.GPA; } }; Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 59 / 83 Example: Function Template + Operator Overloading #include /* File: larger-calls.cpp */
using namespace std;
#include “date.h”
#include “student.h”
template inline const T&
larger(const T& a, const T& b) { return (a < b) ? b : a; } int main() { int x = 4, y = 8; cout << larger(x, y) << " is a bigger number." << endl; string a("cheetah"), b("gorilla"); cout << larger(a, b) << " is stronger!" << endl; Date date1(120), date2(300); Date r = larger(date1, date2); cout << r.month() << "/" << r.day() << " is a later date.\n"; Student adam("Adam", "CSE", 3.8), joseph("Joseph", "MAE", 3.8); cout << larger(joseph, adam) << " has a better GPA!" << endl; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 60 / 83 Template + Operator Overloading: Be Careful 8 is a bigger number. gorilla is stronger! 10/27 is a later date. (Adam , CSE , 3.8) has a better GPA! Read carefully the semantics of a function template before using it. larger() is originally designed to compare numerical values. If the 2 inputs are the same, it doesn’t matter which one it returns. However, Students are objects! You use larger() to compare their GPAs which are just one component of the objects, but then return the whole object. Now, if their GPAs are the same, who is to return? That is, the return type is not the same as the type of things you are comparing with. Otherwise, template + operator overloading + creativity may lead to powerful generic programming. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 61 / 83 Summary: Member or Non-member Operator Functions The operators: = (assignment), [ ] (indexing), ( ) (call) are required by C++ to be defined as class member functions. A member operator function has an implicit first argument of the class. Thus, if the left operand of an operator must be an object of the class, it can be a member function. If the left operand of an operator must be an object of other classes, it must be a non-member function. e.g., operator<<. For commutative operators like + and *, it is usually preferred to be defined as non-member functions to allow automatic conversion of types using the conversion constructors. string x("dot"), y("com"), z; z = x + y; z = x + "com"; z = "dog" + y; Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 62 / 83 Part III Friend Functions or Classes Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 63 / 83 Operator<< as a Member Function Let’s try to implement operator<< as a member function. #include /* File: vector-os-nonfriend.h */
class Vector
{
public:
Vector(double a = 0, double b = 0) : x(a), y(b) { }
double getx() const { return x; }
double gety() const { return y; }
ostream& operator<<(ostream& os); private: double x, y; }; ostream& Vector::operator<<(ostream& os) { return(os<<'(' < /* File: vector-os-nonfriend.cpp */
using namespace std;
#include “vector-os-nonfriend.h”
Vector operator+(const Vector& a, const Vector& b)
{ return Vector(a.getx() + b.getx(), a.gety() + b.gety()); }
int main() {
Vector a(1.1, 2.2);
Vector b(3.3, 4.4);
Vector d = a + b;
// Do you notice the strange output syntax?
d << (cout << "vector + vector: a + b = ") << endl; (b + 1.0) << (cout << "vector + scalar: b + 1.0 = ") << endl; (8.2 + a) << (cout << "scalar + vector: 8.2 + a = ") << endl; } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 65 / 83 Issues of Operator<< as a Member Function operator<< is a binary operator. As a member function, the Vector object must be on the left of << and cout on the right. To print a Vector x, now you have to write: x << cout; Furthermore, to cascade outputs, say, to print Vectors x, y and then z, now you will have to write: z << (y << (x << cout)); instead of the usual output syntax: cout << x << y << z; For such kinds of operators, it is better to implement them as global non-member functions. Two issues: 1. Since global non-member functions can’t access private data members, don’t forget to provide the latter with public assessor member functions. 2. However, non-member operators are less efficient due to the additional calls to assessor functions. A solution: Making friends! Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 66 / 83 Friend Member Operator<< #include /* File: vector-with-friends.h */
using namespace std;
class Vector
{
friend ostream& operator<<(ostream& os, const Vector& a); friend Vector operator+(const Vector& a, const Vector& b); public: Vector(double a = 0, double b = 0) : x(a), y(b) { } private: double x, y; }; ostream& operator<<(ostream& os, const Vector& a) {return(os<<'(' <print(); cout << ' '; } cout << endl; #endif // V_STUDENT_H Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 73 / 83 Student with a Bad Hacker Friend: hacker.h #ifndef HACKER_H #define HACKER_H #include "v-student.h" class Hacker { private: string name; /* File: hacker.h */ public: Hacker(const string& s) : name(s) { } void add_course(Student& s) { s.GPA = 0.0; } #endif // Uh oh!! }; Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 74 / 83 Student with a Bad Hacker Friend: Ooops #include
using namespace std;
#include “v-student.h”
#include “hacker.h”
int main() {
/* File: bad-friend.cpp */
Student freshman(“Naive”, CIVL, 4.0);
Hacker cool_guy(“$#%&”);
freshman.print();
freshman.add_course(“COMP2012H”);
freshman.print();
cool_guy.add_course(freshman);
freshman.print();
return 0;
}
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 75 / 83

Further Reading:
Templates with Multiple Arguments and Different Return Type
Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 76 / 83

larger Template w/ Multiple Arguments I
1 #include /* File: larger-cond-statement.cpp */
2 using namespace std;
3
4 template
5 inline const T1& larger(const T1& a, const T2& b)
6{
7 8 9
10
11 } 12
13 int
14 {
15
16
17 }
if (a < b) return b; else return a; main() cout << larger(4, 5.5) << endl; // T1 is int, T2 is double cout << larger(5.5, 4) << endl; // T1 is double, T2 is int Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 77 / 83 Problem with fcn-template-2arg.cpp larger-cond-statement.cpp: In instantiation of const T1& larger(const T1&, const T2&) [with T1 = int; T2 = double]: larger-cond-statement.cpp:8:16: warning: returning reference to temporary [-Wreturn-local-addr] return b; ^ larger-cond-statement.cpp: In instantiation of const T1& larger(const T1&, const T2&) [with T1 = double; T2 = int]: larger-cond-statement.cpp:8:16: warning: returning reference to temporary [-Wreturn-local-addr] return b; ^ Problem: if the condition is true, the program has to convert the value b of type T2 to type T1&. Another complication is that the program returns by const reference. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 78 / 83 Problem: Reference to a Different Type 1 #include /* File: convert-reference-err.cpp */
2 using namespace std;
3
4 int main()
5{
6 double x = 5.6;
7 int&ip=x;
8 cout << ip << endl; 9 return 0; 10 } convert-reference-err.cpp:7:10: error: non-const lvalue reference to type ’int’ cannot bind to a value of unrelated type ’double’ int& ip = x; ^~ Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 79 / 83 Solution: const Reference to a Different Type Is OK 1 #include
2 using namespace std;
3
4 int main() 5{
6 double x = 5.6;
7 const int& ip = x;
8 cout << ip << endl; 9 return 0; 10 } /* File: convert-reference.cpp */ Line 7: a temporary int variable is created from double x to which ip is referenced to. Similarly, for the program “larger-cond-statement.cpp”, when the returned value is of a different type, 􏰢 a temporary variable of type T1 is created from b so that it can be returned by reference of type const T1&. 􏰢 on return to main, main tries to output the value of a temporary variable on the released activation record of larger ⇒ runtime error! Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 80 / 83 larger Template w/ Multiple Arguments II 1 #include /* File: larger-cond-expression-rbcr.cpp */
2 using namespace std;
3
4 template
5 inline const T1& larger(const T1& a, const T2& b)
6 { return (a < b) ? b : a; } 7 8 int main() 9{ 10 cout << larger(4, 5.5) << endl; // T1 is int, T2 is double 11 cout << larger(5.5, 4) << endl; // T1 is double, T2 is int 12 } The use of the conditional operator ? : has further complication when the types T1 and T2 are different as the expression can only return one single type. The rule is that when T1 and T2 are different. 􏰢 the returned value is an rvalue. Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 81 / 83 larger Template w/ Multiple Arguments II .. 􏰢 the returned type is the common type between them. In our case, it is double. Thus, again a temporary variable is created to convert the resulting rvalue from the conditional expression to const T1&, and we have the same problem as before. A solution is to change from RBR to RBV. 1 #include /* File: larger-cond-expression-rbv.cpp */
2 using namespace std;
3
4 template
5 inline T1 larger(const T1& a, const T2& b)
6 { return (a < b) ? b : a; } 7 8 int main() 9{ 10 cout << larger(4, 5.5) << endl; // T1 is int, T2 is double 11 cout << larger(5.5, 4) << endl; // T1 is double, T2 is int 12 } Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 82 / 83 That’s all! Any questions? Rm 3553, desmond@ust.hk COMP2012 (Fall 2020) 83 / 83