lexicographical_compare on empty ranges

[Bjorn Reese]

The description of lexicographical_compare only describes the default
case where the comparison operator is less<T>().

It is unclear to me how lexicographical_compare should work with another
Compare argument.

For example, [alg.lex.comparison] states that "An empty sequence is
[...] not [lexicographically] less than any empty sequence". What is
supposed to happen when we compare two empty ranges with
std::equal_to<T>() as the Compare argument? Should it be interpreted
as "An empty sequence is not lexicographically equal to any empty
sequence"?

[Daniel Krügler]

equal_to doesn't meet the requirements imposed on Compare.
[alg.sorting] specifies the semantic constraints imposed on function
objects named Compare throughout the whole sub-clause [alg.sorting].
Objects of that type shall induce a strict weak ordering on the
argument values.

- Daniel

[Andrew Schepler]

On Saturday, October 14, 2017 at 11:53:42 AM UTC-4, Daniel Krügler wrote:

equal_to doesn't meet the requirements imposed on Compare.

I disagree. Although [alg.sorting]/3 just says "comp shall induce a strict weak ordering on the values" without specifying what values, every functor input to a standard library algorithm has an implicit domain which is the set of all elements in all input iterator ranges and/or containers. We don't say std::less<double>{} is not a valid comparator because the existence of NaNs means you can have (x<0.0), (0.0<x), (x<1.0), (1.0<x) all false, meaning x is equivalent to both 0.0 and 1.0 which are not equivalent to each other. Instead, we say std::less<double>{} is a valid comparator if and only if std::isnan() would return false for every input element. Likewise, when the value type is a pointer type, a comparator doesn't need consistent or even well-defined behavior on null inputs if you can guarantee the elements will never be null pointer values.

So for two empty ranges, it is vacuously true that every functor induces a strict weak ordering on the domain, which is the empty set.

And for the original question, yes, std::lexicographical_compare(i, i, j, j, comp) must always return false. This follows from the normative Remark "If two sequences have the same number of elements and their corresponding elements (if any) are equivalent, then neither is lexicographically less than the other" and is then confirmed by the non-normative Note Bjorn quoted.