126 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H10#define _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H11 12#include <__algorithm/min.h>13#include <__algorithm/three_way_comp_ref_type.h>14#include <__compare/compare_three_way.h>15#include <__compare/ordering.h>16#include <__concepts/arithmetic.h>17#include <__config>18#include <__iterator/iterator_traits.h>19#include <__type_traits/common_type.h>20#include <__type_traits/is_constructible.h>21#include <__utility/move.h>22 23#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)24# pragma GCC system_header25#endif26 27_LIBCPP_PUSH_MACROS28#include <__undef_macros>29 30_LIBCPP_BEGIN_NAMESPACE_STD31 32#if _LIBCPP_STD_VER >= 2033 34// Fast path for random access iterators which computes the number of loop iterations up-front and35// then skips the iterator comparisons inside the loop.36template <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(signed_integral<__iterator_difference_type<_InputIterator1>>,41 "Using a non-integral difference_type is undefined behavior.");42 static_assert(signed_integral<__iterator_difference_type<_InputIterator2>>,43 "Using a non-integral difference_type is undefined behavior.");44 45 using _Len1 = __iterator_difference_type<_InputIterator1>;46 using _Len2 = __iterator_difference_type<_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 iteration66template <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 92template <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 iteration107 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 112template <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 >= 20120 121_LIBCPP_END_NAMESPACE_STD122 123_LIBCPP_POP_MACROS124 125#endif // _LIBCPP___ALGORITHM_LEXICOGRAPHICAL_COMPARE_THREE_WAY_H126