### Defining Key or Element Equality

A sorted collection must define either key equality or element equality. A sorted collection that does not have a key defined must have an ordering relation defined for the element type. This relation implicitly defines element equality.

Keys can be used to access a particular element in a collection. The alternative to defining element equality as equality of all data members is to define it as equality of keys only. (In the example below, this means defining job equality as equality of the job ID.) Use this alternative only when you are sure that keys are unique. When you use this alternative, you can locate an element only with the key (using locateElementWithKey(key) instead of locate(element). Locating elements by key improves performance, particularly if the complete element is large or difficult to construct in comparison to the key alone. Consider the two alternatives in the following example:

    // First solution
    JobId const& key (Job const& t) {  return t.id;  }
    KeySet < Job, int > jobs;
    // ...
    jobs.locateElementWithKey (1);

    // Second solution
    IBoolean operator== (Job const& t1, Job const& t2)
    {  return t1.id == t2.id;  }
    Set < Job > jobs;
    // ...
    Job t1;
    t1.id = 1;
    jobs.locate (t1);

The first solution is superior, if job construction (Job (t1) requires a significant proportion of the total system resources used by the program.

The Collection Class Library provides sorted and unsorted versions of maps and relations, for which both key and element equality must be defined. These collections are similar to key set and key bag, except that they define functions based on element equality, namely union and intersection. The add function behaves differently toward maps and relations than it does toward key set and key bag.

Introduction to the Collection Classes
Collection Characteristics
Access by Key
Equality Relation
Overview of Iteration
Iteration with Cursors
Iteration with allElementsDo
Flat Collections
Trees

Defining Equality Relation
Defining an Operations Class
Implementing Element- and Key-Type Functionality
Defining Member Functions of the Element Object Type
Defining Separate Global Functions
Using or Defining an Element Operation Class
Things to Watch Out For
Choosing the Appropriate Smart Pointer Class
Constructing Smart Pointers
Using Element Pointers
Using Cursors to Locate and Access Elements
Instantiating the Collection Classes