Rogue Wave banner
Previous fileTop of DocumentContentsIndex pageNext file
Essential Tools Module User's Guide

6.11 Function Objects for Comparison

The associative container-based and the sorted sequence-based collection classes maintain order internally. This ordering is based on a comparison object, an instance of a comparison class you must supply when instantiating the template. A comparison object must contain a const member operator(), the function-call operator, which takes two potential elements of the collection class as arguments and returns a bool value. The returned value should be True if the first argument must precede the second within the collection class, and False otherwise. Often, it is easiest to use one of the function-object classes provided by the Standard C++ Library in the header file <functional>. In particular, use less<T> to maintain elements in increasing order, or greater<T> to maintain them in decreasing order. For example:

Here mySet1 is a set of integers kept in increasing order, while mySet2 is a set of dates held in decreasing order; that is, from the most recent to the oldest. You can use these comparison objects from the Standard C++ Library as long as the expression (x < y) for the case of less<T>, or (x > y) for the case of greater<T>, are valid expressions that induce a total ordering on objects of type T.

6.11.1 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:

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:

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:

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:

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.



Previous fileTop of DocumentContentsIndex pageNext file

©2004 Copyright Quovadx, Inc. All Rights Reserved.
Rogue Wave and SourcePro are registered trademarks of Quovadx, Inc. in the United States and other countries. All other trademarks are the property of their respective owners.
Contact Rogue Wave about documentation or support issues.