v1/__algorithm/lexicographical_compare_three_way.h

0001 //===----------------------------------------------------------------------===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H
0010 #define _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H
0011
0012 #include <__algorithm/min.h>
0013 #include <__algorithm/three_way_comp_ref_type.h>
0014 #include <__compare/compare_three_way.h>
0015 #include <__compare/ordering.h>
0016 #include <__concepts/arithmetic.h>
0017 #include <__config>
0018 #include <__iterator/iterator_traits.h>
0019 #include <__type_traits/common_type.h>
0020 #include <__type_traits/is_constructible.h>
0021 #include <__utility/move.h>
0022
0023 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
0024 #  pragma GCC system_header
0025 #endif
0026
0027 _LIBCPP_PUSH_MACROS
0028 #include <__undef_macros>
0029
0030 _LIBCPP_BEGIN_NAMESPACE_STD
0031
0032 #if _LIBCPP_STD_VER >= 20
0033
0034 // Fast path for random access iterators which computes the number of loop iterations up-front and
0035 // then skips the iterator comparisons inside the loop.
0036 template <class _InputIterator1, class _InputIterator2, class _Cmp>
0037 _LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path(
0038     _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp)
0039     -> decltype(__comp(*__first1, *__first2)) {
0040   static_assert(
0041       signed_integral<__iter_diff_t<_InputIterator1>>, "Using a non-integral difference_type is undefined behavior.");
0042   static_assert(
0043       signed_integral<__iter_diff_t<_InputIterator2>>, "Using a non-integral difference_type is undefined behavior.");
0044
0045   using _Len1   = __iter_diff_t<_InputIterator1>;
0046   using _Len2   = __iter_diff_t<_InputIterator2>;
0047   using _Common = common_type_t<_Len1, _Len2>;
0048
0049   _Len1 __len1      = __last1 - __first1;
0050   _Len2 __len2      = __last2 - __first2;
0051   _Common __min_len = std::min<_Common>(__len1, __len2);
0052
0053   for (_Common __i = 0; __i < __min_len; ++__i) {
0054     auto __c = __comp(*__first1, *__first2);
0055     if (__c != 0) {
0056       return __c;
0057     }
0058     ++__first1;
0059     ++__first2;
0060   }
0061
0062   return __len1 <=> __len2;
0063 }
0064
0065 // Unoptimized implementation which compares the iterators against the end in every loop iteration
0066 template <class _InputIterator1, class _InputIterator2, class _Cmp>
0067 _LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_slow_path(
0068     _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp)
0069     -> decltype(__comp(*__first1, *__first2)) {
0070   while (true) {
0071     bool __exhausted1 = __first1 == __last1;
0072     bool __exhausted2 = __first2 == __last2;
0073
0074     if (__exhausted1 || __exhausted2) {
0075       if (!__exhausted1)
0076         return strong_ordering::greater;
0077       if (!__exhausted2)
0078         return strong_ordering::less;
0079       return strong_ordering::equal;
0080     }
0081
0082     auto __c = __comp(*__first1, *__first2);
0083     if (__c != 0) {
0084       return __c;
0085     }
0086
0087     ++__first1;
0088     ++__first2;
0089   }
0090 }
0091
0092 template <class _InputIterator1, class _InputIterator2, class _Cmp>
0093 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way(
0094     _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp __comp)
0095     -> decltype(__comp(*__first1, *__first2)) {
0096   static_assert(__comparison_category<decltype(__comp(*__first1, *__first2))>,
0097                 "The comparator passed to lexicographical_compare_three_way must return a comparison category type.");
0098   static_assert(std::is_copy_constructible_v<_InputIterator1>, "Iterators must be copy constructible.");
0099   static_assert(std::is_copy_constructible_v<_InputIterator2>, "Iterators must be copy constructible.");
0100   __three_way_comp_ref_type<_Cmp> __wrapped_comp_ref(__comp);
0101   if constexpr (__has_random_access_iterator_category<_InputIterator1>::value &&
0102                 __has_random_access_iterator_category<_InputIterator2>::value) {
0103     return std::__lexicographical_compare_three_way_fast_path(
0104         std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref);
0105   } else {
0106     // Unoptimized implementation which compares the iterators against the end in every loop iteration
0107     return std::__lexicographical_compare_three_way_slow_path(
0108         std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref);
0109   }
0110 }
0111
0112 template <class _InputIterator1, class _InputIterator2>
0113 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way(
0114     _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {
0115   return std::lexicographical_compare_three_way(
0116       std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::compare_three_way());
0117 }
0118
0119 #endif // _LIBCPP_STD_VER >= 20
0120
0121 _LIBCPP_END_NAMESPACE_STD
0122
0123 _LIBCPP_POP_MACROS
0124
0125 #endif // _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H