Re: [boost] Please don't define a fake"operator<"just for ordered containers

From: Sean Parent (sparent_at_[hidden])
Date: 2006-07-11 13:44:50

More comments -

IMHO it is important to come up with a specific set of rules for  
operator < () than it is to argue about "fake", "feelings",  
"natural", "expected", and other such terms.

What are the semantics of operator <?

I'd state the following:

1. It must provide a total ordering (simply a strict weak ordering is  
not sufficient - for example a strict weak ordering on a pointer  
could compare just the second byte of the address).

2. Less than ordering must be average constant complexity with worst  
case complexity proportional to the area of the objects.

3. When there is a strongly established convention for the ordering  
then that convention should be used.

I don't think we have much disagreement on the above points (perhaps  
some confusion). Now I'd add the following:

4. In the absence of established convention (such as from the domain  
of mathematics), lexicographical ordering by comparing the parts  
should be used.
        Examples from the standard: std::string (which does not sort by  
established linguistic rules), std::pair, std::vector, std::set,  
tr1::tuple.
        Counter examples (which should be fixed): std::complex (real,  
imaginary).

Mathematicians do not have memory or complexity to deal with  
(mathematicians don't sort) - so arguing that the lack of a rule in  
mathematics implies that one shouldn't exist in computer science is  
vacuous.

5. If an object is Incrementable (and/or Decrementable) then the  
ordering should be such that give:

        T b(a);
        ++a;
        assert (b < a);

        Examples: pointers within the same array, random access iterators  
(not forward iterators because of item 2), int

This item is potentially debatable (Alex disagrees in his notes -  
I'll argue it more with him later today).

6. For objects for which a comparison is based upon properties which  
are not defined across invocations (such as object identity) operator  
< should not be defined (and not provided where reasonable)

        Examples: pointers to different arrays, random access iterators to  
different containers, type_info, forward iterators.

For these types, a standard way to get to a total ordering should be  
provided. Currently we have std::less<> for pointers,  
type_info::before(), iterators can be converted to pointers - &*iter  
and then std::less can be used. My recommendation is to use  
std::less<> - which could be specialized for each of these types.  
That is std::less<> should provide a total ordering even when  
operator < does not (but consistent with operator < when it is  
defined). std::less must still obey 1 and 2.

4a. For composite types for which some of the parts do not define  
operator < (per item 6). They should define std::less<> based on the  
lexicographical ordering of the parts using std::less<>.

        Examples: none - but it would be trivial to specialize std::less<>  
for pair, tuple, etc.

With the above rules, there are _very_ few cases where std::less<>  
would not be defined (an example would a hash_map where the  
implementation would violate item 2).

If operator < is defined then all comparison operators (>, <=, ==,  
 >=, !=) should be defined consistently. Likewise for std::greater et  
al.

 From item 6 - I'd remove the operator < from shared_ptr. If we were  
going to keep operator < for shared ptr, then I would have to argue  
to change all of the examples from 6 for consistency (or provide a  
semantic difference between shared_ptr and these cases.

Sean