2.3.6. Copying and comparing item-based types and item types

2.3.6. Copying and comparing item-based types and item types
	2.3. Linear lists (class list)

Learning objectives

Copying of item-based types

Copying of items

Copying of LEDA types in general

The LEDA rule “Copy of a value”, part c

Equality and identity of LEDA objects

A question that occurs again and again in connection with item-based LEDA types and that regularly causes confusion is of the following kind: What happens when a list is assigned to another list? What exactly is copied then? In which sense are the two lists equal? And what happens when an item is assigned to another one? Does the second item change when the first is changed? Or does it change when the contents of the container that the first item refers to are changed? To answer these questions let us first have a look at the following program:

Filename: ListEquality.C

LEDA users as of version 5.0: Note that header files are now partitioned into modules (subfolders)!

#include <LEDA/list.h>
#include <iostream>

using leda::list;
using leda::list_item;
using std::cout;
using std::endl;

int main() 
{

  list<int> L;

  L.append(5); L.append(3);

  list<int> A = L; // copy according to LEDA rule 9

  if(L == A) cout << "L equals A." << endl;
  else       cout << "L does not equal A." << endl;

  list_item it1, it2;
  it1 = it2 = L.first();

  L[it1] = 7; // change value of container which it1 refers to
  // it1 and it2 remain unchanged and still refer to the same container

  L.print("L: "); cout << endl;
  A.print("A: "); cout << endl;

  if(it1 == it2) 
    cout << "it1 and it2 are still equal." << endl; // LEDA rule 2
  else          
    cout << "it1 and it2 are not equal." << endl;

  if(L.contents(it1) == L.contents(it2))
    cout << "Therefore they refer to the same container." << endl;
  else
    cout << "They do not refer to the same container." << endl;
}

The output is

L does not equal A.
L:  7 3
A:  5 3
it1 and it2 are still equal.
Therefore they refer to the same container.

Copying of objects of an item-based type

To understand what the assignment operator does when assigning a list to another one by A = L, we consult the LEDA rule “Copy of a value” once again. We have already got to know the parts a and b in Section 2.2.1; here, part c is decisive.

At first, this part of the rule says that a value x of an item-based, structured type is a structured collection of values. This is a more or less trivial statement. In the case of a list this simply means that an object of type list is a linear sequence of interlinked containers.

Furthermore, part c of the rule says that a copy of x is a collection of new values, each one of which is the copy of a value in x, the original, and that the combinatorial structure that is imposed on the new values is isomorphic to the structure of the original x.

Good gracious! First of all, this rule teaches us that LEDA was designed and described by scientists. But it is not so difficult to understand. In the above situation this statement means: By no means A points now to the same physical object as L in any sense; rather, an isomorphic copy of the combinatorial structure of L is made and assigned to A. Of course, here this structure is a sequence of containers since L is a list. A copy of the value of the corresponding original container is placed in every new container.

In other words: There are twice as many containers now, and in every container of A a copy of an integer number is located now; this copy already was in a corresponding container of L before. We see that this is correct also by the fact that after changing the first element of L to the value 7 in the above program, the elements of A are still unmodified.

Now the question can be answered what the assignment operator does when dealing with structured types that store structured types themselves, for example a list of arrays, an array of lists, or a list of lists: The rule “Copy of a value” is then used recursively! Thereby, the question what generally happens when copying a LEDA object, be it of structured or primitive type, is settled, too: The parts a, b, and c of the rule have to be applied recursively in accordance with the template structure that the type is based on.

Comparisons of LEDA objects

Why are L and A unequal immediately after the assignment? After all, they contain exactly the same elements in the same order! This, of course, is also due to the fact that both are completely different objects, which refer to different memory locations. L and A are not the same physically, but only equal concerning their structure (“isomorphic”). In this sense the equality predicate (implemented by the operator ==) never returns the value true when non-primitive LEDA objects are compared with it.

On the other hand, consider the items it1 and it2, which both are initialized so that they reference the first container of L. (Remember: In accordance with the rule “Copy of a value” the copy of a value of an item type is a bitwise copy of this value.) These items are not changed in the above program even if the contents of the container are changed. The two items are therefore equal also after the modification.

This is underlined in the LEDA rule “Equality and identity”, part a: “For objects x and y of a dependent item type the equality predicate x==y means the equality between the values of these objects.” This seems trivial; how should it1 and it2 be unequal here? After all, we did not modify the (reference) values!

The sense of the rule discloses itself not until we notice its part b: “For objects x and y of an independent item type T the equality predicate x==y is defined individually for every such item type. In the majority of cases it means equality between the values of x and y, but this is not guaranteed for every type.” We will come to independent item types later; let us mention here only the following example: The class point stores points of the 2-dimensional plane and works with an handle scheme. What does it mean here for points to be “equal”? Let us look at the following code fragment:

point p(2.0,3.0); // a point with coordinates (2.0,3.0)
point q(2.0,3.0); // another point with the same coordinates
p == q;           // evaluates to true

p and q are equal here in accordance with part b of the rule although the values of the references are different (p and q reference different objects, which, however, have the same “contents”): The equality operator is defined for point in such a way that it compares the coordinates of the points.

Anticipatory, let us already mention that for such independent item types an identity predicate

bool identical(const T&, const T&);

may be defined; in terms of this predicate, p and q are not identical - a function call

identical(p, q); // evaluates to false

returns false.


2.3.5. User-defined type parameters		2.3.7. Further information and tips