C++ Week 17

Objects containing pointers

Assigning and copying objects that contain pointers

When we built our Date class, there were some operations that we did not need to program explicitly; the system provided default versions of these operations and these were adequate for our purposes. Specifically, we were able to use one Date object to create another. Assuming we had already defined a Date d1 - as in, say, Date d1(25,12); - we could write Date d2(d1); We were using the default version of the copy constructor. And we did not need to program the assignment operation. Assuming we had already defined Dates d1 and d3, we could simply write d3 = d1; and the assignment would take place as we wanted. And we could pass Dates as value parameters, and they would behave as we would expect value parameters to behave. If a function began int func(Date dx) and we called it as int x = func(d1); then dx would be a copy of d1 and the function could do what it liked to dx without having any effect on d1.

The default versions of these operations simply copy data items from one object to another, which is fine if the items are simple things like integers. But, if the objects contain pointers, this is almost certainly not what we want.

Take assignment as the example. If some object o1 contains, as its only data member, a pointer to a linked list, then the default version of the assignment o2 = o1; will do no more than copy the value of the pointer in o1 to the pointer in o2. So now, the pointer in o1 and the pointer in o2 are pointing at one and the same linked list. But that is not what we wanted. We wanted o2 to be pointing at a linked list of its own, an exact copy of the one that o1 is pointing at. We have to do some programming to make this happen.

We'd have the same problem if we used the default copy constructor to create o2 as in Objtype o2(o1); And we'd have the same problem if we passed o1 as a value parameter, say in int x = func(o1); to a function beginning int func(Objtype ox) - the pointer in ox would be pointing at the same linked list as the one in o1.

An implementation of a stack

We will illustrate the technique with a simple stack class, which we will implement with a singly-linked list. A stack is a list structure in which insertions and deletions take place at the same end. The class definition, before the additions we are about to make, looks like this:

class Stack
{ public:
	Stack() : top(NULL) {}
	void push(int);
	int pop();
	void display() const;
	bool empty() const;
  private:
	class Node;
	Node* top;
};

class Stack::Node
{ public:
	int n;
	Node* link;
	Node(int x) : n(x), link(NULL) {}	// constructor defined inside the Node class definition
};

Click here for a full listing of the code

This implementation of the stack is fairly straightforward, consisting of push() and pop() functions. Note that, in the full listing, we define a constructor for the Node class outside the class definition, so we have to write:

Stack::Node::Node(int x)
{  ...
}

Node(int x) is the constructor, and the one we are talking about here belongs to the Stack::Node class.

Overloading assignment and the copy constructor

Let's suppose we have populated a stack, S1 and want to make a copy of it, S2. A simple assignment of the form

S2 = S1;

will only copy the top pointer stored in S1 to S2, so if you did anything to the stack S2 you would actually be making changes to S1 (and vice-versa). The same would happen if you used the copy constructor

Stack S2(S1);

So we have to overload both of these operations to make them work properly.

The easiest way to do this is to create two private functions called copy() and free(). The first of these builds a new list, pointed at by tnew and copies the values from an existing list pointed at by texist. Since we've just done recursion, let's do it recursively (non-recursive would also be OK):

void Stack::copy(Node*& tnew, Node* texist)
{  if (texist == NULL)
      tnew = NULL;
   else
   {  tnew = new Node(texist->n);
      copy(tnew->link, texist->link);
   }
}

If we are assigning S2 = S1; and S2 already exists, we have to make sure that we make S2 empty before we do anything, otherwise we will leak memory. For this we define a free() function. Again I'll do it recursively (the non-recursive version is equally straightforward):

void Stack::free(Node*& ts)
{  if (ts != NULL)
   {  free(ts->link);
      delete ts;
      ts = NULL;
   }
} 

Now we are in a position to implement the copy constructor and the assignment operator.

The copy constructor

The copy constructor can simply call copy() because we know that the one that's being constructed does not already exist:

Stack::Stack(const Stack& sx)
{  copy(top, sx.top);
}

The overloaded assignment operator

The assignment operator first has to call free() because the stack being assigned to might already exist:

Stack& Stack::operator=(const Stack& sx)
{  if (this != &sx)
   {  free(top);
      copy(top, sx.top);
   }
   return *this;
}

The condition in the function is required as we have to deal with the special case of an assignment of the form stk = stk; It would be a pointless assignment, but not an invalid one. If we didn't guard against it, we would first destroy stk, with free(), and then try to copy the nodes from the Stack we had just destroyed. To prevent ourselves from doing that, we check whether the Stack we are copying from is exactly the same Stack as the one we are copying to. this is a pointer to the implicit parameter - the Stack we are copying to - and &sx is the address of the explicit parameter - the one we are copying from.

The reason why the assignment operator returns something is that assignment in C++ is a function, not a procedure. You will recall that you can have x = y = 10; This works because y = 10 not only assigns a value to y but also returns the value (more precisely it returns a reference to y, as we'll see later), so that it can be assigned to x also. (Assignment is right-associative, so if we put in the implicit brackets, we would have x = (y = 10);) If we are to do the same with Stack objects, our overloaded assignment also has to return a Stack. We return it as a non-const ref. (For more on this point, see the end of this lesson.)

Value parameters

Providing our Stack class with a copy constructor also solves the problem of value parameters. Say we had a function that began int func(Stack sx) and we called it with int x = func(s1); If Stack did not have a copy constructor, the default copy constructor would be used and we'd have the pointers in sx and s1 pointing at the same stack. But, if the Stack class has a copy constructor, then it's Stack's own copy constructor that will be used for the parameter passing, so sx will be a separate stack from s1.

(In practice, you'd be more likely to use a const ref parameter than a value parameter, since that's how you generally pass objects to functions, so you shouldn't have this problem anyway, but it's nice to know that the value parameter would work as it ought to, if you wanted to use one.)

The destructor ~Stack

When we create variables with local scope, they are destroyed automatically when the procedure is finished. In the case of pointers, and structures that use them, we have to take care to destroy them explicitly, otherwise we will leak memory. For example, consider the following fragment:

for (int i = ...)
{  Stack st;
...
}

Every time the loop iterates, we create a new stack and presumably push items onto it, so, by the time the loop ends, we will have created a new singly-linked list. At the end of each iteration, the private variable top of st will be destroyed, but NOT the structure it points to. We need a procedure that will do this at the end of each loop. In C++ this procedure resides in the so-called destructor member function of the class:

Stack::~Stack()
{  free(top);
}

Its name is just the name of the class, preceded by a tilde, ~. You don't have to call the destructor explicitly - it happens automatically.

The destructor would also be called if you had a pointer to a Stack and did a delete on it:

Stack*  sptr = new Stack;   // calls Stack constructor
sptr->push(99);             // use the Stack that sptr is pointing at
...
delete sptr;                // calls Stack destructor

Now you can see why it is convenient to have the private functions copy and free. The copy constructor just calls copy, the destructor just calls free, and the assignment operator calls both.

Our class declaration now looks like this:

class Stack
{ public:
   Stack();
   void push(int x);
   int pop( );
   void display( ) const;
   bool empty( ) const;
   Stack(const Stack&);
   ~Stack();
   Stack& operator=(const Stack&);
  private:
   class Node;
   Node* top;
   void copy(Node*&, Node*);
   void free(Node*&);
};

Should assignment return a const ref or a non-const ref?

Given that the assignment operator has to return something, should we return a const ref or a non-const ref? Have a look at this simple class (which is pointless as well as pointer-less, but it will serve as illustration):

class Number
{ private:
	int n;
  public:
	Number(int x) : n(x) {}
	int get() const { return n; }
	Number& operator=(const Number& x)
	{	n = x.get();
		return *this;
	}
};

int main()
{	Number	a(1), b(2), c(3);
	a = b = c;			// or, equivalently, a = (b = c);
	cout << "a is " << a.get() << ", b is " << b.get() << ", c is " << c.get() << endl;	// outputs "a is 3, b is 3, c is 3"
}

Now remember that, if you return a reference, then the part of the program that receives the reference can now make changes to the thing that was returned. (If you cast your mind back to the overloaded [] operator in the Safevec class, we returned an int& because this was exactly the effect we wanted to achieve.) What would happen if we changed the above program with some brackets?

(a = b) = c;

a is 3, b is 2, c is 3

	const Number& operator=(const Number& x)

You might well feel that, unlikely though such a scenario might be, you'd like to prevent it, by returning a const ref. Weirdly, however, programmers are in fact allowed to do things exactly like that to the built-in types such as int. For example:

int main()
{	int	x = 5, y = 6, z = 7;      // just the ordinary int type, not the Number class
	(x = y) = z;
	cout << x << " " << y << " " << z << endl;		// output is 7 6 7
}

Notes on R. Mitton's lectures by S.P. Connolly, edited by R. Mitton, 2000