[boost] Comment on operator <

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 <http://www.stepanovpapers.com/ 
notes.pdf>.

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.

Sean