You Can Program In C++ (2006) [eng]

288 CHAPTER 16

struct bad_data: exception{ };

to the definition of rational.

You may want to add polish to the implementation of get from( ); at the very least, it is reasonable to ensure that we do not change the stored value in a rational object until we know we have successfully acquired the complete replacement value. Here is a modified version that provides that guarantee:

std::istream & rational::get_from(std::istream & in){ int n1, d1;

in >> n1;

if(in.get( ) != '/') throw rational::bad_data( ); in >> d1;

if(not in) throw rational::bad_data( ); n = n1; d = d1;

return in;

}

Now we can provide operator>> to extract a rational value from an input source. Add this definition to rational.h:

inline std::istream & operator>>(std::istream & in, rational & r){ return r.get_from(in);

}

Providing Multiplication for rational

We would normally expect to be able to multiply a rational number by an integer as well as by another rational number. We would also expect to be able to multiply an integer by a rational number. For example, we would expect the following code to compile and execute:

void test(rational & r, int i){ rational r1(2, 3);

std::cout << r << " times " << r1 << " is " << r * r1 << '\n'; std::cout << r << " times " << i << " is " << r * i << '\n'; std::cout << i << " times " << r << " is " << i * r << '\n';

}

Overloading operator* with a member function would deal with the first two cases. However, in the third case the left operand of * is not a rational (though it can be converted to one), and so the compiler will not be able to use a member function (the left operand of an operator determines which scope the compiler searches for an overload). This gives us the clue that we have another case where we should provide a global or namespace overload for the operator.

You might choose to use exactly the same mechanism as we did for the streaming operators: provide the functionality through a member function, and then delegate to that when providing the global operator overload. However, there is another option for arithmetic operators: provide an overload for the corresponding compound assignment operator as a class member. There is a sense in which the compound assignment operators are more primitive than the apparently simpler standard ones. Here is how to do it (the same basic design works for all arithmetic operators, for all user-defined arithmetic types).

Add this declaration to the definition of rational:

rational & operator*=(rational const &);

Now add this inline definition to the header file:

OVERLOADING OPERATORS AND CONVERSION OPERATORS

289

inline rational operator*(rational lhs, rational const & rhs){ return lhs *= rhs;

}

Note that the declaration of operator*=( ) returns by reference, but the definition of operator*( ) returns by value. Also, note that, because we do not want to alter the value of the left operand of operator*( ), we have to pass it by value.

Finally, add the implementation of *= to rational.cpp:

rational & rational::operator*=(rational const & r){ n *= r.n;

d *= r.d; return *this;

}

EXERCISES

2.Write a program that uses test( ) to test that the multiplication works correctly.

3.Implement and test division (operator/( )) for rational. (If you have forgotten your high-school math, we divide rationals by inverting the numerator and denominator of the right-hand operand and then multiplying.) At this point, you do not need to trap division by zero.

4.Implement and test addition and subtraction for rational. (If two rational numbers are represented by n1/d1 and n2/d2, their sum has numerator n1 * d2 + n2 * d1 and denominator d1 * d2.)

Conversion Operators

C++ overloads the operator keyword to support outward conversion operators that support implicit conversion from the class type to another type (single-argument constructors that have not been qualified as explicit provide inward conversions). These can be useful in some cases but must be treated with great care, because conversion operators (all kinds: built-in ones, single-argument constructors and outward conversion operators) often have surprising and unwanted consequences. For example, it seems reasonable to provide an implicit conversion from rational to one or more floating-point types. However, doing so is far from cost free.

Converting to double

Here is a declaration of an operator to provide an implicit conversion from a rational value to a double:

operator double( );

Add this definition to the implementation:

rational::operator double( ){ return double(n)/d;

}

290	CHAPTER 16

T R Y T H I S

Try the above conversion operator with the code we used earlier for testing multiplication.

If you have it right, the code now fails to compile with an ambiguity error for r * i (i.e. multiplying a rational by an int).

What is the problem? Once we provide a user-defined conversion from rational to double, the compiler has two choices for r * i. It can use the converting constructor to convert i to a rational (which is what it was doing before), and then use the operator*( ) we provided for rational. Alternatively, it can convert the rational into a double by using the conversion operator we have just provided, and then use the built-in multiplication for double. As far as the compiler is concerned, both of those conversions are of equal weight, and so it cannot choose between them. We have to resolve that ambiguity by removing one of the causes. We can remove one of the conversions, or explicitly tell the compiler which operand we wish to convert by using a cast. See also ‘Another Way to Deal With Ambiguity’ below.

As the conversion operator causes problems, we should consider other options. The simplest one is to provide an explicit conversion function such as

double to_double( );

implemented by:

double rational::to_double( ){ return double(n)/d

}

EXERCISE

5. Write a program that tests the use of to double( ) to convert from rational to double.

Another Way to Deal With Ambiguity

Another option for removing ambiguity is to provide several overloads for the operator in question. This often requires the addition of more overloads than at first seem necessary. For example, we could replace the single overload for rational operator*(rational lhs, rational const & rhs) with:

inline rational operator*(rational lhs, rational const & rhs){ return lhs *= rhs;

}

inline double operator*(double lhs, rational const & rhs){ return lhs * to_double(rhs);

}

inline double operator*(rational lhs, double rhs); return rhs * to_double(lhs);

}

inline rational operator*(long lhs, rational const & rhs)

OVERLOADING OPERATORS AND CONVERSION OPERATORS

291

return rational(lhs) * rhs;

}

inline rational operator*(rational lhs, long rhs) return lhs * rational(rhs);

}

The last two of those ensure that multiplication of a rational by an integer value will result in a rational value, rather than a double.

The moral of all this is that conversion operators are deceptive and often add complexity rather than removing it.

Tidying Up

There is a good deal more to do if we are to provide a robust, industrial-strength implementation of rational. For example, we should do something about trapping overflow of the values stored for the numerator and denominator. We should consider how to deal with attempts at constructing a rational from a floating-point type such as double. We should also consider providing a function to simplify rational values by eliminating common factors from the numerator and denominator. That last function might be a reasonable place to check for a zero denominator.

I am leaving you to deal with these issues because they do not directly concern the subject of this chapter. However, here is an example of how to block the construction of a rational from a double (assuming you want to block it rather than provide a way to do it); add this declaration to the private interface of rational:

rational(double);

It follows the same idea as we used earlier for blocking copy semantics; if you do not want something, declare it as private.

Function Objects

If you have never come across the idea before, you will probably find the idea that ( ) is an operator a little strange. If you then discover that C++ allows you to overload the ( ) operator, you will probably have a number of reactions – including doubting that it could be useful. While I understand such reactions, overloading operator( ) is one of the most powerful tools in C++. It is used extensively in that part of the Standard Library that is often referred to as the STL (Standard Template Library), which provides a rich collection of container types and functions to operate on them. We will be looking at some of these in the next chapter. It is also the basis for providing manipulators with arguments for iostream objects. (For example, std::setw( ), which sets the field width for input/output, uses overloading of operator( ) to achieve its objective.)

I am going to use a simple mathematical example to demonstrate how we can overload the function operator in a way that will make domain-specific code more approachable to the domain expert. Back in your school days, you would have drawn the graph of a mathematical function f(x). One way of doing this is to plot the points (x, f(x)) for a sample of values of x in the range required. We can express that in programming terms as:

void draw_graph(double lower, double upper, double interval, math_function & f){

double x(lower); do{

292 CHAPTER 16

plot(x, f(x));

} while((x += interval) < upper);

}

Would it not be nice if we could write exactly that? Here is a simple example of how to do that for a quadratic function. First, the class definition to go in quadratic.h (do not forget the header guards):

class quadratic{ public:

quadratic(int a, int b, int c); double operator( )const(double x);

private:

int a_, b_, c_;

};

And next the implementation (in quadratic.cpp):

quadratic::quadratic(int a, int b, int c):a_(a), b_(b), c_(c){ } double quadratic::operator( )const(double x){

return ((a_*x + b_)*x + c_);

}

We are almost done. Add the declaration

void draw_graph(double lower, double upper, double interval, quadratic const & f);

to quadratic.h, and add this implementation to quadratic.cpp:

void draw_graph(double lower, double upper, double interval, quadratic const & f){

double x(lower); do{

plot(x, f(x));

} while((x += interval) < upper);

}

Finally, we have to declare and implement plot( ). If you have acquired some fluency with my Playpen library, you might want to exercise it by using the fgw::plot( ) function provided in that library as a basis for plotting curves. If you do not want to do that, we can provide a version of plot( ) that writes out the coordinates to the console. As this is an implementation detail, it belongs in the unnamed namespace of quadratic.cpp. Here is the code:

namespace{

void plot(double x, double y){

std::cout << "(" << x << ", " << y << ")\n";

}

}

Now that we have all that done and compiled, here is a short test program:

#include "quadratic.h"

int main( ){

draw_graph(-4, 4, .2, quadratic(1, 3, 2));

}

OVERLOADING OPERATORS AND CONVERSION OPERATORS

293

If you are still a little puzzled, quadratic(1, 3, 2) constructs a temporary quadratic object and passes it to the last parameter of draw graph( ). Because that parameter takes a const reference, it can bind to a temporary.

EXERCISES

6.Enhance the above program so that the arguments for the call of draw graph( ) are provided at run time.

7.Modify draw graph( ) so that you can specify the output stream. Then test it with the following program:

#include "quadratic.h" #include <exception> #include <fstream>

int main( ){ try{

ofstream outfile("graph.data");

if(not outfile) throw "Cannot open graph.data for writing"; draw_graph(-4, 4, .2, quadratic(1, 3, 2), outfile);

}

catch(...){

std::cerr << "Something went wrong.\n";

}

}

Generalizing

You may feel that this is all very well, but it only works for quadratic functions; what about all the other mathematical functions that you might want to plot? Notice that the draw graph( ) implementation does not care what the function is. However, we have tied it to quadratic functions by declaring the type of the last parameter as quadratic. We can do with some polymorphic behavior that will fit the computation to the type of the function.

You may be surprised by how little change we need to provide. Add the following abstract base class to quadratic.h (perhaps not that good a name for the header file – change it if you want to)

struct math_function{

virtual double operator( )(double)const = 0; // pure virtual

};

Modify the definition of quadratic so that it inherits (publicly) from math function. Finally, change the type of the last parameter of draw graph( ) to math function &:

class quadratic: public math_function{ public:

quadratic(int a, int b, int c); double operator( )const(double x);

294 CHAPTER 16

private:

int a_, b_, c_;

};

void draw_graph(double lower, double upper, double interval, math_function & f){

double x(lower); do{

plot(x, f(x));

} while((x += interval) < upper);

}

That is it. The program you wrote for Exercise 6 should still work and produce the same results. Now you can add in other functions by deriving suitable classes from math function. Notice that draw graph( ) is now exactly what we started this section with.

S T R E T C H I N G E X E R C I S E

8.Review the way we encapsulated the idea of a general chess piece into a chesspiece type. Now design, implement, and test a function type that encapsulates a selection of mathematical functions. If you are already familiar with the concept of patterns and understand the factory pattern, try to produce a function factory. (Note that the latter is really too advanced for this book, but it is such an obvious development of the theme that I felt it worth mentioning.)

Conclusion

This chapter has only briefly touched on operator overloading, and there are many more aspects of it. The whole of the smart-pointer technology is built on the foundation of overloading operator* (the dereference operator, not the multiplication operator) and operator->. A great deal of the convenience of the STL containers depends on overloading operator[ ] (the subscript operator). Many of the algorithms provided for manipulation of containers depend on the ability to overload operator( ) (the function operator).

One of the biggest problems you will have with operator overloading is recognizing when it provides a good solution. It is also necessary to learn how to defuse the potential dangers of overloading operators. For example, it is relatively easy to provide a na¨ıve overload of the subscript operator. However, such implementations nearly always break encapsulation or behave in unexpected ways. Getting it right is not that hard, but you are unlikely to do so without guidance or many hours of debugging.

REFERENCE SECTION

Almost all the C++ operators can be overloaded. Some of them, such as assignment (=), subscript ([ ]), and function (( )) can only be overloaded in the context of a class. All of them require that at least one operand is of a user-defined type. When overloading an operator in class scope, the left-hand operand will be of that class type.

OVERLOADING OPERATORS AND CONVERSION OPERATORS

295

When the left-hand operand of an operator will be of a user-defined type whose definition cannot be changed, you have to overload the operator at global or namespace scope. It is usual to overload an operator whose operands are symmetrical (such as operator+ and operator==) at global or namespace scope.

Generally, the functionality for global/namespace overloads can be provided by a named function at class scope. The only time you should consider using the friend mechanism to provide access to a class’s private data when overloading an operator is if the operator needs access to the private members of two classes for its left and right operands.

You should be careful to restrict overloading of operators to places where you get real benefits. You need a clear understanding of why you are overloading an operator before doing it. Some operators, such as the sequence (comma) operator and the logic operators, where the built-in versions use lazy evaluation, are probably poor candidates for overloading, even though the language allows you to do so.

C H A P T E R 17

Containers, Iterators,

and Algorithms

One of the great strengths of C++ is the way that the Standard Library has used template technology to provide generic implementations of some of the basic building blocks of modern programming. Because of its historical origins, many people call the part of the Standard Library that provides these the Standard Template Library (usually just STL). Alex Stepanov and Dave Musser developed the basic ideas and implementation. Once they had proved the concept, they offered their work to the committees who were drafting the C++ Standard. The STL was clearly a great collection of components, and few people had any hesitation about adopting it into the Standard Library and then refining it.

Put simply, the STL has four elements, including: a set of containers (data structures); suitable iterators for those containers; and a set of functions that provide most of the common algorithms that programmers want to apply to containers. The important fourth element is that the C++ Standard specifies how a programmer can add a data structure that will work with the STL algorithms, and how to add algorithms to work with the STL containers. In other words, the STL is designed to be extensible.

The purpose of this chapter is to introduce you to some of the power of the STL, and encourage you to explore it further. The STL has one serious weakness for the newcomer: the names of the various components are sometimes less than intuitive, and the behavior of some components is not what their names imply. In other words, the names sometimes suggest different behavior, and sometimes the behavior you want will be provided by a name you would not guess. This means that a comprehensive reference plus access to experienced users is just about essential if you are to get maximum benefit. The best references are The Standard C++ Library [Josuttis 1999] and Generic Programming and the STL [Austern 1999]. The former is appropriate if you want to focus on using what is provided by the Standard Library, and the latter if you want to understand the STL well enough to add your own extensions to it.

The Standard provides std::vector<> (giving the functionality of a dynamic array), std:: deque<> (a double-ended queue – another random-access data structure), std::list<> (a doubly linked list, a useful data structure for when frequent changes are made by adding or removing elements internally), and std::basic string<> (a sequence of a character type; std::string and std::wstring are specializations for char and wchar t).

In addition, the Standard provides four associative containers: std::map<>, std::multimap<>, std::set<>, and std::multiset<>.

Finally, the Standard provides std::stack<> and std::priority queue<> as adaptors of other containers to provide those data structures.

Many other data structures are available through third parties (such as Boost) and, recently, via a Technical Report that provides a number of extensions to the Standard Library. Many of the items in the Technical Report are likely to be added to the C++ Standard in its next full release (circa 2009).