I. introduction to pointers and dynamic data (HR 7)
 A. preview
-----------------------------
    POINTERS AND DYNAMIC DATA (HR 7)

Problem:

   Amount of input data varies between uses

Some solutions:

  - Allocate the maximum amount

  - Ask user how much to allocate

  - Allocate space at run-time
    (dynamically)
-----------------------------
	what is done in a typical Scheme program?
-----------------------------
Problem:

   - how the name dynamically allocated
     storage?
-----------------------------
	how is that done in Scheme?
 B. memory model
---------------------------
    MODEL OF MEMORY

     hardware             C++

          Memory     Program    
Address    Cell      Identifier Type

  3000   [ 12000 ]    intPtr    int *
  3004   [ 12004 ]    lintPtr   long int *
  ...
 12000   [       ]              int
 12004   [       ]              long int


     ABSTRACT PICTURE





// pointerIntro.C
#include <iostream.h>
int main()
{
  int * intPtr;
  long int * lintPtr;

  intPtr = new int;
  *intPtr = 20;
  lintPtr = new long int;
  *lintPtr = 30;
  cout << *intPtr + *lintPtr << endl;
}
---------------------------
	Does the star (*) above mean multiplication?
---------------------------
        SUMMARY

C++ presents the memory of a computer
as cells (or objects), each of which has:
  - a 
  - a 
  - a 
The       may change during execution.
----------------------------
	What ADT is memory like?
	If you think of memory as a big array, what is a pointer like?
-----------------------------------
def: a *pointer* is an address with a type
     The type tells
-------------------------------------
--------------------------------------
def: a *variable* is
-------------------------------------
	What's the difference between a variable and a constant?
	What's the difference between a constant and a value?
	What is a pointer? a value? a constant? or a variable?
	What are the operations on variables?
	What is an integer variable?
-------------------------------------
def: a *pointer variable* is a variable
     that 
     Its type is called a
------------------------------------
II. pointers in C++ (HR 7.1-2, 7.4)
 A. pointer types (HR 7.1)
---------------------------
   POINTER TYPES

A pointer type in C++ is written

    <Type> *

Examples:

    int *
    int*
    float *
    int * *
---------------------------
	does whitespace matter in this form?
  1. declarations
----------------------------
      POINTER VARIABLE DECLARATIONS

Follow the standard declaration syntax.

Examples:

    int* ip;
    int * intPtr;
    int * ip1, * ip2;
    int *ip3, i;

    int * pa[10];
------------------------------
	  what's the type of i?
  2. operations
-----------------------------
   BASIC OPERATIONS ON char* POINTERS

int main()
{
  char  c = 'a';
  char  *charPtr = &c;  // dangerous
  char  *dcp = 0;
  dcp = new char;
  *dcp = *charPtr;
  delete dcp;
}
--------------------------------
  3. examples
----------------------------------
       PROBLEM

Implement the following specification

void IntCellSwap(int* c1, int* c2)
  // PRE: c1 and c2 are valid pointers
  // MODIFIES: *c1, *c2
  // POST: *c1 == *c2<entry>
  // && *c2 == *c1<entry>
----------------------------------
----------------------------------
       FOR YOU TO DO

Implement the following specification
(without using swap):

int* IntCellMin(int* c1, int* c2, int* c3)
  // PRE: c1, c2, c3 are valid pointers
  // && *c1, *c2, and *c3 are distinct
  // POST: FCTVAL is a pointer to
  // the smallest of *c1, *c2, and *c3
----------------------------------
	can you give a sample call?  Can you draw pictures of it executing?
  4. summary of pointer ADT
---------------------------------
    SUMMARY OF BASIC POINTER OPERATIONS
         (for type char*)

 Operation  Example 	    Type

 0	    0		    char*
 new	    new char	    char*

 &	    &c		    char*
 *	    *charPtr	    char
 =          dcp = new char  char*

 delete     delete dcp;     (void)
-----------------------------
	What's the opposite of &?
	What would change if this were int*?
	Why didn't we have anything like delete in Scheme?
 B. constant pointer expressions and pointer arithmetic (HR 7.2)
  1. pointers to const objects vs. const pointer objects (DD 5.5)
------------------------------
   POINTERS TO const OBJECTS
  USEFUL FOR FORMAL PARAMETERS

An array of const int objects:

  int Minimum(const int arr[], int size)

    arr[i] is a const int object
  
Pointers to const int objects:

   int IntCellMin(const int *c1,
                  const int *c2)

     *c1 is 
--------------------------
---------------------------
   call:

References to const int objects:

   int IntVarMin(const int & c1,
                 const int & c2)
------------------------------
	what would a call of IntVarMin look like?
-----------------------------
       FOR YOU TO DO

Given the following declarations:

  const float e = 2.73;
  float f = 7.4;
  const float pi = 3.14159;
  const float *pcf = &pi;

Draw a picture of these variables

Which of the following are legal?  Why?

    *pcf = 7.3;  // (a)
    *pcf = e;    // (b)
    pcf = &e;    // (c)
    pcf = &f;    // (d)
------------------------------
  2. constant pointer expressions
--------------------------------
       const POINTER OBJECTS
  NOT USEFUL FOR FORMAL PARAMETERS

A const pointer to an int:

    int *const unchangingPtr = new int;

Can do:
    *unchangingPtr = 3;

Cannot do:
    unchangingPtr = &i;
--------------------------------
--------------------------------
        const POINTER OBJECTS
     vs. POINTERS to const OBJECTS
vs. const POINTER OBJECTS to const OBJECTS

      int *const nochangePtr = new int;
const int *nochangeCellPtr;
const int *const nochangePtrToNochange
                 = nochangePtr;
--------------------------------
	what is a constant int expression?
-------------------------------
     CONSTANT POINTER EXPRESSIONS

def: a *constant pointer expression* is
     an expression that denotes a pointer
     and that is known before run-time.

Examples:
   0
   noChangePtr  // if has type int *const
   &vec[0]      // if vec is an array
   vec          // if vec is an array
-------------------------------
  3. pointers and arrays (HR 7.2, DD 5.8-9)
-----------------------------
  ARRAY NAMES ARE CONSTANT POINTER EXPRS

Fact: given the declarations

	char myStr[5] = "abcd";
        char *s = myStr;

equivalent expressions:

        myStr[3]
        s[3]
        *(s+3)
        *(myStr+3)
-----------------------------
	what's the type of these?
-----------------------------
equivalent statements:

	myStr[0] = 'y';
	*(myStr+0) = 'y';
	*myStr = 'y';
	*s = 'y';
	*(s+0) = 'y';
	s[0] = 'y';

illegal:

	myStr++;
	myStr = myStr + 1;
------------------------------
	why?
----------------------------------
      SOME HELPFUL TERMINOLOGY

def: an *lvalue* is an expression
     that
----------------------------------
----------------------------------
Key characteristic:
	can take the address of an lvalue
		&myVar, &(*(p+3))

examples:

----------------------------------
	what other examples are there?
	is the name of a const an lvalue?
----------------------------------
Not an lvalue:
     array names
----------------------------------
	is the number 3 an lvalue?  the char literal 'c'?
  4. pointer arithmetic (HR 7.2, DD 5.7)
-----------------------------
    POINTER ARITHMETIC

You can:

   add pointer and int       p + 1
   subtract pointer and int  p - 1
   use assignment ops	     p += 3, p++
      with + and - and ints  p -= 2, --p


        MEANING

  long int arr[5] = {0, 1, 2, 3, 4};
  long int *p = myArr;

     hardware             C++

          Memory     Program    
Address    Cell      Identifier Type

  3000   [     0 ]    arr[0]    long int
  3004   [     1 ]    arr[1]    long int
  3008   [     2 ]    arr[2]    long int
  3012   [     3 ]    arr[3]    long int
  3016   [     4 ]    arr[4]    long int
  3020   [  3000 ]    p         long int *
-------------------------------------------
-------------------------------------------
       POINTERS ARE *NOT* INTEGERS

You cannot:

   use multiplication	     p*3
       division, mod, etc.   p/4, p%2


        POINTERS CAN BE COMPARED

However, you can:

   compare pointers to 0
	   p == 0, p != 0, !p

   compare pointers into the same array

       double coefs[100];
       double *p1 = &coefs[10];
       double *p2 = coefs + 20;

       p1 < p2,  p2 > p1, p2 >= p1
       p1 <= p2, p1 == p1, p1 != p2
-----------------------------
  5. examples
-------------------------------
         PROBLEM

Implement the following specification:

char* strcat(char *to, const char *from)
 // PRE: to and from are null-terminated
 // && to points to enough space
 // MODIFIES: to[strlen(to)
 //             ..strlen(to)+strlen(from)]
 // POST: FCTVAL == to && chars in from
 // are copied into the end of to
-------------------------------
------------------------------
      FOR YOU TO DO

An error:

  char myName[] = "Gary";
  myName = "Fred";       // error

What does this do?

  char *str = myName;
  str = "Fred";

Implement the following specification:

char* strcpy(char *to, const char *from)
 // PRE: to and from are null-terminated
 // && to points to enough space
 // MODIFIES: to[0..strlen(from)]
 // POST: FCTVAL == to && chars in from
 // are copied into to including the '\0'
------------------------------
  6. the truth about arrays
-------------------------------
    THE TRUTH ABOUT PASSING ARRAYS
          AS PARAMETERS

An array name is
   a constant pointer expression.

Arrays are in effect passed by reference,
because
-------------------------------
	So how are strings passed in C++?
---------------------------------
Equivalent for clients:

  char* strcpy(char *to,
               const char *from)

  char* strcpy(char to[],
               const char from[])

The only difference is in definitions:

  char *s;
  char str[10];
---------------------------------
	Can you draw a picture of the last two definitions?
 C. pointers vs. references (HR 7.4, DD 5.6)
  1. example
--------------------------------
    POINTERS vs. REFERENCES

// using references
void assign2(int& v1, int& v2,
             int  e1, int  e2)
{
  v1 = e1;    v2 = e2;
}

// using pointers
void assign2(int *v1, int *v2,
             int  e1, int  e2)
{
  *v1 = e1;  *v2 = e2;
}


int main()
{
  int i = 3;
  int j = 4;

  // call using reference version
  assign2(i,   j, j+1, i+1);

  // call using pointer version
  assign2(&i, &j, j+1, i+1);
}
------------------------------
	Which is more convenient?  Which is more error prone?
  2. differences and usage
-------------------------------------
       DIFFERENCES BETWEEN
   REFERENCES AND POINTER VARIABLES

  int i = 5;
  int j = 6;
  int& ri = i;
  int *pi;
  pi = &i;
  pi = &j;

		    reference  pointer var

separate variable?	no       yes
can be changed		no       yes
must be initialized	yes      no


       WHEN TO USE EACH

pass-by-reference	references
loops		        pointer variables
data that may change    pointer variables
-------------------------------------
III. dynamic data (HR 7.5-8, DD 7.6)
 A. what it is and why it's used (HR 7.5)
-----------------------------
    POINTERS AND DYNAMIC DATA (HR 7)

Problem:

   Amount of input data varies between uses

Some solutions:

  - Allocate the maximum amount

  - Ask user how much to allocate

  - Allocate space at run-time
    (dynamically)
-----------------------------
-------------------------
       DYNAMIC STORAGE ALLOCATION
          AND DEALLOCATION
             OVERVIEW

In Scheme:
      (let ((ls ; allocate
                (cons 1 '())))
         ; compute
         ... ls ...)

      ; storage deallocated when not used
      
In C++:
      // allocate
      List *ls = new Cons(1, EmptyList());
      // compute
       ... *ls ...

      // deallocate
      delete ls;
--------------------------
 B. operator new
------------------------------
      OPERATOR new

Syntax examples:

 int *ip = new int;
 char *cp = new char;

 int *ia = new int [i+20];
 char *s = new char[size];

 IntVec *ivp = new IntVec(i+20);

 FlexIntVec *fia = new FlexIntVec [size2];

Semantics:
   returns a pointer to new cell
      (or array of new cells)
      "new" means no other pointers to it

   if not enough space,
      returns null pointer (0).

   the cell is unitialized,
      unless the type is a class,
      then the constructor is called
------------------------------
-----------------------------
        PROBLEM

Implement the following spec.

// strdup.h
#include <iostream.h>

extern char* strdup(const char *s);
  // PRE: s in null-terminated
  // MODIFIES: cerr
  // POST: if space can't be allocated
  // prints an error to cerr
  // and returns with FCTVAL == 0,
  // otherwise return a pointer to new
  // space containg a copy of s.
-----------------------------
 C. operator delete
----------------------------
       OPERATOR delete

Syntax examples:

     delete ip;
     delete cp;

     delete [] ia;
     delete [] s;

     delete ivp;
     delete [] fia;

Semantics:
   space pointed at is returned to C++

   argument must be: either 0
        or result of previous call to new

   if argument is 0, nothing happens.

   form with [] must be used for arrays
   form without [] must be used otherwise

   class objects have destructor called

   the object pointed to may be modified
----------------------------
-------------------------------
      PROBLEM

Implement the following specification:

// Deallocate.h
extern void Deallocate(int* &intPtr);
  // PRE: value of intPtr was returned
  // a call to new, and hasn't yet been
  // given to delete
  // MODIFIES: free store, intPtr
  // *intPtr is deallocated && intPtr == 0
-------------------------------
 D. errors (HR 7.7)
  1. dangling pointers
-----------------------------------
    DANGLING POINTERS (1)

// deleting an alias

int main()
{
  int *intPtrA = new int;
  *intPtrA = 77;
  int *intPtrB = intPtrA;
  delete intPtrA;
  // ...
  cout << *intPtrB << endl;  // error!
}
----------------------------------
----------------------------------
    DANGLING POINTERS (2)

struct complex {int re; int im};

complex* cmul(complex *a, complex *b)
{
  complex result;
  result.re = (*a).re * (*b).re;
  result.im = a->im * b->im;
  return &result;
}
-----------------------------------
	can you make the same error with refrerences?
-----------------------------------

// fix:
complex* cmul(complex *a, complex *b)
{
  complex *result = new complex;
  result->re = a->re * b->re;
  result->im = a->im * b->im;
  return &result;
}
----------------------------------
  2. memory leaks
------------------------------------
      MEMORY LEAKS

Complex & operator *(const Complex & a,
                     const Complex & b)
{
  Complex *result
     = new Complex(a.real() * b.real(),
                   a.imag() * b.imag());
  return *result;
}

// ...

int main()
{
  Complex x, y;

  cout << x * y * z << endl;
  // ...
}
------------------------------------
	Who deletes the objects created by operator *?
  3. guidelines (p. 320)
--------------------------------
  THINGS TO BE AWARE OF WHEN
     USING DYNAMIC DATA

Is this pointer valid?

 - if variable not initialized, no?

 - if it's null (0), then no?

Is there memory allocated at the end?

 - after passing it to delete, no.

 - before a call to new or assignment, no

Is this going to cause a memory leak?

 - overwriting the last pointer to object

 - returning from a function
   without returning pointer to allocated
   objects, or without deleting them

Could this make other pointers invalid?

 - deleting one of several aliases
----------------------------------
 E. classes with dynamic memory (HR 7.8)
----------------------------------
        PROBLEM

Design and implement a type
that is like array, but more flexible
and safer.

Want:
   - size determined at run-time
   - trap invalid subscripts
   - aggregate assignment
   - aggregate copying (pass by value)
----------------------------------
	how can the dynamically-allocated data be deleted?
  1. destructors (HR 7.8)
------------------------------------------
       DESTRUCTOR OVERVIEW (HR 7.8)

Destructor for class IntVec
  - is a member function nasmed ~IntVec()
  - called implicitly 
------------------------------------------
------------------------------------------
  - job is to delete
------------------------------------------
------------------------------------------
  - *not* responsible for deleting self

Constructor and destructor example:
// IntVec.pri
private:
  int *vec;
  int size;

// IntVec.C
// ...
IntVec::IntVec( int num )
  : vec(new int[num]), size(num) { }

IntVec::~IntVec()
{
  delete vec;
}
------------------------------------------
------------------------------------------
          WHEN DESTRUCTOR INVOKED

At block exit, for variables

    int& Dangle(int n)
    {
       IntVec alpha(n);
       // ...
       return alpha[n-1];
    }

    // call
    Dangle(7) = 3;
------------------------------------------
------------------------------------------
Also:

 - as first part of deleting dynamic data
      IntVec * ivPtr = new IntVec(20);
      // ...
      delete ivPtr;

 - other times objects deallocated
------------------------------------------
------------------------------------------
            DESTRUCTOR SUMMARY

 - no parameters, no return type

 - called when variable goes out of scope

 - needed only to deallocate storage
   allocated by constructor
           

               WARNINGS

 - need a copy constructor!

 - don't call exit function, as may loop 
------------------------------------------
  2. assignment operators (HR pp. 326-7)
------------------------------------------
                 PROBLEM
     DEFAULT (C++-DEFINED) ASSIGNMENT
                   vs.
    DATA MEMBERS THAT ARE POINTER VARS

// kaboom.C
#include <iostream.h>
#include "IntVec.h"

int main()
{
   IntVec myVec(4);
   IntVec yourVec(3);
   for (int i = 0; i < 3; i++) {
      myVec[i] = 1;
      yourVec[i] = myVec[i] + 10;
   }
   myVec[3] = 3;
   yourVec = myVec; // with built-in =
   cout << yourVec[0] << endl;
}
------------------------------------------
------------------------------------------
               SOLUTION
    OVERLOAD THE ASSIGNMENT OPERATOR
------------------------------------------
------------------------------------------
   IntVec myVec(4);
   IntVec theirVec(4);

Before:





   myVec = theirVec;

After:





------------------------------------------
  3. copy constructors (pp. 328-330) 
------------------------------------------
                 PROBLEM
  DEFAULT (C++-DEFINED) COPY CONSTRUCTOR
                   vs.
    DATA MEMBERS THAT ARE POINTER VARS
       IN CLASS WITH A DESTRUCTOR

// kaboom2.C
#include <iostream.h>
#include "IntVec.h"

IntVec incAll(IntVec iv)
{
  for (int i = 0; i < 4; i++) {
    iv[i] += i;
  }
  return iv;
}

int main()
{
  IntVec myVec(4);
  for (int i = 0; i < 4; i++) {
    myVec[i] = 1;
  }
  IntVec yourVec = incAll(myVec);
  cout << yourVec[0];
}
------------------------------------------
------------------------------------------
           SEQUENCE OF EVENTS

In main before call:





activation frame for incAll(myVec):





When returning:





------------------------------------------
------------------------------------------
      DESIRED SEQUENCE OF EVENTS

In main before call:





activation frame for incAll(myVec):





When returning:





------------------------------------------
------------------------------------------
           COPY CONSTRUCTORS

IntVec::IntVec( const IntVec & another )
------------------------------------------
------------------------------------------

Used by C++ implicitly during:

  1. initializations in declarations:

         IntVec yourVec = myVec;

  2. passing parameters by value

         IntVec incAll(IntVec iv)
         {
           // ...
           return iv;
         }

         incAll(myVec);

  3. returning results by value

         return iv;
------------------------------------------
	Why isn't the parameter to the copy constructor passed by value?
  4. safety guidelines, summary (HR pp. 330-1)
------------------------------------------
  GUIDELINES FOR SAFE USE OF DYNAMIC DATA
            IN C++ CLASSES

To prevent unwanted indirect aliasing
           and dangling refrences:

  - always overload


------------------------------------------
------------------------------------------
To prevent memory leaks:

  - always overload
------------------------------------------
------------------------------------------
        Never use destructor
  usless you use a copy constructor
------------------------------------------
------------------------------------------
           A SAFE CLASS OUTLINE
            WITH DYNAMIC DATA

// MyCls.h
#include "Foo.h"
class MyCls {
public:
  MyCls();
  ~MyCls();
  MyCls& operator =(const MyCls& oth);
  MyCls(const MyCls & oth);
  // ...
#include "MyCls.pri"
};

// MyCls.pri
private:
  Foo* data;

// MyCls.C
#include "MyCls.h"
MyCls::MyCls() : data(new Foo()) {}
~MyCls::MyCls() { delete data; }
MyCls& MyCls::operator =(const MyCls& oth)
{ *data = *(oth.data); }
MyCls::MyCls(const MyCls & oth)
  : data(new Foo(*oth.data)) {}
------------------------------------------
  5. other alternatives (may omit)
	What happens if just leave off destructor?
	In this case, can omit deep copies.  But what happens then?
	What was Scheme like?
------------------------------------------
	OTHER SAFE ALTERNATIVES

Prohibit pass by value and assignment:

  - client has to use references
------------------------------------------
------------------------------------------
  - need to declare the copy constructor
    and the assignment operator,
    but 
------------------------------------------
------------------------------------------
  - destructor does *not* dealloctate
  - use a garbage collector
------------------------------------------
------------------------------------------
Reference counting:

  - copy constructor, assignment operator
    don't make deep copies but increment
    a reference count

  - destructor decrements reference count,
    only deletes storage when
    the reference count reaches 0.

  - has indirect aliasing
------------------------------------------
 F. summary and further examples