libcxx/include/__cxx03/__algorithm/lexicographical_compare_three_way.h

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H
  10 #define _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H
  11
  12 #include <__cxx03/__algorithm/min.h>
  13 #include <__cxx03/__algorithm/three_way_comp_ref_type.h>
  14 #include <__cxx03/__compare/compare_three_way.h>
  15 #include <__cxx03/__compare/ordering.h>
  16 #include <__cxx03/__concepts/arithmetic.h>
  17 #include <__cxx03/__config>
  18 #include <__cxx03/__iterator/iterator_traits.h>
  19 #include <__cxx03/__type_traits/common_type.h>
  20 #include <__cxx03/__type_traits/is_constructible.h>
  21 #include <__cxx03/__utility/move.h>
  22
  23 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  24 #  pragma GCC system_header
  25 #endif
  26
  27 _LIBCPP_PUSH_MACROS
  28 #include <__cxx03/__undef_macros>
  29
  30 _LIBCPP_BEGIN_NAMESPACE_STD
  31
  32 #if _LIBCPP_STD_VER >= 20
  33
  34 // Fast path for random access iterators which computes the number of loop iterations up-front and
  35 // then skips the iterator comparisons inside the loop.
  36 template <class _InputIterator1, class _InputIterator2, class _Cmp>
  37 _LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_fast_path(
  38     _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp)
  39     -> decltype(__comp(*__first1, *__first2)) {
  40   static_assert(
  41       signed_integral<__iter_diff_t<_InputIterator1>>, "Using a non-integral difference_type is undefined behavior.");
  42   static_assert(
  43       signed_integral<__iter_diff_t<_InputIterator2>>, "Using a non-integral difference_type is undefined behavior.");
  44
  45   using _Len1   = __iter_diff_t<_InputIterator1>;
  46   using _Len2   = __iter_diff_t<_InputIterator2>;
  47   using _Common = common_type_t<_Len1, _Len2>;
  48
  49   _Len1 __len1      = __last1 - __first1;
  50   _Len2 __len2      = __last2 - __first2;
  51   _Common __min_len = std::min<_Common>(__len1, __len2);
  52
  53   for (_Common __i = 0; __i < __min_len; ++__i) {
  54     auto __c = __comp(*__first1, *__first2);
  55     if (__c != 0) {
  56       return __c;
  57     }
  58     ++__first1;
  59     ++__first2;
  60   }
  61
  62   return __len1 <=> __len2;
  63 }
  64
  65 // Unoptimized implementation which compares the iterators against the end in every loop iteration
  66 template <class _InputIterator1, class _InputIterator2, class _Cmp>
  67 _LIBCPP_HIDE_FROM_ABI constexpr auto __lexicographical_compare_three_way_slow_path(
  68     _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp& __comp)
  69     -> decltype(__comp(*__first1, *__first2)) {
  70   while (true) {
  71     bool __exhausted1 = __first1 == __last1;
  72     bool __exhausted2 = __first2 == __last2;
  73
  74     if (__exhausted1 || __exhausted2) {
  75       if (!__exhausted1)
  76         return strong_ordering::greater;
  77       if (!__exhausted2)
  78         return strong_ordering::less;
  79       return strong_ordering::equal;
  80     }
  81
  82     auto __c = __comp(*__first1, *__first2);
  83     if (__c != 0) {
  84       return __c;
  85     }
  86
  87     ++__first1;
  88     ++__first2;
  89   }
  90 }
  91
  92 template <class _InputIterator1, class _InputIterator2, class _Cmp>
  93 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way(
  94     _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _Cmp __comp)
  95     -> decltype(__comp(*__first1, *__first2)) {
  96   static_assert(__comparison_category<decltype(__comp(*__first1, *__first2))>,
  97                 "The comparator passed to lexicographical_compare_three_way must return a comparison category type.");
  98   static_assert(std::is_copy_constructible_v<_InputIterator1>, "Iterators must be copy constructible.");
  99   static_assert(std::is_copy_constructible_v<_InputIterator2>, "Iterators must be copy constructible.");
 100   __three_way_comp_ref_type<_Cmp> __wrapped_comp_ref(__comp);
 101   if constexpr (__has_random_access_iterator_category<_InputIterator1>::value &&
 102                 __has_random_access_iterator_category<_InputIterator2>::value) {
 103     return std::__lexicographical_compare_three_way_fast_path(
 104         std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref);
 105   } else {
 106     // Unoptimized implementation which compares the iterators against the end in every loop iteration
 107     return std::__lexicographical_compare_three_way_slow_path(
 108         std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), __wrapped_comp_ref);
 109   }
 110 }
 111
 112 template <class _InputIterator1, class _InputIterator2>
 113 [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto lexicographical_compare_three_way(
 114     _InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {
 115   return std::lexicographical_compare_three_way(
 116       std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), std::compare_three_way());
 117 }
 118
 119 #endif // _LIBCPP_STD_VER >= 20
 120
 121 _LIBCPP_END_NAMESPACE_STD
 122
 123 _LIBCPP_POP_MACROS
 124
 125 #endif // _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H