[libc++][spaceship] Implement `operator<=>` for `vector`

[H-G-Hristov]

Summary

Implements part of P1614R2 "The Mothership has Landed"

Depends on D150188

[avogelsgesang]

update review link

[avogelsgesang]

rebase

[avogelsgesang]

improve test cases

[avogelsgesang]

needs to be adjusted to use the still-to-be-introduced test utilities from https://reviews.llvm.org/D132312 is done

[avogelsgesang]

add missing _LIBCPP_HIDE_FROM_ABI; use new test utility

[avogelsgesang]

Incorporate feedback received for similar review (list instead of vector; https://reviews.llvm.org/D132312)

[Mordante]

I had a quick look and no real comments. Can you fix the CI? I prefer to review the changes after a CI run.

[avogelsgesang]

Remove trailing whitespace (hopefully fixes CI)

[avogelsgesang]

Guard against ADL

[avogelsgesang]

still need to fix CI

[avogelsgesang]

@H-G-Hristov unfortunately, I don't know when I will find time to come back to this (and https://reviews.llvm.org/D132265). Feel free to take this over, if you are blocked by it

[H-G-Hristov]

In D132268#4275440, @avogelsgesang wrote:

@H-G-Hristov unfortunately, I don't know when I will find time to come back to this (and https://reviews.llvm.org/D132265). Feel free to take this over, if you are blocked by it

Thank you. I'll probably take them over then if you haven't finished them before I get the time.

[H-G-Hristov]

• [libc++][spaceship] Implement operator<=> for vector
• Fixes, incl. a change to lexicographical_compare_three_way to fix std::vector<bool> comparision operators support

[avogelsgesang]

libcxx/include/__algorithm/lexicographical_compare_three_way.h

112

I fear the actual issue is that `__three_way_comp_ref_type is currently buggy, and this change here only masks the issue.

I think the changes

   template <class _Tp, class _Up>
-  _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp& __x, _Up& __y) {
+  _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(const _Tp& __x, const _Up& __y) {

and

 // Pass the comparator by lvalue reference. Or in debug mode, using a
 // debugging wrapper that stores a reference.
-#  ifndef _LIBCPP_ENABLE_DEBUG_MODE
+#  ifdef _LIBCPP_ENABLE_DEBUG_MODE

are required. Not sure if sufficient, though

[H-G-Hristov]

Addressed review comments

[H-G-Hristov]

Trigger CI

[H-G-Hristov]

Rebased

[H-G-Hristov]

libcxx/include/__algorithm/lexicographical_compare_three_way.h

112

I think it's good now. Thank you for the review/tip. I don't understand what's going on with the CI at the moment but build the local build of the latest revision is fine.

[Mordante]

libcxx/docs/Status/SpaceshipProjects.csv

43

Did you validate this output looks good?

libcxx/test/std/containers/sequences/vector.bool/compare.three_way.pass.cpp

56

lx and tx are identical.

[H-G-Hristov]

• Rebased and addressed comments

[H-G-Hristov]

@Mordante Thank you for the review.

libcxx/docs/Status/SpaceshipProjects.csv

43

I use a VSCode extension to preview the tables. It looks good. Text is ordered on two separate lines. I can remove myself. I don't care about credit. I was curious how it can be done.
Is there another easy/more correct way to validate?

[H-G-Hristov]

• Addressed review comment

[philnik]

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

libcxx/include/__algorithm/three_way_comp_ref_type.h

31

Why is this change needed?

libcxx/test/std/containers/sequences/vector.bool/compare.three_way.pass.cpp

60

Maybe also test one empty and one with {false}?

[H-G-Hristov]

• Addressed comments

[H-G-Hristov]

@philnik Thank you for the review!

In D132268#4320495, @philnik wrote:

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(

libcxx/include/__algorithm/three_way_comp_ref_type.h

31

Without it the build fails.

[philnik]

In D132268#4321925, @H-G-Hristov wrote:

@philnik Thank you for the review!

In D132268#4320495, @philnik wrote:

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(

Ah OK. It's for iterators not returning an lvalue reference. In this case I think it would be better to forward the arguments, since that will definitely be correct.

[H-G-Hristov]

In D132268#4322098, @philnik wrote:

In D132268#4321925, @H-G-Hristov wrote:

@philnik Thank you for the review!

In D132268#4320495, @philnik wrote:

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(

Ah OK. It's for iterators not returning an lvalue reference. In this case I think it would be better to forward the arguments, since that will definitely be correct.

Sorry, I think I confused you. The actual problem is in the compare function, the last parameter of: :

note: candidate template ignored: substitution failure [with _InputIterator1 = std::__bit_iterator<std::vector<bool>, true, 0>, _InputIterator2 = std::__bit_iterator<std::vector<bool>, true, 0>, _Cmp = std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>]: no matching function for call to object of type 'std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>'
_LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path(

[philnik]

In D132268#4321925, @H-G-Hristov wrote:

@philnik Thank you for the review!

In D132268#4320495, @philnik wrote:

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(

Ah OK. It's for iterators not returning an lvalue reference. In this case I think it would be better to forward the arguments, since that will definitely be correct.

In D132268#4322470, @H-G-Hristov wrote:

In D132268#4322098, @philnik wrote:

In D132268#4321925, @H-G-Hristov wrote:

@philnik Thank you for the review!

In D132268#4320495, @philnik wrote:

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(

Ah OK. It's for iterators not returning an lvalue reference. In this case I think it would be better to forward the arguments, since that will definitely be correct.

Sorry, I think I confused you. The actual problem is in the compare function, the last parameter of: :

note: candidate template ignored: substitution failure [with _InputIterator1 = std::__bit_iterator<std::vector<bool>, true, 0>, _InputIterator2 = std::__bit_iterator<std::vector<bool>, true, 0>, _Cmp = std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>]: no matching function for call to object of type 'std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>'
_LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path(

In D132268#4322470, @H-G-Hristov wrote:

In D132268#4322098, @philnik wrote:

In D132268#4321925, @H-G-Hristov wrote:

@philnik Thank you for the review!

In D132268#4320495, @philnik wrote:

Looks basically good, but I'd like to understand the __debug_three_way_comp change before approving.

This change was proposed by avogelsang above actually, as without it the tests of vector<bool> build fails with:

lexicographical_compare_three_way.h:103:12: error: no matching function for call to '__lexicographical_compare_three_way_fast_path'

return std::__lexicographical_compare_three_way_fast_path(
       ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

vector:3296:17: note: in instantiation of function template specialization 'std::lexicographical_compare_three_way<std::bit_iterator<std::vector<bool>, true, 0>, std::bit_iterator<std::vector<bool>, true, 0>, std::strong_ordering (*)(const bool &, const bool &)>' requested here

return std::lexicographical_compare_three_way(

Ah OK. It's for iterators not returning an lvalue reference. In this case I think it would be better to forward the arguments, since that will definitely be correct.

Sorry, I think I confused you. The actual problem is in the compare function, the last parameter of: :

note: candidate template ignored: substitution failure [with _InputIterator1 = std::__bit_iterator<std::vector<bool>, true, 0>, _InputIterator2 = std::__bit_iterator<std::vector<bool>, true, 0>, _Cmp = std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>]: no matching function for call to object of type 'std::__debug_three_way_comp<std::strong_ordering (*)(const bool &, const bool &)>'
_LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path(

IIUC the problem is that __bit_iterator::operator* returns an object instead of a reference, which can't bind to an lvalue reference. If we use perfect forwarding that should fix the problem?

[H-G-Hristov]

• Use std::forward instead of move.
• Everything &&

[H-G-Hristov]

In D132268#4322525, @philnik wrote:

IIUC the problem is that __bit_iterator::operator* returns an object instead of a reference, which can't bind to an lvalue reference. If we use perfect forwarding that should fix the problem?

Could you please confirm if I understand correctly: I am supposed to perfectly forward the arguments to std::__lexicographical_compare_three_way_fast_path something like that:

return std::__lexicographical_compare_three_way_fast_path(
    std::forward<_InputIterator1>(__first1),
    std::forward<_InputIterator1>(__last1),
    std::forward<_InputIterator2>(__first2),
    std::forward<_InputIterator2>(__last2),
    __wrapped_comp_ref);

No, that still wasn't enough. The compilation fails without changes to LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp& __x, _Up& __y)'s signature. There was ways an issue with the 5th parameter (for the record I tried forward, move).
In the current revision I changed all references to rvalue references and applied forward to the iterators . I admit that I am not quite sure if that's the correct approach.

[philnik]

In D132268#4324117, @H-G-Hristov wrote:

In D132268#4322525, @philnik wrote:

IIUC the problem is that __bit_iterator::operator* returns an object instead of a reference, which can't bind to an lvalue reference. If we use perfect forwarding that should fix the problem?

Could you please confirm if I understand correctly: I am supposed to perfectly forward the arguments to std::__lexicographical_compare_three_way_fast_path something like that:

return std::__lexicographical_compare_three_way_fast_path(
    std::forward<_InputIterator1>(__first1),
    std::forward<_InputIterator1>(__last1),
    std::forward<_InputIterator2>(__first2),
    std::forward<_InputIterator2>(__last2),
    __wrapped_comp_ref);

No, that still wasn't enough. The compilation fails without changes to LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp& __x, _Up& __y)'s signature. There was ways an issue with the 5th parameter (for the record I tried forward, move).
In the current revision I changed all references to rvalue references and applied forward to the iterators . I admit that I am not quite sure if that's the correct approach.

I meant that you should perfect-forward the arguments in __debug_three_way_comp::operator(). i.e. std::forward the arguments to __comp_. The std::forwards you are currently doing in the calls are essentially just std::moves, since the arguments are prvalue types.

[Mordante]

A few more comments. I want to have a short look at the final version especially the answers to some of @philnik's remarks.

libcxx/include/__algorithm/lexicographical_compare_three_way.h

37

I think it would be better to have the changes to this file and the changes directly related to it in a separate commit.

If you feel strongly about not doing that, then mention these changes in the commit message.

libcxx/test/std/containers/sequences/vector.bool/compare.three_way.pass.cpp

12

The synopsis should use the synopsis for the vector<bool> specialization.

libcxx/test/support/test_container_comparisons.h

65

All changes in this file are just NFC cleanups right? If so I prefer to remove them from this patch and commit them separately.
(That commit doesn't need a review.)

[H-G-Hristov]

• Addressed comments

[H-G-Hristov]

@Mordante Thank you for the suggestions!

libcxx/include/__algorithm/lexicographical_compare_three_way.h

37

I agree. I'll do that.

libcxx/test/std/containers/sequences/vector.bool/compare.three_way.pass.cpp

12

To my understanding there isn't a synopsis specific to vector<bool> for operator<=>. I added // class vector<bool>. I hope that's what you mean.

[H-G-Hristov]

• Addressed comments

[H-G-Hristov]

Try to fix CI

[H-G-Hristov]

Rebased

[Mordante]

LGTM when the CI passes.

[H-G-Hristov]

Rebased

[H-G-Hristov]

Rebased

[H-G-Hristov]

In D132268#4361459, @Mordante wrote:

LGTM when the CI passes.

Thank you for the review. This one now passes but it still needs the stacked change to be completed/approved.

libcxx/docs/Status/SpaceshipProjects.csv

 | `[stacktrace.entry.cmp] <https://wg21.link/stacktrace.entry.cmp>`_,| `stacktrace_entry <https://reviews.llvm.org/D123228>`_,None,Nikolas Klauser,|In Progress|
 | `[stacktrace.basic.cmp] <https://wg21.link/stacktrace.basic.cmp>`_,| `basic_stacktrace <https://reviews.llvm.org/D123228>`_,[alg.three.way],Nikolas Klauser,|In Progress|
 | `[string.cmp] <https://wg21.link/string.cmp>`_,| `basic_string <https://reviews.llvm.org/D131421>`_,None,Mark de Wever,|Complete|
 | `[string.view.comparison] <https://wg21.link/string.view.comparison>`_,| `basic_string_view <https://reviews.llvm.org/D130295>`_,None,Mark de Wever,|Complete|
 | `[array.syn] <https://wg21.link/array.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `array <https://reviews.llvm.org/D132265>`_,[expos.only.func],Adrian Vogelsgesang,|In Progress|
 | `[deque.syn] <https://wg21.link/deque.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `deque <https://reviews.llvm.org/D144821>`_,[expos.only.func],Hristo Hristov,|Complete|
 | `[forward.list.syn] <https://wg21.link/forward.list.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `forward_list <https://reviews.llvm.org/D145172>`_,[expos.only.func],Hristo Hristov,|Complete|
 | `[list.syn] <https://wg21.link/list.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `list <https://reviews.llvm.org/D132312>`_,[expos.only.func],Adrian Vogelsgesang,|Complete|
-| `[vector.syn] <https://wg21.link/vector.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `vector <https://reviews.llvm.org/D132268>`_,[expos.only.func],Adrian Vogelsgesang,|In Progress|
+| `[vector.syn] <https://wg21.link/vector.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),| `vector <https://reviews.llvm.org/D132268>`_,[expos.only.func],"| Adrian Vogelsgesang
+| Hristo Hristov",|Complete|
 | `[associative.map.syn] <https://wg21.link/associative.map.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),"| `map <https://reviews.llvm.org/D145976>`_
 | `multimap <https://reviews.llvm.org/D145976>`_",[expos.only.func],Hristo Hristov,|Complete|
 | `[associative.set.syn] <https://wg21.link/associative.set.syn>`_ (`general <https://wg21.link/container.opt.reqmts>`_),"| multiset
 | set",[expos.only.func],Hristo Hristov,|In Progress|
 | `[queue.ops] <https://wg21.link/queue.ops>`_,| `queue <https://reviews.llvm.org/D146066>`_,None,Hristo Hristov,|In Progress|
 | `[stack.ops] <https://wg21.link/stack.ops>`_,| `stack <https://reviews.llvm.org/D146094>`_,None,Hristo Hristov,|In Progress|
 | `[reverse.iter.cmp] <https://wg21.link/reverse.iter.cmp>`_,| `reverse_iterator <https://reviews.llvm.org/D113695>`_,None,Mikhail Maltsev,|Complete|
 | `[move.iter.op.comp] <https://wg21.link/move.iter.op.comp>`_,| `move_iterator <https://reviews.llvm.org/D117656>`_,None,Arthur O'Dwyer,|Complete|

libcxx/include/__algorithm/lexicographical_compare_three_way.h

 #include <__algorithm/three_way_comp_ref_type.h>
 #include <__compare/compare_three_way.h>
 #include <__compare/ordering.h>
 #include <__concepts/arithmetic.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/common_type.h>
 #include <__type_traits/is_copy_constructible.h>
+#include <__utility/forward.h>
 #include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 #if _LIBCPP_STD_VER >= 20
 
 // Fast path for random access iterators which computes the number of loop iterations up-front and
 // then skips the iterator comparisons inside the loop.
 template <class _InputIterator1, class _InputIterator2, class _Cmp>
 _LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path(
-    _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp)
+    _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp&& __comp)
     -> decltype(__comp(*__first1, *__first2)) {
   static_assert(
       signed_integral<__iter_diff_t<_InputIterator1>>, "Using a non-integral difference_type is undefined behavior.");
   static_assert(
       signed_integral<__iter_diff_t<_InputIterator2>>, "Using a non-integral difference_type is undefined behavior.");
 
   using _Len1   = __iter_diff_t<_InputIterator1>;
   using _Len2   = __iter_diff_t<_InputIterator2>;
_LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path(
   }
 
   return __len1 <=> __len2;
 }
 
 // Unoptimized implementation which compares the iterators against the end in every loop iteration
 template <class _InputIterator1, class _InputIterator2, class _Cmp>
 _LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_slow_path(
-    _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp)
+    _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp&& __comp)
     -> decltype(__comp(*__first1, *__first2)) {
   while (true) {
     bool __exhausted1 = __first1 == __last1;
     bool __exhausted2 = __first2 == __last2;
 
     if (__exhausted1 || __exhausted2) {
       if (!__exhausted1)
         return strong_ordering::greater;
_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way(
   static_assert(__comparison_category<decltype(__comp(*__first1, *__first2))>,
                 "The comparator passed to lexicographical_compare_three_way must return a comparison category type.");
   static_assert(std::is_copy_constructible_v<_InputIterator1>, "Iterators must be copy constructible.");
   static_assert(std::is_copy_constructible_v<_InputIterator2>, "Iterators must be copy constructible.");
   __three_way_comp_ref_type<_Cmp> __wrapped_comp_ref(__comp);
   if constexpr (__is_cpp17_random_access_iterator<_InputIterator1>::value &&
                 __is_cpp17_random_access_iterator<_InputIterator2>::value) {
     return std::__lexicographical_compare_three_way_fast_path(
-        std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref);
+        std::forward<_InputIterator1>(__first1),
+        std::forward<_InputIterator1>(__last1),
+        std::forward<_InputIterator2>(__first2),
+        std::forward<_InputIterator2>(__last2),
+        std::move(__wrapped_comp_ref));
   } else {
     // Unoptimized implementation which compares the iterators against the end in every loop iteration
     return std::__lexicographical_compare_three_way_slow_path(
-        std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref);
+        std::forward<_InputIterator1>(__first1),
+        std::forward<_InputIterator1>(__last1),
+        std::forward<_InputIterator2>(__first2),
+        std::forward<_InputIterator2>(__last2),
+        std::move(__wrapped_comp_ref));
   }
 }
 
 template <class _InputIterator1, class _InputIterator2>
 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way(
     _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {
   return std::lexicographical_compare_three_way(
-      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::compare_three_way());
+      std::forward<_InputIterator1>(__first1),
+      std::forward<_InputIterator1>(__last1),
+      std::forward<_InputIterator2>(__first2),
+      std::forward<_InputIterator2>(__last2),
+      std::compare_three_way());
 }
 
 #endif // _LIBCPP_STD_VER >= 20
 
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H

libcxx/include/__algorithm/three_way_comp_ref_type.h

 #if _LIBCPP_STD_VER >= 20
 
 template <class _Comp>
 struct __debug_three_way_comp {
   _Comp& __comp_;
   _LIBCPP_HIDE_FROM_ABI constexpr __debug_three_way_comp(_Comp& __c) : __comp_(__c) {}
 
   template <class _Tp, class _Up>
-  _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp& __x, _Up& __y) {
+  _LIBCPP_HIDE_FROM_ABI constexpr auto operator()(_Tp&& __x, _Up&& __y) {
     auto __r = __comp_(__x, __y);
     __do_compare_assert(0, __y, __x, __r);
     return __r;
   }
 
   template <class _LHS, class _RHS, class _Order>
   _LIBCPP_HIDE_FROM_ABI constexpr inline void __do_compare_assert(int, _LHS& __l, _RHS& __r, _Order __o)
     requires __comparison_category<decltype(std::declval<_Comp&>()(std::declval<_LHS&>(), std::declval<_RHS&>()))>

libcxx/include/vector

 };
 
 template <class InputIterator, class Allocator = allocator<typename iterator_traits<InputIterator>::value_type>>
    vector(InputIterator, InputIterator, Allocator = Allocator())
    -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17
 
 template <class Allocator> struct hash<std::vector<bool, Allocator>>;
 
-template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
-template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
-template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
-template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);
-template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
-template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);
+template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // constexpr since C++20
+template <class T, class Allocator> bool operator!=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
+template <class T, class Allocator> bool operator< (const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
+template <class T, class Allocator> bool operator> (const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
+template <class T, class Allocator> bool operator>=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
+template <class T, class Allocator> bool operator<=(const vector<T,Allocator>& x, const vector<T,Allocator>& y);   // removed in C++20
+template <class T, class Allocator> constexpr
+  constexpr synth-three-way-result<T> operator<=>(const vector<T, Allocator>& x,
+                                                  const vector<T, Allocator>& y);                                  // since C++20
 
 template <class T, class Allocator>
 void swap(vector<T,Allocator>& x, vector<T,Allocator>& y)
     noexcept(noexcept(x.swap(y)));
 
 template <class T, class Allocator, class U>
 typename vector<T, Allocator>::size_type
-erase(vector<T, Allocator>& c, const U& value);       // C++20
+erase(vector<T, Allocator>& c, const U& value);       // since C++20
 template <class T, class Allocator, class Predicate>
 typename vector<T, Allocator>::size_type
-erase_if(vector<T, Allocator>& c, Predicate pred);    // C++20
+erase_if(vector<T, Allocator>& c, Predicate pred);    // since C++20
 
 
 template<class T>
  inline constexpr bool is-vector-bool-reference = see below;        // exposition only, since C++23
 
 template<class T, class charT> requires is-vector-bool-reference<T> // Since C++23
  struct formatter<T, charT>;
 
 }  // std
 
 */
 
 #include <__algorithm/copy.h>
 #include <__algorithm/equal.h>
 #include <__algorithm/fill_n.h>
 #include <__algorithm/lexicographical_compare.h>
+#include <__algorithm/lexicographical_compare_three_way.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_if.h>
 #include <__algorithm/rotate.h>
 #include <__algorithm/unwrap_iter.h>
 #include <__assert> // all public C++ headers provide the assertion handler
 #include <__bit_reference>
 #include <__concepts/same_as.h>
 #include <__config>

 inline _LIBCPP_HIDE_FROM_ABI
 bool
 operator==(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
 {
     const typename vector<_Tp, _Allocator>::size_type __sz = __x.size();
     return __sz == __y.size() && std::equal(__x.begin(), __x.end(), __y.begin());
 }
 
+#if _LIBCPP_STD_VER <= 17
+
 template <class _Tp, class _Allocator>
-_LIBCPP_CONSTEXPR_SINCE_CXX20
 inline _LIBCPP_HIDE_FROM_ABI
 bool
 operator!=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
 {
     return !(__x == __y);
 }
 
 template <class _Tp, class _Allocator>
-_LIBCPP_CONSTEXPR_SINCE_CXX20
 inline _LIBCPP_HIDE_FROM_ABI
 bool
 operator< (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
 {
     return std::lexicographical_compare(__x.begin(), __x.end(), __y.begin(), __y.end());
 }
 
 template <class _Tp, class _Allocator>
-_LIBCPP_CONSTEXPR_SINCE_CXX20
 inline _LIBCPP_HIDE_FROM_ABI
 bool
 operator> (const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
 {
     return __y < __x;
 }
 
 template <class _Tp, class _Allocator>
-_LIBCPP_CONSTEXPR_SINCE_CXX20
 inline _LIBCPP_HIDE_FROM_ABI
 bool
 operator>=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
 {
     return !(__x < __y);
 }
 
 template <class _Tp, class _Allocator>
-_LIBCPP_CONSTEXPR_SINCE_CXX20
 inline _LIBCPP_HIDE_FROM_ABI
 bool
 operator<=(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y)
 {
     return !(__y < __x);
 }
 
+#else // _LIBCPP_STD_VER <= 17
+
+template <class _Tp, class _Allocator>
+_LIBCPP_HIDE_FROM_ABI constexpr __synth_three_way_result<_Tp>
+operator<=>(const vector<_Tp, _Allocator>& __x, const vector<_Tp, _Allocator>& __y) {
+    return std::lexicographical_compare_three_way(
+        __x.begin(), __x.end(), __y.begin(), __y.end(), std::__synth_three_way<_Tp, _Tp>);
+}
+
+#endif // _LIBCPP_STD_VER <= 17
+
 template <class _Tp, class _Allocator>
 _LIBCPP_CONSTEXPR_SINCE_CXX20
 inline _LIBCPP_HIDE_FROM_ABI
 void
 swap(vector<_Tp, _Allocator>& __x, vector<_Tp, _Allocator>& __y)
     _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
 {
     __x.swap(__y);

libcxx/test/std/containers/sequences/vector.bool/compare.three_way.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <vector>
+
+// template<class T, class Allocator>
+//   constexpr synth-three-way-result<T> operator<=>(const vector<T, Allocator>& x,
+//                                                   const vector<T, Allocator>& y);
+
+#include <cassert>
+#include <vector>
+
+#include "test_comparisons.h"
+
+constexpr bool test_sequence_container_spaceship_vectorbool() {
+  // Empty containers
+  {
+    std::vector<bool> l1;
+    std::vector<bool> l2;
+    assert(testOrder(l1, l2, std::strong_ordering::equivalent));
+  }
+  // Identical contents
+  {
+    std::vector<bool> t1{true, true};
+    std::vector<bool> t2{true, true};
+    assert(testOrder(t1, t2, std::strong_ordering::equivalent));
+
+    std::vector<bool> f1{false, false};
+    std::vector<bool> f2{false, false};
+    assert(testOrder(f1, f2, std::strong_ordering::equivalent));
+  }
+  // Less, due to contained values
+  {
+    std::vector<bool> l1{true, false};
+    std::vector<bool> l2{true, true};
+    assert(testOrder(l1, l2, std::strong_ordering::less));
+  }
+  // Greater, due to contained values
+  {
+    std::vector<bool> l1{true, true};
+    std::vector<bool> l2{true, false};
+    assert(testOrder(l1, l2, std::strong_ordering::greater));
+  }
+  // Shorter list
+  {
+    std::vector<bool> l1{true};
+    std::vector<bool> l2{true, false};
+    assert(testOrder(l1, l2, std::strong_ordering::less));
+
+    std::vector<bool> t1{true};
+    std::vector<bool> t2{true, true};
+    assert(testOrder(t1, t2, std::strong_ordering::less));
+
+    std::vector<bool> f1{false};
+    std::vector<bool> f2{false, false};
+    assert(testOrder(f1, f2, std::strong_ordering::less));
+
+    std::vector<bool> e;
+    assert(testOrder(e, t1, std::strong_ordering::less));
+    assert(testOrder(e, f1, std::strong_ordering::less));
+  }
+  // Longer list
+  {
+    std::vector<bool> l1{true, false};
+    std::vector<bool> l2{true};
+    assert(testOrder(l1, l2, std::strong_ordering::greater));
+
+    std::vector<bool> t1{true, true};
+    std::vector<bool> t2{true};
+    assert(testOrder(t1, t2, std::strong_ordering::greater));
+
+    std::vector<bool> f1{false, false};
+    std::vector<bool> f2{false};
+    assert(testOrder(f1, f2, std::strong_ordering::greater));
+
+    std::vector<bool> e;
+    assert(testOrder(t2, e, std::strong_ordering::greater));
+    assert(testOrder(f2, e, std::strong_ordering::greater));
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  assert(test_sequence_container_spaceship_vectorbool());
+  static_assert(test_sequence_container_spaceship_vectorbool());
+  return 0;
+}

libcxx/test/std/containers/sequences/vector/compare.three_way.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+// UNSUPPORTED: c++03, c++11, c++14, c++17
+
+// <vector>
+
+// template<class T, class Allocator>
+//   constexpr synth-three-way-result<T> operator<=>(const vector<T, Allocator>& x,
+//                                                   const vector<T, Allocator>& y);
+
+#include <cassert>
+#include <vector>
+
+#include "test_container_comparisons.h"
+
+int main(int, char**) {
+  assert(test_sequence_container_spaceship<std::vector>());
+  static_assert(test_sequence_container_spaceship<std::vector>());
+  return 0;
+}

libcxx/test/support/test_container_comparisons.h

if constexpr (std::is_same_v<Elem, PartialOrder>) {
     Container<Elem> l2{1, 2};
     assert(testOrder(l1, l2, Order::unordered));
   }
 }
 
 // Tests the `operator<=>` on sequence containers
 template <template <typename...> typename Container>
 constexpr bool test_sequence_container_spaceship() {
+  // Thanks to SFINAE, the following is not a compiler error but returns `false`
+  struct NonComparable {};
+  static_assert(!std::three_way_comparable<Container<NonComparable>>);
+
   // The container should fulfil `std::three_way_comparable`
   static_assert(std::three_way_comparable<Container<int>>);
 
   // Test different comparison categories
   test_sequence_container_spaceship_with_type<Container, int, std::strong_ordering>();
   test_sequence_container_spaceship_with_type<Container, StrongOrder, std::strong_ordering>();
   test_sequence_container_spaceship_with_type<Container, WeakOrder, std::weak_ordering>();
   test_sequence_container_spaceship_with_type<Container, PartialOrder, std::partial_ordering>();
 
   // `LessAndEqComp` does not have `operator<=>`. ordering is sythesized based on `operator<`
   test_sequence_container_spaceship_with_type<Container, LessAndEqComp, std::weak_ordering>();
 
-  // Thanks to SFINAE, the following is not a compiler error but returns `false`
-  struct NonComparable {};
-  static_assert(!std::three_way_comparable<Container<NonComparable>>);
-
   return true;
 }
 
 // Implementation detail of `test_ordered_map_container_spaceship`
 template <template <typename...> typename Container, typename Key, typename Val, typename Order>
 constexpr void test_ordered_map_container_spaceship_with_type() {
   // Empty containers
   {
if constexpr (std::is_same_v<Val, PartialOrder>) {
     assert(testOrder(l1, l2, Order::unordered));
   }
 
   // Identical contents
   {
     Container<Key, Val> l1{{1, 1}, {2, 1}, {2, 2}};
     Container<Key, Val> l2{{1, 1}, {2, 1}, {2, 2}};
     assert(testOrder(l1, l2, Order::equivalent));
+
     Container<Key, Val> l3{{1, 1}, {2, 1}, {2, 2}};
     Container<Key, Val> l4{{2, 1}, {2, 2}, {1, 1}};
     assert(testOrder(l3, l4, Order::equivalent));
   }
   // Less, due to contained values
   {
     Container<Key, Val> l1{{1, 1}, {2, 1}, {2, 1}};
     Container<Key, Val> l2{{1, 1}, {2, 2}, {2, 2}};
     assert(testOrder(l1, l2, Order::less));
+
     Container<Key, Val> l3{{1, 1}, {2, 1}, {2, 1}};
     Container<Key, Val> l4{{2, 2}, {2, 2}, {1, 1}};
     assert(testOrder(l3, l4, Order::less));
   }
   // Greater, due to contained values
   {
     Container<Key, Val> l1{{1, 1}, {2, 3}, {2, 3}};
     Container<Key, Val> l2{{1, 1}, {2, 2}, {2, 2}};
     assert(testOrder(l1, l2, Order::greater));
+
     Container<Key, Val> l3{{1, 1}, {2, 3}, {2, 3}};
     Container<Key, Val> l4{{2, 2}, {2, 2}, {1, 1}};
     assert(testOrder(l3, l4, Order::greater));
   }
   // Shorter list
   {
     Container<Key, Val> l1{{1, 1}, {2, 2}};
     Container<Key, Val> l2{{1, 1}, {2, 2}, {2, 2}, {3, 1}};
     assert(testOrder(l1, l2, Order::less));
+
     Container<Key, Val> l3{{1, 1}, {2, 2}};
     Container<Key, Val> l4{{3, 1}, {2, 2}, {2, 2}, {1, 1}};
     assert(testOrder(l3, l4, Order::less));
   }
   // Longer list
   {
     Container<Key, Val> l1{{1, 2}, {2, 2}, {2, 2}, {3, 1}};
     Container<Key, Val> l2{{1, 1}, {2, 2}};
     assert(testOrder(l1, l2, Order::greater));
+
     Container<Key, Val> l3{{1, 2}, {2, 2}, {2, 2}, {3, 1}};
     Container<Key, Val> l4{{2, 2}, {1, 1}};
     assert(testOrder(l3, l4, Order::greater));
   }
   // Unordered
   if constexpr (std::is_same_v<Val, PartialOrder>) {
     Container<Key, Val> l1{{1, 1}, {2, std::numeric_limits<int>::min()}, {2, 3}};
     Container<Key, Val> l2{{1, 1}, {2, 2}, {2, 3}};
     assert(testOrder(l1, l2, Order::unordered));
+
     Container<Key, Val> l3{{1, 1}, {2, std::numeric_limits<int>::min()}, {2, 3}};
     Container<Key, Val> l4{{2, 3}, {2, 2}, {1, 1}};
     assert(testOrder(l3, l4, Order::unordered));
   }
 }
 
 // Tests the `operator<=>` on ordered containers
 template <template <typename...> typename Container>
 constexpr bool test_ordered_map_container_spaceship() {
+  // Thanks to SFINAE, the following is not a compiler error but returns `false`
+  struct NonComparable {};
+  static_assert(!std::three_way_comparable<Container<int, NonComparable>>);
+
   // The container should fulfil `std::three_way_comparable`
   static_assert(std::three_way_comparable<Container<int, int>>);
 
   // Test different comparison categories
   test_ordered_map_container_spaceship_with_type<Container, int, int, std::strong_ordering>();
   test_ordered_map_container_spaceship_with_type<Container, int, StrongOrder, std::strong_ordering>();
   test_ordered_map_container_spaceship_with_type<Container, int, WeakOrder, std::weak_ordering>();
   test_ordered_map_container_spaceship_with_type<Container, int, PartialOrder, std::partial_ordering>();
 
   // `LessAndEqComp` does not have `operator<=>`. ordering is sythesized based on `operator<`
   test_ordered_map_container_spaceship_with_type<Container, int, LessAndEqComp, std::weak_ordering>();
 
-  // Thanks to SFINAE, the following is not a compiler error but returns `false`
-  struct NonComparable {};
-  static_assert(!std::three_way_comparable<Container<int, NonComparable>>);
-
   return true;
 }
 
 #endif