Previous Section
 < Free Open Study > 
Next Section


6.4 Copy Structures

In this section, we reverse the usual order of presentation. We show an example of a problem, and then we give the solution to the general problem. Let's look at an example where a client of the Stack ADT needs a CopyStack operation.

The client has access to all public member functions of StackType but cannot access any of the private data members. To make a copy of a stack, we must take all the items off oldStack and store them in a temporary stack. We can then copy the temporary stack back into copy.

template<class ItemType>
void CopyStack(StackType<ItemType> oldStack,
     StackType<ItemType>& copy)
{
  StackType<ItemType> tempStack;
  ItemType item;

  while (!oldStack.IsEmpty())
  {
    item = oldStack.Top();
    oldStack.Pop();
    tempStack.Push(item):
  }

  // oldStack is now empty; tempStack is the reverse of oldStack.
  while (!tempStack.IsEmpty())
  {
    item = tempStack.Top();
    tempStack.Pop();
    copy.Push(item);
  }
}

This situation seems quite straightforward. We realize that oldStack is empty because all of the items have been popped, but because oldStack is a value parameter, the original stack is not affected. Right? Wrong! If the static, array-based implementation of StackType is used, this function works correctly. The array is physically located within a class object. The class object is copied into the value parameter oldStack, and the original object is protected from change. But what happens if we use the dynamically linked implementation? The external pointer to the stack is copied into oldStack and is not changed, but the items to which it points change; they are not protected. See Figure 6.12.

Click To expand
Figure 6.12: Stack is a value parameter

Can't we solve this problem by copying tempStack back into oldStack? Let's consider the code for the Push operation and see what happens in the linked implementation. The first item is pushed onto the stack, and its address is stored into the data member topPtr of the parameter oldStack. As each successive item is placed on the stack, its address is stored into data member topPtr. Therefore, the topPtr data member of oldStack should contain the address of the last item put onto the stack, which is what we want. Because the stack is passed by value, however, only the copy of the external pointer to the stack (data member topPtr of oldStack) is passed to the function; the original pointer does not change. We have recreated the stack, but its external pointer is not transmitted back to the calling code.

Two solutions to this problem are possible: We can make the first parameter a reference parameter and recreate the stack, or we can provide a copy constructor as described in the next section.

Shallow versus Deep Copies

The problem described in the previous section occurred because when a class object is passed by value, a shallow copy of the parameter is made. With a shallow copy, only the data members in the parameter are copied. In the case of CopyStack, only a copy of the external pointer to the stack was passed as the parameter. When pointers are involved, we need a deep copy, one where the data members of the parameter and everything to which the data members point are copied. Figure 6.13 shows the difference.

Click To expand
Figure 6.13: Shallow copy versus deep copy of a stack

Shallow copy An operation that copies one class object to another without copying any pointed-to data

Deep copy An operation that not only copies one class object to another but also makes copies of any pointed-to data

If the calling code passes an actual parameter callerStack to the CopyStack function, a shallow copy causes the data member callerStack.topPtr to be copied into oldstack.topPtr. Both pointers now point to the same linked structure (Figure 6.13a). When the CopyStack function removes the items from the stack, it destroys the caller's stack! What we want is a deep copy of the stack so that CopyStack works with an identical but separate copy of the caller's stack (Figure 6.13b). In this case, the caller's stack remains unchanged by any manipulations within the function.

Class Copy Constructors

Copy constructor A special member function of a class that is implicitly invoked when passing parameters by value, initializing a variable in a declaration, and returning an object as the value of a function

C++ uses shallow copying in the following cases: passing parameters by value, initializing a variable in a declaration (StackType myStack = yourStack;), returning an object as the value of a function (return thisStack;), and implementing the assignment operation (stack1 = stack2;). Again, because of the active stance of a class object, C++ supports another special class operation called the copy constructor, which we describe shortly. If present, the copy constructor is used implicitly when a class object is passed by value, when a class object is initialized in a declaration, and when an object is a function return value.

What about the assignment operation? If you want to assign one object to another using a deep copy, you have to (a) write a member function to perform the deep copy and explicitly invoke it rather than use the assignment operator, or (b) overload the assignment operator. We discuss the first alternative in this section and the second alternative in the next section.

The copy constructor has a special syntax. Like the class constructor and destructor, it has no return type, just the class name.

template <class ItemType>
class StackType
{
public:
  .
  .
  // Copy constructor.
  StackType(const StackType<ItemType>& anotherStack);
  .
  .
};

The pattern that signals a copy constructor is the single reference parameter of the class type. The reserved word const protects the parameter from being altered even though it is passed by reference. Because the copy constructor is a class member function, the implementation has direct access to the class data. To copy a linked structure, we must cycle through the structure one node at a time, making a copy of the node's content as we go. Therefore we need two running pointers: one pointing to successive nodes in the structure being copied and one pointing to the last node of the new structure. Remember, in the deep copy of a linked structure, the info members are the same but the next members are not. In writing the algorithm, we must be sure to take care of the case where the stack being copied is empty.

Notice that our algorithm avoids using an extra pointer to the new node being inserted by storing its address directly into the structure where the new node will go.ptr1 points to the node to be copied; ptr2 points to the last node copied. See Figure 6.14.

Click To expand
Figure 6.14: Relative position of pointers at the beginning of each iteration
template <class ItemType>
StackType<ItemType>::StackType(const StackType<ItemType>& anotherStack)
{
  NodeType<ItemType>* ptr1;
  NodeType<ItemType>* ptr2:

  if (anotherStack.topPtr == NULL)
    topPtr = NULL;
  else
  {
    topPtr = new NodeType<ItemType>;
    topPtr->info = anotherStack.topPtr->info;
    ptr1 = anotherStack.topPtr->next;
    ptr2 = topPtr;
    while (ptr1 != NULL)
    {
      ptr2->next = new NodeType<ItemType>;
      ptr2 = ptr2->next;
      ptr2->info = ptr1->info;
      ptr1 = ptr1->next;
    }
    ptr2->next = NULL;
  }
}

Copy Function

We saw how the client program could write a function CopyStack to copy one stack into another, provided a class copy constructor is defined to maintain the integrity of the original stack passed as a value parameter. Alternatively, could we include a member function to copy one stack into another and let the client invoke it explicitly? Sure, but first we must decide whether we are copying self into another object or another object into self. That is, member functions are always applied to an object of the class type. One stack would be the object to which the function is applied, and the other stack would be a parameter of the function. Given the statement

myStack.Copy(yourStack);

is myStack being copied into yourStack or the other way around? Of course, we can't answer this question until we see the function declaration. If yourStack is being copied into myStack, then the code for Copy would be nearly identical to the class copy constructor. The difference is that self already points to a dynamic structure, and we must deallocate all the nodes of this structure by applying MakeEmpty before the copying begins. On the other hand, if myStack is being copied into yourStack, then we have to rethink the algorithm. We leave this change as an exercise.

There is a third way to implement a copy function. Suppose that we'd like to write a function in which both stacks are parameters to the function.

Copy(myStack, yourStack);

Compared to dot notation, this syntax is more familiar to (and therefore more comfortable for) some programmers. But we just said that member functions are applied to an object of the class type. How can we do this? C++ provides a syntactic device called a friend function that allows this type of construction. A friend function is not a member of the class, yet it has permission to access private class members directly. Here is how this friend function would be declared and implemented:

template<class ItemType>
class StackType
{
public:
  
  friend void Copy(StackType<ItemType>, StackType<ItemType>&):
  
};

template<class ItemType>
void Copy(StackType<ItemType> original, StackType<ItemType>& copy)
{
  if (original.topPtr == NULL)
    copy.topPtr = NULL;
  else
  {
    NodeType<ItemType>* ptr1;
    NodeType<ItemType>* ptr2;

    copy.topPtr = new NodeType<ItemType>;
    copy.topPtr->info = original.topPtr->info;
    ptr1 = original.topPtr->next;
    ptr2 = copy.topPtr;
    while (ptr1 != NULL)
    {

      ptr2->next = new NodeType<ItemType>;
      ptr2 = ptr2->next;
      ptr2->info = ptr1->info;
      ptr1 = ptr1->next;
    }
    ptr2->next = NULL;
  }
}

Notice that we do not preface the name of the function with the class name. Copy is a friend function, not a member function. Copy does have access to the private data members of its parameters, but access to them must be qualified by the parameter name and a dot. There is no implicit self in a friend function. The friend function is declared within a class definition, but it is not a member function of the class.

Overloading the Assignment Operator

In the last section, we pointed out that the assignment operator (=) normally causes shallow copying. It would be nice if we could write

myStack = yourStack;

Of course, if the stack is implemented as a dynamic linked structure, this code would result in two pointers pointing to the same stack rather than two distinct stacks. We can solve the problem of shallow copying with the assignment operator by overloading its meaning. In Chapter 3, we showed how to overload the relational operators. We can do the same thing for the assignment operator.

template<class ItemType>
class StackType
{
public:
  
  void operator=(StackType<ItemType>);
  
};

The function definition looks like this:

template<class ItemType>
void StackType<ItemType>::operator=
     (StackType<ItemType> anotherStack)
{
  
}

The function body is identical to that of the Copy member function that we discussed (but left as an exercise) earlier. Therefore, if we have already written a Copy member function, then to overload the assignment operator we make only one small change: Change the function name from Copy to operator=.

With an operator= function provided by the StackType class, the client code can use a statement like

myStack = yourStack;

The compiler implicitly translates this statement into the function call

myStack.operator=(yourStack);

Thus, the class object to the left of the equals sign in the client code is the object to which the operator= function is applied, and the object to the right of the equals sign becomes the parameter to the function.

We can overload the assignment operator for any number of classes. When the compiler sees an assignment operator, it looks at the types of the operands and uses the appropriate code. If the operands are objects of a class that has not overloaded the assignment operator, the default meaning of assignment is used-copying of data members only, yielding a shallow copy.

C++: Further Guidelines for Operator Overloading
Start example
  1. All C++ operators may be overloaded except ::, ., sizeof, and ?:.

  2. At least one operand of the overloaded operator must be a class instance.

  3. You cannot change the standard order of operator precedence, define new operator symbols, or change the number of operands of an operator.

  4. Overloading unary operators: If data is of type SomeClass, and you want to overload, say, the unary minus operator (-), then -data is equivalent to data.operator-() if operator- is a member function and to operator- (data) if operator- is a friend function.

  5. Overloading binary operators: If data is of type SomeClass and you want to overload, say, the addition operator (+), then data + otherData is equivalent to data.operator+ (otherData) if operator+ is a member function and to operator+(data, otherData) if operator+ is a friend function.

  6. Overloading the ++ and -- operators requires client code to use the preincrement form: ++someObjector or --someObject.

  7. Operator functions must be member functions when overloading =, (), [], and ->. Other restrictions apply as well. See a C++ reference book before attempting to overload (), [], and ->.

  8. The stream operators << and >> must be overloaded using a friend function. See a C++ reference book before attempting to overload << and >>.

  9. Many meanings for an operator can coexist as long as the compiler can distinguish among the data types of the operands.

End example

One final comment before we leave the problems related to classes in which at least one of the data members is a pointer type: If one of the three-class destructor, copy constructor, or overloaded assignment operator-is necessary, then most likely all three are necessary. This is sometimes called the "Rule of the big 3."



Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)