Boost logo

Boost :

From: Sean Parent (sparent_at_[hidden])
Date: 2006-07-10 19:46:48

operator < should be defined anytime an objects of type can be
totally ordered and the comparison has average constant complexity
with worst case complexity proportional to the area of the object
(the complexity guarantees are why we don't provide a less-than-
operator for hash containers - we could just as we do for vector, but
the cost is prohibitive). In the absence of a better choice, a
lexicographical comparison of the members should be provided.

The ordering must be total because !(a < b) && !(b < a) => a == b
[trichotomy law]. The reason for the allowing comparison functions is
containers is to allow for other orderings, including partial ones.

Recommended reading - lecture 7 of <

Alex asserts in his notes that even when the less than operator has
no meaning other than to provide a runtime ordering (such as for
iterators on linked lists) it should be provided. In the case of
linked list iterator - I also think that in the presence of increment
that a < b should imply that [a, b) is a valid range and b is
reachable from a through increment (which would not be the case using
pointer ordering for linked list iterators). Limiting the application
of operator < to relationships which survive serialization (that is,
ones which do not depend on accidental relationships of object
identity) would be my preference.


Boost list run by bdawes at, gregod at, cpdaniel at, john at