This email is best viewed with a fixed width font like
Courier.  I'll put it up on the web site:
http://www.cs.washington.edu/education/courses/cse143/CurrentQtr/AH/
It's also really, really, really, really long.  Really,
really.  You should print it out and read it offline, so you
can refer to earlier stuff as you read along.

<PRE> // for you HTML viewing folks

Well, I think I failed at the CS Hippocratic Oath to
"... avoid harm."  I'll see if I can give some more examples
and code that may help clarify the memory, pointers, arrays
thing.


I'll assume the following classes:

class Blob {
public:
    Blob();
    Blob(int val);

    void update(int change);
    int value();

private:
    int n;
};


class WordList{};  // same idea as homework

class Point {
public:
  Point();
  Point(int x, int y);

  int x, y;
};


You declare a variable of a certain type:

int x;
char input;
Blob bubba;
WordList the_list;
Point myp;
Blob arrayb[10];

If you declare an instance of a class, as above, then the
default constructor is invoked.  In particular, if you
declare an array of objects (classes) each of the elements
of the array will have its constructor called.  So for
arrayb, all 10 will have their default constructors called,
so arrayb[3].value() is 42.

To invoke a different constructor, you specify
it at the time that you declare the variable:

Blob fred(13);
Point ap(10,17);

These variables must exist someplace in memory.
They are created on what is called the stack.

You declare a pointer of a certain type using the *:

int *p;		      // pointer to an int
char *ch;	      // pointer to char
Blob *bp;	      // pointer to a Blob
Point *pp;	      // pointer to a Point

Since they are variables, they must also exist somewhere.
They are created automatically as well, and exist on the
stack.

Now, if you assign a pointer, you must give it a pointer.
Just like to store a character, you must give it a
character.  Moreover, you must assign a pointer to a pointer
of the same type.  The & creates a pointer to a variable.

So:

int *x;  // int pointer
int j;   // plain old int
j = 14;  // assignment

x = &j;  // &j gives as an int pointer which we assign to x
p = x;   // p and x are both int pointers


Pictorially:

  x            j
____          ______
| ----------> | 14 |
----          ------
                ^
  p             |
____            |
| ---------------
----

Now both p and x point at j.  What is going on behind the
scenes is that what the & does is it gets the actual memory
address of the variable j.  It stores this value, the memory
address of j, into x.  Then when the assignment p = x
happens, p gets a copy of the value stored in x, which is
the address of variable j.  In essence, p and x now point to
the same thing, j.


Similarly, you could do:

Point usefulp;
pp = &np;

Now pp, which is a Point pointer, has the address of the
variable usefulp.  More importantly, we can think of pp as
pointing to usefulp.  Note that the creation of np above did
not create an actual Point (like usefulp).  It created a
pointer, which just stores an address.


 pp         usefulp
____       _________
|  ------->|       |
----       ---------

So far, all of the memory has been done on the stack.

This has certain drawbacks.  If we want an array:

int myints[100];

It has to have a fixed size.  If we had Dynamic Memory, we
could change the size of the array as we needed.  Dynamic
memory is created on the heap.  We can create an object of
any type using the keyword new.

So if we have:

int *myi;  // this is an uninitiazlied pointer

 myi
_____
|  ------->  ???
-----

it doesn't actually point at anything.  But we can change
that by doing:

myi = new int;  

new creates an anonymous instance of the type, and returns a
pointer to it.

So the pictures is now:

 myi
_____        _____
|  --------> |   |
-----        -----

Notice that the memory on the right doesn't have a name.

Now, remember how behind the scene pointers store an address
of memory.  Well, that means that myi stores the address of
that block of memory created somewhere on the heap.

You can create a new object of any time, so we can do:

ch = new char;      // ch points at a char
bp = new Blob;      // bp points at a Blob
pp = new Point;     // pp points at a Point

This is the same things as doing:

Blob b;
Blob *blobp;

Point p;
Point *pointp;

blobp = &b;
pointp = &p;

Except that if we use new, as above, then we don't have an
extra variable name cluttering up our code (b, p don't exist
if we just do the new as with bp and pp). 

To access the members of a pointer to an object, you do
the same thing as with pointers to structs, using the ->
notation:

cout << bp->value() << endl;    // call value of bp, prints 42
blobp->update(4);               // add 4 to blobp's value

pp->x = 4;                      // set the public data member
                                // of pp to the value 4


Note that if you create a new object, then it's default
constructor will be invoked:

bp = new Blob;    // default constructor for a Blob is called
bp->value();      // value 42

If you want to invoke a different constructor you can do:

bp = new Blob(14);
bp->value();

This will invoke the overloaded constructor, which gives 
n the value 14.  (n is a private data member of bp).

As motivation, we wanted to be able to create dynamically
lengthed arrays.  How do we do this with arrays?  Well, we
declare an array as:

int myarr[100];

This creates 100 consecutive ints on the stack.  We access
them: myarr[2] = 4;

We can access the array through a pointer.  Remember,
that each individual element of the array has the
type of the array (in this case int).

x = myarr[2];         // x is now 4, both x and myarr[2] are ints

p = &x;               // p points to x, &x is a pointer to x
p = &myarr[2];        // p points to the 3rd element of myarr,
                      // which is an integer.  &myarr[2] is 
		      // the address of the 3rd element of myarr

In slightly greater detail: myarr[2] is an integer, so it
must live some place in memory, and that place has an
address.  &myarr[2] gets the address, which is the same as
creating a point to myarr[2], and we then assign it to p.

In C++, myarr (without the []) is the address of the first
element of the array.  So the following:

if (myarr == &myarr[0])
  cout << "Good";

will print out Good.  Therefore, we can think of myarr as a
pointer to the first element of the array, and so if
myarr[0] makes sense, then p[0] works the same way.
However, the assignment above to p makes it such that p[0]
== myarr[2].  I think Hal will talk more about this in class
on Friday.

With this understanding of the similarity between pointers
and arrays, we can now understand the following:

int *ip;

ip = new int[15];

ip is a pointer to the first element of the anonymous array
which is created on the heap.  That is, ip is a pointer to
the array.  We can use ip like an array, so ip[3] is the 4th
element of the array.  Remember that what new returns is a
pointer (an address), so in this case, new returns a pointer
to the block of memory that starts the array.	   

Similarly we can do:

bp = new Blob[12];
pp = new Point[17];

Remember, that since these are arrays of classes, that the
default constructor will be called on each of the elements
of the arrays.  So 12 Blob default constructs, and 17 Point
default constructors are called.

Lastly, the best part about dynamic memory is the dynamic
part.  This means that you can decide how long you want
arrays at run-time, not statically at compile-time.
For example:


int length = 20;

ip = new int[length];

I can specify a variable inside the [] brackets of new,
and that will be how many ints I get.  You access them
as before, ip[8] = 14;

Similarly, you could do:

cout << "How many? ";
cin >> length;

Blob *pblobs;

pblobs = new Blob[length];

And then you use the individual ones just like a normal
array of classes:

pblobs[4].update(3);         // or
cout << pblobs[2].value();


There was a question today about why we can do things like:

Blob *bc = new Blob;

This is just a special shorthand notation for:

Blob *bc;
bc = new Blob;

The thing on the left is a declaration of a pointer, and the
thing on the right is a pointer, so those types are the same.
Don't get confused between declaring a pointer (char *ch; and
dereferencing a pointer, *ch = 'A'; which both use the *).

You could NOT do:

*bc = new Blob;

You could, but would never, ever want to, do something like:

Blob ed;

ed = *(new Blob);


I'm hoping that these explanations will do more good than
harm.  There are clearly some open questions, like how do I
delete memory I created (use delete: int *xx = new int; delete xx;)
which will be covered soon.


Please come talk to me, or any other TA, if you're still unclear,
and want more help.


-Justin



PS:  Here's a little program that you should look at and run,
and think over.

#include <iostream>

class P {
 public: 
   int n;
};

int main() {
  int x = 4;
  int *p;
  int *q;

  p = &x;
  q = p;

  cout << "x: " << x << endl
       << "address of x: " << &x << endl
       << "p: " << p << endl
       << " value of what p points to: " << *p << endl
       << "q: " << q << " val q: " << *q << endl;


  int arr[100];
  arr[0] = 4;

  if (arr == &arr[0]) {
    cout << "Good" << endl;
  }

  cout << *arr << endl;     


  P *pp;
  pp = new P[10];

  pp[0].n = 14;

  return 0;
}


</PRE>