Herb Sutter (http://www.gotw.ca/) chairs the ISO C++ Standards committee and is an architect in Microsoft's Developer Division. His most recent books are Exceptional C++ Style and C++ Coding Standards (Addison-Wesley). Jim Hyslop is a senior software designer for Leitch Technology International. He can be reached at [email protected].
Hey, Junior," Bob's voice grated at me. I grit my teeth and turned to him. "You got a problem with one of your classes," he continued, sipping at his latte.
"What is it this time?" I asked. He plopped down at the keyboard, and called up a class I had written:
class JuniorsClass
{
map< Key, Value > theItems_;
public:
void AddItem( const Key &,
const Value & );
Value & FindValue( const Key & );
};
"See, the problem is, Junior, I add a couple of items, which your AddItem function takes and puts into that map contraption. But later, when I call FindValue, your class gives me the wrong value. Here, I know how much you like test code, so I whipped up this baby to show what's going wrong." He called up another file in the editor:
#include <JuniorsClass.h>
#include <BobsClass.h>
int main()
{
JuniorsClass jc;
Key key1(1), key2(2);
Value value1(10), value2(20);
jc.AddItem( key1, value1 );
jc.AddItem( key2, value2 );
Value & lookup = jc.FindValue( key1 );
assert( lookup == value1 );
}
"See, even though I'm giving you two distinct Key objects, you're not returning the correct Value object. It's returning value2, not value1."
I frowned in thought. "But the functions are pretty simple, Bob," I said as I took over the keyboard and called up the source for my class:
void JuniorsClass::AddItem( const Key &
key, const Value & value )
{
theItems_[ key ] = value;
}
Value & JuniorsClass::FindValue(
const Key & key )
{
return theItems_[ key ];
}
"See? All I do is put the Key and Value into the map. It can't go wrong."
"Well, I'm telling you, Junior, that your class isn't working. You can see for yourself that the program chokes on the assertion."
He had me there. "Okay, Bob, I'll have another look at it."
Bob picked up his latte cup and ambled off to the kitchen for a refill. I sighed and turned to my monitor. What could be wrong with my code? Snap—the familiar sound of the Guru's tome pulled me out of my contemplations.
"Your writings, my child," the Guru's voice sounded behind me, "live in piousness. Consider this, though. What are the sorting requirements on an associative container?"
"Uh, well, the key has to provide an operator <," I said without hesitation. The Guru didn't respond—she just arched an eyebrow. Maybe I should've hesitated. "Ah, that is," I mumbled while scrambling for my copy of the Standard, "it, um...oh, here it is. The map takes a comparison class that, um, sorts the elements." I pointed at the section of the Standard:
namespace std {
template <class Key, class T, class
Compare = less<Key>,
class Allocator =
allocator<pair<const Key, T> > >
class map { [1]
"And this Compare class, which defaults to std::less, does what, my child?"
"It compares the two Keys?" I ventured. The Guru sighed.
"In general terms, my apprentice, what order does class Compare impose?"
"It...Oh!" I exclaimed as the penny dropped. "It imposes a strict weak ordering!" I beamed at her.
"Very good, my apprentice. Now what does a strict weak ordering mean?"
"Uh..." Deer. Headlights. The Guru sighed again.
"Intuitively, my child, it simply means putting the elements in order, just as the < comparison can be used to sort integers in order. Speaking more piously, the comparison function must be irreflexive, which is to say that for a comparison function, bool comp( const Key & key1, const Key & key2 ) and a Key a, comp(a, a) must return false.
"This irreflexivity can be used to set up an equivalence relation—that is, for Keys a and b, if comp(a, b) is false and comp(b, a) is false, then a and b must be equivalent. Note that the Holy Standard is careful to distinguish equivalence from equality—a and b may be equivalent, but a.operator==(b) may not necessarily return true.
"Furthermore, my child, the Holy Standard requires the comparison and equivalence to be transitive, which is to say that given three Keys a, b, and c, if a and b are equivalent, and if b and c are equivalent, then a and c must also be equivalent. Similarly, if comp(a,b) returns true, and comp(b,c) returns true, then comp(a,c) must also return true.
"Now, with all that in mind, let us examine Bob's comparison function." I turned to the keyboard and called up his code:
bool Key::operator<(const Key & Fred) const
{
return field1 < Fred.field1 && field2
< Fred.field2;
}
The Guru began clucking her tongue the instant the function scrolled into view.
"It is as I expected," she said. "Pray, child, where are the unit tests for this class?"
I hunted around for a few minutes, then began to feel like I did the day when I was eight, and I had been asked to fetch a can of dehydrated water. I turned to the Guru.
"There are no unit tests," we chorused.
"Hang on a sec," I continued. "Let me see if I understand the problem with this function. Suppose Key represented a version number, with a major and a minor number. And suppose that both major revision numbers, in field1, are the same—the function will always return false because the minor revision will not be checked."
"Precisely, my child. The expression will return true only for the precise condition stated. The comparison function must impose an ordering on the fields. How would you rewrite this function to work properly?"
After a moment's thought, I changed the implementation:
bool Key::operator<(const Key & other) const
{
if ( field1 < other.field1 ) return true;
if ( field1 == other.field1 ) return field2 < other.field2;
return false;
}
The Guru nodded. "Well done. Now, is there a way you can do this using the Standard Library?" That stumped me. The Guru picked up a marker, and wrote on my whiteboard:
return make_pair( field1, field2 ) < make_pair( other.field1, other.field2 );
"std::pair has a comparison operator that does effectively the same comparisons as your version. One more thought, my apprentice—how would you handle this if you were unable to modify the class Key, or if the class did not have an operator <?"
"Ummm...well, I guess I could provide my own Compare class," I said.
"Very good, apprentice. Compare is simply a binary predicate. Among the faithful, there are those who believe that 'less than' is not necessarily semantically correct for a class. For example, suppose there is a class like this:
class StockItem
{
string medium_; // book, DVD, tape, etc.
string title_;
"What does it mean for a book entitled I, Robot to be 'less than' a DVD entitled Shrek II? For those faithful, they can write their own comparison function, thusly:"
bool CompareOther( const StockItem & other) const
{
int compareResult = medium_.compare( other.medium_ );
if ( compareResult < 0 ) return true;
if ( compareResult == 0 ) return title_.compare(
other.title_ ) < 0;
return false;
}
"But when you get down to brass tacks," I interrupted, "the comparison is still a less-than comparison letter by letter."
"True, my child—for the individual characters that make up the strings. But for the StockItem itself, the comparison is between two StockItems to impose a specific ordering. Now, if I may continue, once the CompareOther function has been written, the faithful needs only to write a binary predicate to wrap the comparison function:"
class CompareItems
{
public:
bool operator()( const StockItem & item1, const StockItem
& item2 )
{
return item1.CompareOther( item2 );
}
};
set< StockItem, CompareItems > stock;
"The Compare class can also be used to provide different sort criteria; for example, if you wanted a second map, or a multiset, to sort stock based on the title regardless of the medium, then you would write a comparison function that sorted primarily by title, then by medium."
The Guru turned and continued as she walked away, "The, er, key, my apprentice, is to keep your wits about you when writing comparison functions that deal with multiple fields. And, of course, to have proper unit tests in place to detect..." she turned the corner and was gone, leaving me once again to clean up Bob's mess.
References
[1] ISO C++ Standard, ISO/IEC14882:2003(E), clause 25.3.1.
Acknowledgments
Special thanks to the programmers who took part in the survey conducted by the authors. Particular thanks to Stefan Heinzmann for reminding the authors of the std::pair<> solution, and the members of the accu-general mail list for the (as always) lively discussion around this issue.
