Functions, continued

Review of functions

A function is a way of assigning a name to a block of statements, so that we can refer to it elsewhere in our program, instead of just copy-pasting it every time we need that kind of behavior.

Some simple functions:

int max(int a, int b) {
    return a > b ? a : b;
}

int max3(int a, int b, int c) {
    return max(max(a,b), c);
}

int max4(int a, int b, int c, int d) {
    return max(max(a,b), max(c,d));
    // or max(max3(a,b,c),d)
}

Here’s an interesting example: suppose we want to find out whether a given int (assumed to be \(\ge 0\)) is odd or even. The only two numbers we know anything about for certain are 0 and 1:

Starting out, we write two functions:

bool even(int x); // Declaration

bool odd(int x) {
    if(x == 0)
        return false;
    else if(x == 1)
        return true;
    else 
        ...
}

bool even(int x) {
    if(x == 0)
        return true;
    else if(x == 1)
        return false;
    else 
        ...
}

What about values \(\gt 1\)? We will say that a number \(x\) is even if \(x-1\) is odd. Likewise, a number \(x\) is odd if \(x-1\) is even. In code, this looks like this:

bool odd(int x) {
    if(x == 0)
        return false;
    else if(x == 1)
        return true;
    else 
        return odd(x-1);
}

bool even(int x) {
    if(x == 0)
        return true;
    else if(x == 1)
        return false;
    else 
        return even(x-1);
}

Does this seem like it would work? It does, because every call to odd/even is independent of every other. They don’t “share” x, or anything at all. The only communication between functions is via parameters (input) and return values (output). If we trace through the result of doing odd(4) we’ll see what happens:

odd(4)   x = 4
  |
even(3)  x = 3
  |
odd(2)   x = 2
  |
even(1)  x = 1
  |
false

Every x is separate and independent of every other x, in the same way that we can have two variables with the same name, as long as one is in an inner scope: the “old” x’s are still around, just not currently accessible.

Function call stack.

Converting numbers to string

Converting numbers to strings

We are gradually going to build a program to convert an integer value into a string representation, so that 123 becomes “one hundred twenty three”.

#include <iostream>
#include <string>

int main() {
    int x;
    cout << "Enter a number: ";
    cin >> x;

    ...
    return 0;  
}

To start out simply, though, we’re going to begin by translating a single digit into a string:

/* digit_name(digit)
   Converts a value between 0...9 into its name "one", "two", etc.

   digit: int between 0 and 9
*/
string digit_name(int digit) {
    switch(digit) {
        case 0: return "zero"; // Why no break?
        case 1: return "one";
        case 2: return "two";
        case 3: return "three";
        case 4: return "four";
        case 5: return "five";
        case 6: return "six";
        case 7: return "seven";
        case 8: return "eight";
        case 9: return "nine";
        default: return "ERROR";
    }
}

To begin, we can assume that the user will enter only a single digit:

int x;
cin >> x;
cout << digit_name(x);

Suppose the user enters a multi-digit number: 123. We’ll leave printing out “one hundred twenty three” for later and just print out “one two three”. How do we get access to the individual digits?

One way would be to convert to a string. You can do this with

string s = to_string(x);

We can then use .at to access the individual characters, convert them back into numbers, and use those.

Another option is to use math: if you take any number mod 10, that gives you the ones digit. E.g., 123 % 10 == 3. How do we get the higher digits? Divide by 10, 100, etc. If you divide 123 by 10, it rounds down so you get 12. Then take that mod 10 to get its lowest digit. We stop when the number is less than 10; at that point, the number itself is the last (highest) digit.

string all_digits(int x) {
    string s;
    while(x >= 10) {
        s = digit_name(x % 10) + " " + s;
        x /= 10;
    }

    // Get last digit
    s = digit_name(x % 10) + " " + s;

    return s;
}

Note that because we get the digits in order from lowest to highest, we add them onto the front of s, so that they’ll be in the right order in the result.

This is a good start. Let’s extend it by writing a function to handle any two digit number:

To convert a number \(n < 100\) to its name, we do it in two parts:

What about numbers \(100 \le n < 999\)? All we do is add “x hundred” in front of the 2-digit part:

if(n >= 100 & n < 1000)
    return number_name(n / 100) + "hundred and " + number_name(n % 100);

To do a thousand number, we do something similar, only we let the number_name function handle the hundred part:

if(n >= 1000 && n < 1000000)
    return number_name(n / 1000) + " thousand, " + number_name(n % 1000);

This can handle anything up to “nine hundred, ninety-nine thousand, nine hundred and ninety nine”.

You can continue the pattern to add support for millions and billions:

if(n >= 1000000 && n < 1000000000)
    return number_name(n / 1000000) + " million, " + number_name(n % 1000000);

Since we’re basically doing the same thing over and over, we should put it into a function: the low end of the comparison is the base, and the high end is always that times 1000:

string big_number_name(int n, int base, string name) {
    if(n >= base && n < base * 1000)
        return number_name(n / base) + name + ", " + number_name(n % base);
    else
        return "";
}

The fact that this returns an empty string if it can’t handle the input means that we can put it to use even for “small” numbers:

return big_number_name(n, 1000000, "million") + " " +
       big_number_name(n, 1000, "thousand") + " " +
       number_name(n % 1000)

Another example: dice

Let’s write a program that lets the user enter two integers, which are interpreted as the number of sides on a pair of dice. If the user enters 6 and 6, that means, roll a pair of 6-sided dice. Then, for every possible sum-of-rolls, we’ll print out how many ways there are to roll that. E.g., if the user entered 3 and 3, we would print

2 #
3 ##
4 ###
5 ##
6 #

where the number of pound signs is how many ways there are to roll that number (i.e., the probability of rolling that sum).

What kind of functions will we need?

There are two general ways we can approach this, top-down and bottom-up. In top down, we start with main and write it in terms of other functions, which are not yet written, getting the overall structure of our program out of our way. In bottom-up, we start with the most basic functions, those that don’t rely on anything else, and work our way up to main (which depends, directly or indirectly, on all the other functions). Top-down is often easier to start with:

int main() { 
  cout << "Enter two dice sizes: ";
  int a,b;
  cin >> a >> b;

  print_rolls(a,b);

  return 0;
}

At each step, we look for functions that we have not written yet, in this case print_rolls:

void print_rolls(int a, int b) {
  // Loop over all possible roll-sums
  for(int r = 2; r <= a+b; r++) {
      print_roll(a,b,r);
  }
}

void print_roll(int a, int b, int r) {

  // Count the number of possible rolls
  int count = 0;
  for(int i = 1; i <= a; ++i) 
    for(int j = 1; j <= b; ++j)
      if(i + j == r)
        count += 1;

  // Print results
  cout << r << " ";
  print_hashes(count);
  cout << endl;
}

void print_hashes(count) {
  for(int i = 0; i < count; ++i)
    cout << "#";
}

Function overloading

We know that we can’t declare two variables with the same name:

int a = 1; 
...
int a = 10; // Error!

What happens if we declare two functions with the same name?

float average(int sum, int size) {
    return 1.0 * sum / size;
}

float average() {
    float x, sum = 0, count = 0;
    while(cin >> x) {
        sum += x;
        ++count;
    }

    return sum / count;
}

Surprisingly, this is perfectly fine! This is what’s called function overloading: using the same name, for functions with different formal parameters. The reason why this is allowed (and useful!) is because the compiler can tell, when we use the function, which version we want:

average(10,5); // Two int arguments, we want the first one
average();     // No arguments, second one

Function overloads allow us to group common behavior (in this case, computing the average of something) under a common descriptive name. Function overloads are allowed as long as the compiler can tell the difference between them. In particular, the things that distinguish two overloaded functions are:

The return type is not sufficient to distinguish two overloads:

float average(float sum, float size) {
    return 1.0 * sum / size;
}

// This will cause an error
int average(int sum, int size) {
    return sum / size; // Rounding
}

One overload can even use another:

float average() {
    ...
    return average(sum, count); // uses average(float,float)
}

Every overload must have its own declaration, because they are all technically different functions, and the compiler needs to be aware of them before you can use them.

Default arguments

Last time we wrote a function to read in a vector, with a limit on the number of items read in. We saw that if we used -1 as the limit, then it would read in an unlimited number of items. It might be nice to have an overload of read_input that took no arguments, and did this:

// Original: reads up to n ints
vector<int> read_input(int n) {
  vector<int> data;
  int e;

  while(cin >> e && n != 0) {
      data.push_back(e);
      n--;
  }

  return data;
}

// Overload: reads an unlimited number of ints
vector<int> read_input() {
  return read_input(-1);
}

C++ has a shortcut for this kind of situation: default arguments. Instead of writing a totally separate overload, we can just modify the original:

vector<int> read_input(int n = -1) {
  vector<int> data;
  int e;

  while(cin >> e && n != 0) {
      data.push_back(e);
      n--;
  }

  return data;
}

The = -1 in the formal parameters says that n is an optional parameter; if you leave it out when you call the function, it defaults to -1. In other words, this version works exactly like the pair of overloads.

Sample problems…

File access

This doesn’t have anything to do with functions, but I need to cover it at some point, so why not today?

How do we access files in C++? That is, how do we write a program that either reads in the contents of a file and does something with it, or else writes out information to a file (or maybe both)? In C++, this is easy, thanks to something called iostreams.

The basic idea behind iostreams is that writing to a file is a lot like writing to the screen, and similarly, reading from a file is a lot like reading from the keyboard. In fact, a lot of things are “like” that, so the C++ committee came up with ostreams and istreams. An ostream is anything that you can write to; the “o” stands for “out”. An istream is anything that you can read from: the “i” stands for “in”. You’ve seen two already:

Files can be ostreams, istreams, or both, depending on how you access them. If you have an istream-like file, you can only read from it; an ostream-like file can only be written to. An iostream file can be read and written to, you can even write something out and then read it back in!

The standard stream hierarchy

Just as exceptions are grouped into a hierarchy, so are streams. For example, some streams (like cout) can only be written to, some (like cin) can only be read from, and some can do both. Some streams support seeking, moving around in the stream to read things you’ve already read (files support this, cin does not). The standard stream hierarchy encodes these different abilities.

Inheritance

Both the exception hierarchy and the stream hierarchy are built using inheritance. This is a way to “borrow” parts of one class when building another class. For example, the exception class logic_error “borrows” .what() from it’s parent class, exception. Just remember that when we say “class X inherits from Y” (or “X is a subclass of Y) this means that anything Y can do, X can also do.

ios (from ios_base)
|
+----- istream (cin)
|         +-------------- ifstream
|         +-------------- istringstream
|
+----- ostream (cout)
          +-------------- ofstream
          +-------------- ostringstream

   istream               ostream
      |                     |
      +----------+----------+
                 |
             iostream
                 |
              fstream  
                 |
            stringstream

The stream hierarchy

At the root of the stream is the class ios (defined in header <ios>). You never really use this class by itself, as it exists only to specify what kinds of things all streams can do. Every stream class inherits from ios, so if you look at what ios can do, you know that any stream can do those things also.

The state flags for a stream tell us what state it is in: is everything OK? Have we reached the end of the stream? Has some kind of error occured? The state flags are

Note that .eof(), .fail(), and .bad() are only set after you try to access a stream. The only way to detect whether something has gone wrong with a stream is to try to use it.

It’s also possible to tell a stream to throw an exception when it goes into fail, bad or eof. Normally the stream state is set “silently” and you have to check it yourself. For example, if we want eof to throw an exception:

cin.exceptions(istream::eofbit);

Those are the things that all streams support, input, output, file, whatever. Keep them in mind as we talk about other kinds of streams. If you want to turn off all exceptions later, just do .exceptions(0).

Streams for input and output

Next up in the hierarchy are istream and ostream (defined in headers <istream> and <ostream>, respectively), more abstract classes that add things specific for input and output.

In particular, istream adds >> (the extraction operator) and .get, our two old friends, but it also adds some other things we haven’t talked about:

Although getline is technically part of <string>, it will work with any istream including file streams and stringstreams.

ostream gives us << which we are familiar with from cout, but also a few other things (which cout has but we haven’t talked about):

iostream

iostream is an (abstract) class for streams that support both input and output. Hence, it inherites from both istream and ostream, and supports everything that they can both do. All of the specific types of streams we’re going to talk about come in three variants:

Note that iostream doesn’t add anything new of its own: there are no operations that are specific to streams that support both input and output, there are only input-specific operations and output-specific operations.

Note that input/output streams actually have both an input position (accessed through seekg/tellg) and an output position (seekp/tellp) which are independent of each other. This means that in a file (for example) you can be reading in one location, and writing in another.

File streams

The file stream types are ifstream (input), ofstream (output) and fstream (input/output), all defined in header <fstream>. Everything we said about about input/output operations applies to these; the only things new are things specific to files: how do we open a file given its name, how do we close a file, etc.

Opening a file stream

The easiest way to open a file stream is when we create it:

#include<fstream>

fstream file("myfile.txt"); // Opens myfile.txt for input/output

After doing this, we can use all our familiar stream operations (in particular, << and >> on file, just like with cin and cout):

string first_line;
getline(file, first_line); // Get the first line of the file

file << "Hello"; // Write some text into the file

We can also open a file, after we create the stream:

fstream file();

file.open("myfile.txt"); // Same as above

When you’re done with a file it’s polite to close it:

file.close();

The default way to open a file is for both reading and writing, and with the starting stream position at the beginning of the file. Furthermore, if we open the file for writing and the file already exists, then its existing contents will be left unchanged. We can specify a number of flags when opening a file that change these defaults:

// Open for input, but starting at the end
fstream file("myfile.txt", ios_base::in | ios_base::ate);

// Open for output, starting at the end (append)
fstream file2();
file2.open("stuff.txt", ios_base::out | ios_base::app);

This opens the file for input only, and starts the stream position at the end of the file. The full list of flags is

(You can think of the difference between ate and app is that ate moves the stream position to the end of the file when it is first opened, while app moves the stream position to the end of the file after every write.)

Note that while the default is both in and out, if you give any of these flags the defaults will not be added to them. A common mistake is to write:

fstream file("myfile.txt", ios_base::trunc);

intended to truncate the file and open it for writing. However, this does not specify in or out, and hence the file that is opened is actually not able to be read from or written to at all! You have to do

fstream file("myfile.txt", ios_base::trunc | ios_base::out);

Note that because the default is both in and out, if you try to open a file that is read-only for your user (cannot be written to), it will fail (set the fail bit permanently) unless you either