Implementing operator<, std::mismatch vs. std::lexicographical_compare

[Daryle Walker]

I implemented operator== for my container type with std::equal. I was
about to use std::lexicographical_compare for my operator<, but I
realized it may be inefficient:

1. Return special-case value if one or both lists end early.
2. You do *l < *r and return TRUE if this comparison does so.
3. Else, do *r++ < *l++ and return FALSE if this comparison returns
true.
4. Otherwise, you're currently equal and go back to (1).

The lexicographical compare makes its decision at the first unequal
pair of elements (or FALSE if all are equal). Instead of two calls to
operator< to determine equality, just use one call to operator==, then
return the comparison at the mismatch point.

Now, I know this plan would require carrying two different comparators
for the non-operator variants (and hoping that their comparison
philosophies are in sync); that's probably why the standard versions
just call operator< twice. But for my private code, where I pre-
condition the element type to have both operators, would it be better
to just use std::mismatch & one operator< call instead of
std::lexicographical_compare?

(BTW, my structure has all containers have the same size, so I don't
do that check.)

Daryle W.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

[Daniel Krügler]

Am 06.05.2013 18:37, schrieb Daryle Walker:
> The lexicographical compare makes its decision at the first unequal
> pair of elements (or FALSE if all are equal). Instead of two calls
> to operator< to determine equality, just use one call to operator==,
> then return the comparison at the mismatch point.

Yes, this approach makes sense, if you can impose additional
constraints upon == and <. For types with a total order this
assumption holds.

> Now, I know this plan would require carrying two different
> comparators for the non-operator variants (and hoping that their
> comparison philosophies are in sync); that's probably why the
> standard versions just call operator< twice.

I think the more fundamental reason is, because the Standard Library
generally only assumes (strict) weak orders. For such systems the
trichotomy law doesn't necessary hold, i.e. the guarantee that for any
pair of values (x, y) of the domain of the relation, exactly one of

x < y
x == y
x > y

holds.

> But for my private code, where I pre- condition the element type to
> have both operators, would it be better to just use std::mismatch &
> one operator< call instead of std::lexicographical_compare?

I have not enough data to say that it would be better, but this
approach sounds quite plausible to me. It means you impose a total
order among the values of a given type.

HTH & Greetings from Bremen,

Daniel Kr�gler