This changes everything ...

Several weeks ago, the addition of loops to our programs had a huge impact on the power we wielded as programmers. Before loops, the computer never performed more steps than the poor programmer typed in. With loops, a short, simple program could make the computer do an almost limitless amount of work!


Today we are introducing another game-changing idea:
Arrays

Up till now, a program couldn't store -- couldn't remember -- anything except in variables. This meant that the program couldn't remember more data than the number of variables than the programmer put into the program. Essentially the program can't remember more data than the programmer typed in while creating the program.

Arrays shatter that limitation: An array is a single variable with which a program can store and retrieve a nearly limitless amount of data.

A Simple Problem Made Difficult

Let's start with a simple problem:

Write a program that works as follow:

For example, a typical run of the program might look like:

~/$ ./prog
William Shakespeare
Shakespeare, William
... where the red text is user input. This should be no problem, something like this will do:

string first, last;
cin >> first >> last;
cout << last << ", " << first << endl;

Now let's make things more difficult:

No matter how hard you work with what we've learned of C++, there's no way you can write this program! You can capitalize, you can switch first and last names, you just can't do both together.

The problem is:

Length of a string

The "how many characters are in the strings" part is easy. It turns out that whenever you have an object of type string you can put a .length() at the end of it and the resulting expression returns the length of the string. So, from the previous code I could ask for

first.length()
and (with first name "Chris") the result would be 5.

Using indices

As you might suspect, it is also possible to reference characters within a string - not by specific names, but by indices.

Using indices, we can make sure that every character within the string first is printed in capitals:


// prototype
char capitalize(char c);

// definition
char capitalize(char c)
{
  if ('a' <= c && c <= 'z')
    return 'A' + (c - 'a');
  else
    return c;
}

for(int i = 0; i < first.length(); i++)
{
  cout << capitalize(first[i]);
} 

As you seen in the above code, the function captalize() capitalizes the input character.

The Idea of Arrays

Donald Knuth

http://xkcd.com/163/

When we access an ordered collection of objects, all of the same type, by indices rather than by individual names, we are using arrays. This is one of the most powerful ideas in computer science, so you better learn to love it!

The excercises below and the remainder of the notes here are just to help you play with the idea of accessing objects within an array by index rather than by specific name. A string is, essentially, and array of objects of type char. In coming lectures, you'll see that we can have arrays of any type of object we choose.

Arrays allow us to store and compute with large amounts of information in programs without needing separate variable names for each object we store.

Power of arrays: In the past example, a single variable name first stood for as many char objects as needed.

The key behind this indexing with strings, is that the expression first[i] is an object of type char. (In particular, it is an lvalue of type char, meaning that it can, among other things, appear on the left-hand side of an assignment.) You don't need any special rules to tell you what you can and can't do with an expression like first[i], because anything you can do with a char you can do with it.

Important!

Modifying Strings

Now, we might want to actually change the string we've got - for example modify it so that all of its letters are capitals. We can do this the following way:

string s;
cin >> s;
for(int i = 0; i < s.length(); i++)
  s[i] = capitalize(s[i]);          // simple assignment!

cout << s << endl;
You say "How do I know I can assign a value to s[i] like that?" Well, s[i] is an lvalue of type char like any other so, you can assign to it just like you assign to any char variable!

In fact, you can overload the function capitalize() to capitalize a string, by using the above function capitalize() for characters.


// prototype
// overload the function: for the string type!
string capitalize(string w);            

// definition
string capitalize(string w)
{
  for(int i = 0; i < w.length(); i++)
  {
    // use capitalize(char ) defined above!
    w[i] = capitalize(w[i]);        
  }
  
  return w;
}
Now, given the two capitalize() functions, printing out a captalized string becomes very easy.

string s;
cin >> s;
cout << capitalize(s) << endl;

Problems

  1. Print in reverse (non-recursive)
  2. Print in reverse (recursive!)
  3. A predicate that tests whether two strings are reverses of each other.
  4. palindromes
  5. A predicate that takes a string s and a char c, and tests whether or not c appears in s.