Courses/CS 2114/Lab Manual/Chapter 14

From A-State Computer Science Wiki
Jump to: navigation, search

Operator Overloading and Templates

A portion of this lab is to be done during the scheduled lab time. The take-home programming assignment is to be turned in before the next lab; see the lab website. The in-lab portion is worth 40% of the lab credit; the programming assignment is worth the other 60%. See the website for details on how the programming assignment will be graded. You are not responsible for user errors in input unless specified in the assignment. Feedback will be provided explaining your grade on each assignment.

It is important that you complete each step before going on to the next, as the exercises build upon one another. You will find it helpful to diagram the action of each method or function as you go along. If you have difficulty in some step, DO NOT proceed before resolving it; seek assistance from your lab proctor. You will not be able to fully appreciate the remaining content of the lab and you are likely to compound the problem.

Introduction

In order to create code that is as generally useful as possible, C++ supports the ability to extend the available set of operators to work with new types of data. This is accomplished through operator overloading. Additionally, it is possible to create generic functions that can perform an algorithm that is data type agnostic on any type of data. This is made possible by implementing function templates. This lab will examine operator overloading and function templates in the context of abstract data types.

Topics Covered in this Lab:
  • Overloading C++ binary operators
  • Overloading C++ unary operators
  • Generic functions using template

Questions Answered in this Lab:

  • How can operators be overloaded in C++
  • What parameters are required for overloading a binary C++ operator?
  • What parameters are required for overloading a unary C++ operator?
  • What is generic programming?
  • What are function templates?
  • What are template parameters? What do they represent?

Demonstrable Skills Acquired in this Lab:

  • Ability to overload unary and binary operators in C++.
  • Ability to create function templates in C++.
  • Ability to recognize the data requirements inherent in a function template, and communicate those requirements in documentation.

Getting Started

Start a program in file sp_operators_templates_iL.cpp. You will need to add #include directives and using statements as needed as you progress with this lab.

During the course of this lab, you will be defining new abstract data types using structures, and then develop functionality through the use of overloaded operators and function templates. You should add the code to your program as necessary to implement and test the features under discussion. All structures should be defined at global scope.

A 2-D Vector

In math, a vector is used to represent a value that has both a magnitude and a direction. Such values are very useful in scientific applications, physics simulations, and game programming. Vectors are used to describe concepts such as velocity, acceleration, and force. If you are unfamilliar with the basic concept of a vector, take a moment to read over the information at [1].

For the sake of simplicity, we will define a 2-dimensional Vector2D structure as follows:

Verbatimcode.pngCode Illustration
/**
 * A 2-dimensional Euclidean vector
 */
struct Vector2D{
    double x;       // component in the x direction
    double y;       // component in the y direction
};

Common vector operations that we want to implement include:

  • determining the magnitude (or "length") of the vector
  • addition
  • reversal
  • subtraction
  • multiplication by a scalar value
  • dot product (or "inner product")
  • ability to input a vector using standard notation
  • ability to output a vector in standard notation
  • ability to compare two vectors with relational operators

In order for you to test and demonstrate your code as you work on the mathematical operators, it would be nice to be able to do input and output of Vector2Ds directly using the familliar >> and << operators. For this reason the overloaded stream operators will be given priority and developed first.

Stream insertion using the << operator is accomplished by first defining a simple textual representation of the data, in terms of the existing parts and operators that are already defined to work on those parts. The stream insertion operator expects an output stream (type std::ostream) as its left-hand operand, and the object being inserted into the stream on the right. The operator itself evaluates to the stream (so that stream insertion can be cascaded). The prototype for an overloaded stream insertion operator for use with a Vector2D value would look like:

std::ostream& operator<<(std::ostream& stream, const Vector2D& rhs);

Notice that the stream is both passed to the function by reference and also returned by reference. This is so that no copy of the active stream is ever made; it wouldn't make sense to create a copy of a stream since the resource that stream is attached to may be exclusive (there is only one instance of the output terminal on the system). As for an output format for a vector, a common mathematical notation for vectors specified as directional components is:

\langle 3, 4 \rangle

The above would represent a 2-D vector with an x component of 3 and a y component of 4. Since the angle brackets used to enclose the components are similar to the angle brackets we are used to on the keyboard, we can use those. So our output of the same vector would look like:

<3,4>

Implement the overloaded stream insertion operator for Vector2D now.

Stream extraction using the >> operator is the logical inverse of the stream insertion operation defined above. Since we chose the output format in which the components are surrounded by angle brackets and separated by a comma, we must account for that same format when doing input. In order to make our input as robust as possible, we should also be agnostic of whitespace surrounding the parts of the input value. And since even mathematicians do not all agree on the "angle bracket" syntax (some use parentheses instead), we can write our algorithm in such a way that the brackets don't actually matter. Thus, the algorithm would be:

1. read a single character (ignoring whitespace) -- this is the open bracket
2. read the value of the x-component (ignoring whitespace)
3. read a single character (ignoring whitespace) -- this is the comma
4. read the value of the y-component (ignoring whitespace)
5. read a single character (ignoring whitespace) -- this is the close bracket

Note that in all cases where the single character values are being read, the actual value of that character is unimportant for our protocol; the character is used to indicate position in the input, but otherwise it is ignored.

Much like the stream insertion operator above, the stream extraction operator is a binary operator that expects the output stream to be its left-hand operand and the item being filled with data to be its right-hand operand. And like the stream insertion operator, the >> operator should return the stream itself to allow cascading. The type of a generic input stream is std::istream. Thus, the prototype is:

std::istream& operator>>(std::istream& stream, Vector2D& rhs);

One difference is that in this case the Vector2D is not held constant — the purpose of the stream extraction operator is to fill in the value of the item on its right from the stream on its left. So the right-hand operand must be modified by the operation. Implement the stream extraction operator now.


Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate that your stream insertion and stream extraction operators are working properly.


Vector length, or magnitude (also sometimes called the norm) is written mathematically as \|\mathbf{a}\| where \mathbf{a} is the name of a vector. It is easily computed using the Pythagorean theorem:

\|\mathbf{a}\| = \sqrt{x^2 + y^2}

Implement a function to determine the length of a vector, providing the prototype:

double length(const Vector2D& a);

Addition of vectors is defined in terms of simply adding the x and y components of each. The result of this addition is also a vector:

\mathbf{c}=\mathbf{a}+\mathbf{b}
\mathbf{c}=\langle\mathbf{a_x}+\mathbf{b_x} , \mathbf{a_y}+\mathbf{b_y}\rangle

Implement an overloaded operator+ for adding two Vector2D values, with the following prototype:

Vector2D operator+(const Vector2D& lhs, const Vector2D& rhs);

Note that both the left- and right-hand operands are passed by const reference so that no copies are made; but the addition operation should not modify either operand either. The return value is a Vector2D, which is a third vector, represented by \mathbf{c} in the formulas above.

Reversal: Subtraction of vectors involves first reversing the direction of the vector on the right-hand side of the subtraction, then adding them. The reversal of a vector \mathbf{a} is expressed mathematically as:

-\mathbf{a}

This operation looks like mathematical negation (a unary operation), and in fact it is a natural extension of the negation concept. A vector is reversed by negating the values of its x and y components:

-\mathbf{a} = \langle -\mathbf{a_x} , -\mathbf{a_y} \rangle

This provided a strong argument for overloading the unary - operator to perform vector reversal. The prototype for the unary - operator would be:

Vector2D operator-(const Vector2D& rhs);

Importantly, the negation operation returns a reversed copy of the original value; it does not change the original variable in any way. For this reason, the parameter should be passed by const reference. Implement this function now.

Subtraction: Now that you have a working vector reversal operator, you can define vector subtraction in terms of reversal and addition:

\mathbf{c}=\mathbf{a} - \mathbf{b}
\mathbf{c}=\mathbf{a} + -\mathbf{b}

The usual binary subtraction operator - will work just fine for this operation. Overload the binary - operator to perform vector subtraction (in terms of negation and addition) at this time. The prototype should look almost identical to the addition operator's prototype (except for the operator symbol, of course).


Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate that your length, addition, reversal, and subtraction operators are working properly.


There are three multiplication-like operations defined for vectors:

  • scalar multiplication
  • dot product (or inner product)
  • cross product (or outer product)

Since our vectors are being constrained to 2 dimensions, however, the cross product would not make sense; it requires at least 3 dimensions to produce a cross product. In addition to this, there is only one "multiplication" operator available to us in C++ — the * operator. A closer look at the operations of scalar multiplication and dot product are in order before proceeding.

Scalar multiplication involves multiplying a vector by a scalar value (meaning just a regular Real number). This has the effect of scaling the vector — making its magnitude larger if the absolute value of the scalar is >1 or smaller if it is <1. Essentially this works just by multiplying the directional components of the vector \mathbf{a} by the scalar value x, producing a new scaled vector \mathbf{c}:

\mathbf{c} = x \cdot \mathbf{a}  
\mathbf{c} = \langle x \cdot \mathbf{a_x} , x \cdot \mathbf{a_y} \rangle

Since this operation really does involve multiplication in the traditional sense on each of the directional components, it makes perfect sense to overload the * operator for this purpose. It is worth noting that the scalar value may appear either to the left or the right of the vector, depending on the way the expression is written. The following two expressions are both possible:

\mathbf{c} = x \cdot \mathbf{a}  
\mathbf{c} = \mathbf{a} \cdot x

Of course, the compiler will not automatically allow both possibilities — if you write your overloaded operator such that the left-hand operand is type double, the compiler will only allow the first version. This means in order to make both versions work as expected you will need to provide two overloaded operator* functions — one with the scalar on the left and the other with the scalar on the right.

Even though you will need to create both versions of the function, you may observe that scalar multiplication is associative — the order of the operands does not matter to the result. So, you can (and should) define the second version of the function in terms of the first, avoiding any repeated code. Implement the overloaded * functions for scalar multiplication now.

Dot product (or inner product) is an operation that takes two vectors and multiplies them in such a way that a scalar value is produced. The physical interpretation of what this value means depends on your application, but one way of thinking of it (from a physics point-of-view) is this: How much energy/push is one vector giving to the other [2]? The formula for dot product is:

x = \mathbf{a} \cdot \mathbf{b}  
x = \mathbf{a_x} \cdot \mathbf{b_x} + \mathbf{a_y} \cdot \mathbf{b_y}

Note that the dot product is a scalar value (a Real number). Importantly though, the operation still "looks" a lot like multiplication; additionally, the operands are sufficiently different from the ones in the scalar multiplication case (they are both vectors) so that the * operator can be overloaded to perform this operation as well. Implement the overloaded * operator to perform the dot product operation now.


Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate that your scalar multiplication and dot product operations are working properly.


Relational operations on vectors are a more complicated subject, since the way vectors should be compared may depend upon the application. One possibility is that the magnitude and direction of the vectors are of equal importance when comparing them; thus, two vectors are equal if and only if their magnitude and directions are equal. This seems reasonable at first glance. However, if the same logic is applied to the concepts of "less-than" and "greater-than", then things get somewhat murky. What does it mean for the direction of vectors to be "less-than" or "greater-than"? Perhaps the concepts of "less-than" and "greater-than" apply only to the magnitude of the vector, but not the direction? If that is the case, why should the direction be used for asserting equality? It would certainly seem odd if two vectors pointing in very different directions were considered equal simply because their magnitude was the same...

In situations like this, the utility of overloaded operators must be weighed carefully with any confusion that might be caused if the operations do not behave in an intuitive way. Sometimes some context can help us make the decision about whether or not to overload an operator (and if so, how). In the case of a data value like a vector, it is likely that the programming use would be related to some physics property (like force, velocity, or acceleration). If that is the case, it would seem reasonable that a property such as "less-than" would refer to the amount of force/velocity/acceleration — the magnitude. Still, it would be hard to accept the idea that two vectors would be reported as "equal" with no regard given to their direction. Perhaps the following compromise could be acceptable, if properly and plainly documented:

Let the relational operators be defined as follows for type Vector2D values a and b:

a < b 
returns true if and only if the magnitude of a is less than the magnitude of b
a > b 
returns true if and only if the magnitude of a is greater than the magnitude of b
a <= b 
returns true if and only if the magnitude of a is not greater than the magnitude of b
a >= b 
returns true if and only if the magnitude of a is not less than the magnitude of b
a == b 
returns true if and only if the directional components of a are equal to the directional components of b
a != b 
returns true if and only if the directional components of a are not equal to the directional components of b

This compromise allows the "less-than" and "greater-than" operators to check the magnitudes of the vectors for operations like sorting or finding a min/max. The strict equality and inequality operators are used to define "same-ness" where two vectors are the same if and only if their component values are the same. Note that since all values involved in this process are floating-point, EPSILON comparisons should be employed throughout. For this purpose, you may create a global value for EPSILON, set to an appropriately small number. Implement the six relational operators now.


Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate that your relational operators are working according to the specifications above. Additionally, propose an alternative way of defining the relational operators besides the ones discussed above, with an example of why it might be useful.


Function Templates

The previous sections dealt with creating overloaded operators to make abstract data behave more like built-in data; in this section we will see a way of creating abstract functions and making them work with any type of data. Many algorithms are data agnostic in nature: they would logically apply equally well to any type of data value, provided that the data can behave in the ways required by the algorithm. For example, the algorithm for squaring a value is defined as:

 v^2 = v  \times  v

This algorithm holds true for any kind of value, provided that the multiplication operation is defined for that kind of value. C++ allows us to write functions in a data agnostic way by utilizing a language feature called function templates. Templates allow us to let the data type itself remain variable through the use of a template parameter, which is simply a named placeholder for a type. The actual type will be determined at compile-time by examining the type of the data being passed in the actual parameter. Consider a C++ implementation of the generic squaring algorithm shown above:

template<class ValueType>
ValueType square(const ValueType& v){
  return v * v;
}

The code template<class ValueType> is called the template specification (or template declaration). It tells the compiler that the function being defined (or prototyped) will be a function template, and gives the template parameter list (the part inside the angle brackets). The template parameter list is a comma-separated list of template parameters, which will take the form class ParamName or typename ParamName where ParamName is an identifier used to name the type parameter. The usual rules for identifiers apply to the type parameter name, but it is conventional to begin the name with an uppercase letter.

Once the type parameter has defined an alias for a type, the type parameter name may be used to stand in for that type (but only for a single type). For example, if the square() function shown above is called in the following way:

int ans = square(4);

The ValueType parameter will bind to the type int (which the compiler determines by examining the actual parameter 4 ). The compiler will therefore write a version of the square() function where ValueType is replaced with int. The compiler does the function overloading for you! Note that there is a deeper meaning here as well: The compiler does not compile the function template itself, and no memory is required by the function template. Only when the function template is actually used in a call will the compiler produce the corresponding code; this means there is less overhead (in terms of executable code size) to using templates than to manually overloading functions for possibilities that do not end up being used. Unfortunately, it also means that the compiler will not fully error-check code in function templates either; you must be sure to make the necessary calls to the function so that the compiler will write (and error-check) real code during testing.

In the following sections, you will create function templates to perform some common tasks; up until now you needed to re-write these functions each time you wanted to use them for a new type of data. With function templates, you will make the compiler do that work for you.

Bubblesort: Sorting an array in ascending order is one of the most common algorithms that must be performed. Almost any type of data may be sorted, provided that a reasonable way to compare the data for ordering can be found. You have written the Bubblesort function several times at this point for various types of data; write it now as a function template so that you don't have to re-write it for new data types. The prototype is:

template<class ValueType>
void bubble_sort(ValueType array[], int size);

You may assume that the data being sorted can be compared using the < operator (that is, the data to be sorted must have an overloaded operator<() function). You may also assume that the data being sorted can be assigned using the standard = operator. No other assumptions about the data should be made. Your documentation for this function should state what the requirements are for data to be sorted. Since the data type is allowed to vary, your documentation becomes very important for making sure any data constraints are understood by users of your code.

To test your bubble_sort function, create an array of 10 double values, another array of 10 string values, and a third array of 10 Vector2D values, and sort each of them.


Labcheckpoint.png FOR IN-LAB CREDIT: Demonstrate that your bubble_sort function works as expected with all three data types. Explain to the lab proctor what limitations are placed on the data type by the nature of the algorithm itself



Labsubmitsinglefile.pngFOR IN-LAB CREDIT: Upload the solution for each of the above lab steps in a file named sp_operators_templates_iL.cpp.