Section: 27.8.12 [alg.three.way] Status: WP Submitter: Casey Carter Opened: 2020-02-27 Last modified: 2021-06-07 16:58:04 UTC
View all other issues in [alg.three.way].
View all issues with WP status.
27.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.]
This wording is relative to N4885.
Modify 27.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));
-1- Mandates: decltype(comp(*b1, *b2)) is a comparison category type.
-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;