Using structs to solve problems

The main goal of this lecture is to work through some of the problems at the end of these notes and feel a little bit more comfortable with using structs to get things done in programs. It's worth noting that structs and bottom-up programming are a natural fit. You want to write a program that's going to have to deal with 2D points? So you implement a nice 2D point struct with all sorts of helpful funtions to read, write, add and compare points. Later you can go and use all this nice functionality to solve whatever particular problem you had to solve.

A little something fun — making your new type act like the builtin types

C++ allows the programmer to make new types that really act like the builtin types, by which I mean that the usual operators, like *, <, ++, work with the new types, and I/O with << and >>, and so on. There's actually some controversy about this, i.e. about whether or not it's a good idea to let programmers do this. Some people feel that it leads to hard-to-follow code. In any event, it's not going to be a major theme for this course, but I'd like to show it to you so that you understand that we really can build new types in C++ if we want to. Also, I should note, this is why + and >> and so on work with C++ string objects. The implementers of the string library defined all these operators for their nice string type.

Let's write a program that sort of plots a course this way. You start out at (0,0), and then you can enter in "moves". A move of (-2,4) means move down 2 units and to the right 4 units from wherever your current position is. The user enters moves continually until he finally enters a q to quit. My first solution is a pretty simple program. The meat of the program is:

// Initialization
ofstream OUT("out.txt");
point p,m;
p.x = p.y = m.x = m.y = 0;

// Get moves & write moves
do {
  // Compute new position p from move m
  p.x = p.x + m.x;
  p.y = p.y + m.y;

  // Write move
  OUT << p.x << '\t' << p.y << endl;

While it may be simple, it would be nice to be able to write the function as if point were a built-in type, meaning that I could add points p and m by saying p + m. This wouldn't change what I could accomplish, but it would add a little "syntactic sugar" to sweeten the program a bit. Then the meat of the program would look like:

// Initialization
ofstream OUT("out.txt");
point p,m;
p.x = p.y = m.x = m.y = 0;

// Get moves & write moves
do {
  p = p + m;
  OUT << p.x << '\t' << p.y << endl;

To do this, we need to be able to tell the compiler what it means to + to point objects. Doing this is quite easy once you understand that a + b is just the same as the function call operator+(a,b) in C++. So if you want to tell the compiler what + means for two point objects, you need to define the function operator+(point a,point b) --- i.e. overload the + operator for points. The prototype is clear:

point operator+(point a, point b);

... at least I hope it's clear that we should return a point when we add two points. The function definition is ... just like any other function definition:

point operator+(point a, point b) {
  point S;
  S.x = a.x + b.x;
  S.y = a.y + b.y;
  return S;

So with that addition, here's my second verison of the program. Now, the syntactic sugar may not seem worth the effort here, but you'll probably be using the point struct over and over, and you'll like being able to add points. Wouldn't it be nice to define the midpoint function like this:

point midpoint(point a, point b) {
  return (a + b)/2.0;

"Operator overloading" is the term used for defining versions of the C++ operators for the new structs we define. In general, if you have an expression A Π B, where "Π" stands for some operator, then that is equivalent to a function call operatorΠ(A,B). So, to subtract two points we'd define

Point operator-(Point A, Point B);

... and to compare two points with less than we'd define

bool operator<(Point A, Point B);

... or to multiply a point (on the left) by a real number (on the right) we'd define

Point operator*(Point A, double w);

Now, in addition to defining operator+ for two point objects, what else would you need? Well, (a + b) is an object of type point, and I'm dividing it by an object of type double, so I need to define operator/(point,double). What type of object should be returned here?

point operator/(point P, double z) {
  point Q;
  Q.x = P.x / z;
  Q.y = P.y / z;
  return Q;

I/O and overloading

Just to round out our examples, here's how to overload << and >>.

istream& operator>>(istream &in, Point &A) {
  char c;
  return in >> c >> A.x >> c >> A.y >> c;

ostream& operator<<(ostream &out, Point A) {
  return out << '(' << A.x << ',' << A.y << ')';

The prototypes of these two should actually make some sense. For example, we've talked before about how cin >> x actually evaluates back to cin. What is new, however, is the "return by reference". Normally, when a function returns an object X, the returned object in the calling function is a copy of that X. By using return by reference, we're saying "no, I want the calling function to get the exact same object I returned, not a copy". Of course, this can only be done with something that doesn't go out of scope and die at the end of the function call. To wrap all of this function overloading stuff up, consider this example: point.cpp.


  1. Be the bank! Write a program that manages account information for a simple bank. You have the file BankAccts.txt, which lists all your bank account information at the beginning of the year. You also have the file Transactions.txt, which lists all the deposit transactions for the year, each transaction consisting of a line giving the date, the account number, and the $'s deposited. Your program should print out an end of the year report that lists all the accounts with their account numbers, owner name, and end of year balance in exactly the same format as used in the input file Here's my solution.
  2. Turtles revisted! Recall that in an early lab we wrote programs in which we drew lines with turtles using notation like this:


    which means that the turtle goes forward two steps, then turns clockwise by some fixed angle (specific to this turtle), then goes forward two more steps, and so on. Now let's up the ante and allow ... multiple turtles! The input will look like this:

    N = 3
    Joe 30
    Sue 45
    Tom 15
    Joe FF+FF-;
    Sue F+;
    Joe FF+;
    Tom F-F-F-F;
    Sue F-;
    Sue F+F+;
    Tom F-F-F-;
    Sue F-F-;

    ... each time you encounter "print" you print out the name and current x,y-coordinate of each of the turtles. When the turtles are initialized, the number next to the name is their "turn angle". You should assume that they start off at coordinate 0,0 and heading 0-degrees (counter-clockwise from the x-axis). For all turtles, the forward step will be one unit.

  3. In HTML, colors are specified by a "number". for example, yellow is specified by the "number" #FFFF00. And you can color words using this. For example, if I want to Write "Hello", in HTML (i.e. Hello with a yellow H on the front), I use the following HTML:

    <font color="#FFFF00">H</font>ello

    The file colors.txt contains a list of number/names. Write a program that reads in this file, allows the user to enter colors and words, and finally produces an HTML file that writes those words in those colors. Example:

    Enter color and word, or quit: Blue  Somewhere
    Enter color and word, or quit: Green over
    Enter color and word, or quit: Aquamarine the
    Enter color and word, or quit: Gold rainbow
    Enter color and word, or quit: quit

    With this, your program should create an html file like this.

  4. Write a program that reads in points from the file points.txt and writes out the lower left and upper right coordinates of the smallest rectangle containing all the points from the file. Here's My Solution.