Below is the code for the node class used with the singly linked list class in C++.
class IntSLLNode {
public:
int info;
class IntSLLNode *next;
IntSLLNode(int el, IntSLLNode *ptr = 0) {
info = el; next = ptr;
}
};
The constructor for this class uses a special feature in C++ called the default parameter. The second parameter in the constructor uses the syntax
IntSLLNode *ptr = 0
to indicate that it is a default parameter. A default parameter supplies a default value to use for that parameter in cases where the caller has not supplied that parameter. For example, the code
head = new IntSLLNode(x);
is missing the second parameter, so the default value of 0 will be used for that parameter automatically. Thus, this code is equivalent to
head = new IntSLLNode(x,0);
The only special restriction on default parameters is that all default parameters must appear at the end of the parameter list. In cases where there are multiple default parameters, the compiler automatically assigns any parameter values supplied by the caller to the parameters in left-to-right order and uses the default values to fill in any missing parameters at the end of the list. For example, given the function definition
int foo(int a,int b = 5,int c = 8)
{
return a + b*b + c*c*c;
}
the call
z = foo(1,2);
is equivalent to
z = foo(1,2,8);
Over the next couple of lectures I am going to be talking about a collection of C++ language features all centered around the concept of generic programming. Generic programming is actually a combination of two closely related ideas, generic data structures, and generic algorithms.
The premier example of generic programming in C++ is found in the C++ Standard Template Library (STL for short), which is a collection of generic data structures along with a collection of useful generic algorithms that can be used with those data structures. The purpose of the next two lectures in this class is to present the set of C++ language concepts needed to understand and work with the STL.
The C++ template mechanism allows us to write generic functions that work regardless of the data types involved. Here a template version of the sort function that implements selection sort.
template <class T>
void sort(T X[],int N) {
// Use selection sort to sort the array
for(int n = 0;n < N - 1;n++) {
T smallest = X[n];
int where = n;
for(int k = n + 1;k < N;k++)
if(X[k] < smallest) {
smallest = X[k];
where = k;
}
X[where] = X[n];
X[n] = smallest;
}
}
The code for this function looks just like the code for the ordinary selection sort acting on ints or any other data type. The only difference is that we have replaced the int data type with a generic type called T and slapped a template declaration onto the start of the function. When we use a template function in a program, the compiler will automatically figure out what type needs to be substituted for T and compile a custom version of the function. For example, we can use this template sorting function to sort arrays of ints or strings:
int x[100]; string y[50]; // Load the arrays with data... sort(x,100); // sorts an array of ints sort(y,50); // sorts an array of strings
This works well as long as any type that we try to substitute for T understands all of the operations that are being applied to it in the code for the sort function. In particular, this code will only work for types for which the comparison operator < is defined. Below we will see how to get around that problem in cases where the < operation is not defined initially.
Another application of the template concept is to create template classes. A template class is a class in which the types of some of the data members have been replaced by placeholders. For example, we can use the template mechanism to create a completely generic ArrayList class:
template <class T>
class ArrayList
{
private:
T *A;
int N;
public:
ArrayList(); // Default constructor
ArrayList(int size); // Standard constructor
ArrayList(const ArrayList<T> &other); // Copy constructor
~ArrayList(); // Destructor
ArrayList<T>& operator=(const ArrayList<T>& other);
int size() const;
void resize(int newSize);
void set(int n,const T& x);
T get(int n) const;
};
Once a class has been made a template class we have to use a special template syntax to declare instances of that class or write the code for the class member functions.
ArrayList<int> x(100); // How to declare a templated class variable
template<class T>
void ArrayList<T>::resize(int newSize)
{
T *temp = new T[newSize];
int max = newSize;
if(newSize > N)
max = N;
for(int k = 0;k < max;k++)
temp[k] = A[k];
delete[] A;
A = temp;
N = newSize;
}
Although it is possible to use the 'separate class declaration and function definitions' approach with template classes, in practice it works better not to separate the two. It turns out that you can write the code for member functions right into the class declaration just as you do in Java. That approach works best for template classes. From here on out, for most template classes we study you are going to see the entire code for that class packed into a class declaration sitting in a header file.
C++ makes a fundamental distinction between primitive types like int, char, and double and classes. One aspect of this distinction is that many basic operations simply will not work with classes. For example, suppose we want to make a class to represent times.
class Time
{
private:
int hour,min,sec;
// Convert s 'raw seconds' to the equivalent hour, min, sec values
void Convert(int s);
public:
// Constructor functions
Time(); // Default constructor - initializes to 0:0:0
Time(int s); // Initialize from raw seconds
Time(int hr,int m,int s); // Initialize from hour/min/sec
// Accessor functions
int getHours() const;
int getMinutes() const;
int getSeconds() const;
int getTime() const; // Return the equivalent time in raw seconds.
// Mutator functions
void add(const Time& other); // Add another time to yourself
void add(int t); // Add t seconds to your time
void subtract(const Time& other); // Subtract this time from yourself
void subtract(int t); // Subtract t seconds from your time
};
Given the class declaration above, none of these statements are legal:
Time worked = out - in; // Illegal - can't subtract Time objects cout << worked; // Illegal - can't write a Time to cout string str = (string) worked; // Illegal - can't cast a Time to a string
The problem in each of these cases is that none of the operations we are trying to carry out have been defined. Nonetheless, it would be really convenient to be able to write this code. Fortunately, C++ offers a handy syntactical mechanism that makes it possible to define each of these operations. This mechanism is the operator overload mechanism.
In C++ we say that a function or other operation is overloaded if there are two or more functions with the same name that differ in the parameters they take. The Time class already contains some examples of overloaded functions. Both the add and subtract member functions are overloaded. The two functions in each case differ in the number or type of parameters they take, so the compiler can use the number or type of the parameters to distinguish between the two functions. Consider this example:
Time x(5,0,30); x.add(200); // Add 200 seconds - use the second version of add. Time y(12,20,0); y.add(x); // Add x to y - use the first version of add
C++ makes it possible to overload ordinary operators as well. To do this, C++ uses a special implicit function notation for operators. This is best explained through an example. We would like to rewrite the example above using more natural notation:
Time x(5,0,30); x += 200; // Add 200 seconds Time y(12,20,0); y += x; // Add x to y
Unless we do something special to define what '+=' means for Time objects, this operation will be undefined. The first step to making this legal would be to change the name of the functions we use to do addition and subtraction in the declaration to the Time class:
class Time
{
private:
int hour,min,sec;
// Convert s 'raw seconds' to the equivalent hour, min, sec values
void convert(int s);
public:
// Constructor functions
Time(); // Default constructor - initializes to 0:0:0
Time(int s); // Initialize from raw seconds
Time(int hr,int m,int s); // Initialize from hour/min/sec
Time(const Time& other); // Copy constructor
// Accessor functions
int getHours() const;
int getMinutes() const;
int getSeconds() const;
int getTime() const; // Return the equivalent time in raw seconds.
// Mutator functions
Time& operator+=(const Time& other); // Add another time to yourself
Time& operator+=(int t); // Add t seconds to your time
Time& operator-=(const Time& other); // Subtract this time from yourself
Time& operator-=(int t); // Subtract t seconds from your time
Time& operator=(const Time& other); // operator=
};
Operator overloads make it possible to redefine basic operators to make them apply to new data types. Once we have provided an operator overload for the += operator we will be able to use that operation with Time objects. Now when the compiler encounters the statement
x += 200;
it will try to reinterpret the code as a function call involving an operator function:
x.operator+=(200);
Now that we have provided this operator for Time objects the compiler will know what to do with this code.
Here is an example showing how to write code for one of these operator member functions.
Time& Time::operator+=(const Time& other) {
// Add our seconds value to other's seconds value.
int newSecs = this->getSeconds() + other.getSeconds();
// Make that be our new time value
this->convert(newSecs);
// return a reference to ourselves.
return *this;
}
When the C++ compiler encounters an operator expression involving non-primitive types it will try a couple of different options for how to interpret the expression as a function call. Consider this example.
Time now(3,15,30); Time later = now + 30;
When the compiler encounters the expression now + 30 it will try interpreting it in one of two ways:
now.operator+(30); operator+(now,30);
In the first case the compiler goes looking for a member function in the Time class called operator+. In the second case it goes looking for a free function named operator+ that takes a Time object and an int as its parameters. If either of these functions is defined somewhere, the compiler will use it to evaluate the expression now + 30.
Given that you have a choice to create either form, which should you choose? As a general rule, operator overloads for binary operators like + should be written as free functions. Here is what the free function version of operator+ looks like.
Time& operator+(const Time& t,int n) {
int newSecs = t.getSeconds() + n;
return Time(newSecs);
}
Why are the free function forms better? The free forms provide greater symmetry between the two operands. We can take advantage of that symmetry to write a version of operator+ that takes an int and a Time as its parameters.
Time& operator+(int n,const Time& t) {
int newSecs = n + t.getSeconds();
return Time(newSecs);
}
This will allow the compiler to compile both of the statements below:
Time later = now + 30; Time evenLater = 30 + later;
Operator signatures
One of the more confusing aspects of operator overloading in C++ is the fact that each operator that the language recognizes comes with a signature consisting of the types it takes as its parameters and the type it is supposed to return. To properly overload an operator you have to know both of these things. With a little bit of practice you can quickly learn to guess what parameter types are appropriate, but knowing when and how to return something is a little trickier.
For example, it is immediately obvious that operator+ should return a Time object when you use it to do addition with Time objects. A less obvious example is the code for the stream insertion operator, operator<<:
ostream& operator<<(ostream& out,const Time& t)
{
out << t.getHours();
out << ':' << t.getMinutes();
out << ':' << t.getSeconds();
return out;
}
The reason that operator<< needs to return its first parameter is to make it possible to chain several instances of operator<< together. Consider this example.
Time breakfast(7,30,0); Time lunch(12,0,0); cout << "Meal times are " << breakfast << " and " << lunch;
The compiler will translate the third statement to
operator<<(
operator<<(
operator<<(
operator<<(cout,"Meal times are "),
breakfast),
" and "),
lunch);
For all of this to work properly, each call to operator<< has to return a reference to cout so that the next operator<< in the call sequence can use cout as its first parameter.
Let us now return to the generic sorting function I introduced above.
template <class T>
void sort(T X[],int N) {
// Use selection sort to sort the array
for(int n = 0;n < N - 1;n++) {
T smallest = X[n];
int where = n;
for(int k = n + 1;k < N;k++)
if(X[k] < smallest) {
smallest = X[k];
where = k;
}
X[where] = X[n];
X[n] = smallest;
}
}
If you tried using this sort function on an array of Time objects as defined above, you would get a compiler error something like the following:
error C2676: binary '<' : 'Time' does not define this operator or a conversion to a type acceptable to the predefined operator
The fix for this problem is to supply the appropriate comparison operator for the Time class via an overload of the < operator:
bool operator<(const Time& one,const Time& two)
{
return one.getTime() < two.getTime();
}
With this capability in place, we have now worked around the most significant obstacle to making truly generic algorithms.