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