Section 1 - Deep Copies of Images

6B.1.1 Shallow Copies

At some point we end up having to deal with the sticky topic of shallow and deep copies.  It all starts when, one day, we notice that an object has been modified when we never modified it.  How can this be?  We used shallow copies when we should have been using deep copies.  We have discussed the meaning of deep and shallow data twice before in this class, so you already know what I mean.  We dealt with it in CString examples where we were allocating and de-allocating char arrays.  Now we want to really see this concept in fine detail by doing an example with dynamic two-dimensional arrays.

Recall that for classes with simple primitive data members, we normally can get by with a shallow copy, where we supply a copy constructor and simply move the data from the parameter object to this as in:

TwoDimImage::TwoDimImage( const TwoDimImage & tdi )
{
  this->data = tdi.data;
}

We know this won't work for deep data. 

If data is a pointer to dynamically allocated memory we are sunk. 

Consider a client making use of the above copy constructor:

TwoDimImage sam(janet);

After the instantiation of sam, both sam and janet's data member are pointing to the same memory (just look at the copy constructor) so changing data using sam will be reflected if we later examine janet.  While we sometimes do want two objects controlling the same data, most of the time we really want a true, separate, copy for each object.  We will study this in detail right now.

Let's take a class that has a two-dimensional array of ints.  Since grayscale pictures are really nothing more than such animals, we'll call this class TwoDimImage.  Let's design the class with the above, inadequate, copy constructor embedded in the definition.  We do this naively, but intentionally, as an experiment.

We will use our prior study of dynamic two-dimensional arrays and allow the data to be nothing more than an  int**, on which we will build both dimensions of the two dimensional array.  We've done this in week 3, so refer back if you need a refresher.

Here is the private int **data of the class along with a couple static consts that will be used to size our array:

private:
  int **data;

public:
  static const int MAX_HEIGHT;
  static const int MAX_WIDTH;

Now, I am going to do this more simply than I would normally, because we are not interested in squeezing out every ounce of efficiency here, but rather, getting practice with deep copies.  To that end, we will always instantiate the same size 2-D array, namely MAX_HEIGHT x MAX_WIDTH.  In a real class, I would allow each object to be a different size and do dynamic sizing as the application needed it.  With this simplification, we can use the following two straightforward private utilities to allocate and de-allocate memory.  These will be used by the constructors and destructor:

void TwoDimImage::allocateCleanArray()
{
  int row, col;

  if (data != NULL)
    deallocateArray();

  data = new int*[MAX_HEIGHT];
  for ( row = 0; row < MAX_HEIGHT; row++ )
    data[row] = new int[MAX_WIDTH];

  for ( row = 0; row < MAX_HEIGHT; row++ )
    for ( col = 0; col < MAX_WIDTH; col++ )
      data[row][col] = 0;
}

void TwoDimImage::deallocateArray()
{
  int row;

  if (data == NULL)
    return;

  for ( row = 0; row < MAX_HEIGHT; row++ )
    delete[] data[row];
  delete[] data;
  data = NULL;
}

Before going any further, memorize these methods.  You need to do this sort of thing in your sleep.   If you have a question about even a semicolon, don't hesitate to ask us in the forums.

Now we easily write the default constructor and destructor:

TwoDimImage::TwoDimImage()
{
  // build the image matrix
  data = NULL;
  allocateCleanArray();
}

TwoDimImage::~TwoDimImage()
{
  deallocateArray();
}

Nothing surprising there.  The most interesting method comes next: the non-default constructor.  We want to be able to instantiate our object quickly, rather than call the mutator a billion times, once for each int in the matrix.  So we design a constuctor that will take a big fat int matrix (a 2-D array).  The problem is, we want to allow any size int matrix, as long as its size is smaller or equal to that of our data array, which is, as I said, MAX_HEIGHT × MAX_WIDTH.  This is easy in Java, if you happen to come from that world, but not in C++.  Here, we have to take an int** and two dimensions.  Here is the constructor:

TwoDimImage::TwoDimImage(int **inData, int width, int height)
{
  int row, col;

  // build the image matrix
  data = NULL;
  allocateCleanArray();

  if ( !checkSize(inData, width, height) )
    return;  // silent, but there's an error, for sure

  // copy
  for ( row = 0; row < height; row++ )
    for ( col = 0; col < width; col++ )
      data[row][col] = inData[row][col];
}

It creates an empty dynamic array, and if the size of the incoming inData array is sensible, it copies the data into it.

There are a few methods that I won't separate out from the main listing because they are nothing to write home about, and you can read them at your leisure.  They are the accessor/mutator getElement()/setElement(), the private utility checkSize() and the I/O method display().

Here is the full class prototype with all member functions, both the ones we put on exhibit above and those we have yet to define.  After you scan it, you'll have a sense of the entire class. 

class TwoDimImage
{
private:
  int **data;

public:
  static const int MAX_HEIGHT;
  static const int MAX_WIDTH;

  TwoDimImage();
  ~TwoDimImage();
  TwoDimImage(int **intData, int width, int height);
  TwoDimImage(const TwoDimImage &tdi);
  bool setElement(int row, int col, int val);
  int getElement(int row, int col);
  void display();

private:
  bool checkSize(int **inData, int width, int height);
  void allocateCleanArray();
  void deallocateArray();
};

Now for the trial main().  We allocate two objects, one from a dynamic array of ints, and the second using the first object via the copy constructor:

int inputArray[3][5] = {
  {1, 1, 1, 1, 1},
  {2, 2, 2, 2, 2},
  {3, 3, 3, 3, 3}
};
int *userArray[3];

// convert the inputArray to an array controlled by an int**
for ( row = 0; row < 3; row++ )
  userArray[row] = &inputArray[row][0];

TwoDimImage imObj1(userArray, 5, 3);
TwoDimImage imObj2(imObj1);

This might be a good time for you to review the meaning of *, [], [][], and & as we described in week 4.  You should think about two things:

1. Why can't we just pass inputArray directly into the constructor?  Can we redefine the constructor in any reasonable way that would allow us to do so?
2. userArray is really an int**.  It may not look like it, but you should stare at the code until you are convinced it is.  Now, we have something we can pass to the constructor.

This little code snippet tells us how to write clients that build 2-D arrays that can be turned into TwoDimImage objects.

Finally, we want to test how the two objects are, or are not, related after the above instantiations.  What happens when we change only one object, and print them both out?  Here's the rest of main() which does that:

// change ONLY the first object
imObj1.setElement(2, 2, 9);
imObj1.setElement(4, 0, 9);

// show both
imObj1.display();
imObj2.display();

Remember, we still have a bogus copy constructor because we want to see what kind of damage it will inflict.  Besides that, though, we are ready to run.  Here we go:

Ouch.  Before we even panic about the assertion (i.e., the crash), we should look at what happened in the console before the crash.

We changed the first object's data using:

// change ONLY the first object
imObj1.setElement(2, 2, 9);
imObj1.setElement(4, 0, 9);

and, sadly,  both objects got modified.  The offending method is, as we already mentioned,  the ill-designed copy constructor:

TwoDimImage::TwoDimImage( const TwoDimImage & tdi )
{
  this->data = tdi.data;
}

While this assignment would work if data were primitive, it does not work here because data refers to stuff that is outside our object, proper.  In other words, data is a deep memory handle.  So, our object controls deep data, but the class copy constructor is providing only a shallow copy.  This explains why both matrices look identical when we only changed one.  Make sure you have this point.

Next, we can explain the crash. Since the console output suggests that the program must have executed up until the bitter end before it crashed, we suspect the destructor, and yes, that's where the crash occurred.  The destructor, though, is doing what it should:

TwoDimImage::~TwoDimImage()
{
  deallocateArray();
}

And you already saw that deallocateArray() is also rock solid.  So while the crash happened inside the destructor, it was caused by the copy constructor.  The very idea that we are de-allocating deep memory on  two objects that share that memory (because of our ill-designed copy constructor) tells us exactly what happened.  Once the first object was destructed, the second object tried to deallocate the same deep memory that was already deleted, thus .... crash!

This is unacceptable.  Therefore, we do need a better copy constructor.

6B.1.2 Deep Copies In Copy Constructors

We can fix this simply by rewriting our copy constructor:

TwoDimImage::TwoDimImage(const TwoDimImage &tdi)
{
  int row, col;

  // build the image matrix
  data = NULL;
  allocateCleanArray();

  // copy
  for ( row = 0; row < MAX_HEIGHT; row++ )
    for ( col = 0; col < MAX_WIDTH; col++ )
      data[row][col] = tdi.data[row][col];
}

Now we can see the run:

That's more like it. (Ignore the invisible man behind the little white curtain.  It's just your programming teacher jumping in to get a close look at the program run.)

6B.1.3 Copy Constructor In Step with Assignment Operator

Any time you need a copy constructor, you can be sure you also need an overloaded assignment operator.  The correct order is to define  the assignment operator first, then call it from the copy constructor. To wit:

TwoDimImage::TwoDimImage( const TwoDimImage & tdi )
{
  data = NULL;
  allocateCleanArray();
  *this = tdi;
}

const TwoDimImage &TwoDimImage::operator=( const TwoDimImage & rhs )
{
  int row, col;

  // copy (no reallocation since all objects are the same size)
  if (this != &rhs)
  {
    for ( row = 0; row < MAX_HEIGHT; row++ )
      for ( col = 0; col < MAX_WIDTH; col++ )
        data[row][col] = rhs.data[row][col];
  }
  return *this;
}

Often, the allocation/de-allocation must be done in operator=(), rather than the copy constructor, because objects have different memory needs, but as I mentioned in my preamble, I am restricting this class to a single-size matrix. 

Molly, here, will be the first to argue that it is very important to make sure you clone your objects using the above techniques:

Full Source for TwoDimImage

#include <iostream>
#include <string>
#include <limits>

using namespace std;

class TwoDimImage
{
private:
  int **data;

public:
  static const int MAX_HEIGHT;
  static const int MAX_WIDTH;

  TwoDimImage();
  ~TwoDimImage();
  TwoDimImage(int **intData, int width, int height);
  TwoDimImage(const TwoDimImage &tdi);
  const TwoDimImage &operator=(const TwoDimImage &rhs);
  bool setElement(int row, int col, int val);
  int getElement(int row, int col);
  void display();

private:
  bool checkSize(int **inData, int width, int height);
  void allocateCleanArray();
  void deallocateArray();
};

// main method ---------------------------------------
int main()
{
  int row;
  int inputArray[3][5] = {
  {1, 1, 1, 1, 1},
  {2, 2, 2, 2, 2},
  {3, 3, 3, 3, 3}
  };
  int *userArray[3];

  // convert the inputArray to an array controlled by an int**
  for (row = 0; row < 3; row++)
  userArray[row] = &inputArray[row][0];

  TwoDimImage imObj1(userArray, 5, 3);
  TwoDimImage imObj2(imObj1);

  // change ONLY the first object
  imObj1.setElement(2, 2, 9);
  imObj1.setElement(4, 0, 9);

  // First secret message
  imObj1.display();
  imObj2.display();
}

const int TwoDimImage::MAX_HEIGHT = 5;
const int TwoDimImage::MAX_WIDTH = 5;

TwoDimImage::TwoDimImage()
{
  // build the image matrix
  data = NULL;
  allocateCleanArray();
}

TwoDimImage::~TwoDimImage()
{
  deallocateArray();
}

TwoDimImage::TwoDimImage(int **inData, int width, int height)
{
  int row, col;

  // build the image matrix
  data = NULL;
  allocateCleanArray();

  if ( !checkSize(inData, width, height) )
    return;  // silent, but there's an error, for sure

  // copy
  for ( row = 0; row < height; row++ )
    for ( col = 0; col < width; col++ )
      data[row][col] = inData[row][col];
}

TwoDimImage::TwoDimImage(const TwoDimImage &tdi)
{
  data = NULL;
  allocateCleanArray();
  *this = tdi;
}

const TwoDimImage &TwoDimImage::operator=(const TwoDimImage &rhs)
{
  int row, col;

  // copy (no reallocation since all objects are the same size)
  if (this != &rhs)
  {
    for ( row = 0; row < MAX_HEIGHT; row++ )
      for ( col = 0; col < MAX_WIDTH; col++ )
        data[row][col] = rhs.data[row][col];
  }
  return *this;
}

bool TwoDimImage::checkSize(int **inData, int width, int height)
{
  if (inData == NULL)
    return false;
  if (width > MAX_WIDTH || width < 0)
    return false;
  if (height > MAX_HEIGHT || height < 0)
    return false;
  return true;
}

bool TwoDimImage::setElement(int row, int col, int val)
{
  if (row < 0 || row >= MAX_HEIGHT || col < 0 || col >= MAX_WIDTH)
    return false;
  data[row][col] = val;
  return true;
}
int TwoDimImage::getElement(int row, int col)
{
  if (row < 0 || row >= MAX_HEIGHT || col < 0 || col >= MAX_WIDTH)
    return INT_MAX; // from limits.h -- use as an error (lame, but easy)
  return data[row][col];
}

void TwoDimImage::display()
{
  int row, col;

  // top row border
  cout << endl;
  for (col = 0; col < MAX_WIDTH + 2; col++)
    cout << "-";
  cout << endl;

  // now each row from 0 to MAX_HEIGHT, adding border chars
  for ( row = 0; row < MAX_HEIGHT; row++ )
  {
    cout << ("|");
    for ( col = 0; col < MAX_WIDTH; col++ )
      cout << data[row][col];
    cout << "|" << endl;
  }

  // bottom
  for (col = 0; col < MAX_WIDTH + 2; col++)
    cout << "-";
  cout << endl;
}

void TwoDimImage::allocateCleanArray()
{
  int row, col;

  if (data != NULL)
    deallocateArray();

  data = new int*[MAX_HEIGHT];
  for ( row = 0; row < MAX_HEIGHT; row++ )
    data[row] = new int[MAX_WIDTH];

  for ( row = 0; row < MAX_HEIGHT; row++ )
    for ( col = 0; col < MAX_WIDTH; col++ )
      data[row][col] = 0;
}

void TwoDimImage::deallocateArray()
{
  int row;

  if (data == NULL)
    return;

  for ( row = 0; row < MAX_HEIGHT; row++ )
    delete[] data[row];
  delete[] data;
  data = NULL;
}