libstdc++: Define std::lexicographical_compare_three_way for C++20

Message ID 20191205124640.GA1500787@redhat.com
State New
Headers show
Series
  • libstdc++: Define std::lexicographical_compare_three_way for C++20
Related show

Commit Message

Jonathan Wakely Dec. 5, 2019, 12:46 p.m.
* include/bits/stl_algobase.h (lexicographical_compare_three_way):
	Define for C++20.
	* testsuite/25_algorithms/lexicographical_compare_three_way/1.cc: New
	test.
	* testsuite/25_algorithms/lexicographical_compare_three_way/
	constexpr.cc: New test.

Tested powerpc64le-linux, committed to trunk.
commit 5012548fd62526fdf5e04aeacee2b127efbac0e0
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Thu Dec 5 12:23:53 2019 +0000

    libstdc++: Define std::lexicographical_compare_three_way for C++20
    
            * include/bits/stl_algobase.h (lexicographical_compare_three_way):
            Define for C++20.
            * testsuite/25_algorithms/lexicographical_compare_three_way/1.cc: New
            test.
            * testsuite/25_algorithms/lexicographical_compare_three_way/
            constexpr.cc: New test.

Comments

Stephan Bergmann Dec. 29, 2019, 11:07 a.m. | #1
On 05/12/2019 13:46, Jonathan Wakely wrote:
> commit 5012548fd62526fdf5e04aeacee2b127efbac0e0

> Author: Jonathan Wakely <jwakely@redhat.com>

> Date:   Thu Dec 5 12:23:53 2019 +0000

> 

>     libstdc++: Define std::lexicographical_compare_three_way for C++20

>     

>             * include/bits/stl_algobase.h (lexicographical_compare_three_way):

>             Define for C++20.

>             * testsuite/25_algorithms/lexicographical_compare_three_way/1.cc: New

>             test.

>             * testsuite/25_algorithms/lexicographical_compare_three_way/

>             constexpr.cc: New test.

> 

> diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h

> index 98d324827ed..a2fd306e6d0 100644

> --- a/libstdc++-v3/include/bits/stl_algobase.h

> +++ b/libstdc++-v3/include/bits/stl_algobase.h

[...]
> @@ -1456,6 +1459,104 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO

>  	 __gnu_cxx::__ops::__iter_comp_iter(__comp));

>      }

>  

> +#if __cpp_lib_three_way_comparison

> +#if __cpp_lib_concepts

> +  // Iter points to a contiguous range of unsigned narrow character type

> +  // or std::byte, suitable for comparison by memcmp.

> +  template<typename _Iter>

> +    concept __is_byte_iter = contiguous_iterator<_Iter>

> +      && __is_byte<iter_value_t<_Iter>>::__value != 0

> +      && !__gnu_cxx::__numeric_traits<iter_value_t<_Iter>>::__is_signed;

> +

> +  // Return a struct with two members, initialized to the smaller of x and y

> +  // (or x if they compare equal) and the result of the comparison x <=> y.

> +  template<typename _Tp>

> +    constexpr auto

> +    __min_cmp(_Tp __x, _Tp __y)

> +    {

> +      struct _Res {

> +	_Tp _M_min;

> +	decltype(__x <=> __y) _M_cmp;

> +      };

> +      auto __c = __x <=> __y;

> +      if (__c > 0)

> +	return _Res{__y, __c};

> +      return _Res{__x, __c};

> +    }

> +#endif

[...]
> +

> +  template<typename _InputIter1, typename _InputIter2>

> +    constexpr auto

> +    lexicographical_compare_three_way(_InputIter1 __first1,

> +				      _InputIter1 __last1,

> +				      _InputIter2 __first2,

> +				      _InputIter2 __last2)

> +    {

> +      return std::lexicographical_compare_three_way(__first1, __last1,

> +						    __first2, __last2,

> +						    compare_three_way{});


FYI, the above fails with -std=c++2a and recent Clang trunk after 
<https://github.com/llvm/llvm-project/commit/bc633a42dd409dbeb456263e3388b8caa4680aa0> 
"Mark the major papers for C++20 consistent comparisons as 'done', and 
start publishing the corresponding feature-test macro":  Clang now 
defines __cpp_impl_three_way_comparison (so 
libstdc++-v3/include/std/version defines __cpp_lib_three_way_comparison) 
but still doesn't define __cpp_lib_concepts, so 
libstdc++-v3/libsupc++/compare doesn't define compare_three_way.

I locally managed that for now with extending the surrounding

  #if __cpp_lib_three_way_comparison

with

  && __cpp_lib_concepts

> +    }

> +#endif // three_way_comparison
Jonathan Wakely Jan. 3, 2020, 2:54 p.m. | #2
On 29/12/19 12:07 +0100, Stephan Bergmann wrote:
>On 05/12/2019 13:46, Jonathan Wakely wrote:

>>commit 5012548fd62526fdf5e04aeacee2b127efbac0e0

>>Author: Jonathan Wakely <jwakely@redhat.com>

>>Date:   Thu Dec 5 12:23:53 2019 +0000

>>

>>    libstdc++: Define std::lexicographical_compare_three_way for C++20

>>            * include/bits/stl_algobase.h (lexicographical_compare_three_way):

>>            Define for C++20.

>>            * testsuite/25_algorithms/lexicographical_compare_three_way/1.cc: New

>>            test.

>>            * testsuite/25_algorithms/lexicographical_compare_three_way/

>>            constexpr.cc: New test.

>>

>>diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h

>>index 98d324827ed..a2fd306e6d0 100644

>>--- a/libstdc++-v3/include/bits/stl_algobase.h

>>+++ b/libstdc++-v3/include/bits/stl_algobase.h

>[...]

>>@@ -1456,6 +1459,104 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO

>> 	 __gnu_cxx::__ops::__iter_comp_iter(__comp));

>>     }

>>+#if __cpp_lib_three_way_comparison

>>+#if __cpp_lib_concepts

>>+  // Iter points to a contiguous range of unsigned narrow character type

>>+  // or std::byte, suitable for comparison by memcmp.

>>+  template<typename _Iter>

>>+    concept __is_byte_iter = contiguous_iterator<_Iter>

>>+      && __is_byte<iter_value_t<_Iter>>::__value != 0

>>+      && !__gnu_cxx::__numeric_traits<iter_value_t<_Iter>>::__is_signed;

>>+

>>+  // Return a struct with two members, initialized to the smaller of x and y

>>+  // (or x if they compare equal) and the result of the comparison x <=> y.

>>+  template<typename _Tp>

>>+    constexpr auto

>>+    __min_cmp(_Tp __x, _Tp __y)

>>+    {

>>+      struct _Res {

>>+	_Tp _M_min;

>>+	decltype(__x <=> __y) _M_cmp;

>>+      };

>>+      auto __c = __x <=> __y;

>>+      if (__c > 0)

>>+	return _Res{__y, __c};

>>+      return _Res{__x, __c};

>>+    }

>>+#endif

>[...]

>>+

>>+  template<typename _InputIter1, typename _InputIter2>

>>+    constexpr auto

>>+    lexicographical_compare_three_way(_InputIter1 __first1,

>>+				      _InputIter1 __last1,

>>+				      _InputIter2 __first2,

>>+				      _InputIter2 __last2)

>>+    {

>>+      return std::lexicographical_compare_three_way(__first1, __last1,

>>+						    __first2, __last2,

>>+						    compare_three_way{});

>

>FYI, the above fails with -std=c++2a and recent Clang trunk after <https://github.com/llvm/llvm-project/commit/bc633a42dd409dbeb456263e3388b8caa4680aa0> 

>"Mark the major papers for C++20 consistent comparisons as 'done', and 

>start publishing the corresponding feature-test macro":  Clang now 

>defines __cpp_impl_three_way_comparison (so 

>libstdc++-v3/include/std/version defines 

>__cpp_lib_three_way_comparison) but still doesn't define 

>__cpp_lib_concepts, so libstdc++-v3/libsupc++/compare doesn't define 

>compare_three_way.

>

>I locally managed that for now with extending the surrounding

>

> #if __cpp_lib_three_way_comparison

>

>with

>

> && __cpp_lib_concepts

>

>>+    }

>>+#endif // three_way_comparison


Should be fixed at r279861 on trunk (also attached). This leaves the
five-argument overload defined for Clang, just not the four-argument
one that uses std::compare_three_way.

We could define that overload unconditionally and do something like
this, but I prefer to just omit it rather than define it badly:

       return std::lexicographical_compare_three_way(__first1, __last1,
						    __first2, __last2,
#if __cpp_lib_concepts
						    compare_three_way{}
#else
						    [](auto&& __l, auto&& __r)
						    { return __l <=> __r; }
#endif // concepts
						    );
commit 9b51d80f860841ea80be6c420970ec8b881c0f9e
Author: redi <redi@138bc75d-0d04-0410-961f-82ee72b054a4>
Date:   Fri Jan 3 14:44:39 2020 +0000

    libstdc++: Only use std::compare_three_way when concepts are supported
    
    Clang now supports three-way comparisons. That causes both overloads of
    std::lexicographical_compare_three_way to be defined, but the second one
    uses std::compare_three_way which depends on concepts. Clang does not
    yet support concepts, so the second overload should also depend on
    __cpp_lib_concepts.
    
            * include/bits/stl_algobase.h (lexicographical_compare_three_way):
            Only define four-argument overload when __cpp_lib_concepts is defined.
    
    git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@279861 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 13de6aecc6c..76c323ab21b 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1751,6 +1751,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	: __first2 != __last2 ? strong_ordering::less : strong_ordering::equal;
     }
 
+#if __cpp_lib_concepts
   template<typename _InputIter1, typename _InputIter2>
     constexpr auto
     lexicographical_compare_three_way(_InputIter1 __first1,
@@ -1762,6 +1763,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 						    __first2, __last2,
 						    compare_three_way{});
     }
+#endif // concepts
 #endif // three_way_comparison
 
   template<typename _InputIterator1, typename _InputIterator2,
Jonathan Wakely Jan. 3, 2020, 3:03 p.m. | #3
On 03/01/20 14:54 +0000, Jonathan Wakely wrote:
>On 29/12/19 12:07 +0100, Stephan Bergmann wrote:

>>FYI, the above fails with -std=c++2a and recent Clang trunk after <https://github.com/llvm/llvm-project/commit/bc633a42dd409dbeb456263e3388b8caa4680aa0> 

>>"Mark the major papers for C++20 consistent comparisons as 'done', 

>>and start publishing the corresponding feature-test macro":  Clang 

>>now defines __cpp_impl_three_way_comparison (so 

>>libstdc++-v3/include/std/version defines 

>>__cpp_lib_three_way_comparison) but still doesn't define 

>>__cpp_lib_concepts, so libstdc++-v3/libsupc++/compare doesn't define 

>>compare_three_way.

>>

>>I locally managed that for now with extending the surrounding

>>

>>#if __cpp_lib_three_way_comparison

>>

>>with

>>

>>&& __cpp_lib_concepts

>>

>>>+    }

>>>+#endif // three_way_comparison

>

>Should be fixed at r279861 on trunk (also attached). This leaves the

>five-argument overload defined for Clang, just not the four-argument

>one that uses std::compare_three_way.

>

>We could define that overload unconditionally and do something like

>this, but I prefer to just omit it rather than define it badly:

>

>      return std::lexicographical_compare_three_way(__first1, __last1,

>						    __first2, __last2,

>#if __cpp_lib_concepts

>						    compare_three_way{}

>#else

>						    [](auto&& __l, auto&& __r)

>						    { return __l <=> __r; }

>#endif // concepts

>						    );


After writing that, I realised that a better approach might be:

--- a/libstdc++-v3/libsupc++/compare
+++ b/libstdc++-v3/libsupc++/compare
@@ -40,7 +40,9 @@

  namespace std
  {
-#define __cpp_lib_three_way_comparison 201711L
+#if __cpp_lib_concepts
+# define __cpp_lib_three_way_comparison 201711L
+#endif

    // [cmp.categories], comparison category types


i.e. don't pretend the library supports three-way comparison if that
support is incomplete. That will still fix the Clang problem because
if that macro isn't defined then we don't define either overload of
std::lexicographical_compare_three_way.

That seems cleaner to me. Anybody disagree?
Jonathan Wakely Jan. 6, 2020, 12:05 p.m. | #4
On 03/01/20 15:03 +0000, Jonathan Wakely wrote:
>On 03/01/20 14:54 +0000, Jonathan Wakely wrote:

>>On 29/12/19 12:07 +0100, Stephan Bergmann wrote:

>>>FYI, the above fails with -std=c++2a and recent Clang trunk after <https://github.com/llvm/llvm-project/commit/bc633a42dd409dbeb456263e3388b8caa4680aa0> 

>>>"Mark the major papers for C++20 consistent comparisons as 'done', 

>>>and start publishing the corresponding feature-test macro":  Clang 

>>>now defines __cpp_impl_three_way_comparison (so 

>>>libstdc++-v3/include/std/version defines 

>>>__cpp_lib_three_way_comparison) but still doesn't define 

>>>__cpp_lib_concepts, so libstdc++-v3/libsupc++/compare doesn't 

>>>define compare_three_way.

>>>

>>>I locally managed that for now with extending the surrounding

>>>

>>>#if __cpp_lib_three_way_comparison

>>>

>>>with

>>>

>>>&& __cpp_lib_concepts

>>>

>>>>+    }

>>>>+#endif // three_way_comparison

>>

>>Should be fixed at r279861 on trunk (also attached). This leaves the

>>five-argument overload defined for Clang, just not the four-argument

>>one that uses std::compare_three_way.

>>

>>We could define that overload unconditionally and do something like

>>this, but I prefer to just omit it rather than define it badly:

>>

>>     return std::lexicographical_compare_three_way(__first1, __last1,

>>						    __first2, __last2,

>>#if __cpp_lib_concepts

>>						    compare_three_way{}

>>#else

>>						    [](auto&& __l, auto&& __r)

>>						    { return __l <=> __r; }

>>#endif // concepts

>>						    );

>

>After writing that, I realised that a better approach might be:

>

>--- a/libstdc++-v3/libsupc++/compare

>+++ b/libstdc++-v3/libsupc++/compare

>@@ -40,7 +40,9 @@

>

> namespace std

> {

>-#define __cpp_lib_three_way_comparison 201711L

>+#if __cpp_lib_concepts

>+# define __cpp_lib_three_way_comparison 201711L

>+#endif

>

>   // [cmp.categories], comparison category types

>

>

>i.e. don't pretend the library supports three-way comparison if that

>support is incomplete. That will still fix the Clang problem because

>if that macro isn't defined then we don't define either overload of

>std::lexicographical_compare_three_way.

>

>That seems cleaner to me. Anybody disagree?



I'm committing this patch to do that.

Tested powerpc64le-linux, committed to trunk.
commit 6eb2a600ef9623cf6fbf2584df44fc5d71fd16f5
Author: Jonathan Wakely <jwakely@redhat.com>
Date:   Mon Jan 6 10:35:48 2020 +0000

    libstdc++: Define __cpp_lib_three_way_comparison conditionally
    
    The contents of the <compare> header are not complete unless concepts
    are supported, so the feature test macro should depend on the macro for
    concepts.
    
    As a result, the std::lexicographical_compare_three_way function will
    not be defined unless concepts are supported, so there is no need to
    check __cpp_lib_concepts before using concepts in those functions.
    
            * include/bits/stl_algobase.h (__is_byte_iter, __min_cmp)
            (lexicographical_compare_three_way): Do not depend on
            __cpp_lib_concepts.
            * include/std/version (__cpp_lib_three_way_comparison): Only define
            when __cpp_lib_concepts is defined.
            * libsupc++/compare (__cpp_lib_three_way_comparison): Likewise.

diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 76c323ab21b..dc922a0f3d2 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -1667,7 +1667,6 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
     }
 
 #if __cpp_lib_three_way_comparison
-#if __cpp_lib_concepts
   // Iter points to a contiguous range of unsigned narrow character type
   // or std::byte, suitable for comparison by memcmp.
   template<typename _Iter>
@@ -1690,7 +1689,6 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	return _Res{__y, __c};
       return _Res{__x, __c};
     }
-#endif
 
   /**
    *  @brief Performs dictionary comparison on ranges.
@@ -1718,7 +1716,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
       __glibcxx_requires_valid_range(__first1, __last1);
       __glibcxx_requires_valid_range(__first2, __last2);
 
-#if __cpp_lib_concepts && __cpp_lib_is_constant_evaluated
+#if __cpp_lib_is_constant_evaluated
       using _Cat = decltype(__comp(*__first1, *__first2));
       static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
 
@@ -1739,7 +1737,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 		  }
 		return __lencmp;
 	      }
-#endif // concepts && is_constant_evaluated
+#endif // is_constant_evaluated
       while (__first1 != __last1 && __first2 != __last2)
 	{
 	  if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
@@ -1751,7 +1749,6 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	: __first2 != __last2 ? strong_ordering::less : strong_ordering::equal;
     }
 
-#if __cpp_lib_concepts
   template<typename _InputIter1, typename _InputIter2>
     constexpr auto
     lexicographical_compare_three_way(_InputIter1 __first1,
@@ -1763,7 +1760,6 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
 						    __first2, __last2,
 						    compare_three_way{});
     }
-#endif // concepts
 #endif // three_way_comparison
 
   template<typename _InputIterator1, typename _InputIterator2,
diff --git a/libstdc++-v3/include/std/version b/libstdc++-v3/include/std/version
index ab8111468e4..81b9112e02a 100644
--- a/libstdc++-v3/include/std/version
+++ b/libstdc++-v3/include/std/version
@@ -191,7 +191,7 @@
 #define __cpp_lib_list_remove_return_type 201806L
 #define __cpp_lib_math_constants 201907L
 #define __cpp_lib_span 201902L
-#if __cpp_impl_three_way_comparison >= 201907L
+#if __cpp_impl_three_way_comparison >= 201907L && __cpp_lib_concepts
 # define __cpp_lib_three_way_comparison 201711L
 #endif
 #define __cpp_lib_to_array 201907L
diff --git a/libstdc++-v3/libsupc++/compare b/libstdc++-v3/libsupc++/compare
index 31969fb5c04..98a592cbb14 100644
--- a/libstdc++-v3/libsupc++/compare
+++ b/libstdc++-v3/libsupc++/compare
@@ -38,10 +38,12 @@
 
 #include <concepts>
 
+#if __cpp_lib_concepts
+# define __cpp_lib_three_way_comparison 201711L
+#endif
+
 namespace std
 {
-#define __cpp_lib_three_way_comparison 201711L
-
   // [cmp.categories], comparison category types
 
   namespace __cmp_cat

Patch

diff --git a/libstdc++-v3/include/bits/stl_algobase.h b/libstdc++-v3/include/bits/stl_algobase.h
index 98d324827ed..a2fd306e6d0 100644
--- a/libstdc++-v3/include/bits/stl_algobase.h
+++ b/libstdc++-v3/include/bits/stl_algobase.h
@@ -72,6 +72,9 @@ 
 #if __cplusplus >= 201103L
 # include <type_traits>
 #endif
+#if __cplusplus > 201703L
+# include <compare>
+#endif
 
 namespace std _GLIBCXX_VISIBILITY(default)
 {
@@ -1456,6 +1459,104 @@  _GLIBCXX_BEGIN_NAMESPACE_ALGO
 	 __gnu_cxx::__ops::__iter_comp_iter(__comp));
     }
 
+#if __cpp_lib_three_way_comparison
+#if __cpp_lib_concepts
+  // Iter points to a contiguous range of unsigned narrow character type
+  // or std::byte, suitable for comparison by memcmp.
+  template<typename _Iter>
+    concept __is_byte_iter = contiguous_iterator<_Iter>
+      && __is_byte<iter_value_t<_Iter>>::__value != 0
+      && !__gnu_cxx::__numeric_traits<iter_value_t<_Iter>>::__is_signed;
+
+  // Return a struct with two members, initialized to the smaller of x and y
+  // (or x if they compare equal) and the result of the comparison x <=> y.
+  template<typename _Tp>
+    constexpr auto
+    __min_cmp(_Tp __x, _Tp __y)
+    {
+      struct _Res {
+	_Tp _M_min;
+	decltype(__x <=> __y) _M_cmp;
+      };
+      auto __c = __x <=> __y;
+      if (__c > 0)
+	return _Res{__y, __c};
+      return _Res{__x, __c};
+    }
+#endif
+
+  /**
+   *  @brief Performs dictionary comparison on ranges.
+   *  @ingroup sorting_algorithms
+   *  @param  __first1  An input iterator.
+   *  @param  __last1   An input iterator.
+   *  @param  __first2  An input iterator.
+   *  @param  __last2   An input iterator.
+   *  @param  __comp  A @link comparison_functors comparison functor@endlink.
+   *  @return   The comparison category that `__comp(*__first1, *__first2)`
+   *		returns.
+  */
+  template<typename _InputIter1, typename _InputIter2, typename _Comp>
+    constexpr auto
+    lexicographical_compare_three_way(_InputIter1 __first1,
+				      _InputIter1 __last1,
+				      _InputIter2 __first2,
+				      _InputIter2 __last2,
+				      _Comp __comp)
+    -> decltype(__comp(*__first1, *__first2))
+    {
+      // concept requirements
+      __glibcxx_function_requires(_InputIteratorConcept<_InputIter1>)
+      __glibcxx_function_requires(_InputIteratorConcept<_InputIter2>)
+      __glibcxx_requires_valid_range(__first1, __last1);
+      __glibcxx_requires_valid_range(__first2, __last2);
+
+#if __cpp_lib_concepts && __cpp_lib_is_constant_evaluated
+      using _Cat = decltype(__comp(*__first1, *__first2));
+      static_assert(same_as<common_comparison_category_t<_Cat>, _Cat>);
+
+      if (!std::is_constant_evaluated())
+	if constexpr (same_as<_Comp, __detail::_Synth3way>
+		      || same_as<_Comp, compare_three_way>)
+	  if constexpr (__is_byte_iter<_InputIter1>)
+	    if constexpr (__is_byte_iter<_InputIter2>)
+	      {
+		const auto [__len, __lencmp]
+		  = std::__min_cmp(__last1 - __first1, __last2 - __first2);
+		if (__len)
+		  {
+		    const auto __c
+		      = __builtin_memcmp(&*__first1, &*__first2, __len) <=> 0;
+		    if (__c != 0)
+		      return __c;
+		  }
+		return __lencmp;
+	      }
+#endif // concepts && is_constant_evaluated
+      while (__first1 != __last1 && __first2 != __last2)
+	{
+	  if (auto __cmp = __comp(*__first1, *__first2); __cmp != 0)
+	    return __cmp;
+	  ++__first1;
+	  ++__first2;
+	}
+      return __first1 != __last1 ? strong_ordering::greater
+	: __first2 != __last2 ? strong_ordering::less : strong_ordering::equal;
+    }
+
+  template<typename _InputIter1, typename _InputIter2>
+    constexpr auto
+    lexicographical_compare_three_way(_InputIter1 __first1,
+				      _InputIter1 __last1,
+				      _InputIter2 __first2,
+				      _InputIter2 __last2)
+    {
+      return std::lexicographical_compare_three_way(__first1, __last1,
+						    __first2, __last2,
+						    compare_three_way{});
+    }
+#endif // three_way_comparison
+
   template<typename _InputIterator1, typename _InputIterator2,
 	   typename _BinaryPredicate>
     _GLIBCXX20_CONSTEXPR
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/1.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/1.cc
new file mode 100644
index 00000000000..b1e70e80de7
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/1.cc
@@ -0,0 +1,129 @@ 
+// Copyright (C) 2019 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do run { target c++2a } }
+
+#include <algorithm>
+#include <testsuite_hooks.h>
+#include <testsuite_iterators.h>
+
+// Lambda that calls lexicographical_compare_three_way on two ranges.
+// Arguments are passed by value intentionally, so that a copy of the range
+// is traversed and the original is not modified. Otherwise when the range
+// has input iterators the range will be consumed after the first comparison.
+auto lexicomp3 = [](auto r1, auto r2) {
+  return std::lexicographical_compare_three_way(r1.begin(), r1.end(),
+						r2.begin(), r2.end());
+};
+
+void
+test01()
+{
+  using __gnu_test::test_container;
+  using __gnu_test::input_iterator_wrapper;
+  using __gnu_test::forward_iterator_wrapper;
+  int arr1[] = { 0, 1, 2, 3, 4, 5, 6, 7 };
+  int arr2[] = { 0, 1, 2, 3, 4, 5, 6, 777 };
+
+  {
+    test_container<int, input_iterator_wrapper> c1(arr1);
+    test_container<int, input_iterator_wrapper> c2(arr2);
+    VERIFY( lexicomp3(c1, c1) == 0 );
+    VERIFY( lexicomp3(c1, c2) < 0 );
+    VERIFY( lexicomp3(c2, c1) > 0 );
+  }
+
+  {
+    test_container<int, input_iterator_wrapper> c1(arr1, arr1+6);
+    test_container<int, input_iterator_wrapper> c2(arr2, arr2+6);
+    VERIFY( lexicomp3(c1, c1) == 0 );
+    VERIFY( lexicomp3(c1, c2) == 0 );
+    VERIFY( lexicomp3(c2, c1) == 0 );
+  }
+
+  {
+    test_container<int, input_iterator_wrapper> c1(arr1);
+    test_container<int, input_iterator_wrapper> c2(arr2, arr2+7);
+    VERIFY( lexicomp3(c1, c1) == 0 );
+    VERIFY( lexicomp3(c1, c2) > 0 );
+    VERIFY( lexicomp3(c2, c1) < 0 );
+  }
+
+  {
+    test_container<int, input_iterator_wrapper> c1(arr1);
+    test_container<int, forward_iterator_wrapper> c2(arr2);
+    VERIFY( lexicomp3(c1, c1) == 0 );
+    VERIFY( lexicomp3(c1, c2) < 0 );
+    VERIFY( lexicomp3(c2, c1) > 0 );
+  }
+
+  {
+    test_container<int, input_iterator_wrapper> c1(arr1);
+    test_container<int, forward_iterator_wrapper> c2(arr2, arr2+7);
+    VERIFY( lexicomp3(c1, c1) == 0 );
+    VERIFY( lexicomp3(c2, c2) == 0 );
+    VERIFY( lexicomp3(c1, c2) > 0 );
+    VERIFY( lexicomp3(c2, c1) < 0 );
+  }
+
+  {
+    test_container<int, forward_iterator_wrapper> c1(arr1, arr1+7);
+    test_container<int, input_iterator_wrapper> c2(arr2);
+    VERIFY( lexicomp3(c1, c1) == 0 );
+    VERIFY( lexicomp3(c2, c2) == 0 );
+    VERIFY( lexicomp3(c1, c2) < 0 );
+    VERIFY( lexicomp3(c2, c1) > 0 );
+  }
+}
+
+void
+test02()
+{
+  using __gnu_test::test_container;
+  using __gnu_test::input_iterator_wrapper;
+  using __gnu_test::forward_iterator_wrapper;
+  std::array<unsigned char, 8> c1 = { 0, 1, 2, 3, 4, 5, 6, 7 };
+  std::array<unsigned char, 8> c2 = { 0, 1, 2, 3, 4, 5, 6, 77 };
+
+  VERIFY( lexicomp3(c1, c1) == 0 );
+  VERIFY( lexicomp3(c1, c2) < 0 );
+  VERIFY( lexicomp3(c2, c1) > 0 );
+
+  std::array<unsigned char, 7> c3 = { 0, 1, 2, 3, 4, 5, 6 };
+  VERIFY( lexicomp3(c3, c3) == 0 );
+  VERIFY( lexicomp3(c1, c3) > 0 );
+  VERIFY( lexicomp3(c3, c1) < 0 );
+}
+
+void
+test03()
+{
+  unsigned char a[2] = { 1, 2 };
+  unsigned char* p = nullptr;
+  // ensure memcmp not called with nullptr
+  VERIFY( std::lexicographical_compare_three_way(p, p, a, a+2) < 0 );
+  VERIFY( std::lexicographical_compare_three_way(a, a+2, p, p) > 0 );
+}
+
+int
+main()
+{
+  test01();
+  test02();
+  test03();
+}
diff --git a/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/constexpr.cc b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/constexpr.cc
new file mode 100644
index 00000000000..5d1e15cc4f3
--- /dev/null
+++ b/libstdc++-v3/testsuite/25_algorithms/lexicographical_compare_three_way/constexpr.cc
@@ -0,0 +1,65 @@ 
+// Copyright (C) 2019 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+// { dg-options "-std=gnu++2a" }
+// { dg-do compile { target c++2a } }
+
+#include <algorithm>
+
+constexpr bool
+test01(int i)
+{
+  int a1[] = { 0, 1, 2, 3, 4, 5, 6, i, 8 };
+  long a2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
+
+  return std::lexicographical_compare_three_way(a1, a1+0, a2, a2+0) == 0
+    && std::lexicographical_compare_three_way(a1, a1+9, a2, a2+9) == (i <=> 7)
+    && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+7) == 0
+    && std::lexicographical_compare_three_way(a1, a1+8, a2, a2+7) > 0
+    && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+8) < 0;
+}
+
+static_assert( test01(~7) );
+static_assert( test01(7) );
+static_assert( test01(8) );
+
+constexpr bool
+test02(unsigned char i)
+{
+  unsigned char a1[] = { 0, 1, 2, 3, 4, 5, 6, i, 8 };
+  unsigned char a2[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 };
+
+  return std::lexicographical_compare_three_way(a1, a1+0, a2, a2+0) == 0
+    && std::lexicographical_compare_three_way(a1, a1+9, a2, a2+9) == (i <=> 7)
+    && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+7) == 0
+    && std::lexicographical_compare_three_way(a1, a1+8, a2, a2+7) > 0
+    && std::lexicographical_compare_three_way(a1, a1+7, a2, a2+8) < 0;
+}
+
+static_assert( test02(248) );
+static_assert( test02(7) );
+static_assert( test02(8) );
+
+constexpr bool
+test03(unsigned char* p)
+{
+  unsigned char a[2] = { 1, 2 };
+  return std::lexicographical_compare_three_way(p, p, a, a+2) < 0
+    && std::lexicographical_compare_three_way(a, a+2, p, p) > 0;
+}
+
+static_assert( test03(nullptr) ); // ensure memcmp not called with nullptr