David E. Goldschmidt, Ph.D.

Example 13: Search using Recursion

Binary Search:

• Suppose you have vector<T> v and v is sorted such that:

v[0] ≤ v[1] ≤ v[2] ≤ ... ≤ v[n-1]

• Now suppose you want to find if a particular value x is in the vector. How can you do this without looking at every value in the vector left-to-right?
• The solution is a recursive algorithm called binary search, based on the idea of checking the middle item of the search interval within the vector and then looking either in the lower half or the upper half of the vector, depending on the result of the comparison.
• In other words, at each recursive function call, we're eliminating half of the list!
• Here's the code:

// Here is the recursive function.  If x is in the vector, then it
// must be located within the subscript range low to high. Therefore,
// when low and high are equal, their common value is the only possible
// place for x.  Otherwise, the middle value is checked, and the search
// continues recursively in either the lower or upper half of the given
// vector.
//
bool
binsearch( const vector<double> &v, int low, int high, double x )
{
  if ( high == low ) {
    return x == v[low];   // did we find x?
  }

  int midpoint = ( low + high ) / 2;

  // recursively call binsearch() with half the given vector
  if ( x <= v[midpoint] ) {
    return binsearch( v, low, mid, x );
  } else {
    return binsearch( v, mid + 1, high, x );
  }
}

// The driver function establishes the search range for the value of x
// based on the minimum and maximum subscripts in the vector.
//
bool
binsearch( const vector<double> &v, double x )
{
  return binsearch( v, 0, v.size() - 1, x );
}

Exercises:

• In the code above, why are there two binsearch() functions? Is this allowed?
• Write a non-recursive version of binary search.
• What is the order of the binary search algorithm? Is it better than searching linearly (i.e. compare x with v[0], then v[1], v[2], etc.)?
• Why is binary search called binary search?

Example 14: Pointers

Pointers:

• Pointers store memory addresses.
• Pointers can be incremented, decremented, added, and subtracted. This is often called pointer arithmetic.
• Pointers can be used to access the values stored at their stored memory address.
• Dynamically allocated memory is accessed through pointers.
• Pointers are also the primitive mechanism underlying vector iterators, which we have used with std::sort and will continue to use throughout the semester.
• Consider the following code segment. What's the output?

int x = 10;
int *p;
p = &x;
*p = 72;

if ( x > 20 ) {
  cout << "x is greater than 20\n";
} else {
  cout << "x is not greather than 20";
}

• x is an ordinary integer, but p is a pointer that can hold the memory address of any integer variable.
• Every variable is attached to a location in memory. This is where the value of that variable is stored.
• Each memory location also has an address, which is itself just an index into the giant array that serves as memory.
• The value stored in a pointer variable is an address in memory. In this case, the statement p = &x; takes the address of x and stores it (the address) in the memory location associated with p.
• The statement *p = 72; causes the computer to read the memory location stored at p, go to that memory location, and store 72 there. Note that *p is an l-value here.

Operations on Pointers:

• The unary operator * in the expression *p is the dereferencing operator. Read this operator as "follow the pointer" and note that *p is either an l-value or an r-value, depending on which side of the = operator it appears on.
• The unary operator & in the expression &x means "the memory address of" or just "address of."
• Pointers can be assigned. This just copies memory addresses as though they were values (which they are).
• What is the output of the following code?

float x = 5, y = 9;
float *p = &x, *q = &y;
*p = 17.0;
*q = *p;
q = p;
*q = 13.0;
cout << x << endl;
cout << y << endl;

• Assignments of integers or floats to pointers are illegal, as are assignments mixing pointers of different types. Continuing the above example:

int *r;
r = q;     // Illegal: different pointer types
p = 35.1;  // Illegal: float assigned to a pointer

• Comparisons between pointers using == and != are both legal and very useful. Other operators (e.g. < and >) are also allowed, but are generally only useful when working with arrays or other data structures stored contiguously in memory.
• Again continuing the above example:

if ( p == q ) {
  // Both pointers point to the same variable
}

if ( p != q ) {
  // Pointers point to different memory locations
}

• What is the output of the following code?

int x = 10, y = 15;

int *a = &x;
cout << x << " " << y << endl;

int *b = &y;
*a = x * *b;
cout << x << " " << y << endl;

int *c = b;
*c = 25;
cout << x << " " << y << endl;

Null Pointers:

• Pointers that don't (yet) point anywhere useful should be given the value 0, a legal pointer value. Most compilers define NULL as a special pointer equal to 0.
• Comparing a pointer to NULL is very useful, often used to indicate whether a pointer has a legal address or is uninitialized. For example, the following code tests to see if p is pointing somewhere useful before accessing the value stored at that location:

if ( p != NULL ) {
  cout << *p << endl;
}

• Dereferencing a NULL pointer leads to memory exceptions and program crashes. So watch out!

Example 15: Pointers and Arrays

Accessing Arrays with Pointers:

• Pointers serve as iterators for arrays. Examine the two versions of code below:

// Using []
const int n = 10;
double a[n];
for ( int i = 0 ; i < n ; i++ ) {
  a[i] = sqrt( double( i ) );      // cast i to type double
}

// Using * and pointer arithmetic
const int n = 10;
double a[n];
for ( double *p = a ; p < a + n ; p++ ) {
  *p = sqrt( p - a );
}

• Both versions of code do the same thing. In the pointer arithmetic version, the assignment statement p = a; takes the address of the start of the array and assigns it to p.
• The name of an array is actually a pointer to the start of a block of memory.
• The assignment statement p = a; could also have been written as follows:

p = &a[0];

• The condition p < a + n checks to see if the value of the pointer (the address) is less than n array locations beyond the start of the array. We could also have used the test p != a + n.
• By incrementing p using p++, we make p point to the next location in the array. This does not add 1 to p; instead it adds the number of bytes required for (in this example) a value of type double.
• In the assignment statement inside the for loop, *p is an l-value that tells the computer to dereference p and store the value of sqrt( p - a ).

Exercises:

For each of the following problems, use only pointers (no array subscripting):

1. Write code to print the array a backwards.
2. Write code to print every other value of the array a.
3. Write a function that checks whether the contents of an array are correctly sorted in increasing (or non-decreasing) order. The function must accept two arguments: a pointer to the start of the array; and an integer indicating the size of the array.

Example 16: Character Arrays and String Literals

C-Style Strings vs. C++ Strings:

• In the following line of code, "Hello!" is a string literal. It is also an array of characters (with no associated variable name).

cout << "Hello!" << endl;

• A C-style string is simply a char array, which can be initialized as follows:

char h1[] = "Hello!";
char h2[] = { 'H', 'e', 'l', 'l', 'o', '!', '\0' };

• Both h1 and h2 have exactly 7 characters, the last one the end-of-string character (just NULL).
• The C and C++ languages have many functions for manipulating these C-style strings. In C++, we do not use them much because the standard string library is easier to use.
• One place we do use C-style strings is in file names and command-line arguments.
• We have also been creating standard string objects from C-style strings when we do:

string s1( "Hello!" );
string s2( h1 );

• You can obtain the C-style string from a standard string using member function c_str, as in s1.c_str().
• C++ strings from the standard library hold sequences of characters and have a sophisticated set of operations defined on them, including resizing, changing characters, appending new characters, etc.
• Both string and vector objects grow and shrink from their end (highest subscripts) rather than their beginning (subscript 0).
• Further, string and vector objects should (almost) always be passed by reference. When no changes are to be made, they should be passed by constant reference using const.

Example 17: Defining a New Type

Defining a Data Type (a.k.a. a Class):

• A type defines both a structuring of memory and a set of operations (i.e. functions) that can be applied to that structured memory. Examples we've covered so far include strings and vectors.
• When we use a class, we don't usually know (or care) how memory is structured. Instead, what we really think about is the set of operations or functions that can be applied.
• A C++ class consists of:
  1. A collection of member variables, usually private
  2. A collection of member functions, usually public, which operate on the private member variables.
• Member functions defined as public can be accessed directly from outside the class.
• Member functions and member variables defined as private can only be accessed indirectly from outside the class by using public member functions.
• Using only function prototypes, we can create a class declaration of a Date class in a header file named Date.h:

// Date.h  <== click here for file

class Date
{
private:      // Begin with private member variables
  int day;
  int month;
  int year;

public:
  // Constructors
  Date();
  Date( int m, int d, int y );

  // Mutator functions
  void setDay( int d );
  void setMonth( int m );
  void setYear( int y );
  void increment();

  // Accessor functions (often defined using const)
  int getDay() const;
  int getMonth() const;
  int getYear() const;

  bool isEqual( const Date &date2 ) const;    // same day, month, year?
  bool isLeapYear() const;
  bool isLastDayInMonth() const;
  int lastDayInMonth() const;

  void print() const;
};

bool sameDayAndMonth( const Date &date1, const Date &date2 );

• The day, month, and year member variables are defined in the private section of the class. This ensures that only member functions have access to these variables, which effectively hides the implementation details of the class (which becomes increasingly important as we look at other classes and data structures in the near future).
• There are two Date() constructors, one without parameters (called the default constructor) and one with three parameters. Both are called when a Date object is created at runtime (e.g. from main()).
• Functions that potentially modify or change member variables are often called mutator functions.
• Functions that only read member variables are often called accessor functions. In C++, defining these with const ensures that the member function does not change the runtime object's member variables.
• All of the function prototypes (both in the class and outside of the class) in Date.h must be defined. It is a good programming practice to define these functions in a Date.cpp file, as shown next:

// Date.cpp  <== click here for file

#include <iostream>
using namespace std;

#include "Date.h"

Date::Date()  // default constructor
{
  month = 1;   // default date is 1/1/2000
  day = 1;
  year = 2000;
}

Date::Date( int m, int d, int y )
{
  month = m;
  day = d;
  year = y;
}

void Date::setDay( int d )
{
  day = d;
}

void Date::setMonth( int m )
{
  month = m;
}

void Date::setYear( int y )
{
  year = y;
}

void Date::increment()
{
  if ( !isLastDayInMonth() )
  {
    day++;
  }
  else
  {
    day = 1;
    if ( month == 12 )   // December
    {
      month = 1;
      year++;
    }
    else
    {
      month++;
    }
  }
}

int Date::getDay() const
{
  return day;
}

int Date::getMonth() const
{
  return month;
}

int Date::getYear() const
{
  return year;
}

bool Date::isEqual( const Date& date2 ) const
{
  if ( day == date2.day
       && month == date2.month
       && year == date2.year )
  {
    return true;
  }
  else
  {
    return false;
  }
}

bool Date::isLeapYear() const
{
  return year % 4 == 0 && ( year % 100 != 0 || year % 400 == 0 );
}

bool Date::isLastDayInMonth() const
{
  return ( day == lastDayInMonth() );
}


const int DaysInMonth[12] = { 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

int Date::lastDayInMonth() const
{
  if ( month == 2 && isLeapYear() ) {
    return 29;
  } else {
    return DaysInMonth[ month - 1 ];
  }
}


void Date::print() const
{
  cout << month << '/' << day << '/' << year;
}

bool sameDayAndMonth( const Date &date1, const Date &date2 )
{
  return date1.getDay() == date2.getDay()
         && date1.getMonth() == date2.getMonth();
}

Class Scope Notation:

• The prefix Date:: indicates that what follows is within the scope of the Date class.
• Within class scope, the member functions and member variables are accessible without the name of the object.

Constructors:

Constructors are special functions that initialize the values of the member variables. You have already used constructors for string and vector objects.

• Default constructors have no arguments.
• Multiple constructors are allowed, just like multiple functions with the same name are allowed. This is called function overloading. The compiler determines which one to call based on the argument list, which must match (in type) the parameter list, just like any other function call.
• When a new object is created, exactly one constructor for the object is called. You cannot prevent this from happening; you can only control which one is called.

Member Functions:

• Member functions are like ordinary functions except:
  1. They can access and modify the object's member variables.
  2. They can call other member functions without using an object name.
  3. Their syntax is slightly different because they are defined within class scope.
• The set and get functions access and change the member variables (e.g. day, month, year).
• The increment() member function calls another member function, isLastDayInMonth().
• The isEqual() member function accepts a second Date object (by reference) and accesses its private member variables directly using the dot notation. Since we are inside class Date scope, this is allowed.
• The lastDayInMonth() function uses a const array also defined in the Date.cpp file.

Accessing and Changing Member Variables:

• When member variables are private (which they should be!), the only means of accessing them and changing them from outside the class is through member functions.
• If member variables are made public, they can be accessed directly. This is usually considered bad style since inconsistent changes might be made. As such, this will not be allowed in this course.

Non-member Functions:

• Functions that are not members must interact with Date objects through the public interface declared for the class. These may perform operations that are closely associated with the class and therefore feel like member functions.
• One example of this is the sameDayAndMonth() function, which accepts two Date objects and compares them by accessing their day and month values through their public member functions.

Constant Member Functions:

• Member functions that do not change member variables (i.e. accessor functions) should be declared using const.
• This must appear consistently in both the member function declaration in the class declaration and the member function definition.

Exercises:

1. Add a member function to the Date class to add a given number of days to the Date object. The number should be the only argument and it should be an unsigned int. Should this function be defined using const?
2. Add a isLessThan() member function to determine if the date is less than (i.e. is earlier than) a Date object passed in by reference.
3. In main() (see below), add some Date objects to a vector. Display the elements of the vector using a loop. Next, sort the vector and display it again.

Main Code:

// date_main.cpp  <== click here for file

#include <iostream>
#include <vector>
using namespace std;

#include "Date.h"

int another_function();

int main()
{
  int aMonth = 5, aDay = 27, aYear = 2009;

  // Create a Date object:
  Date today( aMonth, aDay, aYear );
    // this calls the Date() constructor
    //   that has 3 integer arguments

  Date d;   // NO PARENTHESES HERE!

  int x = another_function();

  cout << "Today's date is: ";
  today.print();
  cout << endl;

  today.increment();
  cout << "Today is now tomorrow: ";
  today.print();
  cout << endl;

  Date bday( 5, 2, 2010 );
  for ( int i = 0 ; i < 365 ; i++ ) {
    cout << "Next day: ";
    today.increment();
    today.print();

    if ( bday.isEqual( today ) ) {
      cout << " (my birthday!)";
    }

    cout << '\n';
  }

  vector<Date> v;
  v.push_back( Date( 4, 10, 1988 ) );
  v.push_back( Date( 2, 28, 2002 ) );
  v.push_back( today );
  v.push_back( bday );

  for ( int i = 0 ; i < v.size() ; i++ ) {
    v[i].print();
    cout << ' ';
  }
  cout << endl;

   // TODO: sort the vector....

  return 0;
}