Advanced Programming I Lecture Notes

19 January 2006 • C++ Review

Outline

• Types

• Pointers and Dynamic Storage.

• Classes and Pointers.

Basic Things You Should Know

• Types.

• Control structures, including conditional and repetitive statements.

• Functions, including declarations, polymorphism, reference parameters, and recursion.

• Arrays, including declaration, initialization, array parameters, and arrays and pointers.

Basic C++ Data Types

Integer Types

• An integer type represents a contiguous range of integers.

  • Understand exactly where the ends of the range are.

• The two important integer characteristics are sign and and size.

Integer Size

• Integer size is given in terms of 8-bit bytes.

  • A one-, two-, four-, eight-, or sixteen-byte integer.

• The sizeof() built-in function returns a type's size.

  • n = sizeof(T) means a value of type T occupies n bytes.

Controlling Integer Size

• Integer size is controlled by the keywords short and long.

  int
  short intopt
  long longopt intopt
  

• The size requirements are

  	sizeof(short int)
  ≤	sizeof(int)
  ≤	sizeof(long int)
  ≤	sizeof(long long int)

Integer Sign

• An integer's signedness determines if it can represent negative numbers.

  • A signed integer can, an unsigned integer can't.

• The unsigned and signed keywords indicate integer signedness.

  • signed is the default and is usually omitted.

Integer Ranges

• An integer's size, signedness, and representation determine its range.

• Let integral type T have size n bytes.

  • If T is signed, it has range -2ⁿ to 2^{n - 1} - 1.

  • If T is unsigned, it has range 0 to 2ⁿ.

Range Asymmetry

• Mind the asymmetry in the range endpoints.

  • Between the extreme positive and negative signed values.

  • Between the maximum signed and unsigned values.

Integer Overflow

• An integer overflow occurs when attempting to use a value outside a type's range.

• C++'s behavior on overflow is undefined, which means it's arbitrary.

  • The usual behavior is to ignore it and truncate the value to fit.

Why Bother?

• Why not just always use the largest signed value and be done with it?

  • Precise use of types convey more information than do imprecise use.

    int find(int a[], int n);
    
    int find(int a[], unsigned n);
    

  • You still have to deal with overflow.

  • It's wasteful of space (and perhaps time).

Floating-Point Data

• A floating-point data type also represents a range of numeric values.

• But, floating-point value ranges are

  • considerably larger than integral ranges of comparable size,

  • do not represent exact values, and

  • are non-contiguous and non-uniform.

Two Points about Floating Point

1. A floating-point value is like a dirt pile: the more you handle it, the smaller it gets and the messier everything else becomes.

2. Never compare floating-point values directly

   if (x == y) { /* whatever */ }
   

   Always compare the difference between floating-point values to some epsilon.

   if (fabs(x-y) < epsilon) {/* whatever */}
   

   Picking the right epsilon can be tricky.

Character Types

• Character values can either be one-byte (char) or two-byte wchar_t (wide characters).

• Character types are integral, but treating characters like integers is usually poor practice.

• char data type signedness is compiler dependent.

  • The signed and unsigned keywords can make it definite.

The Boolean Type

• C++ (but not C) has a built-in boolean type with constants true and false.

• Become familiar with Boolean operators, laws, and manipulations.

  • But the realization of Boolean operators in a language can make it tricky to correctly use the laws and manipulations.

Boolean Operators

• The Boolean operators && (alternatively and) and || (alternatively or) are short-circuit operators.

  • B₁ and B₂ is defined to be

    B1 ? B2 : false
    

    B₁ or B₂ is defined to be

    B1 ? true : B2
    

  • Short-circuiting makes and and or non-commutative.

Ahh, Pointers

• Pointers are not your friends.

• If T is a type, T * is the type pointer to T.

• A T * value is used as the address of a value of type T.

  • It is the programmer's responsibility to make sure that's always true.

• Understand clearly the difference between a pointer to a value and the value itself.

  • Confusing the difference, or forgetting it, can lead to unending, intense pain.

Pointer Operations

• Pointer values can be generated, dereferenced, assigned, compared, and computed.

• The address-of operator & generates pointer values.

  • If v is a variable of type T, then the expression &v is a value of type T*.

Pointer Dereferencing

• The follow (or dereference) operator * follows (or dereferences) a pointer value to return the associated value.

  • It is entirely the programmer's responsibility to make sure the dereferenced pointer value points to a valid value.

Pointer Assignment

• Pointer assignment is straightforward: both sides have to have type T *.

• The consequences of pointer assignment, however, are not so straightforward.

  • The value address on the left-hand side is lost, possibly leading to garbage.

  • The value address on the right-hand side is copied, leading to shared or aliases access.

• It is entirely the programmer's responsibility to make sure that pointer assignment doesn't result in situations where chaos can ensue.

Pointer Comparison

• (In-)equality comparisons are straightforward, as long as you remember that the addresses are being compared, not the values addressed.

  • "hello world" == "hello world" may or may not be true.

• Ordering comparisons (<, >, <= and >=) determine the order between two pointers pointing into the same value sequence.

Pointer Arithmetic

• A pointer may be added to an integer value.

  • The integer value is scaled by the size of the value being pointed at.

• Pointer addition is not closed:

  The sum of a pointer and an integer may not be a valid pointer.

• It is entirely the programmer's responsibility to make sure that pointer addition results in a valid pointer.

Pointer Subtraction

• Two pointers of the same type may be subtracted from each other.

  • Subtraction only makes sense if the two pointers are pointing into the same value sequence.

  • The result is the number of values between the two pointers.

  • The result is signed; for positive results subtract the smaller pointer from the larger.

Dynamic Storage

• Dynamic storage is really not your friend.

  • Make absolutely sure you need it.

• Most C++ value storage is laid-out at compile time.

  • This is known as compile-time (or statically) allocated storage.

• Compile-time allocated storage can be difficult or wasteful to use at run-time.

  • How many customers did your store have yesterday?

Dynamically-Allocated Storage

• Dynamically- (or heap-) allocated storage helps deal with the problems caused by compile-time allocation.

• The two dynamic-storage operators are new and delete.

• The expression new T allocates a storage chunk big enough to hold a value of type T.

  • The storage chunk may or may not be initialized.

  • The result of new T has type T *.

Freeing Dynamic Storage

• If the variable p contains a valid value of type T *, the expression delete p recovers the storage being pointed to by p.

  • The value in p is not changed; but it's now invalid.

    • All pointers to the recovered storage are invalid.

  • Any operation on an invalid pointer value is undefined.

Freeing Rules

• Each dynamically-allocated storage chunk must be freed exactly once.

  • Attempting to free an already freed storage chunk leads to chaos.

• It is the programmer's responsibility to make sure the value in p was returned by a new statement.

Arrays

• An array is a contiguous sequence of values of type T.

  • An array is a homogeneous data structure.

• An individual value in an array is known as an array element.

• The number of elements in an array is the array size.

  • Array size is a cruel joke in C++.

Array Operations

• The array index operator [] provides access to array elements.

• An n-element array has valid indices 0 through n - 1 inclusive at both ends.

• The sizeof() operator on an array returns the total number of bytes in the array, not the number of elements.

Array Size

• The size of an array is fixed; the amount of space allocated to an array doesn't change.

• Array indexing is not fixed; any valid value of n is an acceptable index into an array.

• It is entirely the programmer's responsibility to make sure that array indices fall within the size of the array.

Arrays and Pointers

• Arrays and pointers are closely related.

  • Given the declaration T a[3];, a is just a constant pointer to the first (zeroth) element.

• The indexing operation a[expr] is just a shorthand for the expression *(a + expr).

  • The indexing operator can be applied to any valid pointer.

Multidimensional Arrays

• The array-pointer similarity is dangerous when used with multidimensional arrays.

• An array of arrays is not the same thing as an array of pointers.

  

Classes and Pointers

• Pointers are old C; classes are new C++.

• Pointers and classes can work well together.

  • Unfortunately we won't be studying that.

• Without care, pointers and classes can make your programming life a nightmare.

  • That's what we'll be studying.

Garbage is Born

• Where garbage comes from:

  struct C {
    data * data_ptr;
    C() : data_ptr(new data) { }
    };
  
  static void t(void) { C c; }
  

• This code violates the fundamental rule of dynamic memory:
  If you allocate it, you free it.

Class Destructor

• The class destructor should free class-allocated storage.

  struct C {
    data * data_ptr;
    C() : data_ptr(new data) { }
   ~C() { delete data_ptr; }
    };
  
  static void t(void) { C c; }
  

Unintentional Sharing

• By default, base-type values are bit-wise copied.

• This replicates pointers, leading to un-intentional sharing and dangling pointers on destruction.

Unintentional Sharing Example

struct C {
  data * p;
  C() : p(new data) { }
 ~C() { delete p; }
  };

static void t(C & c) { C c2(c); }

• In t(), c2.p is c.p.

  • Changing *(c2.p) changes *(c.p).

  • Deleting *(c2.p) deletes *(c.p).

Class Instance Copying

• Class instance copying happens all the time.

  • For example, non-reference class parameters.

    void t(C c) { }
    

    The call t(c) makes a copy of c.

The Copy Constructor

• Use the class copy constructor to handle dynamic memory copying.

• The copy constructor prototype is
  C::C(const C &).

  • Don't forget the reference &.

• The details depend on the memory being managed.

Copy Constructor Example

struct C {
  data * data_ptr;

  C() : data_ptr(new data) { }

  C(const C & c) 
    : data_ptr(data_clone(c.data_ptr)) {}

 ~C() { delete data_ptr; }
  };

static void t(C & c) { C local_c(c); }

Class Instance Assignment

• Instance assignment is similar to instance copying.

• The default assignment uses bit copying.

  • This leads to unintended sharing, dangling pointers, and garbage.

Instance Assignment Example

struct C {
  data * p;
  C() : p(new data) { }
  C(const C & c) 
    : p(data_clone(c.p)) {}
 ~C() { delete p; }
  };

static void t(C & c) { C c2; c2 = c; }

Instance Assignment Problems

• Given

  static void t(C & c) { C c2; c2 = c; }
  

  the contents of c.p replaces the contents of c2.p.

  • The previous contents of c2.p is garbage.

  • c2.p and c.p are sharing storage.

The Assignment Operator

• Classes should define an assignment operator to manage memory during assignments.

• Dynamic memory management is simple:

  • Deallocate memory in the instance to the left of the =.

  • Clone memory from the instance to the right of the =.

Assignment Operator Example

struct C {
  data * data_ptr;
  C() : data_ptr(new data) { }
  C(const C & c) : data_ptr(data_clone(c.data_ptr)) {}
 ~C() { delete data_ptr; }

  // Bad example.
  C & operator = (const C & c) {
    delete data_ptr;
    data_ptr = data_clone(c.data_ptr);
    return *this;
    }
  };

Refining Assignment

• Assignment usually can share code with the copy constructor constructor and the destructor.

  • All would call the same private member functions.

• Two tricks to assignment:

  1. Self assignment a = a, and

  2. the assignment expression a = b = c.

The Self-Assignment Problem

• a = a self-assignment does occur in code.

  • Particularly with references and parameters.

  • This is a source of nasty errors.

Self-Assignment Example

C & C::operator = (const C & rhs) {
  delete data_ptr;
  data_ptr = copy_data(rhs.data_ptr);
  return *this;
  }

• What happens with a = a?

• Deallocating in lhs also deallocates in rhs.

  • For a = a, *this = rhs.

  • Deleting data_ptr deletes rhs.data_ptr.

Detecting Self-Assignment

• Make sure *this is different from rhs.

  • If *this and rhs are different, proceeds as normal.

  • If *this and rhs are the same, be careful.

  C & C::operator = (const C & rhs) {
    if (this != &rhs) {
      delete data_ptr;
      data_ptr = copy_data(rhs.data_ptr);
      }
    return *this;
    }
  

Assignments as Expressions

• A little-known C++ fun fact: an assignment is an expression.

  • x = y = z = 0.0;

  • An assignment's value is the rhs's value.

• Assignment should support this.

  • Programmers may expect this behavior.

  • Good programmers don't disappoint their colleagues.

Assignment Expressions

• The assignment prototype is

  T & operator = (const T & rhs)
  

  • The prototype can be different, but it usually shouldn't be.

    T operator = (const T & rhs)
    

    makes a more expensive copy. (Another one!)

Assignment Return

• The assignment return value is *this.

• Here returning a value reference is efficient and safe.

  • Normally returning a value reference is a red flag.

Assignment and Copying

• What's the difference between assignment and copying?

  • Assignment redefines, copying defines (or initializes).

• Sometimes copying looks like assignment.

  widget w1 = w2;
  
  w1 = w2;
  

Assignment vs. Copying

• Despite the syntax, declared variables are initialized; the target state is undefined - unintentional replication.

• In assignment, the target is defined and is redefined; unintentional replication, dangling pointers, and garbage.

• Assignment vs. copy - redefinition vs. initialization; the state of the target.

The Rule of Three

• If a class implements a destructor, a copy constructor, or an assignment operator, then it needs to implement all three.

• Classes with pointer-type instance variables need them all.

Points to Remember

• Understand and use types.

• Dynamic storage and pointers aren't your friends.

• Embrace and internalize the Rule of Three.

Bibliography

• Comparing floating point numbers, Bruce Dawson, Cygnus Software.

• What every computer scientist should know about floating-point arithmetic by David Goldberg in ACM Computing Surveys, March 1991.