Using comparators

Now that you've seen basic examples demonstrating general collection protocol, you should have a general understanding of comparators. It's difficult to talk about collections without a solid understanding of the way collection elements are tested for equality and identity. Searching for an element in a collection and removing an element from a collection both require a means of identifying a specific element without knowing its position. Every collection has associated with it an object called a comparator. To understand the importance of comparators, consider the following example program.

      int main()
      {
          TSetOf<TStandardText>* collection =
              new TSetOf<TStandardText>(NIL, NIL);
  
          collection->Add(new TStandardText("one"));
          collection->Add(new TStandardText("two"));
          collection->Add(new TStandardText("three"));
  
          collection->Add(new TStandardText("one"));
          collection->Add(new TStandardText("two"));
          collection->Add(new TStandardText("three"));
  
          printCollection(collection);
  
          delete collection;
          return 0;
      }

The output from this program is not what you might expect. Again the program uses the polymorphic printCollection function which takes a pointer to any type of collection descending from TCollectionOf. This version of printCollection is based on collection elements of type TStandardText. An implementation of this version of printCollection is shown under "Sample program using no comparator" on page 55

  0> three
  1> one
  2> three
  3> two
  4> two
  5> one

With no comparator defined, equality is based on pointer addresses

The order of elements is unordered, as it should be. However, the set appears to contain duplicate elements. The problem is that the default mechanism used by collections compares pointer addresses of collection elements to determine if two elements are equal. In some cases this definition of equality makes sense. However if the intent of a program like the one above is to weed out duplicates, use another approach. Because each of the calls to the new operator above returns a different pointer, all six pointers in the collection have a different address. Collection elements are not equal for the same reason that the expression

  (new TStandardText("one")) == (new TStandardText("one"))

returns 0 or false. The new operator allocates fresh memory from the heap on each invocation and therefore returns a different pointer address on successive calls. The only way to fix the situation without changing the default constructor for sets is to explicitly manage pointers. For example, if the above program were changed to

      int main()
      {
          TSetOf<TStandardText>* collection =
              new TSetOf<TStandardText>(NIL, NIL);

TStandardText

the resulting output makes more sense for the behavior normally associated with a set.

  0> two
  1> one
  2> three

Using variables is not a practical solution. The main reason for using collections is to avoid maintenance of individual variables to reference each collection element. Individual variables would be particularly unwieldy in a collection of thousands of lines or hundreds of shapes in a CAD system. However the example does help clarify the notion that identity is different from equality.

[Contents] [Previous] [Next]

Click the icon to mail questions or corrections about this material to Taligent personnel.

Generated with WebMaker