3410. lexicographical_compare_three_way is overspecified

Section: 26.8.12 [alg.three.way] Status: C++23 Submitter: Casey Carter Opened: 2020-02-27 Last modified: 2023-11-22

Priority: 3

View all other issues in [alg.three.way].

View all issues with C++23 status.

Discussion:

26.8.12 [alg.three.way]/2 specifies the effects of the lexicographical_compare_three_way algorithm via a large "equivalent to" codeblock. This codeblock specifies one more iterator comparison than necessary when the first input sequence is greater than the second, and two more than necessary in other cases. Requiring unnecessary work is the antithesis of C++.

[2020-03-29 Issue Prioritization]

Priority to 3 after reflector discussion.

[2021-05-19 Tim adds wording]

The wording below simply respecifies the algorithm in words. It seems pointless to try to optimize the code when the reading in the discussion above would entirely rule out things like memcmp optimizations for arbitrary contiguous iterators of bytes.

[2021-05-26; Reflector poll]

Set status to Tentatively Ready after five votes in favour during reflector poll.

[2021-06-07 Approved at June 2021 virtual plenary. Status changed: Voting → WP.]

Proposed resolution:

This wording is relative to N4885.

1. Modify 26.8.12 [alg.three.way] as indicated:

   template<class InputIterator1, class InputIterator2, class Cmp>
     constexpr auto
       lexicographical_compare_three_way(InputIterator1 b1, InputIterator1 e1,
                                         InputIterator2 b2, InputIterator2 e2,
                                         Cmp comp)
           -> decltype(comp(*b1, *b2));
   

   -?- Let N be min(e1 - b1, e2 - b2). Let E(n) be comp(*(b1 + n), *(b2 + n)).

   -1- Mandates: decltype(comp(*b1, *b2)) is a comparison category type.

   -?- Returns: E(i), where i is the smallest integer in [0, N) such that E(i) != 0 is true, or (e1 - b1) <=> (e2 - b2) if no such integer exists.

   -?- Complexity: At most N applications of comp.

   -2- Effects: Lexicographically compares two ranges and produces a result of the strongest applicable comparison category type. Equivalent to:

   for ( ; b1 != e1 && b2 != e2; void(++b1), void(++b2) )
     if (auto cmp = comp(*b1,*b2); cmp != 0)
         return cmp;
   return b1 != e1 ? strong_ordering::greater :
          b2 != e2 ? strong_ordering::less :
                     strong_ordering::equal;