More on Total Ordering
As noted above, the comparison object must induce a total ordering on the type of the items in the collection class. This means that the function-call operator of the comparison object must satisfy the following two conditions (adapted from Knuth (1973)), assuming that comp is the comparison object and x, y, and z are potential elements of the collection class, not necessarily distinct:
I. Exactly one of the following statements is true:
a) comp(x,y) is true and comp(y,x) is false
b) comp(x,y) is false and comp(y,x) is true
c) comp(x,y) is false and comp(y,x) is false
(or, in other words: not both comp(x,y) and comp(y,x)
are true)
II. If comp(x,y) and comp(y,z) are true , then so is
comp(x,z) (transitivity).
The truth of I.a implies that x must precede y within the collection class, while I.b says that y must precede x. More interesting is I.c. If this statement is true, we say that x and y are equivalent, and it doesn't matter in what order they occur within the collection class. This is the notion of equality that prevails for the templates that take a comparison object as a parameter. For example, when the member function contains(T item) of an associative container-based template tests to see if the collection class contains an element equivalent to item, it is really looking for an element x in the collection class such that comp(x,item) and comp(item,x) are both false. It is important to realize that the == operator is not used. Don't worry if at first it seems counter-intuitive that so much negativity can give rise to equivalence—you are not alone! You'll soon be comfortable with this flexible way of ensuring that everything has its proper place within the collection class.
Comparison objects are generally quite simple in their implementation. Take for example:
class IncreasingLength {
public:
bool operator()(const RWCString& x, const RWCString& y) const
{ return x.length() < y.length(); }
};
RWTValSet<RWCString,IncreasingLength> mySet;
Here mySet maintains a collection of strings, ordered from shortest to longest by the length of those strings. You can verify that an instance of the comparison object satisfies the given requirements for total ordering. In the next example, mySet2 maintains a collection class of integers in decreasing order:
class DecreasingInt {
public:
bool operator()(int x, int y) const
{ return x > y; }
};
RWTValSet<int, DecreasingInt> mySet2;
Although the sense of the comparison may seem backwards when you first look at it, the comparison object says that x should precede y within the collection class if x is greater than y; hence, you have a decreasing sequence. Finally, let's look at a bad comparison object:
// DON'T DO THIS:
class BadCompare {
public:
bool operator()(int x, int y) const
{ return x <= y; } // OH-OH! Not a total ordering relation
};
RWSetVal<int, BadCompare> mySet3; // BAD COMPARISON OBJECT
To determine why it's bad, consider an instance badcomp of BadCompare. Note that when using the value 7 for both x and y, none of the three statements I.a, I.b, or I.c is true, which violates the first rule of a total ordering relation. Unfortunately, the requirement for total ordering is a logical, not a semantic one, so the compiler cannot help by rejecting poorly chosen comparators. In general, such code will compile, but probably have unexpected behavior.
